Geodesic
Girth and Independence Ratio
Canadian mathematical bulletin, Tome 25 (1982) no. 2, pp. 179-186

Voir la notice de l'article provenant de la source Cambridge

DOI

Lower bounds are given for the independence ratio in graphs satisfying certain girth and maximum degree requirements. In particular, the independence ratio of a graph with maximum degree Δ and girth at least six is at least (2Δ − 1)/(Δ2 + 2Δ − 1). Sharper bounds are given for cubic graphs.
DOI : 10.4153/CMB-1982-024-9
Mots-clés : 05, Girth, independent sets, cubic 
Hopkins, Glenn; Staton, William. Girth and Independence Ratio. Canadian mathematical bulletin, Tome 25 (1982) no. 2, pp. 179-186. doi: 10.4153/CMB-1982-024-9
@article{10_4153_CMB_1982_024_9,
     author = {Hopkins, Glenn and Staton, William},
     title = {Girth and {Independence} {Ratio}},
     journal = {Canadian mathematical bulletin},
     pages = {179--186},
     year = {1982},
     volume = {25},
     number = {2},
     doi = {10.4153/CMB-1982-024-9},
     url = {http://geodesic.mathdoc.fr/articles/10.4153/CMB-1982-024-9/}
}
TY  - JOUR
AU  - Hopkins, Glenn
AU  - Staton, William
TI  - Girth and Independence Ratio
JO  - Canadian mathematical bulletin
PY  - 1982
SP  - 179
EP  - 186
VL  - 25
IS  - 2
UR  - http://geodesic.mathdoc.fr/articles/10.4153/CMB-1982-024-9/
DO  - 10.4153/CMB-1982-024-9
ID  - 10_4153_CMB_1982_024_9
ER  - 
%0 Journal Article
%A Hopkins, Glenn
%A Staton, William
%T Girth and Independence Ratio
%J Canadian mathematical bulletin
%D 1982
%P 179-186
%V 25
%N 2
%U http://geodesic.mathdoc.fr/articles/10.4153/CMB-1982-024-9/
%R 10.4153/CMB-1982-024-9
%F 10_4153_CMB_1982_024_9

Cité par Sources :