On the structure of linear graphs |
| |
| Authors: | P Erdös |
| |
| Institution: | (1) University of Michigan, Ann Arbor, Michigan, U.S.A. |
| |
| Abstract: | Denote byG(n; m) a graph ofn vertices andm edges. We prove that everyG(n; n
2/4]+1) contains a circuit ofl edges for every 3 ≦l<c
2
n, also that everyG(n; n
2/4]+1) contains ak
e(u
n, un) withu
n=c
1 logn] (for the definition ofk
e(u
n, un) see the introduction). Finally fort>t
0 everyG(n; tn
3/2]) contains a circuit of 2l edges for 2≦l<c
3
t
2.
This work was done while the author received support from the National Science Foundation, N.S.F. G.88. |
| |
| Keywords: | |
| 本文献已被 SpringerLink 等数据库收录！ |
|
