On the total signed domination number of the Cartesian product of paths
DOI:
https://doi.org/10.11575/cdm.v12i2.62445Keywords:
Total signed domination number, Cartesian product, PathsAbstract
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$.
References
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.
Downloads
Published
Issue
Section
License
This copyright statement was adapted from the statement for the University of Calgary Repository and from the statement for the Electronic Journal of Combinatorics (with permission).
The copyright policy for Contributions to Discrete Mathematics (CDM) is changed for all articles appearing in issues of the journal starting from Volume 15 Number 3.
Author(s) retain copyright over submissions published starting from Volume 15 number 3. When the author(s) indicate approval of the finalized version of the article provided by the technical editors of the journal and indicate approval, they grant to Contributions to Discrete Mathematics (CDM) a world-wide, irrevocable, royalty free, non-exclusive license as described below:
The author(s) grant to CDM the right to reproduce, translate (as defined below), and/or distribute the material, including the abstract, in print and electronic format, including but not limited to audio or video.
The author(s) agree that the journal may translate, without changing the content the material, to any medium or format for the purposes of preservation.
The author(s) also agree that the journal may keep more than one copy of the article for the purposes of security, back-up, and preservation.
In granting the journal this license the author(s) warrant that the work is their original work and that they have the right to grant the rights contained in this license.
The authors represent that the work does not, to the best of their knowledge, infringe upon anyone’s copyright.
If the work contains material for which the author(s) do not hold copyright, the author(s) represent that the unrestricted permission of the copyright holder(s) to grant CDM the rights required by this license has been obtained, and that such third-party owned material is clearly identified and acknowledged within the text or content of the work.
The author(s) agree to ensure, to the extent reasonably possible, that further publication of the Work, with the same or substantially the same content, will acknowledge prior publication in CDM.
The journal highly recommends that the work be published with a Creative Commons license. Unless otherwise arranged at the time the finalized version is approved and the licence granted with CDM, the work will appear with the CC-BY-ND logo. Here is the site to get more detail, and an excerpt from the site about the CC-BY-ND. https://creativecommons.org/licenses/
Attribution-NoDerivs
CC BY-ND
This license lets others reuse the work for any purpose, including commercially; however, it cannot be shared with others in adapted form, and credit must be provided to you.