zbMATH — the first resource for mathematics

Paired-domination of Cartesian products of graphs and rainbow domination. (English) Zbl 1200.05154
Raspaud, André (ed.) et al., 7th international colloquium on graph theory, Hyeres, France, September 12–16, 2005. Amsterdam: Elsevier. Electronic Notes in Discrete Mathematics 22, 233-237 (2005).
Summary: The most famous open problem involving domination in graphs is Vizing’s conjecture which states the domination number of the Cartesian product of any two graphs is at least as large as the product of their domination numbers. We investigate a similar problem for paired-domination, and obtain a lower bound in terms of product of domination number of one factor and 3-packing of the other factor. Some results are obtained by applying a new graph invariant called rainbow domination.
For the entire collection see [Zbl 1109.05013].

05C69 Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.)
05C76 Graph operations (line graphs, products, etc.)
05C15 Coloring of graphs and hypergraphs
Full Text: DOI
[1] Clark, W.E.; Suen, S., An inequality related to Vizing’s conjecture, Electron. J. combin., 7, 1, 3, (2000), Note 4, (electronic) · Zbl 0947.05056
[2] Hartnell, B.; Rall, D.F., Domination in cartesian products: Vizing’s conjecture, (), 163-189 · Zbl 0890.05035
[3] Haynes, T.W.; Hedetniemi, S.T.; Slater, P.J., Fundamentals of domination in graphs, (1998), Marcel Dekker New York · Zbl 0890.05002
[4] Haynes, T.W.; Slater, P.J., Paired-domination in graphs, Networks, 32, 199-206, (1998) · Zbl 0997.05074
[5] M.A. Henning and D.F. Rall, On the total domination number of Cartesian products of graph, Graphs and Combinatorics, in press
[6] Jacobson, M.S.; Kinch, L.F., On the domination of the products of graphs II: trees, J. graph theory, 10, 97-106, (1986) · Zbl 0584.05053
[7] Meir, A.; Moon, J.W., Relations between packing and covering numbers of a tree, Pacific J. math., 61, 225-233, (1975) · Zbl 0315.05102
[8] Vizing, V.G., Some unsolved problems in graph theory, Uspehi mat. nauk, 23, 6 (144), 117-134, (1968) · Zbl 0177.52301
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.