Solution of two problems of P. Erdős concerning Hamiltonian cycles
type: Item
instance of: scholarly article
title: Solution of two problems of P. Erdős concerning Hamiltonian cycles
zbMATH Open document ID: 0733.05054
DOI: 10.1016/0012-365X(90)90269-N
author: Jozef Širáň
author: Peter Horák
published in: Discrete Mathematics
publication date: 1990-01-01T00:00:00Z
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\).
Mathematics Subject Classification ID: 05C38
Mathematics Subject Classification ID: 05C45
Mathematics Subject Classification ID: 05C70
zbMATH DE Number: 4212092
zbMATH Keywords: packing
zbMATH Keywords: non-Hamiltonian complement
reviewed by: Norman F. Quimpo
MaRDI profile type: Publication
cites work: Q5722820
cites work: Subgraphs intersecting any Hamiltonian cycle
cites work: Q5722819
full work available at URL: 0012-365x(90)90269-n
OpenAlex ID: W1966215030
Recommended article: Q3715141
Recommended article: Solution to a problem of Bollobás and Häggkvist on Hamilton cycles in regular graphs
Recommended article: A solution to Erdős and Hajnal’s odd cycle problem
Recommended article: On two problems regarding the Hamiltonian cycle game
Recommended article: An extremal problem for cycles in hamiltonian graphs
Recommended article: Q4378246
Recommended article: Q3980663
Recommended article: Q3309913
Recommended article: Q3469119
Recommended article: Q4304421
description: scientific article; zbMATH DE number 4212092