Identifying codes in line graphs

DOI10.1002/JGT.21686MaRDI QIDQ5325952zbMATH OpenOpenAlexFDO

Authors Florent Foucaud, Sylvain Gravier, Reza Naserasr, Aline Parreau, Petru Valicov

Publication date 31 July 2013

Published in Journal of Graph Theory (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1107.0207

zbMATH Keywords

NP-completenessdominating setsidentifying codesline graphs

Mathematics Subject Classification ID

Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Graph operations (line graphs, products, etc.) (05C76)

Abstract: An identifying code of a graph is a subset of its vertices such that every vertex of the graph is uniquely identified by the set of its neighbours within the code. We study the edge-identifying code problem, i.e. the identifying code problem in line graphs. If $ID(G)$ denotes the size of a minimum identifying code of an identifiable graph $G$, we show that the usual bound $ID(G)gelceillo{g}_2(n+1)ceil$, where $n$ denotes the order of $G$, can be improved to $Theta(sqrtn)$ in the class of line graphs. Moreover, this bound is tight. We also prove that the upper bound $ID(mathcalL(G))leq2|V(G)|-5$, where $mathcalL(G)$ is the line graph of $G$, holds (with two exceptions). This implies that a conjecture of R. Klasing, A. Kosowski, A. Raspaud and the first author holds for a subclass of line graphs. Finally, we show that the edge-identifying code problem is NP-complete, even for the class of planar bipartite graphs of maximum degree~3 and arbitrarily large girth.

Recommendations

• Edge identifying codes
• Extremal graphs for the identifying code problem
• Identifying codes in line digraphs
• Identifying codes in trees and planar graphs
• Bounds for identifying codes in terms of degree parameters

Cites work

• Approximability of identifying codes and locating-dominating codes
• Characterizations of derived graphs
• Extremal cardinalities for identifying and locating-dominating codes in graphs
• Extremal graphs for the identifying code problem
• Hardness results and approximation algorithms for identifying codes and locating-dominating codes in graphs
• Line perfect graphs
• Minimal identifying codes in trees and planar graphs with large girth
• Minimizing the size of an identifying or locating-dominating code in a graph is NP-hard.
• New identifying codes in the binary Hamming space
• On a new class of codes for identifying vertices in graphs
• On graphs having a \(V\setminus \{x\}\) set as an identifying code
• On graphs on \(n\) vertices having an identifying code of cardinality \(\lceil \log_{2}(n+1)\rceil\)
• On the size of identifying codes in triangle-free graphs
• The Complexity of Multiterminal Cuts
• The monadic second-order logic of graphs. I: Recognizable sets of finite graphs

Cited in

(34)

• Bounds on the identifying codes in trees
• On three domination-based identification problems in block graphs
• More results on the complexity of identifying problems in graphs
• Unique (optimal) solutions: complexity results for identifying and locating-dominating codes
• Identifying codes in hereditary classes of graphs and VC-dimension
• Separating path systems of almost linear size
• Revisiting and improving upper bounds for identifying codes
• Bounds for identifying codes in terms of degree parameters
• Polyhedra associated with identifying codes in graphs
• Progress on the description of identifying code polyhedra for some families of split graphs
• On the watching number of graphs
• Study of identifying code polyhedra for some families of split graphs
• Watching systems of triangular graphs
• Locating-domination and identification
• Algorithms and complexity for metric dimension and location-domination on interval and permutation graphs
• On three domination-based identification problems in block graphs
• On the path separation number of graphs
• Decision and approximation complexity for identifying codes and locating-dominating sets in restricted graph classes
• Identifying path covers in graphs
• A linear-time algorithm for the identifying code problem on block graphs
• Location-domination in line graphs
• Operads of finite posets
• Optimal identification of sets of edges using 2-factors
• Identifying codes and watching systems in Kneser graphs
• Partial linear spaces and identifying codes
• On the minimum size of an identifying code over all orientations of a graph
• Extremal graphs for the identifying code problem
• Identifying codes in line digraphs
• Complexity and approximation for discriminating and identifying code problems in geometric setups
• Edge identifying codes
• Identification, location-domination and metric dimension on interval and permutation graphs. I: Bounds.
• Bounding the trace function of a hypergraph with applications
• Identification, location-domination and metric dimension on interval and permutation graphs. II: Algorithms and complexity
• On the (adjacency) metric dimension of corona and strong product graphs and their local variants: combinatorial and computational results

This page was built for publication: Identifying codes in line graphs

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