Previous |  Up |  Next


signed edge domination number; signed total edge domination number; graph of the cube of dimension $n$
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$.
[1] J. E. Dunbar, S. T. Hedetniemi, M. A. Henning and P. J. Slater: Signed domination in graphs. In: 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. MR 1405819
[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. MR 1090602
[3] R. Forcade: Smallest maximal matchings in the graph of the $n$-dimensional cube. J.  Combin. Theory Ser. B 14 (1973), 153–156. MR 0321804
[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. MR 0653356
[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. MR 1605684
[6] C. Payan: On the chromatic number of cube-like graphs. Discrete Math. 103 (1992), 272–277. MR 1171780 | Zbl 0772.05043
[7] B. Xu: On signed edge domination numbers of graphs. Discrete Math. 239 (2001), 179–189. DOI 10.1016/S0012-365X(01)00044-9 | MR 1850997 | Zbl 0979.05081
[8] B. Zelinka: On signed edge domination numbers of trees. Math. Bohem. 127 (2002), 49–55. MR 1895246 | Zbl 0995.05112
Partner of
EuDML logo