Identifying codes in line graphs

DOI10.1002/JGT.21686zbMATH Open1269.05092arXiv1107.0207OpenAlexW3124539444MaRDI QIDQ5325952FDOQ5325952

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)

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.

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

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

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)

Cites Work

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

Cited In (34)

• Bounds on the identifying codes in trees
• More results on the complexity of identifying problems in graphs
• Unique (optimal) solutions: complexity results for identifying and locating-dominating codes
• Separating path systems of almost linear size
• Identifying codes in hereditary classes of graphs and VC-dimension
• Revisiting and improving upper bounds for identifying codes
• Bounds for identifying codes in terms of degree parameters
• On the watching number of graphs
• Polyhedra associated with identifying codes in graphs
• Progress on the description of identifying code polyhedra for some families of split graphs
• Study of identifying code polyhedra for some families of split graphs
• Watching systems of triangular graphs
• On three domination-based identification problems in block graphs
• Locating-domination and identification
• Algorithms and complexity for metric dimension and location-domination on interval and permutation graphs
• Decision and approximation complexity for identifying codes and locating-dominating sets in restricted graph classes
• On the path separation number of graphs
• A linear-time algorithm for the identifying code problem on block graphs
• Identifying path covers in 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
• Complexity and approximation for discriminating and identifying code problems in geometric setups
• Identifying codes in line digraphs
• 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
• On three domination-based identification problems in block graphs

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)