On the (total) Roman domination in Latin square graphs

Abstract

Latin square, also known as Latin square matrix, refers to a kind of $ n\times n $ matrix, in which there are exactly $ n $ different symbols and each symbol appears exactly once in each row and column. A Latin square graph $ \Gamma(L) $ is a simple graph associated with a Latin square $ L $. This paper studied the relationships between the (total) Roman domination number and (total) domination number of Latin square graph $ \Gamma(L) $. We showed that $ \gamma_{R}(\Gamma(L)) = 2\gamma(\Gamma(L)) $ or $ \gamma_{R}(\Gamma(L)) = 2\gamma(\Gamma(L))-1 $, and $ \gamma_{tR}(\Gamma(L))\ge \frac{8\gamma_t(\Gamma(L))}{5} $ for $ n\ge 2 $. In 2021, Pahlavsay et al. proved $ \gamma(\Gamma(L))\ge \lceil \frac{n}{2}\rceil $ and $ \gamma_t(\Gamma(L))\ge \lceil \frac{4n-2}{7}\rceil $ for $ n\ge 2 $. In this paper, we showed that $ \gamma_R(\Gamma(L))\ge 2\lceil \frac{n}{2}\rceil $ (equality holds if, and only if, $ \gamma(\Gamma(L)) = \lceil \frac{n}{2}\rceil $) and $ \gamma_t(\Gamma(L)) > \frac{4n}{7} $ for $ n\ge 2 $. Since $ \gamma_R(G)\le 2\gamma(G) $ and $ \gamma_{tR}(G)\le 2\gamma_t(G) $ for any graph $ G $, our results can deduce or improve Pahlavsay et al.'s results. Moreover, we characterized these Latin squares for $ \gamma_R(\Gamma(L)) = 2\lceil \frac{n}{2}\rceil $, which is equal to $ \gamma(\Gamma(L)) = \lceil \frac{n}{2}\rceil $.

Keywords

• latin square
• latin square graphs
• roman domination number
• total roman domination number