✦ LIBER ✦

On the smallest graphs of girth 10 and valency 3

✍ Scribed by P.K. Wong

Publisher: Elsevier Science
Year: 1983
Tongue: English
Weight: 511 KB
Volume: 43
Category: Article
ISSN: 0012-365X
DOI: 10.1016/0012-365x(83)90029-8

No coin nor oath required. For personal study only.

✦ Synopsis

Recently, O'Keefe and Wong have shown that a smallest graph of girth 10 and valency 3 (a (3,lO)-cage) must have 70 vertices. There are three non-isomorphic (3,10)-cages which have been known for some while. In this papel, it is shown that these are the only three possible (3,lO)-cages. Some of the proofs in this paper are derived with the aid of a computer.

📜 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.

On the uniqueness of the smallest graph

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

✍ Pak-Ken Wong 📂 Article 📅 1979 🏛 John Wiley and Sons 🌐 English ⚖ 96 KB 👁 1 views

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 sho

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

On the edge-reconstruction of 3-connecte

On the edge-reconstruction of 3-connected planar graphs with minimum valency 4

✍ Yue Zhao 📂 Article 📅 1995 🏛 Elsevier Science 🌐 English ⚖ 550 KB

It is shown that a 3-connected planar graph with minimum valency 4 is edge-reconstructible if no 4-vertex is adjacent to a 5-vertex. ## 1. Introduction In this paper, all graphs G=(V(G),E(G)) considered will be finite and simple. A connected graph G is said to have connectivity k o = ko(G) if the