Large regular graphs with no induced 2K
2 |
| |
| Authors: | Madeleine Paoli G W Peck W T Trotter Jr Douglas B West |
| |
| Institution: | (1) University of South Carolina, 29208 Columbia, SC, USA;(2) Massachusetts Institute of Technology, 02139 Cambridge, MA, USA;(3) Bellcore, 07960 Morristow, NJ, USA;(4) University of Illinois, 61801 Urbana, IL, USA |
| |
| 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.
Research supported in part by the National Science Foundation under ISP 80110451.
Research supported in part by the National Science Foundation under DMS-8401281.
Research supported in part by the National Science Foundation under DMS-8504322, and by the Office of Naval Research under
N00014-85K0570. |
| |
| Keywords: | |
| 本文献已被 SpringerLink 等数据库收录！ |
|
