PDF

Discussiones Mathematicae Graph Theory 29(3) (2009) 615-627
DOI: https://doi.org/10.7151/dmgt.1468

RELATIONS BETWEEN THE DOMINATION PARAMETERS AND THE CHROMATIC INDEX OF A GRAPH

Włodzimierz Ulatowski

Faculty of Physics and Mathematics
Gdańsk University of Technology
Narutowicza 11/12, 80-952 Gdańsk, Poland
e-mail: twoulat@mif.pg.gda.pl

Abstract

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.

Keywords: domination, domination parameters, chromatic index.

2000 Mathematics Subject Classification: 05C69, 05C15.

References

[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).

Received 19 September 2008
Revised 23 October 2008
Accepted 13 November 2008