✦ LIBER ✦

Neighborhood unions and a generalization of Dirac's theorem

✍ Scribed by R.J. Faudree; R.J. Gould; M.S. Jacobson; L.M. Lesniak

Publisher: Elsevier Science
Year: 1992
Tongue: English
Weight: 818 KB
Volume: 105
Category: Article
ISSN: 0012-365X
DOI: 10.1016/0012-365x(92)90132-y

No coin nor oath required. For personal study only.

✦ Synopsis

Dirac proved that if each vertex of a graph G of order n 23 has degree at least n/2, then the graph is Hamiltonian. This result will be generalized by showing that if the union of the neighborhoods of each pair of vertices of a 2connected graph G of sufficiently large order n has at least n/2 vertices, then G is Hamiltonian.

Other results that are based on neighborhood unions of pairs of vertices will be proved that give the existence of cycles, paths and matchings. Also, Hamiltonian results will be considered that use the union of neighborhoods of more than 2 vertices.

📜 SIMILAR VOLUMES

A generalization of Ore's Theorem involv

A generalization of Ore's Theorem involving neighborhood unions

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

Let G be a graph of order n. Settling conjectures of Chen and Jackson, we prove the following generalization of Ore's Theorem: If G is 2-connected and )N(u)u N(v)1 >:n for every pair of nonadjacent vertices a, u, then either G is hamiltonian, or G is the Petersen graph, or G belongs to one of three

A Generalization of a Theorem of Dirac

✍ Tristan Denley; Haidong Wu 📂 Article 📅 2001 🏛 Elsevier Science 🌐 English ⚖ 85 KB

In this paper, we give a generalization of a well-known result of Dirac that given any k vertices in a k-connected graph where k 2, there is a circuit containing all of them. We also generalize a result of Ha ggkvist and Thomassen. Our main result partially answers an open matroid question of Oxley.

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.

A generalization of Plantholt's theorem

✍ A. J. W. Hilton 📂 Article 📅 1986 🏛 John Wiley and Sons 🌐 English ⚖ 152 KB

A generalization of Turán's theorem

✍ Benny Sudakov; Tibor Szabó; H. Van Vu 📂 Article 📅 2005 🏛 John Wiley and Sons 🌐 English ⚖ 94 KB

## Abstract In this paper, we obtain an asymptotic generalization of Turán's theorem. We prove that if all the non‐trivial eigenvalues of a __d__‐regular graph __G__ on __n__ vertices are sufficiently small, then the largest __K__~__t__~‐free subgraph of __G__ contains approximately (__t__ − 2)/(__

A generalization of Robacker's theorem

✍ S.K. Tipnis; L.E. Trotter Jr. 📂 Article 📅 1989 🏛 Elsevier Science 🌐 English ⚖ 875 KB

Let 9 be the polyhedron given by 9 = {x E R": Nx=O, a~x~b}, where N is a totally unimodular matrix and a and 6 are any integral vectors. For x E R" let (x)' denote the vector obtained from x by changing all its negative components to zeros. Let x1, . . . , xp be the integral points in 9 and let 9+ b