✦ LIBER ✦

Smallest regular graphs with prescribed odd girth

✍ Scribed by Guo-Hui Zhang

Publisher: John Wiley and Sons
Year: 1991
Tongue: English
Weight: 484 KB
Volume: 15
Category: Article
ISSN: 0364-9024
DOI: 10.1002/jgt.3190150502

No coin nor oath required. For personal study only.

✦ Synopsis

Abstract

The odd girth of a graph G gives the length of a shortest odd cycle in G. Let f(k,g) denote the smallest n such that there exists a k‐regular graph of order n and odd girth g. The exact values of f(k,g) are determined if one of the following holds:

k > 2__g__ −5 and k is a prime number,

k > (2⌊(g + 1)/4⌋ −1)^2^, and

k is a perfect square.

📜 SIMILAR VOLUMES

Extremal Regular Graphs with Prescribed

Extremal Regular Graphs with Prescribed Odd Girth

✍ G.H. Zhang 📂 Article 📅 1994 🏛 Elsevier Science 🌐 English ⚖ 496 KB

The odd girth of a graph \(G\) gives the length of a shortest odd cycle in \(G\). Let \(f(k, g)\) denote the smallest \(n\) such that there exists a \(k\)-regular graph of order \(n\) and odd girth \(g\). It is known that \(f(k, g) \geqslant k g / 2\) and that \(f(k, g)=k g / 2\) if \(k\) is even. T

Regular graphs with given girth pair

✍ Frank Harary; Peter Kovács 📂 Article 📅 1983 🏛 John Wiley and Sons 🌐 English ⚖ 453 KB 👁 1 views

## Abstract The girth pair of a graph gives the length of a shortest odd and a shortest even cycle. The existence of regular graphs with given degree and girth pair is proved and simple bounds for their smallest order are developed. Several infinite classes of such graphs are constructed and it is

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

Regular graphs with prescribed chromatic

Regular graphs with prescribed chromatic number

✍ L. Caccetta; N. J. Pullman 📂 Article 📅 1990 🏛 John Wiley and Sons 🌐 English ⚖ 200 KB

## Abstract We determine the minimum number of edges in a regular connected graph on __n__ vertices, containing a complete subgraph of order __k__ ≤ __n__/2. This enables us to confirm and strengthen a conjecture of P. Erdös on the existence of regular graphs with prescribed chromatic number.

On smallest regular graphs with a given

On smallest regular graphs with a given isopart

✍ John Frederick Fink 📂 Article 📅 1985 🏛 John Wiley and Sons 🌐 English ⚖ 408 KB 👁 1 views

## Abstract For a nonempty graph, G, we define p(G) and r(G) to be respectively the minimum order and minimum degree of regularity among all connected regular graphs __H__ having a nontrivial decomposition into subgraphs isomorphic to G. By f(G), we denote the least integer t for which there is a c

(2 + ?)-Coloring of planar graphs with l

(2 + ?)-Coloring of planar graphs with large odd-girth

✍ Klostermeyer, William; Zhang, Cun Quan 📂 Article 📅 2000 🏛 John Wiley and Sons 🌐 English ⚖ 258 KB 👁 3 views

The odd-girth of a graph is the length of a shortest odd circuit. A conjecture by Pavol Hell about circular coloring is solved in this article by showing that there is a function f ( ) for each : 0 < < 1 such that, if the odd-girth of a planar graph G is at least f ( ), then G is (2 + )-colorable. N