✦ LIBER ✦

On the girth of infinite graphs

✍ Scribed by Norbert Seifter

Publisher: Elsevier Science
Year: 1993
Tongue: English
Weight: 599 KB
Volume: 118
Category: Article
ISSN: 0012-365X
DOI: 10.1016/0012-365x(93)90072-2

No coin nor oath required. For personal study only.

✦ Synopsis

Let X be an infinite k-valent graph with polynomial growth of degree d, i.e. there is an integer d and a constant c such that fx(n) 3, d> 1, 123, there exist k-valent connected graphs with polynomial growth of degree d and girth greater than 1. This means that in general the girth of graphs with polynomial growth mainly depends on the constant c in the upper bound of the growth function. We also prove lower bounds for the girth of Cayley graphs of certain classes of groups with polynomial growth.

📜 SIMILAR VOLUMES

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

Girth of sparse graphs

✍ Béla Bollobás; Endre Szemerédi 📂 Article 📅 2002 🏛 John Wiley and Sons 🌐 English ⚖ 73 KB

## Abstract For each fixed __k__ ≥ 0, we give an upper bound for the girth of a graph of order __n__ and size __n__ + __k__. This bound is likely to be essentially best possible as __n__ → ∞. © 2002 Wiley Periodicals, Inc. J Graph Theory 39: 194–200, 2002; DOI 10.1002/jgt.10023

On 3-Transitive Graphs of Girth 6

✍ K. Ching 📂 Article 📅 1994 🏛 Elsevier Science 🌐 English ⚖ 313 KB

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

On the smallest graphs of girth 10 and v

On the smallest graphs of girth 10 and valency 3

✍ P.K. Wong 📂 Article 📅 1983 🏛 Elsevier Science 🌐 English ⚖ 511 KB

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 p