A set L ź V of a graph G = ( V , E ) is a liar's dominating set if (1) for every vertex u ź V , | N u ź L | ź 2 and (2) for every pair u , v ź V of distinct vertices, | ( N u ź N v ) ź L | ź 3 . In this paper, we first provide a characterization of graphs G with γ L R ( G ) = | V | as well as the trees T with γ L R ( T ) = | V | - 1 . Then we present some bounds on the liar's domination number, especially an upper bound for the ratio between the liar's domination number and the double domination number is established for connected graphs with girth at least five. Finally, we determine the exact value of the liar's domination number for the complete r -partite graphs.
['Abdollah Alimadadi', 'Mustapha Chellali', 'Doost Ali Mojdeh']
Liar's dominating sets in graphs