✦ LIBER ✦

Neighborhood unions and hamilton cycles

✍ Scribed by Bill Jackson

Publisher: John Wiley and Sons
Year: 1991
Tongue: English
Weight: 392 KB
Volume: 15
Category: Article
ISSN: 0364-9024
DOI: 10.1002/jgt.3190150409

No coin nor oath required. For personal study only.

✦ Synopsis

Abstract

Let G be a graph on n vertices and N~2~(G) denote the minimum size of N(u) ∪ N(v) taken over all pairs of independent vertices u, v of G. We show that if G is 3‐connected and N~2~(G) ⩾ ½(n + 1), then G has a Hamilton cycle. We show further that if G is 2‐connected and N~2~(G) ⩾ ½(n + 3), then either G has a Hamilton cycle or else G belongs to one of three families of exceptional graphs.

📜 SIMILAR VOLUMES

Long cycles, degree sums and neighborhoo

Long cycles, degree sums and neighborhood unions

✍ H.J. Broersma; J.van den Heuvel; H.J. Veldman 📂 Article 📅 1993 🏛 Elsevier Science 🌐 English ⚖ 747 KB

Neighborhood unions and hamiltonicity of

Neighborhood unions and hamiltonicity of graphs

✍ Ruqun Shen; Feng Tian 📂 Article 📅 1995 🏛 Elsevier Science 🌐 English ⚖ 530 KB

Let G be a graph of order n. In this paper, we prove that if G is a 2-connected graph of order n such that for all u, ve V(G), 2 where dist(u,v) is the distance between u and v in G, then either G is hamiltonian, or G is a spanning subgraph of a graph in one of three families of exceptional graphs.

Long dominating cycles and paths in grap

Long dominating cycles and paths in graphs with large neighborhood unions

✍ H. J. Broersma; H. J. Veldman 📂 Article 📅 1991 🏛 John Wiley and Sons 🌐 English ⚖ 413 KB 👁 1 views

## Abstract Let __G__ be a graph of order __n__ and define __NC(G)__ = min{|__N__(__u__) ∪ __N__(__v__)| |__uv__ ∉ __E__(__G__)}. A cycle __C__ of __G__ is called a __dominating cycle__ or __D__‐__cycle__ if __V__(__G__) ‐ __V__(__C__) is an independent set. A __D__‐__path__ is defined analogously.

Long cycles in graphs with large degree

Long cycles in graphs with large degree sums and neighborhood unions

✍ Van den Heuvel, J. 📂 Article 📅 1996 🏛 John Wiley and Sons 🌐 English ⚖ 801 KB

We present and prove several results concerning the length of longest cycles in 2connected or I-tough graphs with large degree sums. These results improve many known results on long cycles in these graphs. We also consider the sharpness of the results and discuss some possible strengthenings.

Neighborhood unions and Hamiltonian prop

Neighborhood unions and Hamiltonian properties

✍ Min Song Zeng; Zhang Ke Min 📂 Article 📅 1994 🏛 Elsevier Science 🌐 English ⚖ 380 KB

Let G be a simple graph of order n with connectivity k 3 2, independence number cc We prove that if for each independent set S of cardinality k+ 1, one of the following condition holds: (1) there exist u # v in S such that d(u) +d(v) > n or ) N(u)nN(v) I> cr; (2) for any distinct pair u and u in S,

Neighborhood unions and regular factors

✍ Thomas Niessen 📂 Article 📅 1995 🏛 John Wiley and Sons 🌐 English ⚖ 737 KB

We examine bounds on the size of the neighborhood union for two (independent) vertices of a graph that imply the existence of regular factors.