Edge domination in graphs of cubes. (English) Zbl 1009.05102

Summary: The signed edge domination number and the signed total edge domination number of a graph are considered; they are variants of the domination number and the total domination number. Some upper bounds for them are found in the case of the \(n\)-dimensional cube \(Q_n\).


05C69 Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.)
05C35 Extremal problems in graph theory
Full Text: DOI EuDML


[1] J. E. Dunbar, S. T. Hedetniemi, M. A. Henning and P. J. Slater: Signed domination in graphs. Graph Theory, Combinatorics and Applications, Y. Alavi, A. J. Schwenk (eds.) vol. 1, Proc. 7th Internat. Conf. Combinatorics, Graph Theory, Applications, John Wiley & Sons, Inc., 1995, pp. 311-322. · Zbl 0842.05051
[2] T. Dvořák, I. Havel, J.-M. Laborde and P. Liebl: Generalized hypercubes and graph embedding with dilation. Rostocker Mathematisches Kolloquium 39 (1990), 13-20. · Zbl 0719.05036
[3] R. Forcade: Smallest maximal matchings in the graph of the \(n\)-dimensional cube. J. Combin. Theory Ser. B 14 (1973), 153-156. · Zbl 0261.05123 · doi:10.1016/0095-8956(73)90059-2
[4] I. Havel and M. Křivánek: On maximal matchings in \(Q_6\) and a conjecture of R. Forcade. Comment Math. Univ. Carolin. 23 (1982), 123-136.
[5] T. W. Haynes, S. T. Hedetniemi and P. J. Slater: Fundamentals of Domination in Graphs. Marcel Dekker, Inc., New York-Basel-Hong Kong, 1998. · Zbl 0890.05002
[6] C. Payan: On the chromatic number of cube-like graphs. Discrete Math. 103 (1992), 272-277. · Zbl 0772.05043 · doi:10.1016/0012-365X(92)90319-B
[7] B. Xu: On signed edge domination numbers of graphs. Discrete Math. 239 (2001), 179-189. · Zbl 0979.05081 · doi:10.1016/S0012-365X(01)00044-9
[8] B. Zelinka: On signed edge domination numbers of trees. Math. Bohem. 127 (2002), 49-55. · Zbl 0995.05112
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.