Identifying codes of lexicographic product of graphs

MaRDI QIDQ1953370zbMATH OpenFDO

Authors Min Feng, Min Xu, Kaishun Wang

Publication date 7 June 2013

Published in The Electronic Journal of Combinatorics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1106.3607, http://www.combinatorics.org/ojs/index.php/eljc/article/view/v19i4p56

IPFS File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

zbMATH Keywords

identifying codelexicographic product of graphs

Mathematics Subject Classification ID

Graph operations (line graphs, products, etc.) (05C76) Applications of graph theory (05C90) Combinatorial codes (94B25)

Abstract: Gravier et al. investigated the identifying codes of Cartesian product of two graphs. In this paper we consider the identifying codes of lexicographic product G[H] of a connected graph G and an arbitrary graph H, and obtain the minimum cardinality of identifying codes of G[H] in terms of some parameters of G and H.

Review text

Summary: Let \(G\) be a connected graph and \(H\) be an arbitrary graph. In this paper, we study the identifying codes of the lexicographic product \(G[H]\) of \(G\) and \(H\). We first introduce two parameters of \(H\), which are closely related to identifying codes of \(H\). Then we provide a sufficient and necessary condition for \(G[H]\) to be identifiable. Finally, if \(G[H]\) is identifiable, we determine the minimum cardinality of identifying codes of \(G[H]\) in terms of the order of \(G\) and these two parameters of \(H\).

Recommendations

• Identifying codes in the direct product of a complete graph and some special graphs
• Identifying codes of corona product graphs
• New results of identifying codes in product graphs
• The minimum identifying code graphs
• On identifying codes in the Cartesian product of a path and a complete graph

Cited in

(14)

• Identifying codes of Cartesian product of two cliques of the same size
• Identifying codes in the direct product of a complete graph and some special graphs
• Constructing edge-disjoint Steiner paths in lexicographic product networks
• Optimal identifying codes of two families of Cayley graphs
• Path 3-(edge-)connectivity of lexicographic product graphs
• Improved upper bounds for identifying codes in n-dimensional q-ary cubes
• New results of identifying codes in product graphs
• SPC product codes, graphs with cycles and Kostka numbers
• Characterizing identifying codes from the spectrum of a graph or digraph
• Identifying codes of the direct product of two cliques
• Identifying codes of corona product graphs
• On identifying codes in the Cartesian product of a path and a complete graph
• Identifying codes in the direct product of a path and a complete graph
• Identifying codes in vertex-transitive graphs and strongly regular graphs

This page was built for publication: Identifying codes of lexicographic product of graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1953370)