✦ LIBER ✦

An improvement of fraisse's sufficient condition for hamiltonian graphs

✍ Scribed by A. Ainouche

Publisher: John Wiley and Sons
Year: 1992
Tongue: English
Weight: 567 KB
Volume: 16
Category: Article
ISSN: 0364-9024
DOI: 10.1002/jgt.3190160602

No coin nor oath required. For personal study only.

✦ Synopsis

Abstract

Let G be a k‐connected graph of order n. For an independent set c, let d(S) be the number of vertices adjacent to at least one vertex of S and > let i(S) be the number of vertices adjacent to at least |S| vertices of S. We prove that if there exists some s, 1 ≤ s ≤ k, such that Σ~x__i__EX~ d(X{X~i~}) > s(n−1) – k[s/2] – i(X)[(s−1)/2] holds for every independetn set X ={x~0~, x~1~ ⃛x~s~} of s + 1 vertices, then G is hamiltonian. Several known results, including Fraisse's sufficient condition for hamiltonian graphs, are dervied as corollaries.

📜 SIMILAR VOLUMES

One sufficient condition for hamiltonian

One sufficient condition for hamiltonian graphs

✍ Guantao Chen 📂 Article 📅 1990 🏛 John Wiley and Sons 🌐 English ⚖ 220 KB 👁 1 views

## Abstract Let __G__ be a 2‐connected graph of order __n.__ We show that if for each pair of nonadjacent vertices __x__,__y__ ∈ __V(G)__, then __G__ is Hamiltonian.

A new sufficient condition for hamiltoni

A new sufficient condition for hamiltonian graphs

✍ Pierre Fraisse 📂 Article 📅 1986 🏛 John Wiley and Sons 🌐 English ⚖ 160 KB 👁 1 views

A sufficient condition for oriented grap

A sufficient condition for oriented graphs to be Hamiltonian

✍ Odile Favaron; Oscar Ordaz 📂 Article 📅 1986 🏛 Elsevier Science 🌐 English ⚖ 492 KB

A generalization of Bondy's and Fan's su

A generalization of Bondy's and Fan's sufficient conditions for Hamiltonian graphs

✍ X. Liu; B. Wei 📂 Article 📅 1997 🏛 Elsevier Science 🌐 English ⚖ 337 KB

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,

A necessary and sufficient condition for

A necessary and sufficient condition for the star decomposition of complete graphs

✍ Lin, Chiang; Shyu, Tay-Woei 📂 Article 📅 1996 🏛 John Wiley and Sons 🌐 English ⚖ 130 KB 👁 2 views

In this paper w e prove the following result. Let ml 2 m2 2 ... 2 ml be nonnegative integers. A necessary and sufficient condition for the complete graph K,, to be decomposed into stars S,,, , S