Removable matchings and hamiltonian cycles

For a graph G, let σ₂(G) denote the minimum degree sum of two nonadjacent vertices (when G is complete, we let σ₂(G)=∞). In this paper, we show the following two results: (i) Let G be a graph of order n≥4k+3 with σ₂(G)≥n and let F be a matching of size k in G such that G−F is 2-connected. Then G−F is hamiltonian or G≅K₂+(K₂∪K_n−4) or ; (ii) Let G be a graph of order n≥16k+1 with σ₂(G)≥n and let F be a set of k edges of G such that G−F is hamiltonian. Then G−F is either pancyclic or bipartite. Examples show that first result is the best possible.     

On the Set of Cycle Lengths in a Hamiltonian Graph with a Given Maximum Degree

Let n and be two integers such that 2n–1. We describe the set of cycle lengths occurring in any hamiltonian graph G of order n and maximum degree . We conclude that for the case this set contains all the integers belonging to the union [3,2–n+2][n–+2,+1], and for it contains every integer between 3 and +1. We also study the set of cycle lengths in a hamiltonian graph with two fixed vertices of large degree sum. Our main results imply that the stability s(P) for the property of being pancyclic satisfies      

The toughness of split graphs

In this short note we argue that the toughness of split graphs can be computed in polynomial time. This solves an open problem from a recent paper by Kratsch et al. (Discrete Math. 150 (1996) 231–245).     

Estimates on the size of the cycle spectra of Hamiltonian graphs

Given a graph $G$, let $S\left(G\right)$ be the set of all cycle lengths contained in $G$ and let $s\left(G\right)=\left|S\left(G\right)\right|$. Let $?\left(G\right)=\{3,\dots ,n\}?S\left(G\right)$ and let $d$ be the greatest common divisor of $n?2$ and all the positive pairwise differences of elements in $?\left(G\right)$. We prove that if a Hamiltonian graph $G$ of order $n$ has at least $\frac{n(p+2)}{4}+1$ edges, where $p$ is an integer such that $1\le p\le n?2$, then $s\left(G\right)\ge p$ or $G$ is exceptional, by which we mean $d?(??2)$ for some $?\in ?\left(G\right)$. We also discuss cases where $G$ is not exceptional, for example when $n?2$ is prime. Moreover, we show that $s\left(G\right)\ge min\{p,\frac{n?3}{2}\}$, which if $G$ is bipartite implies that $s\left(G\right)\ge min\{?\frac{4(m?1)}{n}?2?,\frac{n?2}{2}\}$, where $m$ is the number of edges in $G$.     

Dirac’s Type Sufficient Conditions for Hamiltonicity and Pancyclicity

Let G = (V, E) be a any simple, undirected graph on n ≥ 3 vertices with the degree sequence . We consider the class of graphs satisfying the condition where , is a positive integer. It is known that is hamiltonian if θ ≤ δ. In this paper,

Forbidden subgraphs for chorded pancyclicity

We call a graph $G$ pancyclic if it contains at least one cycle of every possible length $m$, for $3\le m\le \left|V\left(G\right)\right|$. In this paper, we define a new property called chorded pancyclicity. We explore forbidden subgraphs in claw-free graphs sufficient to imply that the graph contains at least one chorded cycle of every possible length $4,5,\dots ,\left|V\left(G\right)\right|$. In particular, certain paths and triangles with pendant paths are forbidden.     

New sufficient conditions for bipancyclicity of balanced bipartite digraphs

The main results provide sufficient conditions for balanced bipartite digraphs to be bipancyclic. These are analogues to well-known results on pancyclic digraphs.     

The clique-separator graph for chordal graphs

We present a new representation of a chordal graph called the clique-separator graph, whose nodes are the maximal cliques and minimal vertex separators of the graph. We present structural properties of the clique-separator graph and additional properties when the chordal graph is an interval graph, proper interval graph, or split graph. We also characterize proper interval graphs and split graphs in terms of the clique-separator graph. We present an algorithm that constructs the clique-separator graph of a chordal graph in O(n³) time and of an interval graph in O(n²) time, where n is the number of vertices in the graph.     

On k-ordered Hamiltonian graphs

A Hamiltonian graph G of order n is k-ordered, 2 ≤ k ≤ n, if for every sequence v₁, v₂, …, v_k of k distinct vertices of G, there exists a Hamiltonian cycle that encounters v₁, v₂, …, v_k in this order. Define f(k, n) as the smallest integer m for which any graph on n vertices with minimum degree at least m is a k-ordered Hamiltonian graph. In this article, answering a question of Ng and Schultz, we determine f(k, n) if n is sufficiently large in terms of k. Let g(k, n) = − 1. More precisely, we show that f(k, n) = g(k, n) if n ≥ 11k − 3. Furthermore, we show that f(k, n) ≥ g(k, n) for any n ≥ 2k. Finally we show that f(k, n) > g(k, n) if 2k ≤ n ≤ 3k − 6. © 1999 John Wiley & Sons, Inc. J Graph Theory 32: 17–25, 1999     

Cover-incomparability graphs and chordal graphs

The problem of recognizing cover-incomparability graphs (i.e. the graphs obtained from posets as the edge-union of their covering and incomparability graph) was shown to be NP-complete in general [J. Maxová, P. Pavlíkova, A. Turzík, On the complexity of cover-incomparability graphs of posets, Order 26 (2009) 229-236], while it is for instance clearly polynomial within trees. In this paper we concentrate on (classes of) chordal graphs, and show that any cover-incomparability graph that is a chordal graph is an interval graph. We characterize the posets whose cover-incomparability graph is a block graph, and a split graph, respectively, and also characterize the cover-incomparability graphs among block and split graphs, respectively. The latter characterizations yield linear time algorithms for the recognition of block and split graphs, respectively, that are cover-incomparability graphs.     

Long cycles and paths in distance graphs

For n∈N and D⊆N, the distance graph has vertex set {0,1,…,n−1} and edge set {ij∣0≤i,j≤n−1,|j−i|∈D}. Note that the important and very well-studied circulant graphs coincide with the regular distance graphs.A fundamental result concerning circulant graphs is that for these graphs, a simple greatest common divisor condition, their connectivity, and the existence of a Hamiltonian cycle are all equivalent. Our main result suitably extends this equivalence to distance graphs. We prove that for a finite set D of order at least 2, there is a constant c_D such that the greatest common divisor of the integers in D is 1 if and only if for every n, has a component of order at least n−c_D if and only if for every n≥c_D+3, has a cycle of order at least n−c_D. Furthermore, we discuss some consequences and variants of this result.     

图的能量与哈密尔顿性

设G是一个无向简单图, A(G)为$G$的邻接矩阵. 用G的补图的特征值给出G包含哈密尔顿路、哈密尔顿圈以及哈密尔顿连通图的充分条件; 其次用二部图的拟补图的特征值给出二部图包含哈密尔顿圈的充分条件. 这些结果改进了一些已知的结果.     

图的能量与哈密尔顿性

设G是一个无向简单图,A（G）为G的邻接矩阵．用G的补图的特征值给出G包含哈密尔顿路、哈密尔顿圈以及哈密尔顿连通图的充分条件：其次用二部图的拟补图的特征值给出二部图包含哈密尔顿圈的充分条件．这些结果改进了一些已知的结果．     

Hamiltonian connected hourglass free line graphs

Thomassen [Reflections on graph theory, J. Graph Theory 10 (1986) 309-324] conjectured that every 4-connected line graph is hamiltonian. An hourglass is a graph isomorphic to K₅-E(C₄), where C₄ is a cycle of length 4 in K₅. In Broersma et al. [On factors of 4-connected claw-free graphs, J. Graph Theory 37 (2001) 125-136], it is shown that every 4-connected line graph without an induced subgraph isomorphic to the hourglass is hamiltonian connected. In this note, we prove that every 3-connected, essentially 4-connected hourglass free line graph, is hamiltonian connected.     

The Hamiltonian index of graphs

The Hamiltonian index of a graph G is defined as

h(G)=min{m:L^m(G) is Hamiltonian}.     

平面对偶图哈密顿性的一个充分条件

提出了平面单图的对偶图是哈密顿图的一个充分条件     

Noncrossing Hamiltonian paths in geometric graphs

A geometric graph is a graph embedded in the plane in such a way that vertices correspond to points in general position and edges correspond to segments connecting the appropriate points. A noncrossing Hamiltonian path in a geometric graph is a Hamiltonian path which does not contain any intersecting pair of edges. In the paper, we study a problem asked by Micha Perles: determine the largest number h(n) such that when we remove any set of h(n) edges from any complete geometric graph on n vertices, the resulting graph still has a noncrossing Hamiltonian path. We prove that . We also establish several results related to special classes of geometric graphs. Let h₁(n) denote the largest number such that when we remove edges of an arbitrary complete subgraph of size at most h₁(n) from a complete geometric graph on n vertices the resulting graph still has a noncrossing Hamiltonian path. We prove that . Let h₂(n) denote the largest number such that when we remove an arbitrary star with at most h₂(n) edges from a complete geometric graph on n vertices the resulting graph still has a noncrossing Hamiltonian path. We show that h₂(n)=⌈n/2⌉-1. Further we prove that when we remove any matching from a complete geometric graph the resulting graph will have a noncrossing Hamiltonian path.     

On certain Hamiltonian cycles in planar graphs

The problem is considered under which conditions a 4-connected planar or projective planar graph has a Hamiltonian cycle containing certain prescribed edges and missing certain forbidden edges. The results are applied to obtain novel lower bounds on the number of distinct Hamiltonian cycles that must be present in a 5-connected graph that is embedded into the plane or into the projective plane with face-width at least five. Especially, we show that every 5-connected plane or projective plane triangulation on n vertices with no non-contractible cyles of length less than five contains at least distinct Hamiltonian cycles. © 1999 John Wiley & Sons, Inc. J Graph Theory 32: 81–96, 1999