Abstract | ||
---|---|---|
Letr be a positive integer. Considerr-regular graphs in which no induced subgraph on four vertices is an independent pair of edges. The numberv of vertices in such a graph does not exceed 5r/2; this proves a conjecture of Bermond. More generally, it is conjectured that ifv>2r, then the ratiov/r must be a rational number of the form 2+1/(2k). This is proved forv/r¿21/10. The extremal graphs and many other classes of these graphs are described and characterized. |
Year | DOI | Venue |
---|---|---|
1992 | 10.1007/BF02350634 | Graphs and Combinatorics |
DocType | Volume | Issue |
Journal | 8 | 2 |
ISSN | Citations | PageRank |
0911-0119 | 0 | 0.34 |
References | Authors | |
1 | 4 |
Name | Order | Citations | PageRank |
---|---|---|---|
Madeleine Paoli | 1 | 0 | 0.34 |
G. W. Peck | 2 | 27 | 4.13 |
William T. Trotter | 3 | 736 | 152.99 |
Douglas B. West | 4 | 1176 | 185.69 |