On factors in random graphs

DOI10.1007/BF02761675zbMath0475.05067OpenAlexW2014206760MaRDI QIDQ1159696

S. H. Smith

Publication date: 1981

Published in: Israel Journal of Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/bf02761675

zbMATH Keywords

random graphsfactorsaugmenting paths

Mathematics Subject Classification ID

Combinatorial probability (60C05) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Related Items

Graph factors and factorization: 1985--2003: a survey, Packing tree factors in random and pseudo-random graphs, One-factor in random graphs based on vertex choice, Sparse random graphs: Eigenvalues and eigenvectors, On the singularity of adjacency matrices for random regular digraphs, The circular law for random regular digraphs, On 1-sum flows in undirected graphs, Improved queue-size scaling for input-queued switches via graph factorization, Distribution of the number of spanning regular subgraphs in random graphs, How many random edges make a graph Hamiltonian?

Cites Work

• Unnamed Item
• Fast probabilistic algorithms for Hamiltonian circuits and matchings
• One-factor in random graphs based on vertex choice
• Hamiltonian circuits in random graphs
• On the strength of connectedness of a random graph
• The Subgraph Problem
• On the existence of a factor of degree one of a connected random graph