PL EN


Preferencje help
Widoczny [Schowaj] Abstrakt
Liczba wyników
2001 | 21 | 2 | 179-185
Tytuł artykułu

Vertex-disjoint stars in graphs

Autorzy
Treść / Zawartość
Warianty tytułu
Języki publikacji
EN
Abstrakty
EN
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 $K_{1,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.
Słowa kluczowe
Wydawca
Rocznik
Tom
21
Numer
2
Strony
179-185
Opis fizyczny
Daty
wydano
2001
otrzymano
2000-09-27
poprawiono
2001-03-19
Twórcy
  • Department of Mathematics, Keio University, Yokohama, 223-8522 Japan
Bibliografia
  • [1] N. Alon and E. Fischer, Refining the graph density condition for the existence of almost K-factors, Ars Combin. 52 (1999) 296-308.
  • [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.
  • [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.
  • [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.
  • [5] H. Enomoto, Graph decompositions without isolated vertices, J. Combin. Theory (B) 63 (1995) 111-124, doi: 10.1006/jctb.1995.1007.
  • [6] Y. Egawa and K. Ota, Vertex-disjoint claws in graphs, Discrete Math. 197/198 (1999) 225-246.
  • [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.
  • [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.
  • [9] J. Komlós, Tiling Turán theorems, Combinatorica 20 (2000) 203-218.
Typ dokumentu
Bibliografia
Identyfikatory
Identyfikator YADDA
bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1142
JavaScript jest wyłączony w Twojej przeglądarce internetowej. Włącz go, a następnie odśwież stronę, aby móc w pełni z niej korzystać.