Skip to Main content Skip to Navigation
Journal articles

Some Results About a Conjecture on Identifying Codes in Complete Suns

Abstract : Consider a graph G = (V, E) and, for every vertex v ∈ V , denote by B(v) the set {v} ∪ {u : uv ∈ E}. A subset C ⊆ V is an identifying code if the sets B(v) ∩ C, v ∈ V , are all nonempty and distinct. It is a locating-dominating code if the sets B(v) ∩ C, v ∈ V \ C, are all nonempty and distinct. Let S n be the graph whose vertex set can be partitioned into two sets U n and V n , where U n = {u 1 , u 2 ,. .. , u n } induces a clique, and V n = {v 1,2 , v 2,3 ,. .. , v n−1,n , v n,1 } induces an independent set, with edges v i,i+1 u i and v i,i+1 u i+1 , 1 ≤ i ≤ n; computations are carried modulo n. This graph is called a complete sun. We prove the conjecture, stated by Argiroffo, Bianchi and Wagler in 2014, that the smallest identifying code in S n has size equal to n. We also characterize and count all the identifying codes with size n in S n. Finally, we determine the sizes of the smallest locating-dominating codes in S n .
Document type :
Journal articles
Complete list of metadata

https://hal.archives-ouvertes.fr/hal-01613344
Contributor : Antoine Lobstein Connect in order to contact the contributor
Submitted on : Monday, November 30, 2020 - 2:27:41 PM
Last modification on : Thursday, July 8, 2021 - 3:50:25 AM
Long-term archiving on: : Monday, March 1, 2021 - 7:11:51 PM

File

OH-AL-Id-suns.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-01613344, version 1

Citation

Olivier Hudry, Antoine Lobstein. Some Results About a Conjecture on Identifying Codes in Complete Suns. International Transactions in Operational Research, Wiley, 2019, 26 (2), pp.732-746. ⟨hal-01613344⟩

Share

Metrics

Record views

441

Files downloads

90