𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Independence, odd girth, and average degree

✍ Scribed by Christian Löwenstein,; Anders Sune Pedersen,; Dieter Rautenbach;; Friedrich Regen

Publisher
John Wiley and Sons
Year
2010
Tongue
English
Weight
187 KB
Volume
67
Category
Article
ISSN
0364-9024

No coin nor oath required. For personal study only.

✦ Synopsis

We prove several tight lower bounds in terms of the order and the average degree for the independence number of graphs that are connected and/or satisfy some odd girth condition. Our main result is the extension of a lower bound for the independence number of triangle-free graphs of maximum degree at most three due to Heckman and Thomas [Discrete Math 233 (2001), 233-237] to arbitrary triangle-free graphs. For connected triangle-free graphs of order n and size m, our result implies the existence of an independent set of order at least (4n-m-1) / 7. ᭧ 2010 Wiley

📜 SIMILAR VOLUMES

Average degree and contractibility
Average degree and contractibility
✍ Matthias Kriesell 📂 Article 📅 2006 🏛 John Wiley and Sons 🌐 English ⚖ 197 KB

It is proved that for every number k there exists a number f (k) such that every finite k-connected graph of average degree exceeding f (k) contains an edge whose contraction yields again a k-connected graph. For the proof, tree orders on certain sets of smallest separating sets of the graph in ques

Graphs of Prescribed Girth and Bi-Degree
Graphs of Prescribed Girth and Bi-Degree
✍ Z. Furedi; F. Lazebnik; A. Seress; V.A. Ustimenko; A.J. Woldar 📂 Article 📅 1995 🏛 Elsevier Science 🌐 English ⚖ 426 KB
The average distance and the independenc
The average distance and the independence number
✍ F. R. K. Chung 📂 Article 📅 1988 🏛 John Wiley and Sons 🌐 English ⚖ 258 KB

We prove that in every connected graph the independence number is at least as large as the average distance between vertices. Theorem. For every connected graph G , we have a ( G ) 2 D ( G ) , with equality if and only if G is a complete graph.

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__

Edge-superconnectivity of semiregular ca
Edge-superconnectivity of semiregular cages with odd girth
✍ C. Balbuena; D. González-moreno; J. Salas 📂 Article 📅 2011 🏛 John Wiley and Sons 🌐 English ⚖ 153 KB

## Abstract A graph is said to be edge‐superconnected if each minimum edge‐cut consists of all the edges incident with some vertex of minimum degree. A graph __G__ is said to be a $\{d,d+1\}$‐semiregular graph if all its vertices have degree either __d__ or $d+1$. A smallest $\{d,d+1\}$‐semiregula