Total domination in categorical products of graphs

Douglas F. Rall

Discussiones Mathematicae Graph Theory (2005)

  • Volume: 25, Issue: 1-2, page 35-44
  • ISSN: 2083-5892

Abstract

top
Several of the best known problems and conjectures in graph theory arise in studying the behavior of a graphical invariant on a graph product. Examples of this are Vizing's conjecture, Hedetniemi's conjecture and the calculation of the Shannon capacity of graphs, where the invariants are the domination number, the chromatic number and the independence number on the Cartesian, categorical and strong product, respectively. In this paper we begin an investigation of the total domination number on the categorical product of graphs. In particular, we show that the total domination number of the categorical product of a nontrivial tree and any graph without isolated vertices is equal to the product of their total domination numbers. In the process we establish a packing and covering equality for trees analogous to the well-known result of Meir and Moon. Specifically, we prove equality between the total domination number and the open packing number of any tree of order at least two.

How to cite

top

Douglas F. Rall. "Total domination in categorical products of graphs." Discussiones Mathematicae Graph Theory 25.1-2 (2005): 35-44. <http://eudml.org/doc/270633>.

@article{DouglasF2005,
abstract = {Several of the best known problems and conjectures in graph theory arise in studying the behavior of a graphical invariant on a graph product. Examples of this are Vizing's conjecture, Hedetniemi's conjecture and the calculation of the Shannon capacity of graphs, where the invariants are the domination number, the chromatic number and the independence number on the Cartesian, categorical and strong product, respectively. In this paper we begin an investigation of the total domination number on the categorical product of graphs. In particular, we show that the total domination number of the categorical product of a nontrivial tree and any graph without isolated vertices is equal to the product of their total domination numbers. In the process we establish a packing and covering equality for trees analogous to the well-known result of Meir and Moon. Specifically, we prove equality between the total domination number and the open packing number of any tree of order at least two.},
author = {Douglas F. Rall},
journal = {Discussiones Mathematicae Graph Theory},
keywords = {categorical product; open packing; total domination; submultiplicative; supermultiplicative},
language = {eng},
number = {1-2},
pages = {35-44},
title = {Total domination in categorical products of graphs},
url = {http://eudml.org/doc/270633},
volume = {25},
year = {2005},
}

TY - JOUR
AU - Douglas F. Rall
TI - Total domination in categorical products of graphs
JO - Discussiones Mathematicae Graph Theory
PY - 2005
VL - 25
IS - 1-2
SP - 35
EP - 44
AB - Several of the best known problems and conjectures in graph theory arise in studying the behavior of a graphical invariant on a graph product. Examples of this are Vizing's conjecture, Hedetniemi's conjecture and the calculation of the Shannon capacity of graphs, where the invariants are the domination number, the chromatic number and the independence number on the Cartesian, categorical and strong product, respectively. In this paper we begin an investigation of the total domination number on the categorical product of graphs. In particular, we show that the total domination number of the categorical product of a nontrivial tree and any graph without isolated vertices is equal to the product of their total domination numbers. In the process we establish a packing and covering equality for trees analogous to the well-known result of Meir and Moon. Specifically, we prove equality between the total domination number and the open packing number of any tree of order at least two.
LA - eng
KW - categorical product; open packing; total domination; submultiplicative; supermultiplicative
UR - http://eudml.org/doc/270633
ER -

References

top
  1. [1] B.D. Acharya, Graphs whose r-neighbourhoods form conformal hypergraphs, Indian J. Pure Appl. Math. 16 (5) (1985) 461-464. Zbl0571.05037
  2. [2] B.L. Hartnell and D.F. Rall, Lower bounds for dominating Cartesian products, J. Combin. Math. Combin. Comput. 31 (1999) 219-226. Zbl0938.05048
  3. [3] T.W. Haynes, S.T. Hedetniemi and P.J. Slater (eds), Fundamentals of Domination in Graphs (Marcel Dekker, Inc. New York, 1998). 
  4. [4] T.W. Haynes, S.T. Hedetniemi and P.J. Slater (eds), Domination in Graphs: Advanced Topics (Marcel Dekker, Inc. New York, 1998). Zbl0883.00011
  5. [5] M.A. Henning, Packing in trees, Discrete Math. 186 (1998) 145-155, doi: 10.1016/S0012-365X(97)00228-8. 
  6. [6] M.A. Henning and D.F. Rall, On the total domination number of Cartesian products of graphs, Graphs and Combinatorics, to appear. Zbl1062.05109
  7. [7] M.A. Henning and P.J. Slater, Open packing in graphs, J. Combin. Math. Combin. Comput. 29 (1999) 3-16. Zbl0922.05040
  8. [8] W. Imrich and S. Klavžar, Product Graphs: Structure and Recognition (John Wiley & Sons, Inc. New York, 2000). 
  9. [9] L. Lovász, Normal hypergraphs and the perfect graph conjecture, Discrete Math. 2 (1972) 253-267, doi: 10.1016/0012-365X(72)90006-4. Zbl0239.05111
  10. [10] A. Meir and J.W. Moon, Relations between packing and covering numbers of a tree, Pacific J. Math. 61 (1975) 225-233. Zbl0315.05102
  11. [11] R.J. Nowakowski and D.F. Rall, Associative graph products and their independence, domination and coloring numbers, Discuss. Math. Graph Theory 16 (1996) 53-79, doi: 10.7151/dmgt.1023. Zbl0865.05071

NotesEmbed ?

top

You must be logged in to post comments.