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

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

[1] 1. Albertson, M., Bollobas, B. and Tucker, S., The independence ratio and maximum degree of a graph, Proc. 7th S-E Conf. Combinatorics, Graph Theory, and Computing, LSU, (1976), 43-50. Google Scholar

[2] 2. Brooks, R. L., On colouring the nodes of a network, Proc. Cambridge Philos. Soc. 37 (1941), 194-197. Google Scholar

[3] 3. Erdös, P., Graph theory and probability, Canadian J. Math. 11 (1959), 34-38. Google Scholar

[4] 4. Fajtlowicz, S., The independence ratio for cubic graphs, Proc. 8th S-E Conf. Combinatorics, Graph Theory, and Computing, LSU, (1977), 273-277. Google Scholar

[5] 5. Fajtlowicz, S., On the size of independent sets in graphs, Proc. 9th S-E Conf. Combinatorics, Graph Theory, and Computing, Florida Atlantic University, (1978), 269-274. Google Scholar

[6] 6. Staton, W., Independence in graphs with maximum degree three, Proc. 8th S-E Conf. Combinatorics, Graph Theory, and Computing, LSU, (1977), 615-617. Google Scholar

[7] 7. Staton, W., Some Ramsey-type numbers and the independence ratio, Trans. Amer. Math. Soc. 256, (1979), 353-370. Google Scholar

Cité par Sources :