𝔖 Bobbio Scriptorium
✦   LIBER   ✦

On the -optimality in graphs with odd girth and even girth

✍ Scribed by C. Balbuena; P. García-Vázquez; L.P. Montejano; J. Salas

Publisher
Elsevier Science
Year
2011
Tongue
English
Weight
222 KB
Volume
24
Category
Article
ISSN
0893-9659

No coin nor oath required. For personal study only.

✦ Synopsis

a b s t r a c t

For a connected graph G, the restricted edge-connectivity λ ′ (G) is defined as the minimum cardinality of an edge-cut over all edge-cuts S such that there are no isolated vertices in }, d(u) denoting the degree of a vertex u. The main result of this paper is that graphs with odd girth g and finite even girth h ≥ g + 3 of diameter at most h -4 are λ ′ -optimal. As a consequence polarity graphs are shown to be λ ′ -optimal.

📜 SIMILAR VOLUMES

Smallest regular graphs with prescribed
Smallest regular graphs with prescribed odd girth
✍ Guo-Hui Zhang 📂 Article 📅 1991 🏛 John Wiley and Sons 🌐 English ⚖ 484 KB 👁 1 views

## 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__

Sufficient conditions for λ′-optimality
Sufficient conditions for λ′-optimality in graphs with girth g
✍ C. Balbuena; P. García-Vázquez; X. Marcote 📂 Article 📅 2006 🏛 John Wiley and Sons 🌐 English ⚖ 146 KB

## Abstract For a connected graph the restricted edge‐connectivity λ′(__G__) is defined as the minimum cardinality of an edge‐cut over all edge‐cuts __S__ such that there are no isolated vertices in __G__–__S__. A graph __G__ is said to be λ′‐optimal if λ′(__G__) = ξ(__G__), where ξ(__G__) is the m

(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

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