Independence in graphs with maximum degree four |
| |
Authors: | Kathryn Fraughnaugh Jones |
| |
Institution: | University of Colorado, Denver, Colorado 80202 USA |
| |
Abstract: | Let be the class of triangle-free graphs with maximum degree four. A lower bound for the number of edges in a graph of is derived in terms of its order p and independence β. Also a characterization of certain minimum independence graphs in is provided. Let r(k) be the smallest integer such that every graph in with at least r(k) vertices has independence at least k. The values of r(k) for all k may be derived from our main theorem and obtained as the best possible lower bound for the independence ratio of graphs in . |
| |
Keywords: | |
本文献已被 ScienceDirect 等数据库收录! |