pith. sign in

arxiv: 1906.10420 · v2 · pith:DYBXUFSZnew · submitted 2019-06-25 · 🧮 math.CO

Domination versus edge domination

Julien Baste , Maximilian F\"urst , Michael A. Henning , Elena Mohr , Dieter Rautenbach This is my paper

Pith reviewed 2026-05-25 16:36 UTC · model grok-4.3

classification 🧮 math.CO
keywords domination numberedge domination numberregular graphsconjectureclaw-free graphsline graph
0
0 comments X

The pith

For regular graphs the domination number is conjectured to be at most the edge domination number.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper advances the claim that in any Δ-regular graph with Δ at least 1 the smallest vertex set that touches every vertex is no larger than the smallest edge set that touches every edge. This comparison is of interest because both quantities bound covering efficiency and the edge-domination number equals the ordinary domination number of the line graph. The authors establish a general inequality showing the domination number is at most one plus a term that shrinks with degree, times the edge-domination number, together with a sharper factor for cubic graphs. They also confirm the proposed inequality holds throughout the subclass of cubic claw-free graphs.

Core claim

We propose the conjecture that the domination number γ(G) of a Δ-regular graph G with Δ≥1 is always at most its edge domination number γ_e(G). We prove that γ(G)≤(1+2(Δ−1)/(Δ 2^Δ))γ_e(G) for general Δ≥1, and γ(G)≤(7/6−1/204)γ_e(G) for Δ=3. Furthermore, we verify our conjecture for cubic claw-free graphs.

What carries the argument

The conjecture γ(G)≤γ_e(G) for Δ-regular graphs, supported by explicit multiplicative bounds relating the two parameters.

If this is right

  • The proved general bound supplies a concrete approximation factor between the two numbers for every regular degree.
  • The cubic bound improves the approximation factor to roughly 1.16 for three-regular graphs.
  • Verification on cubic claw-free graphs shows the conjecture survives a natural structural restriction.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • If the conjecture holds, it would immediately relate vertex-domination problems to edge-domination problems on the line graph for every regular graph.
  • The same comparison might be tested on nearly regular graphs or on graphs whose degree sequence is bounded.
  • Algorithmic consequences could follow if the edge-domination number is easier to approximate than the ordinary domination number on regular instances.

Load-bearing premise

The graphs under consideration must be regular of fixed degree Δ.

What would settle it

A single Δ-regular graph in which the domination number strictly exceeds the edge domination number would disprove the conjecture.

Figures

Figures reproduced from arXiv: 1906.10420 by Dieter Rautenbach, Elena Mohr, Julien Baste, Maximilian F\"urst, Michael A. Henning.

Figure 1
Figure 1. Figure 1: A non-regular graph G with γ(G) = 2 > 1 = γe(G). Our contributions are three results related to Conjecture 1. A simple probabilistic argument implies a weak version of Conjecture 1, which, for ∆ ≤ 12, is better than the above-mentioned consequence of [2] and (1). Theorem 1. If G is a ∆-regular graph with ∆ ≥ 1, then γ(G) ≤  1 + 2(∆−1) ∆2∆  γe(G). For cubic graphs, Theorem 1 implies γ(G) ≤ 7 6 γe(G), whic… view at source ↗
Figure 2
Figure 2. Figure 2: The edges uv, u ′ v ′ and the sets X and Y . The choice for the coupled pair {uv, u′ v ′} will remain independent of all other random choices involved in the construction of D. Furthermore, the two edges in a coupled pair will not be involved in any other operation modifying the choice of D. 3 [PITH_FULL_IMAGE:figures/full_fig_p003_2.png] view at source ↗
Figure 3
Figure 3. Figure 3: The set S(τ ). During all changes of the initial random choice of D performed so far, we ensure that the following property holds just before we derandomize the triple τ : For every vertex u in R that has a neighbor in V (τ ) ∪ S(τ ), the three neighbors of u in V (M) belong to D independently with probability 1/2. (2) All coupled pairs and derandomized triples will be disjoint. For every edge in M that do… view at source ↗
Figure 4
Figure 4. Figure 4: The sets Spaired, S ′ paired, R0, R1, R2, and R3 Since G has at most 8p edges leaving Spaired, we have 2r2 + r1 ≤ 8p, which implies r1 + 7r2 ≤ 28p. By definition, we obtain |S ′ paired| ≤ 4r0 + 2r2. Considering the number of edges leaving S ′ paired, we obtain r3 ≤ 3|S ′ paired| ≤ 12r0 + 6r2. Therefore, r (1) = r − r0 − r1 − r2 − r3 ≥ r − 13r0 − r1 − 7r2 ≥ r − 13r0 − 28p. (3) Note that, only coupling the p… view at source ↗
Figure 5
Figure 5. Figure 5: The edges in τ and the vertices zt , z, z ′ , and z ′′ . Our derandomized choice of adding always u1, u2, and u3 to D yields P[zt ∈ B] = P[z ∈ B] = P[z ′ ∈ B] = P[z ′′ ∈ B] = 0. Furthermore, property (2) implies P[w ∈ B] = 1/4 for every neighbor w of v1 in R. Since v1 has at most two such neighbors, derandomizing the triple τt additionally reduces the upper bound on E[|B|] given in (4) by at least 4 8 − 2 … view at source ↗
Figure 6
Figure 6. Figure 6: The edges in τ and the vertices zt , z, z ′ , and z ′′ . The choice of P implies that no vertex from R(t) distinct from zt , z, z ′ , and z ′′ has two neighbors in V (τt). Arguing as above, we obtain that derandomizing the triple τt additionally reduces the upper bound on E[|B|] given in (4) by at least 4 8 − 3 8 = 1 8 . Similarly as in Case 1, it follows that |S(τt)| ≤ 18, and that |R (t+1)| = |R (t) \{v … view at source ↗
Figure 7
Figure 7. Figure 7: A subgraph of G with vertex set X, where k = 4. Let vk+1 be the neighbor of uk distinct from vk and ck. Since G is claw-free, the vertex vk+1 is adjacent to ck. Since V (G) \ V (M) is independent, we have uk+1vk+1 ∈ M for some vertex uk+1. Since ck ∈ C and uk ∈ D, we obtain vk+1 6∈ D and uk+1 ∈ D, which implies that the vertex vk+1 does not belong to X. If uk+1 belongs to X, then uk+1 = x, and replacing D … view at source ↗
read the original abstract

We propose the conjecture that the domination number $\gamma(G)$ of a $\Delta$-regular graph $G$ with $\Delta\geq 1$ is always at most its edge domination number $\gamma_e(G)$, which coincides with the domination number of its line graph. We prove that $\gamma(G)\leq \left(1+\frac{2(\Delta-1)}{\Delta 2^{\Delta}}\right)\gamma_e(G)$ for general $\Delta\geq 1$, and $\gamma(G)\leq \left(\frac{7}{6}-\frac{1}{204}\right)\gamma_e(G)$ for $\Delta=3$. Furthermore, we verify our conjecture for cubic claw-free graphs.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

0 major / 2 minor

Summary. The manuscript proposes the conjecture that the domination number γ(G) of any Δ-regular graph G with Δ ≥ 1 satisfies γ(G) ≤ γ_e(G), where γ_e(G) is the edge domination number (equivalently, the domination number of the line graph). It proves the explicit inequality γ(G) ≤ (1 + 2(Δ−1)/(Δ 2^Δ)) γ_e(G) for general Δ ≥ 1, the tighter bound γ(G) ≤ (7/6 − 1/204) γ_e(G) for Δ = 3, and verifies the conjecture on the subclass of cubic claw-free graphs.

Significance. If the conjecture holds, it would establish a direct inequality between two standard domination parameters restricted to regular graphs. The paper supplies explicit, closed-form constants in the proven inequalities (with the general factor approaching 1 for large Δ) and performs a concrete verification on cubic claw-free graphs; these are strengths that provide quantitative partial support even if the equality case remains open.

minor comments (2)
  1. The abstract and introduction state the conjecture and the two proved inequalities, but the manuscript would benefit from an explicit statement (perhaps in a dedicated section or theorem) of the precise hypotheses under which each bound holds, including any additional assumptions such as connectedness or finiteness.
  2. The verification for cubic claw-free graphs is mentioned; adding a brief description of the method (e.g., exhaustive search on a known catalog or reduction to known results) would improve reproducibility without altering the central claims.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for the positive assessment of our work and the recommendation of minor revision. The referee summary correctly captures the conjecture, the general and cubic bounds, and the verification on cubic claw-free graphs.

Circularity Check

0 steps flagged

No significant circularity

full rationale

The paper states an explicit conjecture that γ(G) ≤ γ_e(G) for Δ-regular graphs and separately proves two strict inequalities (a general factor 1 + 2(Δ−1)/(Δ 2^Δ) and a Δ=3 factor 7/6 − 1/204) plus a verification on cubic claw-free graphs. None of these steps reduces by definition or by self-citation to the conjecture itself; the proven bounds are weaker than the conjectured equality and are obtained from independent counting arguments on regular graphs. No fitted parameters, renamed empirical patterns, or load-bearing self-citations appear in the stated results.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The central claim rests on the standard definitions of domination and edge domination together with the restriction to regular graphs; no free parameters, invented entities, or non-standard axioms are introduced in the abstract.

axioms (1)
  • standard math Standard definitions of the domination number γ(G) and edge domination number γ_e(G) in finite undirected graphs.
    The conjecture and bounds are stated directly in terms of these two parameters.

pith-pipeline@v0.9.0 · 5645 in / 1228 out tokens · 29762 ms · 2026-05-25T16:36:32.149541+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

11 extracted references · 11 canonical work pages

  1. [1]

    Allan and R

    R.B. Allan and R. Laskar, On domination and independent domination numbers of a graph, Discrete Mathematics 23 (1978) 73-76

    work page 1978

  2. [2]

    Alon and J.H

    N. Alon and J.H. Spencer, The probabilistic method, 4th edition, Wile y-Interscience Series in Discrete Mathematics and Optimization, Hoboken, NJ: John Wiley & Sons, 2016

    work page 2016

  3. [3]

    Caner Ta¸ skin and T

    Z. Caner Ta¸ skin and T. Ekim, Integer programming formulations for the minimum weighted maximal matching problem, Optimization Letters 6 (2012) 1 161-1171

    work page 2012

  4. [4]

    R. Carr, T. Fujito, G. Konjevod, and O. Parekh, A 2 1 10-approximation algorithm for a generalization of the weighted edge-dominating set problem, Journ al of Combinatorial Optimization 5 (2001) 317-326

    work page 2001

  5. [5]

    Chleb ´ ık and J

    M. Chleb ´ ık and J. Chleb ´ ıkov´ a, Approximation hardness of edgedominating set prob- lems, Journal of Combinatorial Optimization 11 (2006) 279-290

    work page 2006

  6. [6]

    Gotthilf, M

    Z. Gotthilf, M. Lewenstein, and E. Rainshmidt, A ( 2 − c log n n ) approximation algo- rithm for the minimum maximal matching problem, Lecture Notes in Com puter Science 5426 (2009) 267-278

    work page 2009

  7. [7]

    Haynes, S.T

    T.W. Haynes, S.T. Hedetniemi, and P.J. Slater, Fundamentals of Do mination in Graphs, Marcel Dekker, Inc., New York, 1998

    work page 1998

  8. [8]

    Horton and K

    J.D. Horton and K. Kilakos, Minimum edge dominating sets, SIAM Jou rnal on Dis- crete Mathematics 6 (1993) 375-387

    work page 1993

  9. [9]

    Joos, personal communication

    F. Joos, personal communication

    work page

  10. [10]

    Schmied and C

    R. Schmied and C. Viehmann, Approximating edge dominating set in dense graphs, Theoretical Computer Science 414 (2012) 92-99

    work page 2012

  11. [11]

    Yannakakis and F

    M. Yannakakis and F. Gavril, Edge dominating sets in graphs, SIA M Journal on Applied Mathematics 38 (1980) 364-372. 9

    work page 1980