𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Hamiltonian properties of graphs with large neighborhood unions

✍ Scribed by Douglas Bauer; Genghua Fan; Henk Jan Veldman

Publisher
Elsevier Science
Year
1991
Tongue
English
Weight
768 KB
Volume
96
Category
Article
ISSN
0012-365X

No coin nor oath required. For personal study only.

✦ Synopsis

Bauer, D., G. Fan and H.J. Veldman, Hamiltonian properties of graphs with large neighborhood unions, Discrete Mathematics 96 (1991) 33-49.

Let G be a graph of order n, a k =min{~ki=ld(vi): {V 1 ..... Vn} is an independent set of vertices in G}, NC=min{IN(u) 13N(v)l:uv~E(G)} and NC2=min{IN(u) t3

while Faudree et al. proved that G is hamiltonian if G is 2-connected and NC ~> -~(2n -1). It is shown that both results are generalized by a recent result ef Bauer et al. Various other existing results in hamiltonian graph theory involving degree-sums or cardinalities of neighborhood unions are also compdred in terms of generality. Furthermore, some new results are proved. In particular, it is shown that the bound ~(2n -1) on NC in the result of Faudree et al. can be lowered to ~(2n-3), which is best possible. Also, G is shown to have a cycle of length at least min{n, 2(NC2)} if G is 2-connected and 03 ~> n + 2. A Dx-cycle (Dx-path) of G is a cycle (path) C such that every component of G -V(C) has order smaller than 2. Sufficient conditions of Lindquester for the existence of Hamilton cycles and paths involving NC2 are extended to Dx-cycles and D~-paths.

πŸ“œ SIMILAR VOLUMES

Hamiltonian graphs involving neighborhoo
Hamiltonian graphs involving neighborhood unions
✍ Guantao Chen; Warren E. Shreve; Bing Wei πŸ“‚ Article πŸ“… 2006 πŸ› John Wiley and Sons 🌐 English βš– 214 KB

## Abstract Dirac proved that a graph __G__ is hamiltonian if the minimum degree $\delta(G) \geq n/2$, where __n__ is the order of __G__. Let __G__ be a graph and $A \subseteq V(G)$. The neighborhood of __A__ is $N(A)=\{ b: ab \in E(G)$ for some $a \in A\}$. For any positive integer __k__, we show

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,

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~

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.