Long cycles, degree sums and neighborhood unions (Q1309446): Difference between revisions
From MaRDI portal
Removed claims |
Changed an Item |
||
Property / author | |||
Property / author: Hajo J. Broersma / rank | |||
Normal rank | |||
Property / author | |||
Property / author: Jan van den Heuvel / rank | |||
Normal rank | |||
Property / author | |||
Property / author: Henk Jan Veldman / rank | |||
Normal rank | |||
Property / reviewed by | |||
Property / reviewed by: Norman F.Quimpo / rank | |||
Normal rank |
Revision as of 22:00, 12 February 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Long cycles, degree sums and neighborhood unions |
scientific article |
Statements
Long cycles, degree sums and neighborhood unions (English)
0 references
4 July 1994
0 references
Let \(\sigma_ 3\) denote the minimum degree sum of any 3 pairwise nonadjacent vertices. Let \(\text{NC}_ k\) be the minimum number of vertices in a neighborhood union of any \(k\) pairwise nonadjacent vertices. The authors show that every 1-tough graph of order \(n \geq 3\) with \(\sigma_ 3 \geq n+r\) has a cycle of length at least \(\min \{n,n+\text{NC}_{r+5+\varepsilon (n+r)} (G)-\alpha(G)\}\), where \(\varepsilon (i)=0,2\), or 1, accordingly as \(i \equiv 0,1\) or \(2 \pmod 3\), respectively. They also prove that if \(G\) is a 1-tough graph of order \(n \geq 3\) with \(\sigma_ 3 \geq n+r\) and \(n\geq 8t-6r-17\) then \(G\) has a cycle of length at least \(\min \{n,2 \text{NC}_ t(G)\}\). Similar results hold for 2-connected graphs.
0 references
longest cycles
0 references
hamiltonian cycles
0 references
neighborhood union
0 references
1-tough graph
0 references