|
|
Disjoint K4- in claw-free graphs with minimum degree at least five |
Yunshu GAO1,*( ),Qingsong ZOU2 |
1. School of Mathematics and Computer Science, Ningxia University, Yinchuan 750021, China 2. Department of Mathematics, Xidian University, Xi’an 710071, China |
|
|
Abstract A graph is said to be claw-free if it does not contain an induced subgraph isomorphic to K1,3. Let K4- be the graph obtained by removing exactly one edge from K4 and let k be an integer with k≥2. We prove that if G is a claw-free graph of order at least 13k - 12 and with minimum degree at least five, then G contains k vertex-disjoint copies of K4-. The requirement of number five is necessary.
|
Keywords
Forbidden graph
vertex-disjoint subgraph
minimum degree
|
Corresponding Author(s):
Yunshu GAO
|
Issue Date: 30 December 2014
|
|
1 |
Bondy J A, Murty U S R. Graph Theory. 2nd ed. New York: Springer, 2008
https://doi.org/10.1007/978-1-84628-970-5
|
2 |
Fujita S. Disjoint stars and forbidden subgraphs. Hiroshima Math J, 2006, 36: 397-403
|
3 |
Fujita S. Vertex-disjoint copies of K1+ (K1∪K2 ) in claw-free graphs. Discrete Math, 2008, 308(6): 1628-1633
|
4 |
Kawarabayashi K. F-factor and vertex-disjoint F in a graph. Ars Combin, 2002, 62: 183-187
|
5 |
Kawarabayashi K. K4--factor in graphs. J Graph Theory, 2002, 39: 111-128
|
6 |
Wang H. Vertex-disjoint triangles in claw-free graphs with minimum degree at least three. Combinatorica, 1998, 18(3): 441-447
https://doi.org/10.1007/PL00009833
|
7 |
Zhang X, Li N, Wu J L, Yan J. Vertex-disjoint triangles in K1,t-free graphs with minimum degree at least t. Discrete Math, 2010, 310(19): 2499-2503
https://doi.org/10.1016/j.disc.2010.06.013
|
|
Viewed |
|
|
|
Full text
|
|
|
|
|
Abstract
|
|
|
|
|
Cited |
|
|
|
|
|
Shared |
|
|
|
|
|
Discussed |
|
|
|
|