Girth and Independence Ratio
- 1 June 1982
- journal article
- Published by Canadian Mathematical Society in Canadian Mathematical Bulletin
- Vol. 25 (2), 179-186
- https://doi.org/10.4153/cmb-1982-024-9
Abstract
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
This publication has 3 references indexed in Scilit:
- Some Ramsey-type numbers and the independence ratioTransactions of the American Mathematical Society, 1979
- Graph Theory and ProbabilityCanadian Journal of Mathematics, 1959
- On colouring the nodes of a networkMathematical Proceedings of the Cambridge Philosophical Society, 1941