𝔖 Bobbio Scriptorium
✦   LIBER   ✦

K-linked graphs with girth condition

✍ Scribed by Ken-ichi Kawarabayashi

Publisher
John Wiley and Sons
Year
2003
Tongue
English
Weight
55 KB
Volume
45
Category
Article
ISSN
0364-9024

No coin nor oath required. For personal study only.

✦ Synopsis

Abstract

Recently, Mader [7] proved that every 2__k__‐connected graph with girth g(G) sufficiently large is k‐linked. We show here that g(G ≥ 11 will do unless k = 4,5. If k = 4,5, then g(G) ≥ 19 will do. © 2003 Wiley Periodicals, Inc. J Graph Theory 45: 48–50, 2004

📜 SIMILAR VOLUMES

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

Graphs with valency k, edge connectivity
Graphs with valency k, edge connectivity k, chromatic index k + 1 and arbitrary girth
✍ V. Faber; J. Mycielski 📂 Article 📅 1973 🏛 Elsevier Science 🌐 English ⚖ 561 KB

We prove thbt if k>3 and there exists a regular graph with valency k, edge ity k and chromatic index k +l, then there exists such a graph of any girth g 14. connectiv-G=(X.E)iscalledagraph ifXisafinitesetandEc {{xr,.x2)lx1, x2 E X and x1 # x2 ). We call X the set of vertices and E the set of edges o

UniquelyH-colorable graphs with large gi
UniquelyH-colorable graphs with large girth
✍ Zhu, Xuding 📂 Article 📅 1996 🏛 John Wiley and Sons 🌐 English ⚖ 498 KB 👁 2 views

Suppose G and H are graphs. We say G is H-colorable if there is a homomorphism (edge-preserving vertex mapping) from G to H. We say a graph G is uniquely H-colorable if there is an onto homomorphism c from G to H, and any other homomorphism from G to H is the composition o o c of c with an automorph

Regular graphs with given girth pair
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