pith. sign in

arxiv: 1906.08727 · v1 · pith:PHDOTLZPnew · submitted 2019-06-20 · 🧮 math.CO

Traceability of Connected Domination Critical Graphs

Michael A. Henning , Nawarat Ananchuen , Pawaton Kaemawichanurat This is my paper

Pith reviewed 2026-05-25 19:24 UTC · model grok-4.3

classification 🧮 math.CO
keywords connected dominationcritical graphsHamiltonian pathcut-verticestraceabilitydomination numberstructural graph theory
0
0 comments X

The pith

k-γ_c-critical graphs have a Hamiltonian path precisely when the number of cut-vertices is k-3 or k-2.

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

The paper proves that for k at least 4, a k-connected-domination-critical graph contains a Hamiltonian path if and only if it has k-3 or k-2 cut-vertices. This rests on the established fact that such graphs have at most k-2 cut-vertices in total. A sympathetic reader would care because the result ties the edge-addition criticality condition directly to the presence or absence of a spanning path via a simple count of articulation points. The characterization shows how the critical property restricts graph structure enough to decide traceability from the cut-vertex number alone.

Core claim

For k ≥ 4 and 0 ≤ ζ ≤ k-2, every k-γ_c-critical graph with ζ cut-vertices has a Hamiltonian path if and only if k-3 ≤ ζ ≤ k-2. The argument uses the definition that the connected domination number equals k and drops upon addition of any missing edge, together with the known upper bound on cut-vertices.

What carries the argument

The k-γ_c-critical property, which requires connected domination number exactly k and that this number decreases for every added edge; this property bounds cut-vertices at most k-2 and supplies the structural control needed to decide the Hamiltonian path condition.

If this is right

  • Every k-γ_c-critical graph with exactly k-2 cut-vertices contains a Hamiltonian path.
  • Every k-γ_c-critical graph with exactly k-3 cut-vertices contains a Hamiltonian path.
  • Every k-γ_c-critical graph with at most k-4 cut-vertices lacks a Hamiltonian path.
  • The upper bound of k-2 cut-vertices is the value at which traceability is guaranteed at the high end of the range.

Where Pith is reading between the lines

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

  • The same cut-vertex threshold might serve as a test for other path or cycle properties once the criticality definition is relaxed to nearby graph classes.
  • Graphs meeting the ζ = k-3 or k-2 condition could be checked for stronger traceability features such as Hamiltonian cycles under mild extra assumptions.
  • The result positions the cut-vertex count as a practical invariant for deciding long-path existence inside critical domination graphs.

Load-bearing premise

The critical property under edge addition is enough by itself to guarantee that a Hamiltonian path exists exactly when the number of cut-vertices meets or exceeds k-3.

What would settle it

A k-γ_c-critical graph for some k ≥ 4 with exactly k-4 cut-vertices that contains a Hamiltonian path would falsify the claim.

Figures

Figures reproduced from arXiv: 1906.08727 by Michael A. Henning, Nawarat Ananchuen, Pawaton Kaemawichanurat.

Figure 1
Figure 1. Figure 1: A graph G in the class B1 The class U(k). Let B be a graph in the class B1 defined earlier. A graph G in the class U(k) is constructed from the graph B and a path Pk−2 : c0c1 . . . ck−3 of order k −2 by joining ck−3 to b. A graph G in the class U(k) is illustrated by [PITH_FULL_IMAGE:figures/full_fig_p006_1.png] view at source ↗
Figure 2
Figure 2. Figure 2: A graph G in the class U(k) In order to present the characterization due to Kaemawichanurat [19] of k-γc-critical graphs with ζ = k − 3 cut-vertices, we describe next some additional classes of graphs. Let i = (i1, i2, . . . , ik−3) be a (k − 3)-tuple such that i1, i2, . . . , ik−3 ∈ {0, 1} and Pk−3 j=1 ij = 1. Thus, there is exactly one ℓ ∈ [k − 3] such that iℓ = 1 and iℓ ′ = 0 for all ℓ ′ ∈ [k − 3] \ {ℓ}… view at source ↗
Figure 3
Figure 3. Figure 3: A graph G in the class G1(i1 = 1, 0, 0, . . . , 0) t t t ✓ ✒ ✏ ✑ ✬ ✫ ✩ ✪ [PITH_FULL_IMAGE:figures/full_fig_p007_3.png] view at source ↗
Figure 4
Figure 4. Figure 4: A graph G in the class G1(0, 0, . . . , iℓ = 1, 0, . . . , 0) Further, for a (k − 3)-tuple i = (0, 0, . . . , 1) where ik−3 = 1 and iℓ ′ = 0 for ℓ ′ ∈ [k − 4], a 7 [PITH_FULL_IMAGE:figures/full_fig_p007_4.png] view at source ↗
Figure 5
Figure 5. Figure 5: A graph G in the class G1(0, 0, . . . , 1) We proceed further by defining a special class of end blocks. The class B2. Let H be a block graph, and so H is a connected graph that contains a single block. The block H belongs to the family B2 if γc(H) = 3 and H has the following properties. (a) The block H contains a vertex b such that NH (b) is a complete graph. (b) Every vertex v of H different from b belon… view at source ↗
Figure 6
Figure 6. Figure 6: The structure of G[ A ] in the proof of Theorem 7 Claim 1 The set {x 1 j1 , x2 j2 , . . . , xz jz } is an independent set for all ji ∈ {1, ni} and i ∈ [z]. Proof. Suppose, to the contrary, that x i ji x i ′ ji ′ ∈ E(G) for some i and i ′ where 1 ≤ i < i′ ≤ z where ji ∈ {1, ni} and ji ′ ∈ {1, ni ′}. Renaming the vertices on the path P i and P i ′ if necessary, we may assume without loss of generality that j… view at source ↗
Figure 7
Figure 7. Figure 7: The structure of G[ A ] after rearranging the paths Claim 7 If ℓ > 1, then G is traceable. Proof. Suppose that ℓ > 1. Therefore, u ′ ℓ 6= u ′ 1 and u ′ ℓ 6= uℓ . We now consider the graph G + u1u ′ ℓ . For notational simplicity, let D1,ℓ = Du1u ′ ℓ . By Claim 2, we have |D1,ℓ ∩ A| = |D1,ℓ ∩ A| = 1. Further, |D1,ℓ ∩ {u1, u′ ℓ | = 1. Let D1,ℓ ∩ A = {w}. By Lemma 1(c), the vertex w is adjacent to exactly one … view at source ↗
Figure 8
Figure 8. Figure 8: A graph G in the class N (s) Let F(k, ζ) be the class of k-γc-critical graphs with ζ cut-vertices which are non-traceable. In view of Theorem 3, F(k, ζ) = ∅ for all k ∈ [3]. We show next that N (s) ⊆ P(4) and N (s) ⊆ F(4, 0). In particular, this implies that the class P(4) is not empty when k = 4. Lemma 6 For all s ≥ 6, N (s) ⊆ F(4, 0). Moreover, N (s) ⊆ P(4) where in the construction of P(4) here we take … view at source ↗
Figure 9
Figure 9. Figure 9: The graph in the class P(k, ℓ) Theorem 8 For k ≥ 4 and ℓ ≥ 1, every graph in the class P(k, ℓ) is a (k + ℓ)-γc-critical graph. Proof. For k ≥ 4 and ℓ ≥ 1, let G(n1, n2, . . . , nℓ) be a graph in the class P(k, ℓ) that is constructed from a graph G ∈ P(k) with H as the maximal complete subgraph of G having properties (a) and (b) in the construction of G. For notation convenience, we write the graph G(n1, n2… view at source ↗
read the original abstract

A dominating set in a graph $G$ is a set $S$ of vertices of $G$ such that every vertex outside $S$ is adjacent to a vertex in $S$. A connected dominating set in $G$ is a dominating set $S$ such that the subgraph $G[S]$ induced by $S$ is connected. The connected domination number of $G$, $\gamma_c(G)$, is the minimum cardinality of a connected dominating set of $G$. A graph $G$ is said to be $k$-$\gamma_{c}$-critical if the connected domination number $\gamma_{c}(G)$ is equal to $k$ and $\gamma_{c}(G + uv) < k$ for every pair of non-adjacent vertices $u$ and $v$ of $G$. Let $\zeta$ be the number of cut-vertices of $G$. It is known that if $G$ is a $k$-$\gamma_{c}$-critical graph, then $G$ has at most $k - 2$ cut-vertices, that is $\zeta \le k - 2$. In this paper, for $k \ge 4$ and $0 \le \zeta \le k - 2$, we show that every $k$-$\gamma_{c}$-critical graph with $\zeta$ cut-vertices has a hamiltonian path if and only if $k - 3 \le \zeta \le k - 2$.

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

1 major / 0 minor

Summary. The manuscript claims to prove that for k ≥ 4 and 0 ≤ ζ ≤ k-2, every k-γ_c-critical graph with ζ cut-vertices has a Hamiltonian path if and only if k-3 ≤ ζ ≤ k-2. This uses the known global bound that ζ ≤ k-2 for such graphs.

Significance. If correct, the result supplies a precise if-and-only-if threshold linking traceability directly to the number of cut-vertices in connected-domination-critical graphs, sharpening existing bounds in domination theory.

major comments (1)
  1. Abstract: the central if-and-only-if claim is stated precisely, but the full derivation is not supplied; without the argument steps it is impossible to confirm that the criticality condition alone forces a Hamiltonian path exactly on the interval [k-3, k-2] and rules it out for smaller ζ, for all k ≥ 4.

Simulated Author's Rebuttal

1 responses · 0 unresolved

We thank the referee for their comments on our manuscript. We respond point-by-point to the major comment below.

read point-by-point responses

  1. Referee: Abstract: the central if-and-only-if claim is stated precisely, but the full derivation is not supplied; without the argument steps it is impossible to confirm that the criticality condition alone forces a Hamiltonian path exactly on the interval [k-3, k-2] and rules it out for smaller ζ, for all k ≥ 4.

    Authors: Abstracts are intended to state results concisely; full derivations appear in the body of the paper. Sections 3 and 4 contain the complete proofs: sufficiency that ζ ≥ k-3 implies a Hamiltonian path (via induction on block structure and criticality), and necessity via explicit constructions of non-traceable k-γ_c-critical graphs for each ζ < k-3 (k ≥ 4). These use the known global bound ζ ≤ k-2. The abstract therefore requires no change. revision: no

Circularity Check

0 steps flagged

No significant circularity; derivation is self-contained

full rationale

The abstract cites the bound ζ ≤ k-2 as a known external result and states the new if-and-only-if traceability theorem as a result proved in the paper for k ≥ 4. No equation, definition, or step reduces the central claim to a self-definition, a fitted parameter renamed as prediction, or a load-bearing self-citation chain. The criticality condition is used to derive the Hamiltonian-path property on the upper end of the interval, with the lower bound on ζ serving only as a premise rather than being smuggled in or redefined. This matches the default case of an independent mathematical proof building on prior facts without circular reduction.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The paper rests on standard graph-theoretic definitions and one previously established bound; no free parameters, new entities, or ad-hoc axioms are introduced in the abstract.

axioms (2)
  • standard math Standard definitions of dominating set, connected dominating set, cut-vertex, and k-γ_c-critical graphs.
    These are the background concepts required to state the theorem.
  • domain assumption Every k-γ_c-critical graph satisfies ζ ≤ k-2.
    The paper explicitly invokes this known result as the upper bound for the range considered.

pith-pipeline@v0.9.0 · 5807 in / 1336 out tokens · 37003 ms · 2026-05-25T19:24:28.284311+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

34 extracted references · 34 canonical work pages

  1. [1]

    Ananchuen, On domination critical graphs with cut vertices ha ving connected domination number 3

    N. Ananchuen, On domination critical graphs with cut vertices ha ving connected domination number 3. Int. Math. Forum 2 (2007), 3041–3052

    work page 2007

  2. [2]

    Ananchuen, W

    N. Ananchuen, W. Ananchuen, and M. D. Plummer, Matching prop erties in connected domina- tion critical graphs. Discrete Math. 308 (2008), 1260–1267

    work page 2008

  3. [3]

    Binkele-Raible and H

    D. Binkele-Raible and H. Fernau, A parameterized measure-and- conquer analysis for finding a k-leaf spanning tree in an undirected graph. Discrete Math. Theor. Comput. Sci. 16(1) (2014), 179–200

    work page 2014

  4. [4]

    Y. Caro, D. B. West, and R. Yuster, Connected domination and s panning trees with many leaves. SIAM J. Discrete Math. 13(2) (2000), 202–211

    work page 2000

  5. [5]

    X. G. Chen, L. Sun, and D. X. Ma, Connected domination critical g raphs. Applied Math. Letters 17 (2004), 503–507

    work page 2004

  6. [6]

    Chv´ atal, Tough graphs and hamiltonian circuits

    V. Chv´ atal, Tough graphs and hamiltonian circuits. Discrete Math. 5 (1973), 215–228

    work page 1973

  7. [7]

    C. J. Colbourn and L. K. Stewart, Permutation graphs: connec ted domination and Steiner trees. Discrete Math. 86 (1990), 179–189

    work page 1990

  8. [8]

    D’Atri and M

    A. D’Atri and M. Moscarini, Distance-hereditary graphs, Steine r trees, and connected domina- tion. SIAM J. Comput. 17(3) (1988), 521–538

    work page 1988

  9. [9]

    W. J. Desormeaux, T. W. Haynes, and M. A. Henning, Bounds on t he connected domination number of a graph. Discrete Appl. Math. 161(18) (2013), 2925–2931

    work page 2013

  10. [10]

    Duckworth and B

    W. Duckworth and B. Mans, Connected domination of regular gr aphs. Discrete Math. 309(8) (2009), 2305–2322

    work page 2009

  11. [11]

    Favaron, F

    O. Favaron, F. Tian and Lei. Zhang, Independence and hamilton icity in 3-domination-critical graphs. J. Graph Theory 25 (1997), 173–184

    work page 1997

  12. [12]

    Fellows, D

    M. Fellows, D. Lokshtanov, N. Misra, M. Mnich, F. Rosamond, an d S. Saurabh, The complexity ecology of parameters: an illustration using bounded max leaf numbe r. Theory Comput. Systems 45(4) (2009), 822–848

    work page 2009

  13. [13]

    Flandrin, F

    E. Flandrin, F. Tian, B. Wei and L. Zhang, Some properties of 3- domination-critical graphs. Discrete Math. 205 (1999), 65–76

    work page 1999

  14. [14]

    Galbiati, F

    G. Galbiati, F. Maffioli, and A. Morzenti, A short note on the appro ximability of the maximum leaves spanning tree problem. Inf. Process. Lett. 52(1) (1994), 45–49

    work page 1994

  15. [15]

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

    work page 1998

  16. [16]

    T. W. Haynes, S. T. Hedetniemi and P. J. Slater (eds), Domination in Graphs: Advanced Topics , Marcel Dekker, Inc. New York, 1998

    work page 1998

  17. [17]

    M. A. Henning and A. Yeo, Total Domination in Graphs (Springer Monographs in Mathema tics)

    work page

  18. [18]

    ISBN: 978-1-4614-6524-9 (Print) 978-1-4614-6525-6 ( Online)

    work page

  19. [19]

    Kaemawichanurat, Connected domination critical graphs

    P. Kaemawichanurat, Connected domination critical graphs. P h.D. Thesis. PhD supervisor: Louis Caccetta. Curtin University (2016). 25

    work page 2016

  20. [20]

    Kaemawichanurat, Connected domination critical graphs wit h k − 3 cut vertices, submitted

    P. Kaemawichanurat, Connected domination critical graphs wit h k − 3 cut vertices, submitted

    work page

  21. [21]

    Kaemawichanurat and N

    P. Kaemawichanurat and N. Ananchuen, On 4- γc-critical graphs with cut vertices. Utilitas Math. 82 (2010), 253–268

    work page 2010

  22. [22]

    Kaemawichanurat and N

    P. Kaemawichanurat and N. Ananchuen, Connected domination critical graphs with cut vertices. To appear in Discuss. Math. Graph Theory

    work page

  23. [23]

    Kaemawichanurat and L

    P. Kaemawichanurat and L. Caccetta, Hamiltonicity of dominatio n critical claw-free graphs. To appear in J. Combin. Comput. Combin. Math

    work page

  24. [24]

    Kaemawichanurat, L

    P. Kaemawichanurat, L. Caccetta and W. Ananchuen, Hamilton icity of connected domination critical graphs. Ars Combin. 136 (2018), 127–151

    work page 2018

  25. [25]

    Kaemawichanurat and T

    P. Kaemawichanurat and T. Jiarasuksakun, Some results on th e independence number of con- nected domination critical graphs. AKCE Int. J. Graphs Comb. 15 ( 2018), no. 2, 190–196

    work page 2018

  26. [26]

    Karami, S

    H. Karami, S. M. Sheikholeslami, A. Khodkar, and D. B. West, Con nected domination number of a graph and its complement. Graphs Combin. 28(1) (2012), 123–131

    work page 2012

  27. [27]

    T. Liu, Z. Lu, and K. Xu, Tractable connected domination for re stricted bipartite graphs. J. Comb. Optim. 29(1) (2015), 247–256

    work page 2015

  28. [28]

    Sampathkumar and H

    E. Sampathkumar and H. B. Walikar, The connected domination n umber of a graph. J. Math. Phys. Sci. 13(6) (1979), 607–613

    work page 1979

  29. [29]

    L. A. Sanchis, Maximum number of edges in connected graphs wit h a given domination number. Discrete Math. 8(1) (1991), 65–72

    work page 1991

  30. [30]

    D. P. Sumner and P. Blitch, Domination critical graphs. J. COmbin. Theory B 34 (1983) 65–76

    work page 1983

  31. [31]

    F. Tian, B. Wei and L. Zhang, Hamiltonicity in 3-domination critical graphs with α = δ + 2. Discrete Appl. Math. 92 (1999), 57–70

    work page 1999

  32. [32]

    Wojcicka, Hamiltonian properties of domination critical graph s

    E. Wojcicka, Hamiltonian properties of domination critical graph s. J. Graph Theory 14 (1990), 205–215

    work page 1990

  33. [33]

    Wu and H

    J. Wu and H. Li, On calculating connected dominating set for efficie nt routing in ad hoc wireless networks. Proceedings of the 3rd International Workshop on Discrete A lgorithms and Methods for Mobile Computing and Communications ACM (1999), 7–14

    work page 1999

  34. [34]

    Yuansheng, Z

    Y. Yuansheng, Z. Chengye, L. Xiaohui, J. Yongsong and H. Xin, Some 3-connected 4-edge critical non-Hamiltonian graphs J. Graph Theory 50 (2005), 316–320. 26

    work page 2005