Signed total Italian k-domination

Articles in Press

Document Type : Original paper

Author

College of Science, China Jiliang University, Hangzhou 310018, China

Abstract

Let k≥1 be an integer. A signed total Italian k-dominating function (STIkDF) on a graph G=(V,E) is a function f:V→{−1,1,2} satisfying the conditions that ∑u∈N(v)f(u)≥k for each vertex v∈V, where N(v) is the neighborhood of v, and each vertex u with f(u)=−1 is adjacent to a vertex v with f(v)=2 or to two vertices w and z with f(w)=f(z)=1. The weight of an STIkDF f is w(f)=∑v∈Vf(v). The signed total Italian k-domination number of G, denoted by γstIk(G), is the minimum weight of an STIkDF on G. In this paper, we prove that the decision problem for the signed total k-domination is NP-complete for k∈{1,2}. We present tight lower bound on \textcolor{red}{γstI2(G)}, and characterize all extremal graphs. Using a discharging method, we also determine the value \textcolor{red}{γstI2(C3◻Cn)} for all n≥3.

Keywords

Main Subjects

References

[1] M. Chellali, N. Jafari Rad, S. M. Sheikholeslami, and L. Volkmann, Varieties of Roman domination, pp. 273–307, Springer International Publishing, Cham, 2021.
[2] M. Chellali, N. Jafari Rad, S.M. Sheikholeslami, and L. Volkmann, Varieties of Roman domination II, AKCE Int. J. Graphs Comb. 17 (2020), no. 3, 966–984.  https://doi.org/10.1016/j.akcej.2019.12.001
[3] M.A. Henning, Signed total domination in graphs, Discrete Math. 278 (2004), no. 1-3, 109–125. https://doi.org/10.1016/j.disc.2003.06.002
[4] G. Hickey, F. Dehne, A. Rau-Chaplin, and C. Blouin, SPR distance computation for unrooted trees, Evol. Bioinform. 4 (2008), 17–27.  https://doi.org/10.4137/EBO.S419
[5] 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.  http://dx.doi.org/10.7151/dmgt.1871
[6] R. Khoeilar, L. Shahbazi, S.M. Sheikholeslami, and Z. Shao, Bounds on the signed total Roman 2-domination in graphs, Discrete Math. Algorithms Appl. 12 (2020), no. 1, Article ID: 2050013.  https://doi.org/10.1142/S1793830920500135
[7] L. Volkmann, Signed total Roman domination in graphs, J. Comb. Optim. 32 (2016), no. 3, 855–871. https://doi.org/10.1007/s10878-015-9906-6
[8] L. Volkmann, Signed total Roman k-domination in graphs, J. Combin. Math. Combin. Comput. 105 (2018), 105–116. 
[9] L. Volkmann, Signed total Italian domination in graphs, J. Combin. Math. Combin. Comput. 115 (2020), 291–305.
[10] L. Volkmann, Signed total Italian k-domination in graphs, Commun. Comb. Optim. 6 (2021), no. 2, 171–183. https://doi.org/10.22049/cco.2020.26919.1164
[11] B. Zelinka, Signed total domination number of a graph, Czech. Math. J. 51 (2001), no. 2, 225–229. https://doi.org/10.1023/A:1013782511179
Communications in Combinatorics and Optimization

Articles in Press, Accepted Manuscript
Available Online from 13 June 2025

Files

Share

How to cite

Statistics