Hostname: page-component-cd9895bd7-8ctnn Total loading time: 0 Render date: 2024-12-26T13:24:46.398Z Has data issue: false hasContentIssue false
  • English
  • Français

Girth and Independence Ratio

Published online by Cambridge University Press:  20 November 2018

Glenn Hopkins  and
William Staton
Glenn Hopkins
Affiliation:
The University of Mississippi University, Mississippi, 38677
William Staton
Affiliation:
The University of Mississippi University, Mississippi, 38677
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the ‘Save PDF’ action button.

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.

Keywords

05Girthindependent setscubic
Type
Research Article
Information
Canadian Mathematical Bulletin , Volume 25 , Issue 2 , 01 June 1982 , pp. 179 - 186
Copyright
Copyright © Canadian Mathematical Society 1982

References

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. Brooks, R. L., On colouring the nodes of a network, Proc. Cambridge Philos. Soc. 37 (1941), 194-197.Google Scholar
3. Erdös, P., Graph theory and probability, Canadian J. Math. 11 (1959), 34-38.Google Scholar
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. 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. 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. Staton, W., Some Ramsey-type numbers and the independence ratio, Trans. Amer. Math. Soc. 256, (1979), 353-370.Google Scholar