Pith. sign in

REVIEW 2 major objections 4 minor 41 references

Approximate Itai-Zehavi conjecture for random graphs

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

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

Pith's one-line read Random graphs nearly meet the Itai–Zehavi spanning-tree bound

desk verdict The Erdős–Rényi theorem is new, asymptotically optimal, and looks sound; the sparse regular-graph proof has a real gap in the odd-n transfer that must be fixed, and it leans on unproved results from a companion paper. read the letter →

arxiv 2506.23970 v1 pith:E66N2ADX submitted 2025-06-30 math.CO

Lawrence Hollom , Lyuben Lichev , Adva Mond , Julien Portier , Yiting Wang This is my paper · ORCID
classification math.CO MSC 05C8005C0505C40
keywords independentspanningtreesItai–ZehaviconjecturerandomgraphsErdős–Rényigraphregularvertexconnectivitysprinkling
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 tries to prove an approximate version of the Itai–Zehavi conjecture for two random graph models. The conjecture says that every vertex of a d-vertex-connected graph can be the root of d spanning trees whose root-to-vertex paths are internally vertex-disjoint. The authors show that when the edge probability satisfies np = ω(log n), the random graph G(n,p) contains, with high probability, (1−o(1))np such trees rooted at every vertex, asymptotically the maximum possible. For random d-regular graphs they prove that with high probability almost all vertices root ⌊d/4⌋ independent spanning trees, and when d = ω(log n) every vertex roots (1−o(1))d of them. These results positively answer a question posed by Draganić and Krivelevich.

What carries the argument

The Erdős–Rényi argument splits G(n,p) into two independent random graphs G1 and G2, uses breadth-first search in G1 to build disjoint core sets attached to k = (1−ε)np neighbours of the root, and then uses G2 to attach every remaining vertex to the core sets through paths of length at most two; the final step is a perfect-matching argument in a bipartite Erdős–Rényi graph. The sparse regular argument works inside the 1-factorisation model G″(n,d), the union of d uniformly chosen edge-disjoint perfect matchings, grouped into k = ⌊d/4⌋ triples. Each triple forms a 3-regular graph whose breadth-first search supplies a candidate spanning tree, and the fourth matching of each group is used to reroute the few vertices whose root-to-vertex paths would collide. The proof transfers results from this model to G(n,d) via a one-sided contiguity theorem, and it handles odd n by reducing to an even graph on n−1 vertices and adding one new vertex as a leaf.

What would settle it

Test the one-sided contiguity theorem at d = (log n)^2 by computing, say, the probability of a given small cut in both the uniform random d-regular graph and the 1-factorisation-weighted model; if one model accepts a property with high probability while the other rejects it, the transfer breaks and the sparse-regular theorem would not follow.

Watch

Extended reading notes

Core claim

The central claim is that the Itai–Zehavi bound is asymptotically attainable in random graphs. Theorem 1 states that for p = p(n) with np = ω(log n), with high probability every vertex r of G(n,p) is the root of (1−o(1))np independent spanning trees. Theorem 2 states that for d = d(n) ∈ [4,n−1], with high probability at least (1−o(1))n vertices r of the random d-regular graph G(n,d) root ⌊d/4⌋ independent spanning trees, and that when d = ω(log n), with high probability every vertex roots (1−o(1))d such trees. The d = ω(log n) regular case follows from the Erdős–Rényi result through a stochastic comparison between G(n,p) and G(n,d). The sparse regular case is proved in a model built from d edge-disjoint perfect matchings and then transferred to the uniform random regular graph.

Load-bearing premise

The proof for sparse random regular graphs relies on an unproved correspondence between the uniform random regular graph and a model built from edge-disjoint perfect matchings; if that correspondence fails at the required densities, the constant-factor result would not transfer to the actual random graph.

Editorial extensions

If this is right

  • For Erdős–Rényi graphs with np = ω(log n), every vertex is simultaneously the root of (1−o(1))np independent spanning trees, so the Itai–Zehavi bound is attained up to a 1−o(1) factor for every root at once.
  • The same asymptotic bound transfers to random d-regular graphs with d = ω(log n), giving (1−o(1))d independent spanning trees rooted at every vertex.
  • For sparse random regular graphs with d ∈ [4, (log n)^2], almost all vertices root at least ⌊d/4⌋ independent spanning trees, the first linear-in-d constant-factor statement in this regime.
  • The Erdős–Rényi construction is algorithmic: the proof runs a randomised polynomial-time procedure that outputs the family of independent spanning trees with high probability.
  • The odd-n regular case is derived from an even graph on n−1 vertices together with one additional vertex attached as a leaf, so the argument is not interrupted by parity.

Reading between the lines

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

  • The sparse-regime result depends on the one-sided contiguity theorem stated as Theorem 2.6 without proof in this paper; if that model equivalence fails at the relevant densities, the ⌊d/4⌋ conclusion is only established in the artificial 1-factorisation model.
  • The paper itself notes that the constant 1/4 could likely be pushed to 1/3 with a more technical presentation, and it identifies ⌊d/2⌋ as a natural structural barrier for its approach.
  • A direct testable extension is the authors' Conjecture 5.1: for p ≥ (log n)/n, verify whether G(n,p) contains as many independent spanning trees as its minimum degree, which would make the Itai–Zehavi conjecture exact on Erdős–Rényi graphs.
  • The random-overlay computations suggest the sparse-regular statement should survive for degrees up to n^{1/10}; closing the unproved contiguity gap at d = (log n)^2 would extend the result from the 1-factorisation model to the uniform random graph.
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 proves asymptotic versions of the Itai–Zehavi conjecture for two random graph models. For G(n,p) with np=\omega(\log n), it shows that with high probability every root vertex admits (1-o(1))np independent spanning trees (Theorem 1). For G(n,d), it shows that with high probability (1-o(1))n vertices admit \lfloor d/4\rfloor ISTs for every d\in[4,n-1], and when d=\omega(\log n) every vertex admits (1-o(1))d ISTs (Theorem 2). The Erd\H{o}s-R\'enyi proof uses a two-round sprinkling decomposition, a BFS construction of disjoint core sets, and a bipartite perfect-matching step. The random-regular proof works in the 1-factorisation-weighted model G''(n,d), groups the d matchings into \lfloor d/4\rfloor triples plus one matching each, builds BFS trees in the triples, and repairs bad vertices by rerouting along the reserved matchings. The odd-n case is handled by deleting an induced matching from G(n-1,d), adding a vertex, and transferring via a coupling based on Strassen's theorem.

Significance. Assuming the companion-paper contiguity statement and a repaired odd-n transfer, the results are substantial: they answer the question of Dragani\'c and Krivelevich in the random setting, give the first constant-factor IST result for sparse random regular graphs, and the G(n,p) statement is asymptotically optimal and algorithmic. The proof is detailed and mostly coherent, with explicit probabilistic estimates and a clear structural decomposition. The main reservations are that the odd-n conclusion is not justified as written and that a central transfer theorem is imported from the authors' own companion paper [20].

major comments (2)
  1. [§4.2 (Step 4), Lemma 4.24] The deduction of Theorem 4.1 for odd n is not justified. Lemma 4.24 is a fixed-ε statement: it asserts, for every ε>0, P(Gu(n,d)∈U(D_ε))≥1−ε, and the proof actually ends with the weaker bound 1−3ε. Theorem 4.1, however, requires a single high-probability event D_{ε_n} with ε_n→0. The proof of Lemma 4.18 supplies P(G''(n−1,d)∈C^s_ε)=1−o(1) only for fixed ε, and the Markov step used to convert a random-root success statement into the fraction of roots and matchings required by C^s_ε incurs a 1/ε factor. Therefore, for a sequence ε_n→0, the inequality λ(H′)≥1−ε_n−o(1) need not hold, and the final line 'Theorem 4.1 for odd n follows by combining Lemma 4.22 and Lemma 4.24' does not follow. This affects the first part of Theorem 2 for every odd n.
  2. [§2, Theorem 2.6] The sparse regular proof transfers all statements from the 1-factorisation-weighted model G''(n,d) to the uniform model G(n,d) using Theorem 2.6, a one-sided contiguity result quoted from the authors' companion paper [20, Theorem 1.5] without proof. This theorem is load-bearing: if it fails at the required scale, the constant-factor statement ⌊d/4⌋ for d≤(log n)^2 is not established for G(n,d). Please include a proof, or a precise statement with quantitative error bounds, or make the dependency fully explicit and publicly verifiable.
minor comments (4)
  1. [§4.2, proof of Lemma 4.24] The proof concludes with P≥1−3ε while the lemma states P≥1−ε; although for fixed ε the gap can be closed by rescaling ε to ε/3, the text should say this explicitly rather than asserting the lemma follows directly.
  2. [§4.1.4, Claim 4.15] The claim conditions on the high-probability event from Lemma 4.14 that there are at most β^20 unsafe vertices, but the conditioning is only implicit; making it explicit would clarify the union bound that follows.
  3. [§4.2, Definition 4.23 and Claim 4.26] In the bipartite graph W, the notation 'op(Hd) with multiplicity' is used without defining the multiplicity; a sentence stating that B contains one copy for each preimage under op would improve readability.
  4. [§4.2, Lemma 4.18] After proving that a uniformly random root and a uniformly random matching are good with high probability, the proof says this is sufficient for the conclusion C^s_ε, but the averaging/Markov step that turns this into a statement about (1−ε)n roots and a (1−ε) fraction of matchings is left implicit.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the IST theorems are not assumed by the inputs; the self-cited contiguity and overlay lemmas are general model-comparison facts that do not encode the target property.

full rationale

I walked the derivation chain of both main theorems. Theorem 1 is obtained from a two-stage sprinkling argument (G1/G2) and a perfect-matching criterion in an auxiliary bipartite graph; the inputs are expansion bounds, Chernoff's bound, and Theorem 2.4, none of which mention independent spanning trees. The (1-o(1))np count is not fitted: k=(1-epsilon)np is a chosen construction parameter, and the trees are explicitly built. No 'prediction' is a renamed fitted value. For Theorem 2, the dense case is transferred from Theorem 1 via the external stochastic-domination result Theorem 2.5. The sparse case is proved in the 1-factorisation model G''(n,d), and Theorem 2.6 (a one-sided contiguity result cited to the authors' companion paper [20]) transfers high-probability properties back to G(n,d). This is a structural statement about random graph models: it does not mention ISTs, and the present paper supplies all arguments that the IST property holds in G'' before the transfer. The other self-cited input, Lemma 4.7, is a general fact about random overlays avoiding double edges with probability bounded away from zero; it is used to compute probabilities, not to assume the desired conclusion. I therefore find no equation-level reduction of a claimed theorem to its own assumptions, no renamed fit, and no definition of the IST quantity in terms of the tools. The concern that the companion paper is cited without proof is a verification/completeness point, not a circularity point. The skeptic's odd-n objection is a possible quantitative gap in the proof of Lemma 4.24, not a circularity, because it does not exhibit any input that already contains the target IST statement.

Assumptions & free parameters 3 free parameters · 8 assumptions · 0 invented entities

The proof leans on standard probabilistic and enumerative tools (Chernoff, perfect matchings, McKay asymptotics) plus two deep results from the authors' own companion paper [20]: one-sided contiguity (Theorem 2.6) and the random-overlay no-double-edge lemma (Lemma 4.7). No data are fitted; the hand-picked constants α, ψ, β are proof artifacts. The paper introduces no new physical or mathematical entities beyond random graph models.

free parameters (3)
  • alpha (α) = 0.001
    Absolute constant used in stochastic dominance bound (2) in Theorem 3.1; any sufficiently small constant works and the central claim is insensitive to its value.
  • psi (ψ) = 20 log^2 log n
    Hand-picked parameter in (5) used to absorb error probabilities in the sparse regular graph analysis; any sufficiently large slowly growing function would serve.
  • beta (β) = log^2 n + ψ
    Diameter and height bound for BFS trees in Section 4.1.3; chosen to make probability estimates like n^{-1/3+o(1)} work, but the result is robust to larger choices.
assumptions (8)
  • standard math Chernoff bound for binomial tails
    Lemma 2.3, used throughout for concentration of neighbourhood sizes.
  • standard math Existence of perfect matching in bipartite Erdős-Rényi graphs (Theorem 2.4)
    Used in Phase 3 of Theorem 3.1 to assign distinct parent vertices w_i.
  • domain assumption Coupling theorem of Gao, Isaev and McKay (Theorem 2.5)
    Allows the d=ω(log n) case of Theorem 2 to be deduced from Theorem 1; cited from [19].
  • domain assumption One-sided contiguity between uniform G(n,d) and the 1-factorisation model (Theorem 2.6)
    Bridges the sparse regular graph proof to G(n,d); stated without proof and taken from the authors' own companion paper [20].
  • standard math McKay's asymptotic enumeration of perfect matchings in dense graphs (Corollary 2.2)
    Basis for Lemmas 4.2 and 4.3 on colour-subgraph distributions in G''(n,d).
  • standard math Bound on expected triangle count in G(n,d) (Theorem 2.7)
    Used in Claim 4.26 to show most vertices in a random d-regular graph have independent neighbourhoods, enabling the odd-n operation op.
  • standard math Almost all unlabelled d-regular graphs have trivial automorphism group (Theorem 2.8)
    Used in Lemma 4.22 to transfer label-independent properties between labelled and unlabelled models.
  • domain assumption Random overlay model produces no double edges with probability bounded away from zero (Lemma 4.7)
    Core input to the overlay probability calculations in Section 4.1.3; stated as a lemma from the authors' companion paper [20].

how reviews work

0 comments
Cite this review

Pith. "Pith review of Approximate Itai-Zehavi conjecture for random graphs." pith.science (2026). https://pith.science/paper/E66N2ADX

@misc{pith2026250623970,
  author       = {Pith},
  title        = {Pith review of: Approximate Itai-Zehavi conjecture for random graphs},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/E66N2ADX}},
  note         = {Machine review of arXiv:2506.23970}
}
abstract

A famous conjecture by Itai and Zehavi states that, for every $d$-vertex-connected graph $G$ and every vertex $r$ in $G$, there are $d$ spanning trees of $G$ such that, for every vertex $v$ in $G\setminus \{r\}$, the paths between $r$ and $v$ in different trees are internally vertex-disjoint. We show that with high probability the Itai-Zehavi conjecture holds asymptotically for the Erd\H{o}s-R\'enyi random graph $G(n,p)$ when $np= \omega(\log n)$ and for random regular graphs $G(n,d)$ when $d= \omega(\log n)$. Moreover, we essentially confirm the conjecture up to a constant factor for sparser random regular graphs. This answers positively a question of Dragani\'{c} and Krivelevich. Our proof makes use of recent developments on sprinkling techniques in random regular graphs.

Figures

Figures reproduced from arXiv: 2506.23970 by the authors.

Figure 1
Figure 1. Illustration of the proof of Theorem 1. Note that v ∈ S only for illustration convenience. Next, fix a vertex v ∈ V \ {r} and define the set Yv = NG2 (v) ∩ S. By Claim 3.3 and the assumption 3p ≤ ε, we obtain that |S| = n − 1 − k⌈ε/3p⌉ ≥ n − 1 − ((1 − ε)np + 1)(ε/3p + 1) ≥ (1 − 2ε/3)n. Thus, by choosing the constant C suitably large, and by using the Chernoff bound (Lemma 2.3), we obtain that |Yv| ≥ k with probabili… view at source ↗

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

41 extracted references · 40 canonical work pages

  1. [20]

    Hollom, L

    L. Hollom, L. Lichev, A. Mond, J. Portier, and Y. Wang, Monotonicity and decompositions of random regular graphs, 2025

    work page 2025

  2. [1]

    Bollobás, Random graphs, 2nd ed., Cambridge Studies in Advanced Mathematics, Cambridge University Press, 2001

    B. Bollobás, Random graphs, 2nd ed., Cambridge Studies in Advanced Mathematics, Cambridge University Press, 2001

    work page 2001

  3. [2]

    Bollobás and W

    B. Bollobás and W. Fernandez de la Vega,The diameter of random regular graphs, Combinatorica 2 (1982), 125–134

    work page 1982

  4. [3]

    Bollobás and A

    B. Bollobás and A. Thomason,Random graphs of small order, Random graphs ’83 (Poznań, 1983), North-Holland Math. Stud., vol. 118, North-Holland, Amsterdam, 1985, pp. 47–97

    work page 1983

  5. [4]

    Censor-Hillel, M

    K. Censor-Hillel, M. Ghaffari, G. Giakkoupis, B. Haeupler, and F. Kuhn,Tight bounds on vertex connectivity under sampling, ACM Transactions on Algorithms (TALG)13 (2017), no. 2, 1–26

    work page 2017

  6. [5]

    Censor-Hillel, M

    K. Censor-Hillel, M. Ghaffari, and F. Kuhn,A new perspective on vertex connectivity, Proceedings of the twenty-fifth annual ACM-SIAM symposium on Discrete algorithms, SIAM, 2014, pp. 546–561

    work page 2014

  7. [6]

    Chen, Parallel construction of optimal independent spanning trees on Cartesian product of complete graphs, Information Processing Letters111 (2011), no

    X.-B. Chen, Parallel construction of optimal independent spanning trees on Cartesian product of complete graphs, Information Processing Letters111 (2011), no. 5, 235–238

    work page 2011

  8. [7]

    Cheng, D

    B. Cheng, D. Wang, and J. Fan,Independent spanning trees in networks: a survey, ACM Computing Surveys 55 (2023), no. 14s, 1–29

    work page 2023

Show all 41 references
  1. [8]

    Cheriyan and S

    J. Cheriyan and S. Maheshwari,Finding nonseparating induced cycles and independent spanning trees in3-connected graphs, Journal of Algorithms9 (1988), no. 4, 507–537

    1988

  2. [9]

    Cooper, A

    C. Cooper, A. Frieze, and B. Reed,Random regular graphs of non-constant degree: connectivity and Hamiltonicity, Combin. Probab. Comput.11 (2002), no. 3, 249–261

    2002

  3. [10]

    Cuckler and J

    B. Cuckler and J. Kahn, Hamiltonian cycles in Dirac graphs, Combinatorica 29 (2009), no. 3, 299–326

    2009

  4. [11]

    Curran, O

    S. Curran, O. Lee, and X. Yu,Finding four independent trees, SIAM Journal on Computing35 (2006), no. 5, 1023–1058

    2006

  5. [12]

    Diestel,Extremal graph theory, Graph theory, Springer, 2024, pp

    R. Diestel,Extremal graph theory, Graph theory, Springer, 2024, pp. 179–226

    2024

  6. [13]

    Draganić and M

    N. Draganić and M. Krivelevich,Disjoint connected dominating sets in pseudorandom graphs, 2024

    2024

  7. [14]

    Frank,Connectivity and network flows, Handbook of combinatorics1 (1995), 111–177

    A. Frank,Connectivity and network flows, Handbook of combinatorics1 (1995), 111–177

    1995

  8. [15]

    Gao,Triangles and subgraph probabilities in random regular graphs, The Electronic Journal of Combinatorics (2024), paper P1.2

    P. Gao,Triangles and subgraph probabilities in random regular graphs, The Electronic Journal of Combinatorics (2024), paper P1.2

    2024

  9. [16]

    P. Gao, M. Isaev, and B. McKay,Kim–Vu’s sandwich conjecture is true ford≫ log4n, 2020, arXiv preprint arXiv:2011.09449

    2020 arXiv

  10. [17]

    P. Gao, M. Isaev, and B. D. McKay,Sandwiching dense random regular graphs between binomial random graphs, Probability Theory and Related Fields184 (2022), no. 1-2, 115–158

    2022

  11. [18]

    4, 911– 934

    P.GaoandY.Ohapkin, Subgraph probability of random graphs with specified degrees and applications to chromatic number and connectivity, Random Structures and Algorithms62 (2023), no. 4, 911– 934

    2023

  12. [19]

    P. Gao, M. Isaev, and B. D. McKay,Sandwiching random regular graphs between binomial random graphs, Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms, SIAM, 2020, pp. 690–701

    2020

  13. [21]

    Huck, Disproof of a conjecture about independent branchings ink-connected directed graphs, Journal of Graph Theory20 (1995), no

    A. Huck, Disproof of a conjecture about independent branchings ink-connected directed graphs, Journal of Graph Theory20 (1995), no. 2, 235–239

    1995

  14. [22]

    Isaev, B

    M. Isaev, B. D. McKay, A. Southwell, and M. Zhukovskii,Sprinkling with random regular graphs, Electronic Journal of Probability30 (2025), 1–20. 20

    2025

  15. [23]

    Itai and M

    A. Itai and M. Rodeh,The multi-tree approach to reliability in distributed networks, Information and Computation79 (1988), no. 1, 43–59

    1988

  16. [24]

    Janson, T

    S. Janson, T. Łuczak, and A. Rucinski,Random graphs, Wiley-Interscience Series in Discrete Math- ematics and Optimization, Wiley-Interscience, New York, 2000

    2000

  17. [25]

    Kao, K.-J

    S.-S. Kao, K.-J. Pai, S.-Y. Hsieh, R.-Y. Wu, and J.-M. Chang,Amortized efficiency of constructing multiple independent spanning trees on bubble-sort networks, Journal of Combinatorial Optimization 38 (2019), 972–986

    2019

  18. [26]

    Koperberg,Couplings and Matchings: Combinatorial notes on Strassen’s theorem, Statistics and Probability Letters209 (2024), 110089

    T. Koperberg,Couplings and Matchings: Combinatorial notes on Strassen’s theorem, Statistics and Probability Letters209 (2024), 110089

    2024

  19. [27]

    Krivelevich and W

    M. Krivelevich and W. Samotij, Optimal packings of Hamilton cycles in sparse random graphs, SIAM Journal on Discrete Mathematics26 (2012), no. 3, 964–982

    2012

  20. [28]

    Krivelevich, B

    M. Krivelevich, B. Sudakov, V. H. Vu, and N. C. Wormald,Random regular graphs of high degree, Random Structures Algorithms18 (2001), no. 4, 346–363

    2001

  21. [29]

    Ku, B.-F

    S.-C. Ku, B.-F. Wang, and T.-K. Hung,Constructing edge-disjoint spanning trees in product net- works, IEEE Transactions on Parallel and Distributed Systems14 (2003), no. 3, 213–221

    2003

  22. [30]

    Łuczak, Sparse random graphs with a given degree sequence, Random graphs, Vol

    T. Łuczak, Sparse random graphs with a given degree sequence, Random graphs, Vol. 2 (Poznań, 1989), Wiley-Intersci. Publ., Wiley, New York, 1992, pp. 165–182

    1989

  23. [31]

    B. D. McKay,Asymptotics for symmetric0-1 matrices with prescribed row sums, Ars Combinatoria 19 (1985), 15–25

    1985

  24. [32]

    B. D. McKay and N. C. Wormald,Automorphisms of random graphs with specified vertices, Com- binatorica 4 (1984), no. 4, 325–338

    1984

  25. [33]

    Nagai and S

    S. Nagai and S. Nakano,A linear-time algorithm to find independent spanning trees in maximal planar graphs, IEICE transactions on fundamentals of electronics, communications and computer sciences 84 (2001), no. 5, 1102–1109

    2001

  26. [34]

    C. S. J. A. Nash-Williams,Edge-disjoint spanning trees of finite graphs, J. London Math. Soc.36 (1961), 445–450

    1961

  27. [35]

    Obokata, Y

    K. Obokata, Y. Iwasaki, F. Bao, and Y. Igarashi,Independent spanning trees of product graphs and their construction, IEICE transactions on fundamentals of electronics, communications and computer sciences79 (1996), no. 11, 1894–1903

    1996

  28. [36]

    Randall Shaw,Completely independent spanning trees in the hypercube, 2024

    B. Randall Shaw,Completely independent spanning trees in the hypercube, 2024

    2024

  29. [37]

    Schrijver, Fractional packing and covering, Packing and covering in combinatorics, vol

    A. Schrijver, Fractional packing and covering, Packing and covering in combinatorics, vol. 106, Mathematisch Centrum Amsterdam, 1979, pp. 201–274

    1979

  30. [38]

    W. T. Tutte,On the problem of decomposing a graph inton connected factors, J. London Math. Soc. 36 (1961), 221–230

    1961

  31. [39]

    N. C. Wormald,The asymptotic connectivity of labelled regular graphs, Journal of Combinatorial Theory, Series B31 (1981), no. 2, 156–167

    1981

  32. [40]

    Yang, S.-M

    J.-S. Yang, S.-M. Tang, J.-M. Chang, and Y.-L. Wang,Parallel construction of optimal independent spanning trees on hypercubes, Parallel Computing33 (2007), no. 1, 73–79

    2007

  33. [41]

    Zehavi and A

    A. Zehavi and A. Itai,Three tree-paths, Journal of Graph Theory13 (1989), no. 2, 175–188. Appendix A. Proof of Theorem 4.4 Recall that G′′(n,d ) denotes the random graph onn vertices obtained as a union of and-tuple of perfect matchings sampled uniformly at random conditionall...

    1989

Pith tools

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