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
Academic Journal
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

Read the Article

Courtesy of THE LIBRARY OF VIRGINIA

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

Try another library?
Sign out of this library

Other Topics