Hitting time fork edge-disjoint spanning trees in a random graph
Tóm tắt
We show that in almost every random graph process, the hitting time for havingk edge-disjoint spanning trees equals the hitting time for having minimum degreek.
Tài liệu tham khảo
B. Bollobás,Random Graphs, Academic, London, (1985).
B. Bollobás andA.M. Frieze, On matchings and hamiltonian cycles in random graphs,Annals of Discrete Math. 28 (1985), 23–46.
B. Bollobás, T.T. Fenner andA.M. Frieze, An algorithm for finding hamilton paths and cycles in random graphs,Combinatorica 7 (1987), 327–341.
P.A. Catlin, A reduction method to find eulerian subgraphs,J. Graph Theory 12 (1988), 29–45.
A.M. Frieze andT. Łuczak, Edge disjoint spanning trees in random graphs,Per. Math. Hung. 21 (1990), 35–37.
F. Jaeger, A note on subeulerian graphs,J. Graph Theory 3 (1979), 91–93.
C.St.J.A. Nash-Williams, Edge disjoint spanning trees of finite graphs,J. London Math. Soc. 36 (1961), 445–450.
W.T. Tutte, On the problem of decomposing a graph into n factors,J. London Math. Soc. 36 (1961), 221–230.