✦ LIBER ✦

On the uniqueness of the smallest graph of girth 5 and valency 6

✍ Scribed by Pak-Ken Wong

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

No coin nor oath required. For personal study only.

✦ Synopsis

Let G be a regular graph of girth n( 2 5 ) and valency k ( r 3 ) , that has the least possible number f(k, n ) of vertices. Although the existence of such a graph was proved by Erdos and Sachs (see Ref. 6, p. 82), only a few cases have been solved (see Refs. 2-7). Recently, O'Keefe and Wong have shown that f(6,5) = 40 [2]. By using the technique in Ref. 2, it is shown now that this graph is unique. This is quite different from the case n = 5 and k = 5 , in which case the author knows three nonisomorphic graphs.

Let G be a smallest graph of girth 5 and valency 6. Since G has 40 vertices, for any fixed vertex C, there are three "opposite" vertices X , Y, and 2 having distance three from C [2]. Let K ( C ) = {X, Y, Z } be the set of vertices of distance three from A. Then K ( C ) is one of the following types:

(i) X , Y, and 2 are separated. (ii) X is adjacent to Y and 2 is not adjacent to X or Y. (iii) Y is adjacent to both X and Z.

📜 SIMILAR VOLUMES

The smallest graph of girth 6 and valenc

The smallest graph of girth 6 and valency 7

✍ M. O'Keefe; P. K. Wong 📂 Article 📅 1981 🏛 John Wiley and Sons 🌐 English ⚖ 258 KB

## Abstract With the aid of a computer. we give a regular graph of girth 6 and valency 7, which has 90 vertices and show that this is the unique smallest graph with these properties.

The maximum valency of regular graphs wi

The maximum valency of regular graphs with given order and odd girth

✍ Guo-Hui Zhang 📂 Article 📅 1992 🏛 John Wiley and Sons 🌐 English ⚖ 294 KB 👁 1 views

## Abstract The odd girth of a graph __G__ is the length of a shortest odd cycle in __G__. Let __d__(__n, g__) denote the largest __k__ such that there exists a __k__‐regular graph of order __n__ and odd girth __g__. It is shown that __d____n, g__ ≥ 2|__n__/__g__≥ if __n__ ≥ 2__g__. As a consequenc

On the girth of hamiltonian weakly pancy

On the girth of hamiltonian weakly pancyclic graphs

✍ Bollob�s, B�la; Thomason, Andrew 📂 Article 📅 1997 🏛 John Wiley and Sons 🌐 English ⚖ 130 KB 👁 2 views

A graph is called weakly pancyclic if it contains cycles of all lengths between its girth and circumference. In answer to a question of Erdős, we show that a Hamiltonian weakly-pancyclic graph of order n can have girth as large as about 2 n/ log n. In contrast to this, we show that the existence of

On the structure of extremal graphs of h

On the structure of extremal graphs of high girth

✍ Lazebnik, Felix; Wang, Ping 📂 Article 📅 1997 🏛 John Wiley and Sons 🌐 English ⚖ 117 KB 👁 2 views

Let n ≥ 3 be a positive integer, and let G be a simple graph of order v containing no cycles of length smaller than n + 1 and having the greatest possible number of edges (an extremal graph). Does G contain an n + 1-cycle? In this paper we establish some properties of extremal graphs and present sev

The uniqueness of the strongly regular g

The uniqueness of the strongly regular graph on 77 points

✍ A. E. Brouwer 📂 Article 📅 1983 🏛 John Wiley and Sons 🌐 English ⚖ 329 KB 👁 1 views

On the bipartite density of regular grap

On the bipartite density of regular graphs with large girth

✍ Ondřej Zýka 📂 Article 📅 1990 🏛 John Wiley and Sons 🌐 English ⚖ 154 KB 👁 1 views

## Abstract Let __B(G)__ be the edge set of a bipartite subgraph of a graph __G__ with the maximum number of edges. Let __b~k~__ = inf{|__B(G)__|/|__E(G)__‖__G__ is a cubic graph with girth at least __k__}. We will prove that lim~k → ∞~ __b~k~__ ≥ 6/7.