Cover Image

Lower bounds for dominating set reconfiguration on sparse (directed) graphs

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Dirks, Jona, Vigny, Alexandre
Format:	Preprint
Published:	2025
Subjects:	Discrete Mathematics
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Token Sliding Reconfiguration on DAGs
by: Dirks, Jona, et al.
Published: (2025)

Weighted Treedepth is NP-complete on Graphs of Bounded Degree
by: Dirks, Jona, et al.
Published: (2025)

Elimination distance to bounded degree on planar graphs
by: Lindermayr, Alexander, et al.
Published: (2020)

Elimination Distance to Dominated Clusters
by: Schirrmacher, Nicole, et al.
Published: (2025)

The tape reconfiguration problem and its consequences for dominating set reconfiguration
by: Bousquet, Nicolas, et al.
Published: (2025)

Independent set reconfiguration in H-free graphs
by: Bartier, Valentin, et al.
Published: (2024)

Token sliding independent set reconfiguration on block graphs
by: Francis, Mathew C., et al.
Published: (2024)

Minimum stationary values of sparse random directed graphs
by: Cai, Xing Shi, et al.
Published: (2020)

A quasi-optimal upper bound for induced paths in sparse graphs
by: Couëtoux, Basile, et al.
Published: (2025)

Determining a graph from its reconfiguration graph
by: Berthe, Gaétan, et al.
Published: (2025)

Enumerating minimal dominating sets in the (in)comparability graphs of bounded dimension posets
by: Bonamy, Marthe, et al.
Published: (2020)

Advances in Algorithmic Meta Theorems
by: Siebertz, Sebastian, et al.
Published: (2024)

Upper bounds on minimum size of feedback arc set of directed multigraphs with bounded degree
by: Gutin, Gregory, et al.
Published: (2024)

Equitable coloring of sparse graphs
by: Liu, Weichan, et al.
Published: (2024)

Greed is slow on sparse graphs of oriented valued constraints
by: Kaznatcheev, Artem, et al.
Published: (2025)

Multipacking and broadcast domination on cactus graph and its impact on hyperbolic graph
by: Das, Sandip, et al.
Published: (2023)

Canonical labelling of sparse random graphs
by: Verbitsky, Oleg, et al.
Published: (2024)

Twin-width of sparse random graphs
by: Hendrey, Kevin, et al.
Published: (2023)

Long induced paths in sparse graphs and graphs with forbidden patterns
by: Duron, Julien, et al.
Published: (2024)

On cuts of small chromatic number in sparse graphs
by: Aubian, Guillaume, et al.
Published: (2025)

On locating and neighbor-locating colorings of sparse graphs
by: Chakraborty, Dipayan, et al.
Published: (2023)

Lower bounds for the integrality gap of the bi-directed cut formulation of the Steiner Tree Problem
by: Bernardelli, Ambrogio Maria, et al.
Published: (2024)

On open-separating dominating codes in graphs
by: Chakraborty, Dipayan, et al.
Published: (2024)

An improved upper bound for the domination number of a graph
by: Arumugam, Subramanian, et al.
Published: (2024)

Sample compression schemes for balls in structurally sparse graphs
by: Bourneuf, Romain, et al.
Published: (2026)

Secure domination in $P_5$-free graphs
by: Gupta, Uttam K., et al.
Published: (2025)

On graph classes with constant domination-packing ratio
by: Bonamy, Marthe, et al.
Published: (2025)

Vertex-edge domination on subclasses of bipartite graphs
by: Pandey, Arti, et al.
Published: (2025)

The 1/3-conjectures for domination in cubic graphs
by: Dorbec, Paul, et al.
Published: (2024)

Enumerating minimal dominating sets and variants in chordal bipartite graphs
by: Castelo, Emanuel, et al.
Published: (2025)

On three domination-based identification problems in block graphs
by: Chakraborty, Dipayan, et al.
Published: (2018)

Nowhere-zero flow reconfiguration
by: Esperet, Louis, et al.
Published: (2025)

Monitoring arc-geodetic sets of oriented graphs
by: Das, Tapas, et al.
Published: (2024)

Basis sequence reconfiguration in the union of matroids
by: Hanaka, Tesshu, et al.
Published: (2024)

Progress towards the two-thirds conjecture on locating-total dominating sets
by: Chakraborty, Dipayan, et al.
Published: (2022)

Weakly-sparse and strongly flip-flat classes of graphs are uniformly almost-wide
by: Ghasemi, Fatemeh, et al.
Published: (2025)

Extended formulations for induced tree and path polytopes of chordal graphs
by: Dupont-Bouillard, Alexandre
Published: (2025)

Krenn-Gu conjecture for sparse graphs
by: Chandran, L. Sunil, et al.
Published: (2024)

Lower bounding the MaxCut of high girth 3-regular graphs using the QAOA
by: Farhi, Edward, et al.
Published: (2025)

Bounds and extremal graphs for monitoring edge-geodetic sets in graphs
by: Foucaud, Florent, et al.
Published: (2024)