Geodesic
The independence number of graphs with large odd girth
The electronic journal of combinatorics, Tome 1 (1994)
Cet article a éte moissonné depuis la source The Electronic Journal of Combinatorics website

Voir la notice de l'article

Let $G$ be an $r$-regular graph of order $n$ and independence number $\alpha(G)$. We show that if $G$ has odd girth $2k+3$ then $\alpha(G)\geq n^{1-1/k}r^{1/k}$. We also prove similar results for graphs which are not regular. Using these results we improve on the lower bound of Monien and Speckenmeyer, for the independence number of a graph of order $n$ and odd girth $2k+3$.
DOI : 10.37236/1189
Classification : 05C35
Mots-clés : regular graph, independence number, girth, lower bound 
@article{10_37236_1189,
     author = {Tristan Denley},
     title = {The independence number of graphs with large odd girth},
     journal = {The electronic journal of combinatorics},
     year = {1994},
     volume = {1},
     doi = {10.37236/1189},
     zbl = {0814.05045},
     url = {http://geodesic.mathdoc.fr/articles/10.37236/1189/}
}
TY  - JOUR
AU  - Tristan Denley
TI  - The independence number of graphs with large odd girth
JO  - The electronic journal of combinatorics
PY  - 1994
VL  - 1
UR  - http://geodesic.mathdoc.fr/articles/10.37236/1189/
DO  - 10.37236/1189
ID  - 10_37236_1189
ER  - 
%0 Journal Article
%A Tristan Denley
%T The independence number of graphs with large odd girth
%J The electronic journal of combinatorics
%D 1994
%V 1
%U http://geodesic.mathdoc.fr/articles/10.37236/1189/
%R 10.37236/1189
%F 10_37236_1189
Tristan Denley. The independence number of graphs with large odd girth. The electronic journal of combinatorics, Tome 1 (1994). doi: 10.37236/1189

Cité par Sources :