کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
427110 | 686448 | 2015 | 4 صفحه PDF | دانلود رایگان |
• We study the set of all optimal locating-dominating codes in a given graph.
• There is a strong link between such sets and induced subgraphs of Johnson graphs.
• Instead of locating-dominating codes we also consider dominating codes.
Let G be a simple, undirected graph with vertex set V . For every v∈Vv∈V, we denote by N(v)N(v) the set of neighbours of v , and let N[v]=N(v)∪{v}N[v]=N(v)∪{v}. A set C⊆VC⊆V is said to be a dominating code in G if the sets N[v]∩CN[v]∩C, v∈Vv∈V, are all nonempty. A set C⊆VC⊆V is said to be a locating-dominating code in G if the sets N[v]∩CN[v]∩C, v∈V∖Cv∈V∖C, are all nonempty and distinct. The smallest size of a dominating (resp., locating-dominating) code in G is denoted by d(G)d(G) (resp., ℓ(G)ℓ(G)).We study the ensemble of all the different optimal dominating (resp., locating-dominating) codes C , i.e., such that |C|=d(G)|C|=d(G) (resp., |C|=ℓ(G)|C|=ℓ(G)) in a graph G, and strongly link this problem to that of induced subgraphs of Johnson graphs.
Journal: Information Processing Letters - Volume 115, Issue 9, September 2015, Pages 699–702