✦ LIBER ✦

The smallest graphs with certain adjacency properties

✍ Scribed by Geoffrey Exoo; Frank Harary

Publisher: Elsevier Science
Year: 1980
Tongue: English
Weight: 758 KB
Volume: 29
Category: Article
ISSN: 0012-365X
DOI: 10.1016/0012-365x(90)90283-n

No coin nor oath required. For personal study only.

✦ Synopsis

A graph is said to have property Pi,, if for every sequence of n + 1 points, there is another point adjacent only to the first point. It has previously been shown that almost all graphs have property Pi,,. It is easy to verify that for each n, there is a cube with this property. A more delicate question asks for the construction of the smallest graphs having property Pi,,. We fit+ that this problem is intimately related with the discovery of the highly symmetric graphs known as cages, and are thereby enabled to rpsolve this question for 1% sz ~6.

I, The notation

📜 SIMILAR VOLUMES

On the adjacency properties of paley gra

On the adjacency properties of paley graphs

✍ W. Ananchuen; L. Caccetta 📂 Article 📅 1993 🏛 John Wiley and Sons 🌐 English ⚖ 614 KB

In the application of graph theory to problems arising in network design, the requirements of the network can be expressed in terms of restrictions on the values of certain graph parameters such as connectivity, edge-connectivity, diameter, and independence number. In this paper, we focus on network

Characterization of a class of triangle-

Characterization of a class of triangle-free graphs with a certain adjacency property

✍ Brian Alspach; C. C. Chen; Katherine Heinrich 📂 Article 📅 1991 🏛 John Wiley and Sons 🌐 English ⚖ 597 KB

## Abstract Let __m__ and __n__ be nonnegative integers. Denote by __P__(__m,n__) the set of all triangle‐free graphs __G__ such that for any independent __m__‐subset __M__ and any __n__‐subset __N__ of __V__(__G__) with __M__ ∩ __N__ = Ø, there exists a unique vertex of __G__ that is adjacent to e

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.

Graphs with the smallest number of minim

Graphs with the smallest number of minimum cut sets

✍ Derek Smith 📂 Article 📅 1984 🏛 John Wiley and Sons 🌐 English ⚖ 630 KB

The minimal trivalent graphs with given

The minimal trivalent graphs with given smallest odd cycle

✍ Peter Kovács 📂 Article 📅 1985 🏛 Elsevier Science 🌐 English ⚖ 313 KB

A classification of certain graphs with

A classification of certain graphs with minimal imperfection properties

✍ S.H. Whitesides 📂 Article 📅 1982 🏛 Elsevier Science 🌐 English ⚖ 941 KB

IfI,: family of Bar, w) graphs ate of interest for several reasons. For example, any minimal fomenter-example to Rerge's Strong Perfect Graph Conjecture t %ngs to this family. This paper aciounts for ail (4.3) graphs. One of these is not obtainatde by existing techniques for geg~~rati~g (a + I, w) g