Pith. sign in

REVIEW 2 major objections 4 minor 35 references

On graphs whose cycle space is spanned by their Hamilton cycles

T0 review · 2 major / 4 minor · reviewed 2026-08-02 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

Pith's one-line read Four mild strengthenings of standard Hamiltonicity criteria force every cycle to be a sum of Hamilton cycles.

desk verdict Genuine new results extending the CNP recipe to Chvátal–Erdős, McDiarmid–Yolov, CDS, and bipartite settings; the main gap is an unproved bipartite extension of the foundational lemma. read the letter →

arxiv 2606.05835 v2 pith:SCXBTLCE submitted 2026-06-04 math.CO

Dan Hefetz , Michael Krivelevich This is my paper · ORCID
classification math.CO MSC 05C4505C3805C4005C69
keywords cyclespaceHamiltoncyclesHamiltoniangraphvertexconnectivityindependencenumberbipartiteconnecteddominatingsetparityswitcher
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

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

The reading

This paper tackles a stronger question than Hamiltonicity: when does every cycle of a graph arise as the symmetric difference (binary sum) of its Hamilton cycles? Working over the two-element field, the cycle space is spanned by all cycles; the paper asks when the Hamilton cycles alone span it. It proves that several known sufficient conditions for Hamiltonicity, each strengthened by a constant factor, guarantee this spanning property for graphs with an odd number of vertices — and for balanced bipartite graphs in one case. The conditions include high connectivity against independence number, high minimum degree against bipartite independence number, many pairwise disjoint connected dominating sets, and an effective bipartite version of the classic condition. The proofs all run through one construction: a small parity-switcher that toggles whether a Hamilton cycle uses an odd number of edges from a special subgraph.

What carries the argument

The central object is the R-parity switcher: an even cycle with an odd number of edges of the special subgraph R, together with vertex-disjoint short paths pairing opposite vertices. Because the switcher contains two Hamilton paths between the same endpoints, one with an odd and one with an even number of R-edges, it combines with any Hamilton path on the remaining vertices to switch the parity of a Hamilton cycle. The entering wedge is a dichotomy lemma asserting that failure of the spanning property forces such an R; the paper extends this lemma to bipartite graphs and then reduces every theorem to finding a small parity switcher and a Hamilton path through the leftover vertices.

What would settle it

Find a balanced bipartite Hamiltonian graph G with C_{2n}(G) ≠ C(G) and verify that no proper subgraph R has both properties: every Hamilton cycle uses an even number of R-edges, and every cut has at least half its G-edges in R. Such a graph would refute the bipartite dichotomy lemma and invalidate Theorem 1.11; a smaller refutation would be a graph meeting α_BIP(G) ≤ 2δ(G)−24 for which some cycle is not an F2-sum of Hamilton cycles.

Watch

Extended reading notes

Core claim

The central claim is that C_n(G) = C(G) under four (and in the bipartite case, a fifth) moderate strengthenings of known Hamiltonian criteria. In words: every cycle of G is an F2-linear combination of Hamilton cycles. For example, an odd-vertex graph whose vertex connectivity is at least c·max{α(G), log n} or at least c·α(G)², for a sufficiently large absolute constant c, has this property; so does an odd graph with δ(G) ≥ max{2ᾱ(G)+9, ᾱ(G)+18}, and a balanced bipartite graph with α_BIP(G) ≤ 2δ(G)−24. The proof proceeds by contradiction through a five-step reduction: from failure of the spanning property, extract a proper subgraph R that every Hamilton cycle meets evenly, then force a Hamilt

Load-bearing premise

The entire recipe rests on the bipartite extension of the dichotomy lemma, which the paper asserts follows from the odd case 'essentially verbatim' but does not prove; if that extension fails, Theorem 1.11 and the claimed bipartite applicability of the recipe collapse.

Editorial extensions

If this is right

  • For graphs satisfying the conditions of Theorem 1.2 or 1.4, every cycle is an F2-sum of Hamilton cycles; in particular, every edge lies in some Hamilton cycle.
  • Any graph with 16α(G)+12 pairwise disjoint connected dominating sets has the spanning property, and the constants 16 and 12 are tight up to a constant factor: a construction with α(G)−1 disjoint connected dominating sets is non-Hamiltonian and therefore fails it.
  • For odd graphs with δ(G) ≥ max{2ᾱ(G)+9, ᾱ(G)+18}, the minimum-degree-versus-bipartite-independence criterion, strengthened by a constant factor, implies the full spanning property.
  • For balanced bipartite graphs with α_BIP(G) ≤ 2δ(G)−24, the Hamilton cycles on 2n vertices generate the entire cycle space.
  • The paper also exhibits a graph satisfying the pancyclicity-style n ≥ f(α(G)) condition that fails the spanning property, so the strengthened criteria are not vacuous.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • Inference: a promising route to the paper's Conjecture 1.3 is to remove the log-factor in Theorem 1.2 by using disjoint connected dominating sets instead of spanning linkability; Theorem 1.5 already suggests that many dominating sets can replace a large connectivity threshold.
  • Inference: if the bipartite dichotomy lemma holds, the same five-step recipe should adapt to other Hamiltonian criteria for balanced bipartite graphs, such as a bipartite analogue of the n/2 minimum-degree condition, yielding additional bipartite spanning theorems.
  • Inference: the obstruction based on two cliques joined by a 2-edge matching suggests studying the family of Hamilton-generated graphs outside the constant-factor regime; a testable conjecture is that 3-connectedness plus n ≥ c·α(G)² suffices, as raised in the paper's Problem 1.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

2 major / 4 minor

Summary. The paper studies when the subspace of the cycle space spanned by Hamilton cycles, C_n(G), equals the full cycle space C(G). Since this can only happen for odd n or bipartite G, the authors work in those settings. They prove four families of results: (i) Theorem 1.2, a Chvátal–Erdős-type connectivity condition; (ii) Theorem 1.4, a minimum-degree plus connectivity condition; (iii) Theorem 1.5, a connected dominating sets condition; (iv) Theorem 1.8, a McDiarmid–Yolov-type condition; and (v) Theorem 1.11, a balanced bipartite version. The proofs follow the Christoph–Nenadov–Petrova recipe: assume C_n(G) ≠ C(G), obtain a subgraph R satisfying (C1)–(C3), construct a short parity switcher, find disjoint paths and a Hamilton path of the remainder, and derive a contradiction. The paper also gives a tightness example for Theorem 1.5 and discusses open problems.

Significance. If correct, these are substantial results: they show that mild strengthenings of several classical Hamiltonicity criteria imply the much stronger property that Hamilton cycles generate the entire cycle space. The systematic use of the CNP recipe is well executed, and the appeal to external Hamiltonicity benchmarks (Chvátal–Erdős, McDiarmid–Yolov, Ordaz–Amar–Raspaud) avoids circularity. The tightness example for Theorem 1.5 is a useful addition. The main weakness is that the bipartite extension of the foundational dichotomy lemma is asserted, not proved; since Theorem 1.11 and Remark 2.4 depend on it, this is a load-bearing gap that must be addressed before the paper can be accepted.

major comments (2)
  1. [§2.1, Remark 2.2 (used in §5)] Lemma 2.1 is stated for 'n odd or G bipartite', but the proof is cited only from [8] for odd n. Remark 2.2 asserts that the [8] proof applies 'essentially verbatim' to the bipartite case and gives a two-sentence argument only for (C1). This is not sufficient: the construction of R and in particular the proof of (C3) may depend on the parity of n in ways not visible from the remark. Since Lemma 2.1 supplies the subgraph R on which the entire parity-switcher recipe rests, Theorem 1.11 (and the bipartite applicability claimed in Remark 2.4) have no valid starting point unless the bipartite version is proved in the manuscript or cited to a source that contains it. Please include a complete proof or adjust the claims.
  2. [§3, proof of Theorem 1.4, Step (S3)] The construction of the Hamilton path in G' applies Theorem 3.3 inside each V_i \ W with terminal pairs (w_{j-1}, u_j). However, when w_{j-1} = u_j, the same vertex appears twice as a terminal, contrary to the hypothesis of Theorem 3.3 that the 2r vertices are distinct. The text says 'the path P^i_j consists of a single vertex' and appeals to Property (5), but it does not explain how to reduce to the distinct-terminal setting, e.g., by deleting the trivial vertices and applying Theorem 3.3 to the remaining graph. This step is essential for Step (S3) of Theorem 1.4 and should be made explicit.
minor comments (4)
  1. [§3, proof of Theorem 1.2] The line 'assume that κ(G) ≥ c min{max{α, log n}, α²}' is inconsistent with the theorem's 'or' formulation; it should likely be 'κ(G) ≥ c max{α, log n} or κ(G) ≥ c α²'. In the first case, the condition should be κ(G) ≥ c max{α, log n} (not merely κ ≥ c log n) so that the α-term needed for Theorem 3.3 is available. The intended argument is clear, but the text should be corrected.
  2. [§4, proof of Lemma 4.2] In the proof that R is 2-connected, the equality deg_R(v,S) = e_R(S, T ∪ {v}) relies on the fact that S is a component of R - v, so e_R(S,T)=0. This should be stated explicitly; otherwise the displayed chain of inequalities is confusing.
  3. [§3, proof of Lemma 3.6] In the minimality argument at the end of Lemma 3.6, the parity of |P_i| is used implicitly: since the endpoints v_{s_i}, v_{t_i} are even-indexed vertices, |P_i| is even. This should be stated, as it is needed to verify that the shorter cycle has even length.
  4. [§3, Theorem 1.5 tightness example] The phrase 'every independent set of G of maximum size is of the form I ∪ {x} for some x ∈ A' is slightly informal; it means every maximum independent set has that form. This is clear from context, but could be rephrased.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: each theorem derives C_n=C from external Hamiltonicity criteria, with the target never assumed.

full rationale

The claimed theorems are not circular. For example, Theorem 1.2 assumes κ(G) ≥ c·max{α(G), log n} or κ(G) ≥ c·α(G)² and derives C_n(G)=C(G) by first invoking the Chvátal–Erdős theorem (Theorem 1.1) for Hamiltonicity, then Lemma 2.1 from [8] to obtain the subgraph R, Lemma 3.6 to find a parity-switching cycle, and Theorem 3.3 / Theorem 3.2 / Theorem 3.1 to build the required paths. The target identity C_n= C appears only as the conclusion, never as an input. Theorems 1.8 and 1.11 similarly start from the external McDiarmid–Yolov and Ordaz–Amar–Raspaud criteria. No fitted parameter is later relabeled as a prediction, and no conclusion is forced by definition or by a self-citation chain. The only self-citation used in a proof is Theorem 3.3 from [1] (Hefetz and Krivelevich are two of the authors of both papers); it is a published, external path-partition result whose hypotheses (κ ≥ c·max{α, log n, r}) do not include the target statement, so it is genuine independent support rather than circularity. The most fragile point is Remark 2.2: the bipartite extension of Lemma 2.1 is asserted with a two-sentence argument ('its proof in [8] applies essentially verbatim to the bipartite case as well') and is load-bearing for Theorem 1.11. This is an unproved correctness risk, not a circular derivation, so it does not raise the circularity score. Since the derivation is self-contained against external benchmarks, the appropriate score is 0.

Assumptions & free parameters 5 free parameters · 10 assumptions · 0 invented entities

The central claims rest on a stack of published theorems: the CNP dichotomy (Lemma 2.1, [8]), Chvátal–Erdős, McDiarmid–Yolov, Ordaz–Amar–Raspaud, Thomas–Wollan, and the authors' own spanning-linkage theorem ([1]). The paper's genuine additions are the bounded parity-switcher lemmas (3.6, 4.2, 5.1), the path-construction machinery (Lemma 4.3, 5.2, Claim 3.7), and the orchestration of S2/S3 under each hypothesis. No fitted data anywhere (pure combinatorics); constants 180/2000/16/12/9/18/24 are hand-chosen slack explicitly flagged by the authors as non-optimal. The genuinely paper-specific axiom is the sketched bipartite extension of Lemma 2.1 (Remark 2.2). Self-citation [1] supplies a non-explicit constant but no target-dependent circularity.

free parameters (5)
  • c in Theorem 1.2 = c = max{42, 20c'}, c' existential from [1]
    Hand-chosen / inherited; not computed; drives the κ ≥ c·max{α, log n} threshold. Non-explicitness limits checkability.
  • constants 180 and 2000 in Theorem 1.4 = 180; 2000
    Paper states: 'not optimal... chosen in order to make our calculations easy to follow.' Slack thresholds in κ ≥ max{180α, 2000δ⁻²}.
  • constants 16 and 12 in Theorem 1.5 = 16; 12
    Hand-chosen slack in the CDS count 16α+12; tightness example shows α−1 disjoint CDSs are not enough.
  • constants 9 and 18 in Theorem 1.8 = 9; 18
    Slack above McDiarmid–Yolov's δ ≥ ᾱ; set δ ≥ max{2ᾱ+9, ᾱ+18} to make Lemmas 4.2/4.3 work.
  • constant 24 in Theorem 1.11 = 24
    Slack above Ordaz–Amar–Raspaud's α_BIP ≤ 2δ−4; needed for Step (S3) after removing W (|W| ≤ 20).
assumptions (10)
  • domain assumption Lemma 2.1 (CNP dichotomy): if n is odd (or G bipartite) and Cₙ(G) ≠ C(G), there is R ⊆ G with (C1) R ≠ G, (C2) every Hamilton cycle even # of R-edges, (C3) e_R(A,B) ≥ e_G(A,B)/2 and R ≠ G[A,B] for every partition.
    Imported verbatim from [8] including its proof; the paper adds the bipartite case in Remark 2.2. Load-bearing for all five theorems.
  • ad hoc to paper Bipartite extension of Lemma 2.1 (Remark 2.2): the [8] proof applies 'essentially verbatim' when G is bipartite; (C1) follows from (C3) since the bipartition gives R ≠ G[X,Y] = G.
    Asserted with a two-sentence sketch, not proved; Theorem 1.11 stands on it.
  • domain assumption Theorem 3.3 (Aigner-Horev–Hefetz–Krivelevich [1]): if κ ≥ c'·max{α, log n, r}, then any 2r distinct terminals admit pairwise disjoint spanning paths with the prescribed endpoint pairs.
    Published external theorem; constant c' existential and never made explicit, so Theorem 1.2's c = max{42,20c'} is non-computable. Two of three authors are the present authors.
  • standard math Theorem 3.2 (Thomas–Wollan [32]): κ(G) ≥ 10r implies 2r-linkage.
    Published theorem used in Theorems 1.2 (α²-case) and 1.4 (S2b).
  • standard math Theorem 3.1 ([9] Chvátal–Erdős variant): κ > α implies Hamilton-connected.
    Used repeatedly for Step (S3).
  • standard math Theorem 1.1 ([9]): κ ≥ α implies Hamiltonian.
    Establishes Step (S1) for Theorems 1.2/1.4/1.5.
  • standard math Theorem 1.7 (McDiarmid–Yolov [29]): δ ≥ ᾱ implies Hamiltonian; Theorem 4.1 ([35]): δ > ᾱ implies Hamilton-connected.
    Provide (S1) and (S3) for Theorem 1.8.
  • standard math Theorem 1.10 (Ordaz–Amar–Raspaud [30]): α_BIP ≤ 2δ−4 implies Hamilton-biconnected.
    Provides (S1) and (S3) for Theorem 1.11.
  • standard math Lemma 3.4 (Bohman–Frieze–Krivelevich–Martin [5]): partition into k²/(16n)-connected parts of size ≥ k/8.
    Used in Theorem 1.4 to decompose G₁.
  • standard math Parity-switcher structural fact: any R-parity-switcher W (even cycle with odd R-count plus pairwise internally-disjoint paths meeting C exactly at endpoints) contains two Hamilton paths between v₁ and v_{r+1} of opposite R-parity.
    Facts (S4)/(S5) — cited from [8] ('additional details and a figure can be found in [8]'); used without proof in every theorem.

how reviews work

0 comments
Cite this review

Pith. "Pith review of On graphs whose cycle space is spanned by their Hamilton cycles." pith.science (2026). https://pith.science/paper/SCXBTLCE

@misc{pith2026260605835,
  author       = {Pith},
  title        = {Pith review of: On graphs whose cycle space is spanned by their Hamilton cycles},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/SCXBTLCE}},
  note         = {Machine review of arXiv:2606.05835}
}
abstract

The cycle space of a graph $G$, denoted $\mathcal{C}(G)$, is a vector space over ${\mathbb F}_2$, spanned by all incidence vectors of edge-sets of cycles of $G$. If $G$ has $n$ vertices, then $\mathcal{C}_n(G)$ denotes the subspace of $\mathcal{C}(G)$, spanned by the incidence vectors of Hamilton cycles of $G$. We consider several known sufficient conditions for Hamiltonicity and show that an appropriate and fairly mild strengthening of each such condition in fact ensures the stronger property $\mathcal{C}_n(G) = \mathcal{C}(G)$. In particular, we consider the classical Chv\'atal-Erd\H{o}s criterion and prove that (under various additional restrictions) if $n$ is odd and $\kappa(G) \geq c \alpha(G)$, where $c$ is a sufficiently large absolute constant, then $\mathcal{C}_n(G) = \mathcal{C}(G)$. Moreover, considering the McDiarmid-Yolov criterion we prove that if $n$ is odd and $\delta(G) \geq \max \left\{2 \tilde{\alpha}(G) + 9, \tilde{\alpha}(G) + 18 \right\}$, where $\tilde{\alpha}(G)$ is the so-called bipartite independence number of $G$, then $\mathcal{C}_n(G) = \mathcal{C}(G)$. We also prove that if $n$ is odd and $G$ admits $16 \alpha(G) + 12$ pairwise disjoint connected dominating sets, $\mathcal{C}_n(G) = \mathcal{C}(G)$. Finally, we consider an effective Chv\'atal-Erd\H{o}s type criterion for bipartite graphs and prove that if $G$ is a balanced bipartite graph on $2n$ vertices, satisfying $\alpha_{\emph{BIP}}(G) \leq 2 \delta(G) - 24$, then $\mathcal{C}_{2n}(G) = \mathcal{C}(G)$.

Review history (2 revisions) →

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

35 extracted references · 5 linked inside Pith

  1. [8]

    Christoph, R

    M. Christoph, R. Nenadov, and K. Petrova, The Hamilton space of pseudorandom graphs, Journal of Combinatorial Theory, Series B176 (2026), 254–267

    2026

  2. [1]

    Aigner-Horev, D

    E. Aigner-Horev, D. Hefetz, and M. Krivelevich, Cycle lengths in randomly perturbed graphs, Random Structures and Algorithms63(4) (2023), 867–884

    2023

  3. [2]

    Alspach, S

    B. Alspach, S. C. Locke, and D. Witte, The Hamilton spaces of Cayley graphs on abelian groups, Discrete Mathematics82 (2) (1990), 113–126

    1990

  4. [3]

    Ash, Two sufficient conditions for the existence of hamiltonian cycles in bipartite graphs, Ars Combinatoria 16A (1983), 33–37

    P. Ash, Two sufficient conditions for the existence of hamiltonian cycles in bipartite graphs, Ars Combinatoria 16A (1983), 33–37

    1983

  5. [4]

    J. D. Baron and J. Kahn, On the cycle space of a random graph,Random Structures and Algorithms54(1) (2019), 39–68

    2019

  6. [5]

    Bohman, A

    T. Bohman, A. Frieze, M. Krivelevich and R. Martin, Adding random edges to dense graphs, Random Structures and Algorithms24 (2004), 105–117

    2004

  7. [6]

    Bollob´ as and A

    B. Bollob´ as and A. Thomason, Highly linked graphs,Combinatorica16 (1996), 313–320

    1996

  8. [7]

    J. A. Bondy and L. Lov´ asz, Cycles through specified vertices of a graph,Combinatorica1 (1981), 117–140

    1981

Show all 35 references
  1. [9]

    Chv´ atal and P

    V. Chv´ atal and P. Erd˝ os, A note on Hamiltonian circuits,Discrete Mathematics2 (1972), 111– 113

    1972

  2. [10]

    DeMarco, A

    B. DeMarco, A. Hamm, and J. Kahn, On the triangle space of a random graph,Journal of Combinatorics4(2) (2013), 229–249

    2013

  3. [11]

    G. A. Dirac, Some theorems on abstract graphs,Proceedings of the London Mathematical Society 3(1) (1952), 69–81

    1952

  4. [12]

    Dragani´ c, D

    N. Dragani´ c, D. Munh´ a Correia, and B. Sudakov, A generalization of Bondy’s pancyclicity theorem,Combinatorics, Probability and Computing33 (2024), 554–563

    2024

  5. [13]

    Dragani´ c, D

    N. Dragani´ c, D. Munh´ a Correia, and B. Sudakov, Chvatal-Erdos condition for pancyclicity, Journal of the Association for Mathematical Research2 (2024), 1–14

    2024

  6. [14]

    Dragani´ c, D

    N. Dragani´ c, D. Munh´ a Correia, and B. Sudakov, Pancyclicity of Hamiltonian graphs,Journal of the European Mathematical Society(2024)

    2024

  7. [15]

    Erd˝ os, Some problems in graph theory,Hypergraph Seminar, Springer(1972), 187–190

    P. Erd˝ os, Some problems in graph theory,Hypergraph Seminar, Springer(1972), 187–190. 21

    1972

  8. [16]

    Favaron, P

    O. Favaron, P. Mago, and O. Ordaz, On the bipartite independence number of a balanced bipartite graph,Discrete Mathematics121 (1993), 55–63

    1993

  9. [17]

    Fraisse,D λ-cycles and their applications for hamiltonian graphs, Thesis, Universit´ e Paris-Sud, 1986

    P. Fraisse,D λ-cycles and their applications for hamiltonian graphs, Thesis, Universit´ e Paris-Sud, 1986

    1986

  10. [18]

    I. B.-A. Hartman, Long cycles generate the cycle space of a graph,European Journal of Com- binatorics4 (1983), 237–246

    1983

  11. [19]

    Hefetz and M

    D. Hefetz and M. Krivelevich, The Hamilton cycle space of random graphs, arXiv preprint arXiv:2506.19731v1, 2025

    2025 arXiv

  12. [20]

    Hefetz and M

    D. Hefetz and M. Krivelevich, The Hamilton cycle space of random regular graphs and randomly perturbed graphs, arXiv preprint arXiv:2507.04488, 2025

    2025 arXiv

  13. [21]

    Heinig, On prisms, M¨ obius ladders and the cycle space of dense graphs,European Journal of Combinatorics36 (2014), 503–530

    P. Heinig, On prisms, M¨ obius ladders and the cycle space of dense graphs,European Journal of Combinatorics36 (2014), 503–530

    2014

  14. [22]

    Heinig, When Hamilton circuits generate the cycle space of a random graph, arXiv preprint arXiv:1303.0026, 2013

    P. Heinig, When Hamilton circuits generate the cycle space of a random graph, arXiv preprint arXiv:1303.0026, 2013

    2013 arXiv

  15. [23]

    Hou and Z

    X. Hou and Z. Yin, Dirac-type condition for Hamilton-generated graphs, arXiv preprint arXiv:2503.15950v1, 2025

    2025 arXiv

  16. [24]

    Jackson and O

    B. Jackson and O. Ordaz, Chv´ atal-Erd˝ os conditions for paths and cycles in graphs and digraphs. A survey,Discrete Mathematics84 (1990), 241–254

    1990

  17. [25]

    Janson, T

    S. Janson, T. Luczak, and A. Ruci´ nski,Random graphs, Wiley-Interscience Series in Discrete Mathematics and Optimization, Wiley-Interscience, New York, 2000

    2000

  18. [26]

    Letzter, Pancyclicity of highly connected graphs, arXiv preprint arXiv:2306.12579v2, 2023

    S. Letzter, Pancyclicity of highly connected graphs, arXiv preprint arXiv:2306.12579v2, 2023

    2023 arXiv

  19. [27]

    S. C. Locke, A basis for the cycle space of a 2-connected graph,European Journal of Combina- torics6 (1985), 253–256

    1985

  20. [28]

    S. C. Locke, A basis for the cycle space of a 3-connected graph,Annals of Discrete Mathematics 27 (1985), 381–397

    1985

  21. [29]

    McDiarmid and N

    C. McDiarmid and N. Yolov, Hamilton cycles, minimum degree, and bipartite holes,Journal of Graph Theory86(3) (2017), 277–285

    2017

  22. [30]

    Ordaz, D

    O. Ordaz, D. Amar, and A. Raspaud, Hamiltonian properties and the bipartite independence number,Discrete Mathematics161 (1996), 207–215. 22

    1996

  23. [31]

    Robertson and P

    N. Robertson and P. Seymour, Graph Minors XIII, The disjoint paths problem,Journal of Combinatorial Theory Series B63 (1995), 65–100

    1995

  24. [32]

    Thomas and P

    R. Thomas and P. Wollan, An improved linear edge bound for graph linkages,European Journal of Combinatorics26 (2005), 309–324

    2005

  25. [33]

    D. B. West,Introduction to Graph Theory, Prentice Hall, 2001

    2001

  26. [34]

    J. Yu, N. Wang, G. Wand, and D. Yu, Connected dominating sets in wireless ad hoc and sensor networks – A comprehensive survey,Computer Communications36 (2013), 121–134

    2013

  27. [35]

    Q. Zhou, H. Broersma, L. Wang, and Y. Lu, A note on minimum degree, bipartite holes, and Hamiltonian properties,Discussiones Mathematicae Graph Theory44 (2024), 717–726. 23

    2024

Pith tools

Reviewed August 2, 2026 · model on record in the stance chip above.