𝔖 Bobbio Scriptorium
✦   LIBER   ✦

On an adjacency property of graphs

✍ Scribed by Geoffrey Exoo

Publisher
John Wiley and Sons
Year
1981
Tongue
English
Weight
374 KB
Volume
5
Category
Article
ISSN
0364-9024

No coin nor oath required. For personal study only.

✦ Synopsis

Abstract

A graph G has property A(m, n, k) if for any sequence of m + n distinct points of G, there are at least k other points, each of which is adjacent to the first m points of the sequence but not adjacent to any of the latter n points. the minimum order among all graphs with property A(m, n, k) is denoted a(m, n, k). Bounds are given on the numbers a(m, n, k) and some exact results are indicated.

πŸ“œ SIMILAR VOLUMES

Graphs with the n-e.c. adjacency propert
Graphs with the n-e.c. adjacency property constructed from resolvable designs
✍ Catharine A. Baker; Anthony Bonato; Neil A. McKay; PaweΕ‚ PraΕ‚at πŸ“‚ Article πŸ“… 2009 πŸ› John Wiley and Sons 🌐 English βš– 144 KB

## Abstract Only recently have techniques been introduced that apply design theory to construct graphs with the __n__‐e.c. adjacency property. We supply a new random construction for generating infinite families of finite regular __n__‐e.c. graphs derived from certain resolvable Steiner 2‐designs.

Structural properties of plane graphs wi
Structural properties of plane graphs without adjacent triangles and an application to 3-colorings
✍ O. V. Borodin πŸ“‚ Article πŸ“… 1996 πŸ› John Wiley and Sons 🌐 English βš– 190 KB πŸ‘ 1 views

If in a plane graph with minimum degree 2 3 no t w o triangles have an edge in common, then: (1 there are two adjacent vertices with degree sum at most 9, and (2) there is a face of size between 4 and 9 or a 10-face incident with ten 3-vertices. It follows that every planar graph without cycles betw

On a property of cyclic covers of p-grap
On a property of cyclic covers of p-graphs
✍ Themistocles Politof πŸ“‚ Article πŸ“… 1988 πŸ› John Wiley and Sons 🌐 English βš– 177 KB

A directed graph G with a source s and a sink r is called a p-graph if every edge of G belongs to an elementary (s,r)-path of G. If C is a cycle of the p-graph G then a cyclic cover of C is a set of (s,r)-paths of G that contains all the edges of C. A cyclic cover Q is minimal if for

Acyclic 5-choosability of planar graphs
Acyclic 5-choosability of planar graphs without adjacent short cycles
✍ O. V. Borodin; A. O. Ivanova πŸ“‚ Article πŸ“… 2010 πŸ› John Wiley and Sons 🌐 English βš– 93 KB πŸ‘ 1 views

The conjecture on acyclic 5-choosability of planar graphs [Borodin et al., 2002] as yet has been verified only for several restricted classes of graphs. None of these classes allows 4-cycles. We prove that a planar graph is acyclically 5-choosable if it does not contain an i-cycle adjacent to a j-cy