Liar's domination number of generalized petersen graphs P(n, 1) and P(n, 2)

Abstract

A set L ⊆ V(G) is a liar's dominating set if and only if L is a double dominating set and |(N[u] ∪ N[v]) ∩ L| ≥ 3 for every pair u and v of distinct vertices in G. The minimum cardinality of a liar's dominating set for graph G is the liar's domination number of G, denoted by γLR(G). In this paper, we study the liar's domination number of generalized Petersen graphs P(n, 1) and P(n,2). We prove that for n ≥ 3, γLR(P(n, 1)) = [7n/6] and for n ≥ 5, γLR(P(n, 2)) = {⌈10n/9⌉+1 n≡8(mod 9)/⌈10n/9⌉ n ≢(mod 9).