✦ LIBER ✦

Dense Graphs with Cycle Neighborhoods

✍ Scribed by A. Seress; T. Szabo

Publisher: Elsevier Science
Year: 1995
Tongue: English
Weight: 420 KB
Volume: 63
Category: Article
ISSN: 0095-8956
DOI: 10.1006/jctb.1995.1020

No coin nor oath required. For personal study only.

✦ Synopsis

For all (\varepsilon>0), we construct graphs with (n) vertices and (>n^{2-n}) edges, for arbitrarily large (n), such that the neighborhood of each vertex is a cycle. This result is asymptotically best possible. "1995 Academic Press. Inc.

📜 SIMILAR VOLUMES

Coloring Graphs with Sparse Neighborhood

Coloring Graphs with Sparse Neighborhoods

✍ Noga Alon; Michael Krivelevich; Benny Sudakov 📂 Article 📅 1999 🏛 Elsevier Science 🌐 English ⚖ 118 KB

It is shown that the chromatic number of any graph with maximum degree d in which the number of edges in the induced subgraph on the set of all neighbors of any vertex does not exceed d 2 Âf is at most O(dÂlog f ). This is tight (up to a constant factor) for all admissible values of d and f.

Class of graphs with restricted neighbor

Class of graphs with restricted neighborhoods

✍ Kim T. Rawlinson; R. C. Entringer 📂 Article 📅 1979 🏛 John Wiley and Sons 🌐 English ⚖ 286 KB

## Abstract A description is obtained for connected graphs in which a point __u__ is adjacent of __v__ only if __u__ is adjacent to all points whose degree is greater than that of __v__. The minimum number of lines in such a grpah with all points having degree at least __d__ is also determined. Fin

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.

Neighborhood unions and the cycle cover

Neighborhood unions and the cycle cover number of a graph

✍ Guantao Chen; Ronald J. Gould; Michael S. Jacobson; Richard H. Schelp 📂 Article 📅 1994 🏛 John Wiley and Sons 🌐 English ⚖ 413 KB

## Abstract For several years, the study of neighborhood unions of graphs has given rise to important structural consequences of graphs. In particular, neighborhood conditions that give rise to hamiltonian cycles have been considered in depth. In this paper we generalize these approaches to give a

Dense graphs with small clique number

✍ Wayne Goddard; Jeremy Lyle 📂 Article 📅 2010 🏛 John Wiley and Sons 🌐 English ⚖ 121 KB