Solution of two problems of P. Erdős concerning Hamiltonian cycles (Q810050): Difference between revisions
From MaRDI portal
Changed an Item |
Set OpenAlex properties. |
||
(2 intermediate revisions by 2 users not shown) | |||
Property / MaRDI profile type | |||
Property / MaRDI profile type: MaRDI publication profile / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q5722820 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Subgraphs intersecting any Hamiltonian cycle / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q5722819 / rank | |||
Normal rank | |||
Property / full work available at URL | |||
Property / full work available at URL: https://doi.org/10.1016/0012-365x(90)90269-n / rank | |||
Normal rank | |||
Property / OpenAlex ID | |||
Property / OpenAlex ID: W1966215030 / rank | |||
Normal rank |
Latest revision as of 11:21, 30 July 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Solution of two problems of P. Erdős concerning Hamiltonian cycles |
scientific article |
Statements
Solution of two problems of P. Erdős concerning Hamiltonian cycles (English)
0 references
1990
0 references
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\).
0 references
packing
0 references
non-Hamiltonian complement
0 references