✦ LIBER ✦

Class of graphs with restricted neighborhoods

✍ Scribed by Kim T. Rawlinson; R. C. Entringer

Publisher: John Wiley and Sons
Year: 1979
Tongue: English
Weight: 286 KB
Volume: 3
Category: Article
ISSN: 0364-9024
DOI: 10.1002/jgt.3190030308

No coin nor oath required. For personal study only.

✦ Synopsis

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. Finally, an application to communication systems is discussed.

📜 SIMILAR VOLUMES

Dense Graphs with Cycle Neighborhoods

✍ A. Seress; T. Szabo 📂 Article 📅 1995 🏛 Elsevier Science 🌐 English ⚖ 420 KB

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.

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.

Orderly algorithms for generating restri

Orderly algorithms for generating restricted classes of graphs

✍ Charles J. Colbourn; Ronald C. Read 📂 Article 📅 1979 🏛 John Wiley and Sons 🌐 English ⚖ 463 KB

## Abstract Orderly algorithms for the generation of exhaustive lists of nonisomorphic graphs are discussed. The existence of orderly methods to generate the graphs with a given subgraph and without a given subgraph is established. This method can be used to list all the nonisomorphic subgraphs of

Neighborhood conditions for graphs to be

Neighborhood conditions for graphs to be super restricted edge connected

✍ Shiying Wang; Jing Li; Lihong Wu; Shangwei Lin 📂 Article 📅 2009 🏛 John Wiley and Sons 🌐 English ⚖ 212 KB

## Abstract Restricted edge connectivity is a more refined network reliability index than edge connectivity. For a connected graph __G__ = (__V__, __E__), an edge set __S__ ⊆ __E__ is a restricted edge cut if __G__ − __S__ is disconnected and every component of __G__ − __S__ has at least two vertic

Maximal matchings in graphs with large n

Maximal matchings in graphs with large neighborhoods of independent vertices

✍ I. Rinsma; C. H. C. Little; D. R. Woodall 📂 Article 📅 1990 🏛 John Wiley and Sons 🌐 English ⚖ 174 KB

## Abstract We obtain lower bounds on the size of a maximum matching in a graph satisfying the condition |__N(X)__| ≥ __s__ for every independent set __X__ of __m__ vertices, thus generalizing results of Faudree, Gould, Jacobson, and Schelp for the case __m__ = 2.

Neighborhood hypergraphs of bipartite gr

Neighborhood hypergraphs of bipartite graphs

✍ Endre Boros; Vladimir Gurvich; Igor Zverovich 📂 Article 📅 2008 🏛 John Wiley and Sons 🌐 English ⚖ 252 KB

## Abstract Matrix symmetrization and several related problems have an extensive literature, with a recurring ambiguity regarding their complexity and relation to graph isomorphism. We present a short survey of these problems to clarify their status. In particular, we recall results from the litera