TITLE

# New Ore's Type Results on Hamiltonicity and Existence of Paths of Given Length in Graphs

AUTHOR(S)
Lichiardopol, Nicolas
PUB. DATE
January 2013
SOURCE
Graphs & Combinatorics;Jan2013, Vol. 29 Issue 1, p99
SOURCE TYPE
DOC. TYPE
Article
ABSTRACT
The well-known Ore's theorem (see Ore in Am Math Mon 65:55, ), states that a graph G of order n such that d( x) + d( y) â‰¥ n for every pair { x, y} of non-adjacent vertices of G is Hamiltonian. In this paper, we considerably improve this theorem by proving that in a graph G of order n and of minimum degree Î´ â‰¥ 2, if there exist at least n âˆ’ Î´ vertices x of G so that the number of the vertices y of G non-adjacent to x and satisfying d( x) + d( y) â‰¤ n âˆ’ 1 is at most Î´ âˆ’ 1, then G is Hamiltonian. We will see that there are graphs which violate the condition of the so called 'Extended Ore's theorem' (see Faudree et al. in Discrete Math 307:873-877, ) as well as the condition of ChvatÃ¡l's theorem (see ChvÃ¡tal in J Combin Theory Ser B 12:163-168, ) and the condition of the so called 'Extended Fan' theorem' (see Faudree et al. in Discrete Math 307:873-877, ), but satisfy the condition of our result, which then, only allows to conclude that such graphs are Hamiltonian. This will show the pertinence of our result. We give also a new result of the same type, ensuring the existence of a path of given length.
ACCESSION #
84364965

## Related Articles

• Improved Sufficient Conditions for the Existence of Anti-Directed Hamiltonian Cycles in Digraphs. Busch, Arthur; Jacobson, Michael; Morris, Timothy; Plantholt, Michael; Tipnis, Shailesh // Graphs & Combinatorics;May2013, Vol. 29 Issue 3, p359

Let D be a directed graph of order n. An anti-directed ( hamiltonian) cycle H in D is a (hamiltonian) cycle in the graph underlying D such that no pair of consecutive arcs in H form a directed path in D. In this paper we give sufficient conditions for the existence of anti-directed hamiltonian...

• An Implicit Degree Condition for Pancyclicity of Graphs. Li, Hao; Cai, Junqing; Ning, Wantao // Graphs & Combinatorics;Sep2013, Vol. 29 Issue 5, p1459

Zhu, Li and Deng introduced in 1989 the definition of implicit degree of a vertex v in a graph G, denoted by id( v), by using the degrees of the vertices in its neighborhood and the second neighborhood. And they obtained sufficient conditions with implicit degrees for a graph to be hamiltonian....

• Neighborhood Unions for the Existence of Disjoint Chorded Cycles in Graphs. Gao, Yunshu; Li, Guojun; Yan, Jin // Graphs & Combinatorics;Sep2013, Vol. 29 Issue 5, p1337

A chorded cycle is a cycle with at least one chord. We prove that if G is a simple graph with order n â‰¥ 4 k and $${|N_G(x)\cup N_G(y)|\geq 4k+1}$$ for each nonadjacent pair of vertices x and y, then G contains k vertex-disjoint chorded cycles. The degree condition is sharp in general.

• SOME REMARKS ON THE STRUCTURE OF STRONG k-TRANSITIVE DIGRAPHS. HERNÁNDEZ-CRUZ, CÉSAR; MONTELLANO-BALLESTEROS, JUAN JOSÉ // Discussiones Mathematicae: Graph Theory;2014, Vol. 34 Issue 4, p651

A digraph D is k-transitive if the existence of a directed path (v0, v1, ..., vk), of length k implies that (v0, vk) âˆˆ & A(D). Clearly, a 2-transitive digraph is a transitive digraph in the usual sense. Transitive digraphs have been characterized as compositions of complete digraphs on an...

• EQUIVALENT CONDITION AND TWO ALGORITHMS FOR HAMILTONIAN GRAPHS. Abdian, A. Z.; Hosseinhatami; Shahamiri, F. // International Journal on Applications of Graph Theory in Wireles;Sep2014, Vol. 6 Issue 3, p1

In this paper we present a necessary and sufficient condition for Hamiltonian graphs and also two algorithms and two examples in another part.

• The Cycle Spectrum of Claw-free Hamiltonian Graphs. Eckert, Jonas; Joos, Felix; Rautenbach, Dieter // Graphs & Combinatorics;Jan2016, Vol. 32 Issue 1, p93

If $$G$$ is a claw-free Hamiltonian graph of order $$n$$ and maximum degree $$\Delta$$ with $$\Delta \ge 24$$ , then $$G$$ has cycles of at least $$\min \left\{ n,\left\lceil \frac{3}{2}\Delta \right\rceil \right\} -2$$ many different lengths.

• Claw-Free and $$N(2,1,0)$$ -Free Graphs are Almost Net-Free. Furuya, Michitaka; Tsuchiya, Shoichi // Graphs & Combinatorics;Nov2015, Vol. 31 Issue 6, p2201

In this paper, we characterize connected $$\{K_{1,3},N(2,1,0)\}$$ -free but not $$N(1,1,1)$$ -free graphs. By combining our result and a theorem showed by Duffus et al. (every $$2$$ -connected $$\{K_{1,3},N(1,1,1)\}$$ -free graph is Hamiltonian), we give an alternative proof of Bedrossian's...

• Cycle Lengths of Hamiltonian $$P_\ell$$ -free Graphs. Meierling, Dirk; Rautenbach, Dieter // Graphs & Combinatorics;Nov2015, Vol. 31 Issue 6, p2335

For an integer $$\ell$$ at least three, we prove that every Hamiltonian $$P_\ell$$ -free graph $$G$$ on $$n>\ell$$ vertices has cycles of at least $$\frac{2}{\ell }n-1$$ different lengths. For small values of $$\ell$$ , we can improve the bound as follows. If $$4\le \ell \le 7$$ , then $$G$$...

• Uniform Coverings of 2-paths in the Complete Bipartite Directed Graph. Midori Kobayashi; Keiko Kotani; Nobuaki Mutoh; Gisaku Nakamura // AIP Conference Proceedings;2015, Vol. 1648 Issue 1, p1

Let G be a directed graph and H be a subgraph of G. A D(G, H, Î») design is a multiset D of subgraphs of G each isomorphic to H so that every directed 2-path in G lies in exactly Î» subgraphs in D. In this talk, we show that there exists a D(Kn,n*, C2n, 1) design for every n â‰¥ 2, where...

Share