Publications
Sort:
Open Access Research Article Issue
On the (total) Roman domination in Latin square graphs
AIMS Mathematics 2024, 9(1): 594-606
Published: 15 January 2024
Abstract PDF (372.5 KB) Collect
Downloads:9

Latin square, also known as Latin square matrix, refers to a kind of n × 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 Γ ( 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 Γ ( L ). We showed that γ R ( Γ ( L ) ) = 2 γ ( Γ ( L ) ) or γ R ( Γ ( L ) ) = 2 γ ( Γ ( L ) ) − 1, and γ t R ( Γ ( L ) ) ≥ 8 γ t ( Γ ( L ) ) 5 for n ≥ 2. In 2021, Pahlavsay et al. proved γ ( Γ ( L ) ) ≥ ⌈ n 2 ⌉ and γ t ( Γ ( L ) ) ≥ ⌈ 4 n − 2 7 ⌉ for n ≥ 2. In this paper, we showed that γ R ( Γ ( L ) ) ≥ 2 ⌈ n 2 ⌉ (equality holds if, and only if, γ ( Γ ( L ) ) = ⌈ n 2 ⌉) and γ t ( Γ ( L ) ) > 4 n 7 for n ≥ 2. Since γ R ( G ) ≤ 2 γ ( G ) and γ t R ( G ) ≤ 2 γ t ( G ) for any graph G, our results can deduce or improve Pahlavsay et al.'s results. Moreover, we characterized these Latin squares for γ R ( Γ ( L ) ) = 2 ⌈ n 2 ⌉, which is equal to γ ( Γ ( L ) ) = ⌈ n 2 ⌉.

Total 1