𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Quasi-Hamiltonicity: A Series of Necessary Conditions for a Digraph to Be Hamiltonian

✍ Scribed by Gregory Gutin; Anders Yeo

Publisher
Elsevier Science
Year
2000
Tongue
English
Weight
129 KB
Volume
78
Category
Article
ISSN
0095-8956

No coin nor oath required. For personal study only.

✦ Synopsis

We introduce new necessary conditions, k-quasi-hamiltonicity (0 k n&1), for a digraph of order n to be hamiltonian. Every (k+1)-quasi-hamiltonian digraph is also k-quasi-hamiltonian; we construct digraphs which are k-quasi-hamiltonian, but not (k+1)-quasi-hamiltonian. We design an algorithm that checks k-quasihamiltonicity of a given digraph with n vertices and m arcs in time O(nm k ). We prove that (n&1)-quasi-hamiltonicity coincides with hamiltonicity and 1-quasihamiltonicity is equivalent to pseudo-hamiltonicity introduced (for undirected graphs) by L. Babel and G.

πŸ“œ SIMILAR VOLUMES

Sufficient conditions for a digraph to b
Sufficient conditions for a digraph to be Hamiltonian
✍ Bang-Jensen, JοΏ½rgen; Gutin, Gregory; Li, Hao πŸ“‚ Article πŸ“… 1996 πŸ› John Wiley and Sons 🌐 English βš– 412 KB πŸ‘ 2 views

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

A necessary and sufficient condition for
A necessary and sufficient condition for connected, locally k-connected k1,3-free graphs to be k-hamiltonian
✍ Zhou Huai-Lu πŸ“‚ Article πŸ“… 1989 πŸ› John Wiley and Sons 🌐 English βš– 272 KB πŸ‘ 2 views

We prove the following conjecture of Broersma and Veldman: A connected, locally k-connected K,,-free graph is k-hamiltonian if and only if it is (k + 2)-connected ( k L 1). We use [ 11 for basic terminology and notation, and consider simple graphs only. Let G be a graph. By V(G) and E(G) we denote,

Necessary and Sufficient Conditions for
Necessary and Sufficient Conditions for a Fourth Order Functional Differential Equation to be Oscillatory
✍ K. Gopalsamy; Lizhi Wen; Yong-Shao Chen; Xue-Zhong He πŸ“‚ Article πŸ“… 1993 πŸ› John Wiley and Sons 🌐 English βš– 416 KB

## Abstract Necessary and sufficient conditions for a fourth order functional differential equation of the form (1) [r(t)yβ€³(t)]β€³+f(t,y(h~1~(t)), y(h~2~(t)), …, y(h~n~(t)))=0 to be oscillatory are given when f is strongly superlinear or strongly sublinear.