Premium
Some results about a conjecture on identifying codes in complete suns
Author(s) -
Hudry Olivier,
Lobstein Antoine
Publication year - 2019
Publication title -
international transactions in operational research
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.032
H-Index - 52
eISSN - 1475-3995
pISSN - 0969-6016
DOI - 10.1111/itor.12320
Subject(s) - combinatorics , modulo , conjecture , vertex (graph theory) , suns in alchemy , mathematics , graph , discrete mathematics , clique , dominating set , clique graph , line graph , graph power , physics , optoelectronics
Consider a graph G = ( V , E ) and, for every vertex v ∈ V , denote by B ( v ) the set { v } ∪ { u : u v ∈ E } . A subset C ⊆ V is an identifying code if the sets B ( v ) ∩ C , v ∈ V , are nonempty and distinct. It is a locating–dominating code if the sets B ( v ) ∩ C , v ∈ V ∖ C , are nonempty and distinct. Let S n be the graph whose vertex set can be partitioned into two sets, U n and V n , whereU n = { u 1 , u 2 , … , u n }induces a clique andV n = { v 1 , 2 , v 2 , 3 , … , v n − 1 , n , v n , 1 }induces an independent set, with edgesv i , i + 1u iandv i , i + 1u i + 1, 1 ≤ i ≤ n ; computations are carried modulo n . This graph is called a complete sun. We prove the conjecture 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 LD codes in S n .