Abstract
Let \(G\) be a graph with the vertex set \(V(G)\) and the edge set \(E(G)\). A function \(f: E(G)\longrightarrow \{-1, 1\}\) is said to be a signed star dominating function of \(G\) if \(\sum _{e \in E_G(v)}f (e)\ge 1 \), for every \(v \in V(G)\), where \(E_G(v) = \{uv\in E(G)\,|\,u \in V (G)\}\). The minimum values of \(\sum _{e \in E_G(v)}f (e)\), taken over all signed star dominating functions \(f\) on \(G\), is called the signed star domination number of \(G\) and denoted by \(\gamma _{SS}(G)\). In this paper we determine the signed star domination number of regular multigraphs.
Similar content being viewed by others
References
S. Akbari, S. Bolouki, P. Hatami, M. Siami, On signed edge domination number of graphs. Discret. Math. 309, 587–594 (2009)
J. Akiyama, M. Kano, Factors and Factorizations of Graphs (Springer, Berlin, 2011)
B. Bollobás, A. Saito, N.C. Wormald, Regular factors of regular graphs. J. Graph Theory 9, 103 (1985)
J.A. Bondy, U.S.R. Murty, Graph Theory with Applications (North Holland, New York, 1976)
I. Broere, J.H. Hattingh, M.A. Henning, A.A. McRae, Majority domination in graphs. Discret. Math. 138, 135 (1995)
E.J. Cockayne, C.M. Mynhart, On a generalization of signed domination functions of graphs. Ars. Comb. 43, 245 (1996)
J.H. Hattingh, E. Ungerer, The signed and minus \(k\)-subdomination numbers of comets. Discret. Math. 183, 141–152 (1998)
M. Kano, \([a, b]\)-factorization of a graph. J. Graph Theory 9, 129–146 (1985)
J. Petersen, Die theorie der regularen graphen. Acta Math. 15, 193–220 (1891)
R. Saei, S.M. Sheikholeslami, Signed star \(k\)-subdomination numbers in graphs. Discret. Appl. Math. 156, 3066–3070 (2008)
C.P. Wang, The signed star domination numbers of the Cartesian product graphs. Discret. Appl. Math. 155, 1497–1505 (2007)
B. Xu, On signed edge domination numbers of graphs. Discret. Math. 239, 179–189 (2001)
B. Xu, On edge domination numbers of graphs. Discret. Math. 294, 311–316 (2005)
B. Xu, E.J. Cockayne, T.W. Haynes, S.T. Hedetniemi, S. Zhou, Extremal graphs for inequalities involving domination parameters. Discret. Math. 216, 1–10 (2000)
Z. Zhang, B. Xu, Y. Li, L. Liu, A note on the lower bounds of signed domination number of a graph. Discret. Math. 195, 295–298 (1999)
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Zare, S., Rahmati, F. On the signed star domination number of regular multigraphs. Period Math Hung 68, 39–44 (2014). https://doi.org/10.1007/s10998-014-0026-3
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10998-014-0026-3