Name
Title | ||
|---|---|---|
A generalization of Dirac's theorem on cycles through k vertices in k-connected graphs |
Abstract | ||
|---|---|---|
Let X be a subset of the vertex set of a graph G. We denote by @k(X) the smallest number of vertices separating two vertices of X if X does not induce a complete subgraph of G, otherwise we put @k(X)=|X|-1 if |X|>=2 and @k(X)=1 if |X|=1. We prove that if @k(X)>=2 then every set of at most @k(X) vertices of X is contained in a cycle of G. Thus, we generalize a similar result of Dirac. Applying this theorem we improve our previous result involving an Ore-type condition and give another proof of a slightly improved version of a theorem of Broersma et al. |
Year | DOI | Venue |
|---|---|---|
2007 | 10.1016/j.disc.2005.11.052 | Discrete Mathematics |
Keywords | Field | DocType |
05c38,hamiltonian graphs,05c45,cyclability,cycles,graphs,connected graph,hamiltonian graph | Discrete mathematics,Graph,Combinatorics,Vertex (geometry),Hamiltonian path,Vertex (graph theory),Dirac (video compression format),Connectivity,Mathematics | Journal |
Volume | Issue | ISSN |
307 | 7-8 | Discrete Mathematics |
Citations | PageRank | References |
4 | 0.61 | 11 |
Authors | ||
4 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Evelyne Flandrin | 1 | 219 | 25.13 |
| Hao Li | 2 | 4 | 0.61 |
| Antoni Marczyk | 3 | 66 | 10.91 |
| Mariusz Woźniak | 4 | 204 | 34.54 |