Triangles and neighbourhoods of independent sets in graphs

被引:3
作者
Robertshaw, AM [1 ]
Woodall, DR [1 ]
机构
[1] Univ Nottingham, Sch Math Sci, Nottingham NG7 2RD, England
关键词
binding number; neighbourhood condition; triangle-free graph; pancyclic graph;
D O I
10.1006/jctb.2000.1974
中图分类号
O1 [数学];
学科分类号
0701 ; 070101 ;
摘要
It is proved that a graph of order n contains a triangle if \N(X)\ > 1/3 (n + \X\) for every independent set X of vertices. This bound is sharp. (C) 2000 Academic Press.
引用
收藏
页码:122 / 129
页数:8
相关论文
共 8 条
[1]  
Anderson I., 1971, J. Combin. Theory. Ser. B, V10, P183, DOI [10.1016/0095-8956(71)90041-4, DOI 10.1016/0095-8956(71)90041-4]
[2]  
BRANDT S, 1994, THESIS FREIE U BERLI
[3]   A NOTE ON MAXIMAL TRIANGLE-FREE GRAPHS [J].
GODDARD, W ;
KLEITMAN, DJ .
JOURNAL OF GRAPH THEORY, 1993, 17 (05) :629-631
[4]  
Shi R., 1985, Acta Math. Appl. Sin. Engl. Ser., V2, P79
[5]  
Woodall D. R., 1973, Journal of Combinatorial Theory, Series B, V15, P225, DOI 10.1016/0095-8956(73)90038-5
[6]   SUFFICIENT CONDITION FOR HAMILTONIAN CIRCUITS [J].
WOODALL, DR .
JOURNAL OF COMBINATORIAL THEORY SERIES B, 1978, 25 (02) :184-186
[7]  
WOODALL DR, 1990, J LOND MATH SOC, V41, P385
[8]  
[No title captured]