𝔖 Bobbio Scriptorium
✦   LIBER   ✦

The minimal trivalent graphs with given smallest odd cycle

✍ Scribed by Peter Kovács

Publisher
Elsevier Science
Year
1985
Tongue
English
Weight
313 KB
Volume
54
Category
Article
ISSN
0012-365X

No coin nor oath required. For personal study only.

📜 SIMILAR VOLUMES

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

The longest cycle of a graph with a larg
The longest cycle of a graph with a large minimal degree
✍ Noga Alon 📂 Article 📅 1986 🏛 John Wiley and Sons 🌐 English ⚖ 214 KB 👁 1 views

We show that every graph G on n vertices with minimal degree at least n / k contains a cycle of length at least [ n / ( k -111. This verifies a conjecture of Katchalski. When k = 2 our result reduces t o the classical theorem of Dirac that asserts that if all degrees are at least i n then G is Hamil