On the total signed domination number of the Cartesian product of paths

Hong Gao, Huiping Cao, Yuansheng Yang

Abstract


Let $G$ be a finite connected simple graph with a vertex set $V(G)$ and an edge set $E(G)$. A total signed dominating function of $G$ is a function $f: V(G)\cup E(G)\rightarrow \{-1, 1\}$, such that $\sum_{y\in N_T[x]}f(y) \geq 1$ for all $x\in V(G) \cup E(G)$. The total signed domination number of $G$ is the minimum weight of a total signed dominating function on $G$. In this paper, we prove lower and upper bounds on the total signed domination number of the Cartesian product of two paths, $P_m\Box P_n$.


Keywords


Total signed domination number; Cartesian product; Paths

Full Text:

PDF

References


S. Akbari, S. Bolouki, P. Hatami, and M. Siami. On the signed edge domination number of graphs. Discrete Mathematics, 309(3):587–594, 2009.

S. Benecke and C. M. Mynhardt. Domination of generalized Cartesian products. Discrete Mathematics, 310(8):1392–1397, 2010.

O. Favaron. Signed domination in regular graphs. Discrete Mathematics, 158(1):287–293, 1996.

X. Fu, Y. Yang, and B. Jiang. A note on the signed edge domination number in graphs. Discrete Applied Mathematics, 156(14):2790–2792, 2008.

S. Gravier and M. Mollard. On domination numbers of Cartesian product of paths. Discrete applied mathematics, 80(2):247–250, 1997.

R. Haas and T. B. Wexler. Bounds on the signed domination number of a graph. Electronic Notes in Discrete Mathematics, 11:742–750, 2002.

H. Karami, S. M. Sheikholeslami, and A. Khodkar. Some notes on signed edge domination in graphs. Graphs and Combinatorics, 24(1):29–35, 2008.

H. Karami, S. M. Sheikholeslami, and A. Khodkar. Lower bounds on the signed domination numbers of directed graphs. Discrete Mathematics, 309(8):2567–2570, 2009.

A. Khodkar, R. Saei, S. M. Sheikholeslami, and I. R. Tabriz. Signed edge k-subdomination numbers in graphs. Ars Combinatoria, 109:129–141, 2013.

S. Klavˇzar and N. Seifter. Dominating Cartesian products of cycles. Discrete applied mathematics, 59(2):129–136, 1995.

X. Li and J. Xu. The signed edge-domatic number of a graph. Graphs and Combinatorics, 29(6):1881–1890, 2013.

X. Lu. A lower bound on the total signed domination numbers of graphs. Science in China Series A: Mathematics, 50(8):1157–1162, 2007.

M. Mollard. The domination number of Cartesian product of two directed paths. Journal of Combinatorial Optimization, 27(1):144–151, 2014.

X. Pi and H. Liu. On the characterization of trees with signed edge domination numbers 1, 2, 3, or 4. Discrete Mathematics, 309(6):1779–1782, 2009.

E. Shan and T. C. E. Cheng. Upper bounds on the upper signed total domination number of graphs. Discrete Applied Mathematics, 157(5):1098–1103, 2009.

S. M. Sheikholeslami and L. Volkmann. Signed star k-domatic number of a graph. Contributions to Discrete Mathematics, 6(2):20–31, 2011.

V. G. Vizing. The Cartesian product of graphs. Vycisl. Sistemy, 9:30–43, 1963.

L. Volkmann. Upper bounds on the signed (k, k)-domatic number. Aequationes mathematicae, 86(3):279–287, 2013.

L. Volkmann and B. Zelinka. Signed domatic number of a graph. Discrete applied mathematics, 150(1):261–267, 2005.

D. B. West. Introduction to graph theory. 2000.

B. Xu. On signed edge domination numbers of graphs. Discrete Mathematics, 239(1):179–189, 2001.

B. Xu. On edge domination numbers of graphs. Discrete Mathematics, 294(3):311–316, 2005.

R. Yuan, F. Wei, and Jirimutu. On the total signed domination number of nCm. International Journal of Pure and Applied Mathematics, 81(5):765–772, 2012.

B. Zelinka. Signed total domination number of a graph. Czechoslovak Mathematical Journal, 51(2):225–229, 2001.

X. Zhang, J. Liu, X. Chen, and J. Meng. Domination number of Cartesian products of directed cycles. Information Processing Letters, 111(1):36–39, 2010.

Z. Zhang, B. Xu, Y. Li, and L. Liu. A note on the lower bounds of signed domination number of a graph. Discrete Mathematics, 195(1):295–298, 1999.

X. Zou, X. Chen, and G. Sun. Lower bounds on the total signed domination number of graphs. Applied Mathematical Sciences, 1(50):2499–2504, 2007.




Contributions to Discrete Mathematics. ISSN: 1715-0868