PL EN


Preferencje help
Widoczny [Schowaj] Abstrakt
Liczba wyników
2009 | 29 | 3 | 615-627
Tytuł artykułu

Relations between the domination parameters and the chromatic index of a graph

Treść / Zawartość
Warianty tytułu
Języki publikacji
EN
Abstrakty
EN
In this paper we show upper bounds for the sum and the product of the lower domination parameters and the chromatic index of a graph. We also present some families of graphs for which these upper bounds are achieved. Next, we give a lower bound for the sum of the upper domination parameters and the chromatic index. This lower bound is a function of the number of vertices of a graph and a new graph parameter which is defined here. In this case we also characterize graphs for which a respective equality holds.
Słowa kluczowe
Wydawca
Rocznik
Tom
29
Numer
3
Strony
615-627
Opis fizyczny
Daty
wydano
2009
otrzymano
2008-09-19
poprawiono
2008-10-23
zaakceptowano
2008-11-13
Twórcy
  • Faculty of Physics and Mathematics, Gdańsk University of Technology, Narutowicza 11/12, 80-952 Gdańsk, Poland
Bibliografia
  • [1] M. Chellalia and L. Volkmann, Relations between the lower domination parameters and the chromatic number of a graph, Discrete Math. 274 (2004) 1-8, doi: 10.1016/S0012-365X(03)00093-1.
  • [2] E.J. Cockayne, O. Favaron, C. Payan and A.G. Thomas, Contributions to the theory of domination, independence and irredundance in graphs, Discrete Math. 33 (1981) 249-258, doi: 10.1016/0012-365X(81)90268-5.
  • [3] O. Favaron, Stability, domination and irredundance in a graph, J. Graph Theory 10 (1986) 429-438, doi: 10.1002/jgt.3190100402.
  • [4] T. Gallai, Über extreme Punkt-und Kantenmengen, Ann. Univ. Sci. Budapest. Eötvös Sect. Math. 2 (1959) 133-138.
  • [5] T.W. Haynes, S.T. Hedetniemi and P.J. Slater, Fundamentals of Domination in Graphs (Marcel Decker Inc., New York, 1998).
  • [6] D. König, Graphok és alkalmazásuk a determinánsok és a halmazok elméletére, Math. Termész. Ért. 34 (1916) 104-119.
  • [7] D. König, Graphs and matrices, Mat. Fiz. Lapok 38 (1931) 116-119 (in Hungarian).
  • [8] V.G. Vizing, On an estimate of the chromatic class of a p-graph, Metody Diskret. Analiz. 29 (1964) 25-30 (in Russian).
Typ dokumentu
Bibliografia
Identyfikatory
Identyfikator YADDA
bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1468
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ć.