Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
4646892 | Discrete Mathematics | 2014 | 5 Pages |
Abstract
We prove that each {claw, K4}-free 4-regular graph, with just one class of exceptions, is a line graph. Applying this result, we present lower bounds on the independence numbers for {claw, K4}-free 4-regular graphs and for {claw, diamond}-free 4-regular graphs. Furthermore, we characterize the extremal graphs attaining the bounds.
Related Topics
Physical Sciences and Engineering
Mathematics
Discrete Mathematics and Combinatorics
Authors
Liying Kang, Dingguo Wang, Erfang Shan,