Vertex-disjoint stars in graphs
Katsuhiro Ota
Discussiones Mathematicae Graph Theory, Tome 21 (2001), p. 179-185 / Harvested from The Polish Digital Mathematics Library
Access to full text
Full (PDF)

In this paper, we give a sufficient condition for a graph to contain vertex-disjoint stars of a given size. It is proved that if the minimum degree of the graph is at least k+t-1 and the order is at least (t+1)k + O(t²), then the graph contains k vertex-disjoint copies of a star K1,t. The condition on the minimum degree is sharp, and there is an example showing that the term O(t²) for the number of uncovered vertices is necessary in a sense.

Publié le : 2001-01-01
EUDML-ID : urn:eudml:doc:270550 
@article{bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1142,
     author = {Katsuhiro Ota},
     title = {Vertex-disjoint stars in graphs},
     journal = {Discussiones Mathematicae Graph Theory},
     volume = {21},
     year = {2001},
     pages = {179-185},
     zbl = {1002.05039},
     language = {en},
     url = {http://dml.mathdoc.fr/item/bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1142}
}

Katsuhiro Ota. Vertex-disjoint stars in graphs. Discussiones Mathematicae Graph Theory, Tome 21 (2001) pp. 179-185. http://gdmltest.u-ga.fr/item/bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1142/

[000] [1] N. Alon and E. Fischer, Refining the graph density condition for the existence of almost K-factors, Ars Combin. 52 (1999) 296-308. | Zbl 0977.05103

[001] [2] N. Alon and R. Yuster, H-Factors in dense graphs, J. Combin. Theory (B) 66 (1996) 269-282, doi: 10.1006/jctb.1996.0020. | Zbl 0855.05085

[002] [3] K. Corrádi and A. Hajnal, On the maximal number of independent circuits in a graph, Acta Math. Acad. Sci. Hunger. 14 (1963) 423-443, doi: 10.1007/BF01895727. | Zbl 0118.19001

[003] [4] G.A. Dirac, On the maximal number of independent triangle in graphs, Abh. Sem. Univ. Hamburg 26 (1963) 78-82, doi: 10.1007/BF02992869. | Zbl 0111.35901

[004] [5] H. Enomoto, Graph decompositions without isolated vertices, J. Combin. Theory (B) 63 (1995) 111-124, doi: 10.1006/jctb.1995.1007. | Zbl 0834.05046

[005] [6] Y. Egawa and K. Ota, Vertex-disjoint claws in graphs, Discrete Math. 197/198 (1999) 225-246.

[006] [7] H. Enomoto, A. Kaneko and Zs. Tuza, P₃-factors and covering cycles in graphs of minimum degree n/3, Colloq. Math. Soc. János Bolyai 52 (1987) 213-220.

[007] [8] A. Hajnal and E. Szemerédi, Proof of a conjecture of P. Erdős, Colloq. Math. Soc. János Bolyai 4 (1970) 601-623. | Zbl 0217.02601

[008] [9] J. Komlós, Tiling Turán theorems, Combinatorica 20 (2000) 203-218. | Zbl 0949.05063