Various Bounds for Liar’s Domination Number
Let G = (V,E) be a graph. A set S ⊆ V is a dominating set if Uv∈S N[v] = V , where N[v] is the closed neighborhood of v. Let L ⊆ V be a dominating set, and let v be a designated vertex in V (an intruder vertex). Each vertex in L ∩ N[v] can report that v is the location of the intruder, but (at most)...
| Main Authors: | , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
University of Zielona Góra
2016-08-01
|
| Series: | Discussiones Mathematicae Graph Theory |
| Subjects: | |
| Online Access: | https://doi.org/10.7151/dmgt.1878 |
| _version_ | 1797704414579916800 |
|---|---|
| author | Alimadadi Abdollah Mojdeh Doost Ali Rad Nader Jafari |
| author_facet | Alimadadi Abdollah Mojdeh Doost Ali Rad Nader Jafari |
| author_sort | Alimadadi Abdollah |
| collection | DOAJ |
| description | Let G = (V,E) be a graph. A set S ⊆ V is a dominating set if Uv∈S N[v] = V , where N[v] is the closed neighborhood of v. Let L ⊆ V be a dominating set, and let v be a designated vertex in V (an intruder vertex). Each vertex in L ∩ N[v] can report that v is the location of the intruder, but (at most) one x ∈ L ∩ N[v] can report any w ∈ N[x] as the intruder location or x can indicate that there is no intruder in N[x]. A dominating set L is called a liar’s dominating set if every v ∈ V (G) can be correctly identified as an intruder location under these restrictions. The minimum cardinality of a liar’s dominating set is called the liar’s domination number, and is denoted by γLR(G). In this paper, we present sharp bounds for the liar’s domination number in terms of the diameter, the girth and clique covering number of a graph. We present two Nordhaus-Gaddum type relations for γLR(G), and study liar’s dominating set sensitivity versus edge-connectivity. We also present various bounds for the liar’s domination component number, that is, the maximum number of components over all minimum liar’s dominating sets. |
| first_indexed | 2024-03-12T05:20:05Z |
| format | Article |
| id | doaj.art-b8406e94d98b4f0ba057197f82e572c4 |
| institution | Directory Open Access Journal |
| issn | 2083-5892 |
| language | English |
| last_indexed | 2024-03-12T05:20:05Z |
| publishDate | 2016-08-01 |
| publisher | University of Zielona Góra |
| record_format | Article |
| series | Discussiones Mathematicae Graph Theory |
| spelling | doaj.art-b8406e94d98b4f0ba057197f82e572c42023-09-03T07:47:21ZengUniversity of Zielona GóraDiscussiones Mathematicae Graph Theory2083-58922016-08-0136362964110.7151/dmgt.1878dmgt.1878Various Bounds for Liar’s Domination NumberAlimadadi Abdollah0Mojdeh Doost Ali1Rad Nader Jafari2Department of Mathematics University of Tafresh, Tafresh, IranDepartment of Mathematics University of Mazandaran, Babolsar, IranDepartment of Mathematics Shahrood University of Technology, Shahrood, IranLet G = (V,E) be a graph. A set S ⊆ V is a dominating set if Uv∈S N[v] = V , where N[v] is the closed neighborhood of v. Let L ⊆ V be a dominating set, and let v be a designated vertex in V (an intruder vertex). Each vertex in L ∩ N[v] can report that v is the location of the intruder, but (at most) one x ∈ L ∩ N[v] can report any w ∈ N[x] as the intruder location or x can indicate that there is no intruder in N[x]. A dominating set L is called a liar’s dominating set if every v ∈ V (G) can be correctly identified as an intruder location under these restrictions. The minimum cardinality of a liar’s dominating set is called the liar’s domination number, and is denoted by γLR(G). In this paper, we present sharp bounds for the liar’s domination number in terms of the diameter, the girth and clique covering number of a graph. We present two Nordhaus-Gaddum type relations for γLR(G), and study liar’s dominating set sensitivity versus edge-connectivity. We also present various bounds for the liar’s domination component number, that is, the maximum number of components over all minimum liar’s dominating sets.https://doi.org/10.7151/dmgt.1878liar’s dominationdiameterregular graphnordhaus-gaddum |
| spellingShingle | Alimadadi Abdollah Mojdeh Doost Ali Rad Nader Jafari Various Bounds for Liar’s Domination Number Discussiones Mathematicae Graph Theory liar’s domination diameter regular graph nordhaus-gaddum |
| title | Various Bounds for Liar’s Domination Number |
| title_full | Various Bounds for Liar’s Domination Number |
| title_fullStr | Various Bounds for Liar’s Domination Number |
| title_full_unstemmed | Various Bounds for Liar’s Domination Number |
| title_short | Various Bounds for Liar’s Domination Number |
| title_sort | various bounds for liar s domination number |
| topic | liar’s domination diameter regular graph nordhaus-gaddum |
| url | https://doi.org/10.7151/dmgt.1878 |
| work_keys_str_mv | AT alimadadiabdollah variousboundsforliarsdominationnumber AT mojdehdoostali variousboundsforliarsdominationnumber AT radnaderjafari variousboundsforliarsdominationnumber |