Cycles through subsets with large degree sums
Let \(G\) be a 2-connected graph on \(n\) vertices and let \(X\subseteq V(G)\). The paper deals with various conditions that ensure that \(G\) has a cycle covering all vertices of \(X\) (in which case \(G\) is \(X\)-cyclable). The conditions are expressed in terms of various parameters related to \(X\). Let \(\alpha(X)\) denote the independence number of the subgraph \(G[X]\) induced by \(X\). If \(G[X]\) is not complete, then \(\kappa(X)\) denotes the minimum cardinality of a set of vertices of \(G\) separating two vertices in \(X\). Denote by \(\delta(X)\) the minimum degree in \(G\) among the vertices in \(X\). Finally, \(\sigma_3(X)\) denotes the minimum value of the degree sum (in \(G\)) of any three pairwise nonadjacent vertices of \(X\). The main results of the paper are: (i) If \(\sigma_3(X)\geq n+\min\{\kappa(X), \delta(X)\}\), then \(G\) is \(X\)-cyclable. (ii) If \(\alpha(X)\leq\kappa(X)\), then \(G\) is \(X\)-cyclable.
- Cycles through prescribed vertices with large degree sum
- Cycles containing many vertices of subsets in graphs with large degree sums and neighborhood unions
- Cycles through vertices of large maximum degree
- Long cycles in graphs with large degree sums
- Cycles containing many vertices of large degree
- scientific article; zbMATH DE number 2094531
- Cycles containing many vertices of subsets in 1-tough graphs with large degree sums
- Long cycles, degree sums and neighborhood unions
- Degree Sums and Covering Cycles
- scientific article; zbMATH DE number 837058
- 2‐neighborhoods and hamiltonian conditions
- A generalization of a result of Häggkvist and Nicoghossian
- A method in graph theory
- A note on Hamiltonian circuits
- Cycles containing many vertices of large degree
- Cycles through specified vertices
- Graph theory
- scientific article; zbMATH DE number 3630799 (Why is no real title available?)
- Long cycles in graphs with large degree sums
- Long cycles, degree sums and neighborhood unions
- New sufficient conditions for cycles in graphs
- Some Theorems on Abstract Graphs
- A degree sum condition concerning the connectivity and the independence number of a graph
- Degree conditions and degree bounded trees
- A look at cycles containing specified elements of a graph
- On paths and cycles through specified vertices
- A Chvátal-Erdős condition for the existence of a cycle intersecting specified connected subgraphs
- An implicit degree sum condition for cycles through specified vertices
- Disjoint cycles in hypercubes with prescribed vertices in each cycle
- Relative length of longest paths and longest cycles in triangle-free graphs
- On cycles through specified vertices
- An implicit degree condition for cyclability in graphs
- Generalizations of Dirac's theorem in Hamiltonian graph theory -- a survey
- Degree sum conditions for the circumference of 4-connected graphs
- A \(k\)-tree containing specified vertices
- Set-orderedness as a generalization of \(k\)-orderedness and cyclability
- An Ore-type condition for 2-connected \([2,k]\)-factors in 2-connected graphs
- A generalization of Dirac's theorem on cycles through k vertices in k-connected graphs
- On a cycle through a specified linear forest of a graph
- A Chvátal--Erdős type condition for pancyclability
- Hamiltonicity of 4-connected graphs
- Forbidden subgraphs and the existence of paths and cycles passing through specified vertices
- On degree sum conditions for long cycles and cycles through specified vertices
This page was built for publication: Cycles through subsets with large degree sums
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1363686)
