𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Neighborhood unions and regular factors

✍ Scribed by Thomas Niessen

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

No coin nor oath required. For personal study only.

✦ Synopsis

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

πŸ“œ SIMILAR VOLUMES

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

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

Extremal problems involving neighborhood
Extremal problems involving neighborhood unions
✍ Ralph J. Faudree; Ronald J. Gould; Michael S. Jacobson; Richard H. Schelp πŸ“‚ Article πŸ“… 1987 πŸ› John Wiley and Sons 🌐 English βš– 393 KB

We examine several extremal problems for graphs satisfying the property JN(x) u N(y)l ? s f o r every pair of nonadjacent vertices x , y E V ( G ) . In particular, values for s are found that ensure that the graph contains an s-matching, a 1-factor, a path of a specific length, or a cycle of a spec

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