𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Insertible vertices, neighborhood intersections, and hamiltonicity

✍ Scribed by A. Ainouche; I. Schiermeyer

Publisher
John Wiley and Sons
Year
1995
Tongue
English
Weight
475 KB
Volume
20
Category
Article
ISSN
0364-9024

No coin nor oath required. For personal study only.

✦ Synopsis

Abstract

Let G be a simple undirected graph of order n. For an independent set S βŠ‚ V(G) of k vertices, we define the k neighborhood intersections S~i~ = {v Ο΅ V(G)_S_|N(v) ∩ S| = i}, 1 ≦ i ≦ k, with s~i~ = |S~i~|. Using the concept of insertible vertices and the concept of neighborhood intersections, we prove the following theorem.

πŸ“œ SIMILAR VOLUMES

Hamiltonism, degree sum and neighborhood
Hamiltonism, degree sum and neighborhood intersections
✍ E. Flandrin; H.A. Jung; H. Li πŸ“‚ Article πŸ“… 1991 πŸ› Elsevier Science 🌐 English βš– 715 KB

We give a sufficient condition for hamiltonism of a 2-connected graph involving the degree sum and the neighborhood intersection of any three independent vertices.

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.

Hamiltonian graphs with neighborhood int
Hamiltonian graphs with neighborhood intersections
✍ G. Chen; R. H. Schelp πŸ“‚ Article πŸ“… 1994 πŸ› John Wiley and Sons 🌐 English βš– 577 KB

## Abstract In this paper, __k__ + 1 real numbers __c__~1~, __c__~2~, ⃛, __c__~__k__+1~ are found such that the following condition is sufficient for a __k__‐connected graph of order __n__ to be hamiltonian: for each independent vertex set of __k__ + 1 vertices in __G__. magnified image where S~i~

Neighborhood unions and hamilton cycles
Neighborhood unions and hamilton cycles
✍ Bill Jackson πŸ“‚ Article πŸ“… 1991 πŸ› John Wiley and Sons 🌐 English βš– 392 KB

## 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