𝔖 Bobbio Scriptorium
✦   LIBER   ✦

A generalization of Ore's Theorem involving neighborhood unions

✍ Scribed by H.J. Broersma; J. van den Heuvel; H.J. Veldman

Publisher
Elsevier Science
Year
1993
Tongue
English
Weight
656 KB
Volume
122
Category
Article
ISSN
0012-365X

No coin nor oath required. For personal study only.

✦ Synopsis

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 families of exceptional graphs of connectivity 2.

📜 SIMILAR VOLUMES

Neighborhood unions and a generalization
Neighborhood unions and a generalization of Dirac's theorem
✍ R.J. Faudree; R.J. Gould; M.S. Jacobson; L.M. Lesniak 📂 Article 📅 1992 🏛 Elsevier Science 🌐 English ⚖ 818 KB

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 vertic

A generalization of Turán's theorem
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
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

A generalization of carathéodory's theor
A generalization of carathéodory's theorem
✍ Imre Bárány 📂 Article 📅 1982 🏛 Elsevier Science 🌐 English ⚖ 812 KB

The following theorem is lproved. If the sets VI, . . . , Vn+, CR" and a E fly:: conv Vi, then there exist elements ui E Vi (i = 1, . . . , n + 1) such that a E conv{o,, . . . , un+J. Thii is a generalization of Carathtidory's theorem. By applying this and similar results some open questions are ans