Sufficient condition for the existence of three disjoint theta graphs
1
조회
0
다운로드
0
인용
0
참고문헌
키워드
초록
A theta graph is the union of three internally disjoint paths that have the same two distinct end vertices. We show that every graph of order $n \geq 12$ and size at least $\lfloor\frac{11n-18}{2}\rfloor$ contains three disjoint theta graphs. As a corollary, every graph of order $n\geq 12$ and size at least $\lfloor\frac{11n-18}{2}\rfloor$ contains three disjoint cycles of even length.
Abstract
A theta graph is the union of three internally disjoint paths that have the same two distinct end vertices. We show that every graph of order $n \geq 12$ and size at least $\lfloor\frac{11n-18}{2}\rfloor$ contains three disjoint theta graphs. As a corollary, every graph of order $n\geq 12$ and size at least $\lfloor\frac{11n-18}{2}\rfloor$ contains three disjoint cycles of even length.
참고문헌 (10)
- J. A. Bondy, "Graph Theory" (2008), Springer
- S. Chiba, "On a sharp degree sum condition for disjoint chorded cycles in graphs", Graphs Combin, 26(2), pp.173~186 (2010)
- K. Corr´adi, "On the maximal number of independent circuits in a graph", Acta Math. Acad. Sci. Hungar, 14, pp.423~439 (1963)
- G. A. Dirac, "On the maximal number of independent triangles", Abh. Math. Sem. Univ. Hamburg, 26, pp.78~82 (1963)
- H. Enomoto, "On the existence of disjoint cycles in a graph", Combinatorica, 18(4), pp.487~492 (1998)
- D. Finkel, "On the number Of independent chorded cycle in a graph", Discrete Math, 308(22), pp.5265~5268 (2008)
- Y. Gao, "The extremal function for two disjoint cycles", Bull. Malays. Math. Sci. Soc (2014)[DOI]
- K. Kawarabayashi, "K−4 -factor in graphs", J. Graph Theory, 39(2), pp.111~128 (2002)
- L. P´osa, "On the circuits of finite graphs", Magyar Tud. Akad. Mat. Kut. Int. K¨ozl, 8, pp.355~361 (1963)
- H. Wang, "On the maximum number of independent cycles in a graph", Discrete Math, 205(1-3), pp.183~190 (1999)