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

Lichiardopol, Nicolas
January 2013
Graphs & Combinatorics;Jan2013, Vol. 29 Issue 1, p99
Academic Journal
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.


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.


    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...


Read the Article


Sorry, but this item is not currently available from your library.

Try another library?
Sign out of this library

Other Topics