A degree condition implying that every matching is contained in a hamiltonian cycle

We give a degree sum condition for three independent vertices under which every matching of a graph lies in a hamiltonian cycle. We also show that the bound for the degree sum is almost the best possible.     

A sufficient condition for a digraph to be kernel-perfect

Galeana-Sanchez and Neumann-Lara proved that a sufficient condition for a digraph to have a kernel (i.e., an absorbent independent set) is the following: (P) every odd directed cycle possesses at least two directed chords whose terminal endpoints are consecutive on the cycle. Here it is proved that (P) is satisfied by those digraphs having these two properties: (i) the reversal of every 3-circuit is present, and (ii) every odd directed cycle v₁… v_2n+1 V₁ has two chords of the form (v_i, v_i+2). This is stronger than a result of Galeana-Sanchez.     

A sufficient condition for a graph to be hamiltonian

Those non-hamiltonian graphsG withn vertices are characterized, which satisfy the Ore-type degree-conditiond(x)+d(y)n–2 for each pairx,yM of different nonadjacent vertices whereM consists of two vertices ofG. As an application a theorem on hamiltonian connectivity of graphs is given. Furthermore, a condition is presented which is sufficient for the existence of a covering of a graph by two disjoint paths with prescribed set of startpoints and prescribed set of endpoints. A class of graphs is described which have no covering of this kind.     

On distance local connectivity and the hamiltonian index

In this paper we introduce the concept of distance local connectivity of a graph. We give several sufficient conditions in terms of the independence number and of the vertex degrees, and we show a relation between the distance local connectivity and the hamiltonian index of a graph.     

A minimum degree condition forcing a digraph to be k-linked

Given a digraph D, let ${\delta }^0(D):=\min \{{\delta }^{+}(D),{\delta }^{-}(D)\}$ be the minimum semi-degree of D. In [D. Kühn and D. Osthus, Linkedness and ordered cycles in digraphs, submitted] we showed that every sufficiently large digraph D with ${\delta }^0(D)\ge n/2+\ell -1$ is ℓ-linked. The bound on the minimum semi-degree is best possible and confirms a conjecture of Manoussakis [Y. Manoussakis, k-linked and k-cyclic digraphs, J. Combinatorial Theory B 48 (1990) 216-226]. We [D. Kühn and D. Osthus, Linkedness and ordered cycles in digraphs, submitted] also determined the smallest minimum semi-degree which ensures that a sufficiently large digraph D is k-ordered, i.e. that for every sequence $s_1,\dots ,s_k$ of distinct vertices of D there is a directed cycle which encounters $s_1,\dots ,s_k$ in this order.     

A degree sum condition for graphs to be prism hamiltonian

Win, in 1975, and Jackson and Wormald, in 1990, found the best sufficient conditions on the degree sum of a graph to guarantee the properties of “having a k-tree” and “having a k-walk”, respectively. The property of “being prism hamiltonian” is an intermediate property between “having a 2-tree” and “having a 2-walk”. Thus, it is natural to ask what is the best degree sum condition for graphs to be prism hamiltonian. As an answer to this problem, in this paper, we show that a connected graph G of order n with σ₃(G)≥n is prism hamiltonian. The degree sum condition “σ₃(G)≥n” is best possible.     

Fan-type condition on disjoint cycles in a graph

Let $k$ be a positive integer. In this paper, we prove that for a graph $G$ with at least $4k$ vertices, if max$\{d\left(x\right),d\left(y\right)\}\ge 2k$ for any pair of nonadjacent vertices $\{x,y\}?V\left(G\right)$, then $G$ contains $k$ disjoint cycles. This generalizes the results given by Corrá di and Hajnal (1963), Enomoto (1998), and Wang (1999).     

Some approaches to a conjecture on short cycles in digraphs

We consider the following special case of a conjecture due to Caccetta and Häggkvist: Let D be a digraph on n vertices that all have in-degree and out-degree at least n/3. Then, D contains a directed cycle of length 2 or 3. We discuss several necessary conditions for possible counterexamples to this conjecture, in terms of cycle structure, diameter, maximum degree, clique number, toughness, and local structure. These conditions have not enabled us to prove or refute the conjecture, but they lead to proofs of special instances of the conjecture.     

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.     

Degree conditions on claws and modified claws for hamiltonicity of graphs

Ore presented a degree condition involving every pair of nonadjacent vertices for a graph to be hamiltonian. Fan [New sufficient conditions for cycles in graphs, J. Combin. Theory Ser. B 37 (1984) 221-227] showed that not all the pairs of nonadjacent vertices are required, but only the pairs of vertices at the distance two suffice. Bedrossian et al. [A generalization of Fan's condition for hamiltonicity, pancyclicity, and hamiltonian connectedness, Discrete Math. 115 (1993) 39-50] improved Fan's result involving the pairs of vertices contained in an induced claw or an induced modified claw. On the other hand, Matthews and Sumner [Longest paths and cycles in K_1,3-free graphs, J. Graph Theory 9 (1985) 269-277] gave a minimum degree condition for a claw-free graph to be hamiltonian. In this paper, we give a new degree condition in an induced claw or an induced modified claw ensuring the hamiltonicity of graphs which extends both results of Bederossian et al. and Matthews and Sumner.     

The number of reachable pairs in a digraph

For a digraph G, let R(G) (respectively, R^(k)(G)) be the number of ordered pairs (u,v) of vertices of G such that u≠v and v is reachable from u (respectively, reachable from u by a path of length ?k). In this paper, we study the range S_n of R(G) and the range of R^(k)(G) as G varies over all possible digraphs on n vertices. We give a sufficient condition and a necessary condition for an integer to belong to S_n. These determine the set S_n for all n?208. We also determine for k?4 and show that whenever n?k+(k+1)^0.57+2, for arbitrary k.     

Cyclic hamiltonian cycle systems of the complete graph minus a 1-factor

In this paper, we prove that cyclic hamiltonian cycle systems of the complete graph minus a 1-factor, K_n-I, exist if and only if and n≠2p^α with p an odd prime and α?1.     

A degree sum condition for long cycles passing through a linear forest

Let G be a (k+m)-connected graph and F be a linear forest in G such that |E(F)|=m and F has at most k-2 components of order 1, where k?2 and m?0. In this paper, we prove that if every independent set S of G with |S|=k+1 contains two vertices whose degree sum is at least d, then G has a cycle C of length at least min{d-m,|V(G)|} which contains all the vertices and edges of F.     

Arc-disjoint hamiltonian paths in non-round decomposable local tournaments

Thomassen proved that a strong tournament $T$ has a pair of arc-disjoint Hamiltonian paths with distinct initial vertices and distinct terminal vertices if and only if $T$ is not an almost transitive tournament of odd order, where an almost transitive tournament is obtained from a transitive tournament with acyclic ordering $u_1,u_2,\dots ,u_n$ (i.e., $u_i\to u_j$ for all $1\le i<j\le n$) by reversing the arc $u_1{u}_n$. A digraph $D$ is a local tournament if for every vertex $x$ of $D$, both the out-neighbors and the in-neighbors of $x$ induce tournaments. Bang-Jensen, Guo, Gutin and Volkmann split local tournaments into three subclasses: the round decomposable; the non-round decomposable which are not tournaments; the non-round decomposable which are tournaments. In 2015, we proved that every 2-strong round decomposable local tournament has a Hamiltonian path and a Hamiltonian cycle which are arc-disjoint if and only if it is not the second power of an even cycle. In this paper, we discuss the arc-disjoint Hamiltonian paths in non-round decomposable local tournaments, and prove that every 2-strong non-round decomposable local tournament contains a pair of arc-disjoint Hamiltonian paths with distinct initial vertices and distinct terminal vertices. This result combining with the one on round decomposable local tournaments extends the above-mentioned result of Thomassen to 2-strong local tournaments.     

Perfect matchings extend to two or more hamiltonian cycles in hypercubes

Kreweras conjectured that every perfect matching of a hypercube $Q_n$ for $n\ge 2$ can be extended to a hamiltonian cycle of $Q_n$. Fink confirmed the conjecture to be true. It is more general to ask whether every perfect matching of $Q_n$ for $n\ge 2$ can be extended to two or more hamiltonian cycles of $Q_n$. In this paper, we prove that every perfect matching of $Q_n$ for $n\ge 4$ can be extended to at least $2^{2^{n?4}}$ different hamiltonian cycles of $Q_n$.     

On a necessary but not sufficient condition for a γ-generating pair to be a nehari pair

This paper gives a negative answer to a question due to V.M. Adamjan, D.Z. Arov and M.G. Krein, and (what is the same) gives a counterexample to D.Sarason's conjecture^* concerning exposed points inH ¹.     

Sufficient conditions for a digraph to be Hamiltonian

We describe a new type of sufficient condition for a digraph to be Hamiltonian. Conditions of this type combine local structure of the digraph with conditions on the degrees of nonadjacent vertices. The main difference from earlier conditions is that we do not require a degree condition on all pairs of nonadjacent vertices. Our results generalize the classical conditions by Ghouila-Houri and Woodall. © 1996 John Wiley & Sons, Inc.