آمار
| تعداد نشریات | 5 |
| تعداد شمارهها | 116 |
| تعداد مقالات | 1,343 |
| تعداد مشاهده مقاله | 1,344,346 |
| تعداد دریافت فایل اصل مقاله | 1,279,609 |
Signed total Italian $k$-domination | ||
| Communications in Combinatorics and Optimization | ||
| مقالات آماده انتشار، پذیرفته شده، انتشار آنلاین از تاریخ 23 خرداد 1404 | ||
| نوع مقاله: Original paper | ||
| شناسه دیجیتال (DOI): 10.22049/cco.2025.30392.2449 | ||
| نویسنده | ||
| Qin CHEN* | ||
| College of Science, China Jiliang University, Hangzhou 310018, China | ||
| چکیده | ||
| Let $k\geq 1$ be an integer. A signed total Italian $k$-dominating function (STIkDF) on a graph $G=(V, E)$ is a function $f: V\rightarrow \{-1,1,2\}$ satisfying the conditions that $\sum_{u\in N(v)}f(u)\geq k$ for each vertex $v\in 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)=\sum_{v\in V}f(v)$. The signed total Italian $k$-domination number of $G$, denoted by $\gamma_{stI}^k(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\in\{1,2\}$. We present tight lower bound on \textcolor{red}{$\gamma_{stI}^2(G)$}, and characterize all extremal graphs. Using a discharging method, we also determine the value \textcolor{red}{$\gamma_{stI}^2(C_3\Box C_n)$} for all $n\geq 3$. | ||
| کلیدواژهها | ||
| Signed total Italian $k$-domination number؛ signed total Italian $k$-dominating function؛ complexity | ||
| مراجع | ||
|
[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 it alian 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 | ||
|
آمار تعداد مشاهده مقاله: 7 |
||