Long cycles, degree sums and neighborhood unions (Q1309446): Difference between revisions
From MaRDI portal
Set profile property. |
ReferenceBot (talk | contribs) Changed an Item |
||
Property / cites work | |||
Property / cites work: Q3971997 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Hamiltonian properties of graphs with large neighborhood unions / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q4873795 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Long cycles in graphs with large degree sums / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q4192100 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q5422499 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q4014317 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Hamiltonism, degree sum and neighborhood intersections / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: On Maximal Circuits in Finite Graphs / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q5628163 / rank | |||
Normal rank |
Revision as of 12:01, 22 May 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