Relative length of longest paths and cycles in 3-connected graphs
From MaRDI portal
Let \(G\) be a 3-connected graph on \(n\) vertices. Denote by \(p(G)\) and \(c(G)\) the orders of a longest path and a longest cycle in \(G\), respectively. If, for every independent set \(S\) of 4 vertices, \(\sum _{x \in S} \text{ deg}_G x \geq (3/2)n+1\), the authors show that \(p(G)-c(G) \leq 1\). They demonstrate the usefulness of this result by deriving various lower bounds for \(c(G)\) and other properties of longest cycles of \(G\).
Recommendations
- Relative length of longest paths and longest cycles in triangle-free graphs
- Relative length of longest paths and cycles in graphs
- Relative length of longest paths and cycles in 2-connected graphs
- Longest cycles in 3-connected graphs
- On relative length of longest paths and cycles
- scientific article; zbMATH DE number 568790
- Relative length of long paths and cycles in graphs with large degree sums
- Degree conditions and relative length of longest paths and cycles in graphs
- scientific article; zbMATH DE number 4212091
- scientific article; zbMATH DE number 426167
Cites work
Cited in
(21)- A degree sum condition for graphs to be prism Hamiltonian
- A degree sum condition with connectivity for relative length of longest paths and cycles
- Extremal 3-connected graphs
- Longest cycles in 3-connected graphs
- On the circumference of 3-connected graphs
- Length of longest cycles in a graph whose relative length is at least two
- Degree sums and dominating cycles
- Relative length of longest paths and cycles in graphs
- Relative length of longest paths and longest cycles in triangle-free graphs
- Relative length of longest paths and cycles in 2-connected graphs
- On relative length of longest paths and cycles
- scientific article; zbMATH DE number 3902690 (Why is no real title available?)
- Long paths, long cycles, and their relative length
- scientific article; zbMATH DE number 568790 (Why is no real title available?)
- scientific article; zbMATH DE number 1775051 (Why is no real title available?)
- A note on a cycle partition problem
- Relationships between the length of a longest path and the relative length
- Long path lemma concerning connectivity and independence number
- Degree conditions and relative length of longest paths and cycles in graphs
- Edge-diameter of a graph and its longest cycles
- Long cycles in graphs without Hamiltonian paths
This page was built for publication: Relative length of longest paths and cycles in 3-connected graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2746207)
