Some Results About a Conjecture on Identifying Codes in Complete Suns - Equipe Mathématiques discrètes, codage et cryptographie Accéder directement au contenu
Article Dans Une Revue International Transactions in Operational Research Année : 2019

Some Results About a Conjecture on Identifying Codes in Complete Suns

Olivier Hudry
Antoine Lobstein

Résumé

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 .

Mots clés

Fichier principal
Vignette du fichier
OH-AL-Id-suns.pdf (199.01 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)

Dates et versions

hal-01613344 , version 1 (30-11-2020)

Identifiants

  • HAL Id : hal-01613344 , version 1

Citer

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

Partager

Gmail Facebook X LinkedIn More