✦ LIBER ✦

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

✍ Scribed by Guo-Hui Zhang

Publisher: John Wiley and Sons
Year: 1992
Tongue: English
Weight: 294 KB
Volume: 16
Category: Article
ISSN: 0364-9024
DOI: 10.1002/jgt.3190160303

No coin nor oath required. For personal study only.

✦ Synopsis

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 consequence, we prove a conjecture of Pullman and Wormald, which says that there exists a 2__j__‐regular graph of order n and odd girth g if and only if n ≥ gj, where g ≥ 5 is odd and j ≥ 2. A different variation of the problem is also discussed.

📜 SIMILAR VOLUMES

A lower bound on the order of regular gr

A lower bound on the order of regular graphs with given girth pair

✍ C. Balbuena; T. Jiang; Y. Lin; X. Marcote; M. Miller 📂 Article 📅 2007 🏛 John Wiley and Sons 🌐 English ⚖ 129 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 was proved by Harary and Kovács [Regular graphs with given girth pair, J Graph Theory 7 (1983), 209–218]. A (δ, __g__)‐cage is a small

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.

Graphs with given odd sets and the least

Graphs with given odd sets and the least number of vertices

✍ Louis Hakimi, S. 📂 Article 📅 1997 🏛 John Wiley and Sons 🌐 English ⚖ 64 KB 👁 2 views

This note presents a solution to the following problem posed by Chen, Schelp, and Soltés: find a simple graph with the least number of vertices for which only the degrees of the vertices that appear an odd number of times are given.

The maximum interval number of graphs wi

The maximum interval number of graphs with given genus

✍ Edward R. Scheinerman 📂 Article 📅 1987 🏛 John Wiley and Sons 🌐 English ⚖ 202 KB 👁 1 views

The interval number of a graph G, denoted i(G), is the least positive integer t such that G is the intersection graph of sets, each of which is the union of t compact real intervals. It is known that every planar graph has interval number at most 3 and that this result is best possible. We investiga

The minimum order of a cayley graph with

The minimum order of a cayley graph with given degree and diameter

✍ Yahya Ould Hamidoune 📂 Article 📅 1993 🏛 John Wiley and Sons 🌐 English ⚖ 346 KB

On arcs sharing the maximum number of po

On arcs sharing the maximum number of points with ovals in cyclic affine planes of odd order

✍ Gábor Korchmáros; Angelo Sonnino 📂 Article 📅 2009 🏛 John Wiley and Sons 🌐 English ⚖ 187 KB 👁 2 views

## Abstract The sporadic complete 12‐arc in PG(2, 13) contains eight points from a conic. In PG(2,__q__) with __q__>13 odd, all known complete __k__‐arcs sharing exactly ½(__q__+3) points with a conic 𝒞 have size at most ½(__q__+3)+2, with only two exceptions, both due to Pellegrino, which are comp