Solution of two problems of P. Erdős concerning Hamiltonian cycles (Q810050): Difference between revisions

The graphs \(G_ 1,G_ 2,...,G_ r\) are packed into \(K_ n\) if \(K_ n\) has edge-disjoint subgraphs \(G_ 1',G_ 2',...,G_ r'\) such that \(G_ i'\cong G_ i\). Suppose we consider packing graphs into \(K_ n\), requiring each to be a graph on n vertices with a non-Hamiltonian complement. Regarding the packing of such graphs, P. Erdős posed two problems: (1) What is the maximum number g(n) which can be packed into \(K_ n?\) (2) What is \(f(n,r)=\min \sum^{r}_{i=1}e(G_ i)\), where e(G) is the number of edges of G and the minimum is taken over all r-tuples of graphs packed into \(K_ n?\) The paper provides a solution to each question. It is shown that \(g(n)=3+_{\lfloor}\log_ 2(n-1)/3_{\rfloor}\) for \(n\geq 4\). In connection with (2) it is known that for any graph G with non-Hamiltonian complement, there corresponds a number t(G) counting the number of vertices of a certain degree. An expression for f(n,r) is obtained in terms of a function of such t(G). The proofs exploit the properties of a particular collection of extremal graphs which can be packed into \(K_ n\).