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.     

A sufficient condition for a regular graph to be class 1

The core GΔ of a simple graph G is the subgraph induced by the vertices of maximum degree. It is well known that the Petersen graph is not 1-factorizable and has property that the core of the graph obtained from it by removing one vertex has maximum degree 2. In this paper, we prove the following result. Let G be a regular graph of even order with d(G) ≥ 3. Suppose that G contains a vertex ν such that the core of G\ν has maximum degree 2. If G is not the Petersen graph, then G is 1-factorizable. © 1993 John Wiley & Sons, Inc.     

A sufficient condition for a bipartite graph to have a k-factor

P. Katerinis obtained a sufficient condition for the existence of a 2-factor in a bipartite graph, in the spirit of Hall's theorem. We show a sufficient condition for the existence of a k-factor in a bipartite graph, as a generalization of Katerinis's theorem and Hall's theorem.     

A sufficient condition for a polynomial to be stable

A real polynomial is called Hurwitz (stable) if all its zeros have negative real parts. For a given n∈N we find the smallest possible constant dn>0 such that if the coefficients of F(z)=a₀+a₁z+?+anzn are positive and satisfy the inequalities akak+1>dnak−1ak+2 for k=1,2,…,n−2, then F(z) is Hurwitz.     

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 monoid to be a group

I give a sufficient condition for Monoid (G,?) to become a group when one of its elements is deleated. The entire thing has been put in the form of a theorem with its proof and it has been discussed broadly.     

A sufficient condition for a group automorphism to be algebraic

Translated from Algebra i Logika, Vol. 28, No. 1, pp. 117–119, January–February, 1989.     

A sufficient condition for graphs to be weaklyk-linked

We consider graphs, which are finite, undirected, without loops and in which multiple edges are possible. For each natural numberk letg(k) be the smallest natural numbern, so that the following holds:LetG be ann-edge-connected graph and lets ₁,...,s _k,t ₁,...,t _k be vertices ofG. Then for everyi {1,..., k} there existsa pathP _i froms _i tot _i, so thatP ₁,...,P _k are pairwise edge-disjoint. We prove      

A sufficient condition for a graph to contain three disjoint 1-factors

Ore derived a sufficient condition for a graph to contain a Hamiltonian cycle. We obtain a sufficient condition, similar to Ore's condition, for a graph to contain a Hamiltonian cycle and a 1-factor which are edge disjoint.     

A sufficient condition for a graph to have [a,b]-factors

We give a sufficient condition by using neighborhoods for a graph to have [a, b]-factors.Dedicated to Professor Tuyosi Oyama on his 60th Birthday     

Minimum degree condition for a graph to be knitted

For a positive integer $k$, a graph is $k$-knitted if for each subset $S$ of $k$ vertices, and every partition of $S$ into (disjoint) parts $S_1,\dots ,S_t$ for some $t\ge 1$, one can find disjoint connected subgraphs $C_1,\dots ,C_t$ such that $C_i$ contains $S_i$ for each $i\in \left[t\right]?\{1,2,\dots ,t\}$. In this article, we show that if the minimum degree of an $n$-vertex graph $G$ is at least $n∕2+k∕2?1$ when $n\ge 2k+3$, then $G$ is $k$-knitted. The minimum degree is sharp. As a corollary, we obtain that $k$-contraction-critical graphs are $?\frac{k}{8}?$-connected.     

An efficient condition for a graph to be Hamiltonian

Let G=(V,E) be a 2-connected simple graph and let d_G(u,v) denote the distance between two vertices u,v in G. In this paper, it is proved: if the inequality d_G(u)+d_G(v)?|V(G)|-1 holds for each pair of vertices u and v with d_G(u,v)=2, then G is Hamiltonian, unless G belongs to an exceptional class of graphs. The latter class is described in this paper. Our result implies the theorem of Ore [Note on Hamilton circuits, Amer. Math. Monthly 67 (1960) 55]. However, it is not included in the theorem of Fan [New sufficient conditions for cycles in graph, J. Combin. Theory Ser. B 37 (1984) 221-227].     

Necessary and sufficient conditions for a graph to be three-terminal series-parallel-cascade

A “three-terminal series-parallel-cascade graph” is defined as a three-terminal graph which is constructed by means of cascade connections in addition to series and parallel connections which were used in constructing a three-terminal series-parallel graph in our previous paper. Some properties of the graph are presented, and a theorem of the Kuratowski type is given stating that a three-terminal nonseparable graph is three-terminal series-parallel-cascade if and only if none of certain three graphs can be obtained from it by opening or shorting some of the edges. This theorem characterizes a three-terminal series-parallel-cascade graph completely, and clarifies its structual limitation.