Lower bounds on the signed (total) $k$-domination number

Document Type : Original paper

Author

RWTH Aachen University

Abstract

Let $G$ be a graph with vertex set $V(G)$. For any integer $k\ge 1$, a signed (total) $k$-dominating function is a function $f: V(G) \rightarrow \{ -1, 1\}$ satisfying $\sum_{x\in N[v]}f(x)\ge k$ ($\sum_{x\in N(v)}f(x)\ge k$) for every $v\in V(G)$, where $N(v)$ is the neighborhood of $v$ and $N[v]=N(v)\cup\{v\}$. The minimum of the values $\sum_{v\in V(G)}f(v)$, taken over all signed (total) $k$-dominating functions $f$, is called the signed (total) $k$-domination number. The clique number of a graph $G$ is the maximum cardinality of a complete subgraph of $G$. In this note we present some new sharp lower bounds on the signed (total) $k$-domination number depending on the clique number of the graph. Our results improve some known bounds.

Keywords

Main Subjects

References

[1] M. Atapour, S.M. Sheikholeslami, R. Hajypory, and L. Volkmann, The signed k-domination number of directed graphs, Cent. Eur. J. Math. 8 (2010), no. 6, 1048–1057.
[2] W. Chen and E. Song, Lower bounds on several versions of signed domination number, Discrete Math. 308 (2008), no. 10, 1837–1846.
[3] J.E. Dunbar, S.T. Hedetniemi, M.A. Henning, and P.J. Slater, Signed domination in graphs, Graph Theory, Combinatorics, and Applications Vol. 1, Wiley, New York, 1995, 311–322.
[4] T.W. Haynes, S. Hedetniemi, and P. Slater, Fundamentals of Domination in Graphs, Marcel Dekker, New York, 1998.
[5] M.A. Henning, Signed total domination in graphs, Discrete Math. 278 (2004), no. 1-3, 109–125.
[6] M.A. Henning and P.J. Slater, Inequalities relating domination parameters in cubic graphs, Discrete Math. 158 (1996), no. 1-3, 87–98.
[7] S.M. Hosseini Moghaddam, D.A. Mojdeh, B. Samadi, and L. Volkmann, New bounds on the signed total domination number of graphs, Discuss. Math. Graph Theory 36 (2016), no. 2, 467–477.
[8] H. Liang, On the signed (total) k-domination number of a graph, J. Combin. Math. Combin. Comput. 89 (2014), 87–99.
[9] D.A. Mojdeh and B. Samadi, New and improved results on the signed (total) kdomination number of graphs, Discrete Math. Algorithms Appl. 9 (2017), no. 2, Article ID: 1750024.
[10] E. Shan and T.C.E. Cheng, Remarks on the minus (signed) total domination in graphs, Discrete Math. 308 (2008), no. 15, 3373–3380.
[11] S.M. Sheikholeslami and L. Volkmann, Signed total k-domination numbers of directed graphs, An. S¸t. Univ. Ovidius Constant¸a 18 (2010), no. 2, 241–252.
[12] P. Turán, On an extremal problem in graph theory, Math. Fiz. Lapok 48 (1941), 436–452 (in Hungarian).
[13] L. Volkmann, Lower bounds on the signed total k-domination number of graphs, Aequat. Math. 90 (2016), no. 2, 271–279.
[14] L. Volkmann, Lower bounds on the signed k-domination number of graphs, Ars Combin. 135 (2017), 357–367.
[15] C. Wang, The signed k-domination numbers in graphs, Ars Combin. 106 (2012), 205–211.
[16] B. Zelinka, Signed total domination number of a graph, Czechoslovak Math. J. 51 (2001), no. 2, 225–229.
[17] Z. Zhang, B. Xu, Y. Li, and L. Liu, A note on the lower bounds of signed domination number of a graph, Discrete Math. 195 (1999), no. 1-3, 295–298.
Communications in Combinatorics and Optimization
Volume 3, Issue 2
December 2018
Pages 173-178

Files

Share

How to cite

Statistics