Premium
1‐ Pancyclic Hamilton Cycles in Random Graphs
Author(s) -
Cooper C.
Publication year - 1992
Publication title -
random structures and algorithms
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.314
H-Index - 69
eISSN - 1098-2418
pISSN - 1042-9832
DOI - 10.1002/rsa.3240030307
Subject(s) - pancyclic graph , combinatorics , mathematics , generalization , graph , hamiltonian path , enhanced data rates for gsm evolution , discrete mathematics , computer science , line graph , mathematical analysis , artificial intelligence , 1 planar graph
We consider a generalization of the pancyclic property. A graph G is defined to be 1‐pancyclic if there is some Hamilton cycle H in G such that we can find a cycle C s of length s (3 ⩽ s ⩽ n − 1) using only the edges of H and one other edge e s . We show that the threshold for G n,p to be Hamiltonian, is the threshold for the 1‐pancyclic property.