Solution of two problems of P. Erdős concerning Hamiltonian cycles

Paths and cycles (05C38) Eulerian and Hamiltonian graphs (05C45) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Review text

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\).

Recommendations

Cites work

Cited in

(7)

This page was built for publication: Solution of two problems of P. Erdős concerning Hamiltonian cycles

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q810050)