Total Roman domination on Kneser graphs

Document Type : Research Paper

Authors

Department of Mathematics, University of Zanjan, Zanjan, Iran

Abstract

A Roman dominating function (RDF) on a graph $G$ is a function $f : V (G) \longrightarrow \{0, 1, 2\}$ such that any vertex $v$ with $ f(v) = 0$ is adjacent to at least one vertex $w$ with $f(w) = 2$. In addition, if the subgraph of $G$ induced by the set of all vertices for which $f \ne 0$ has no isolated vertices then $f$ is called a total Roman dominating function (TRDF). If $f$ is an RDF (TRDF) then the least value of $\sum_{u\in V} f(u)$ is called Roman domination number (total Roman domination number) of $G$ and is denoted by $\gamma_{_R}(G)$ ( $\gamma_{_{tR}}(G)$). Let $G=G(n, k, 0)$ be a Kneser graph, where $n,k$ are positive integers. In this paper we present some bounds for $\gamma_{_{tR}}(G(n, k, 0))$ for $k^2 < n < k^2+k$. In particular we show that $\gamma_{_{tR}}(G(k^2+k-1, k, 0))=2(k+2)$ and for $n\geqslant 2k+1$, $\gamma_{_{R}}(G(n, k, 0)) \geq max \{ \gamma_{_{R}}(G(n-1, k -1, 0)), \gamma_{_{R}}(G(n, k -1, 0))\}$.

Keywords

Main Subjects

References

[1] H. A. Ahangar, M. A. Henning, V. Samodivkin and I. G. Yero, Total Roman domination in graphs, Appl. Anal. Discrete Math., 10 no. 2 (2016) 501–517.
[2] H. A. Ahangar, M. Soroudi, J. Amjadi and S. M. Sheikholeslami, Total roman domination and 2-independence in trees, Trans. Comb., 13 no. 3 (2024) 213–223.
[3] J. Amjadi, S. Nazari-Moghaddam, S. M. Sheikholeslami and L. Volkmann, Total Roman domination number of trees, Australas. J. Combin., 69 (2017) 271–285.
[4] E. J. Cockayne, P. A. Dreyer, S. M. Hedetniemi and S. T. Hedetniemi, Roman domination in graphs, Discrete Math., 278 no. 1-3 (2004) 11–22.
[5] C. D. Godsil, Algebraic combinatorics, Chapman and Hall Mathematics Series, Chapman & Hall, New York, 1993.
[6] C.-H. Liu and G. J. Chang, Roman domination on strongly chordal graphs, J. Comb. Optim., 26 no. 3 (2013) 608–619.
[7] P. R. J. Ostergard, Z. Shao and X. Xu, Bounds on the domination number of Kneser graphs, [Paging previously given as 197–205], Ars Math. Contemp., 9 no. 2 (2015) 187–195.
[8] C. S. ReVelle and K. E. Rosing, Defendens imperium romanum: a classical problem in military strategy, Amer. Math. Monthly, 107 no. 7 (2000) 585–594.
[9] I. Stewart, Defend the Roman empire!, Sci. Amer., 281 no. 6 (1999) 136–138.
[10] Z. Tatjana and G. Milana, Several Roman domination graph invariants on Kneser graphs, Discrete Mathematics & Theoretical Computer Science, 25:1 (2023) 18 pp.
[11] D. B. West, Introduction to graph theory, Prentice Hall, Inc., Upper Saddle River, NJ, 1996.

Files

History

  • Receive Date: 06 February 2024
  • Revise Date: 07 April 2025
  • Accept Date: 18 April 2025
  • Published Online: 21 April 2025

Share

How to cite

Statistics