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

Włodzimierz Ulatowski

Discussiones Mathematicae Graph Theory (2009)

  • Volume: 29, Issue: 3, page 615-627
  • ISSN: 2083-5892

Abstract

top
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.

How to cite

top

Włodzimierz Ulatowski. "Relations between the domination parameters and the chromatic index of a graph." Discussiones Mathematicae Graph Theory 29.3 (2009): 615-627. <http://eudml.org/doc/270801>.

@article{WłodzimierzUlatowski2009,
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.},
author = {Włodzimierz Ulatowski},
journal = {Discussiones Mathematicae Graph Theory},
keywords = {domination; domination parameters; chromatic index},
language = {eng},
number = {3},
pages = {615-627},
title = {Relations between the domination parameters and the chromatic index of a graph},
url = {http://eudml.org/doc/270801},
volume = {29},
year = {2009},
}

TY - JOUR
AU - Włodzimierz Ulatowski
TI - Relations between the domination parameters and the chromatic index of a graph
JO - Discussiones Mathematicae Graph Theory
PY - 2009
VL - 29
IS - 3
SP - 615
EP - 627
AB - 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.
LA - eng
KW - domination; domination parameters; chromatic index
UR - http://eudml.org/doc/270801
ER -

References

top
  1. [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. [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. [3] O. Favaron, Stability, domination and irredundance in a graph, J. Graph Theory 10 (1986) 429-438, doi: 10.1002/jgt.3190100402. Zbl0612.05056
  4. [4] T. Gallai, Über extreme Punkt-und Kantenmengen, Ann. Univ. Sci. Budapest. Eötvös Sect. Math. 2 (1959) 133-138. Zbl0094.36105
  5. [5] T.W. Haynes, S.T. Hedetniemi and P.J. Slater, Fundamentals of Domination in Graphs (Marcel Decker Inc., New York, 1998). Zbl0890.05002
  6. [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. Zbl46.1451.03
  7. [7] D. König, Graphs and matrices, Mat. Fiz. Lapok 38 (1931) 116-119 (in Hungarian). 
  8. [8] V.G. Vizing, On an estimate of the chromatic class of a p-graph, Metody Diskret. Analiz. 29 (1964) 25-30 (in Russian). 

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.