Essential independent sets and long cycles
An essential independent set is an independent set which has a pair of vertices that are distance two apart. For \(S\subset V(G)\) with \(S\not= \emptyset\), let \(\Delta(S)=\max\{d_G(x)\mid x\in S\}\). The following theorem is proved. Let \(k\geq 2\) and let \(G\) be a \(k\)-connected graph. Suppose that \(\Delta(S)\geq d\) for every essential independent set \(S\) of order \(k\). Then \(G\) has a cycle of length at least \(\min\{|G|,2d\}\). This result is sharp in the following sense. Let \(p\geq d\geq k\) and let \(G=K_d+pK_1\), where the plus sign denotes join. Then it is easy to see that \(G\) is \(k\)-connected and \(\Delta(S)\geq d\) for every essential independent set \(S\) of order \(k\). On the other hand, the length of a longest cycle in \(G\) is \(2d\).
- Essential independent sets and Hamiltonian cycles
- Eternal Independent Sets in Graphs
- Independence equivalence classes of cycles
- The cyclic extensibility of essential components of the fixed point set
- Long cycles in triangle-free graphs with prescribed independence number and connectivity
- scientific article; zbMATH DE number 2016766
- Disjoint essential cycles
- On independent doubly chorded cycles
- Long cycles, degree sums and neighborhood unions
- scientific article; zbMATH DE number 2203978
This page was built for publication: Essential independent sets and long cycles
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1613438)
