Geodesic
Identifying codes in the direct product of a path and a complete graph
Discussiones Mathematicae. Graph Theory, Tome 43 (2023) no. 2, pp. 463-486

Voir la notice de l'article provenant de la source Library of Science

Let G be a simple, undirected graph with vertex set V. For any vertex v ∈ V, the set N[v] is the vertex v and all its neighbors. A subset D ⊆ V(G) is a dominating set of G if for every v ∈ V(G), N[v] ∩ D ∅. And a subset F ⊆ V(G) is a separating set of G if for every distinct pair u, v∈ V(G), N[u]∩ F N[v] ∩ F. An identifying code of G is a subset C ⊆ V(G) that is dominating as well as separating. The minimum cardinality of an identifying code in a graph G is denoted by γ^ID(G). The identifying codes of the direct product G_1 × G_2, where G_1 is a complete graph and G_2 is a complete/ regular/ complete bipartite graph, are known in the literature. In this paper, we find γ^ID(P_n × K_m) for n≥ 3, and m≥ 3 where P_n is a path of length n, and K_m is a complete graph on m vertices.
Keywords: identifying code, direct product, path, complete graph 
@article{DMGT_2023_43_2_a10,
     author = {Shinde, Neeta and Mane, Smruti and Waphare, Baloo},
     title = {Identifying codes in the direct product of a path and a complete graph},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {463--486},
     publisher = {mathdoc},
     volume = {43},
     number = {2},
     year = {2023},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2023_43_2_a10/}
}
TY  - JOUR
AU  - Shinde, Neeta
AU  - Mane, Smruti
AU  - Waphare, Baloo
TI  - Identifying codes in the direct product of a path and a complete graph
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2023
SP  - 463
EP  - 486
VL  - 43
IS  - 2
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DMGT_2023_43_2_a10/
LA  - en
ID  - DMGT_2023_43_2_a10
ER  - 
%0 Journal Article
%A Shinde, Neeta
%A Mane, Smruti
%A Waphare, Baloo
%T Identifying codes in the direct product of a path and a complete graph
%J Discussiones Mathematicae. Graph Theory
%D 2023
%P 463-486
%V 43
%N 2
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DMGT_2023_43_2_a10/
%G en
%F DMGT_2023_43_2_a10
Shinde, Neeta; Mane, Smruti; Waphare, Baloo. Identifying codes in the direct product of a path and a complete graph. Discussiones Mathematicae. Graph Theory, Tome 43 (2023) no. 2, pp. 463-486. http://geodesic.mathdoc.fr/item/DMGT_2023_43_2_a10/