Identifying Codes in Line Graphs
From MaRDI portal
Publication:5325952
DOI10.1002/jgt.21686zbMath1269.05092arXiv1107.0207OpenAlexW3124539444MaRDI QIDQ5325952
Florent Foucaud, Aline Parreau, Reza Naserasr, Petru Valicov, Sylvain Gravier
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
Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Graph operations (line graphs, products, etc.) (05C76)
Related Items
More results on the complexity of identifying problems in graphs, Identifying Codes in Hereditary Classes of Graphs and VC-Dimension, On the path separation number of graphs, Location-domination in line graphs, Identification, location-domination and metric dimension on interval and permutation graphs. II: Algorithms and complexity, Optimal identification of sets of edges using 2-factors, Identifying path covers in graphs, Identifying codes in line digraphs, Complexity and approximation for discriminating and identifying code problems in geometric setups, 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, Identifying codes and watching systems in Kneser graphs, Unnamed Item, Unique (optimal) solutions: complexity results for identifying and locating-dominating codes, Identification, location-domination and metric dimension on interval and permutation graphs. I: Bounds., Progress on the description of identifying code polyhedra for some families of split graphs, Polyhedra associated with identifying codes in graphs, Operads of finite posets, On the minimum size of an identifying code over all orientations of a graph, Bounds on the identifying codes in trees, Decision and approximation complexity for identifying codes and locating-dominating sets in restricted graph classes, Locating-Domination and Identification, Algorithms and Complexity for Metric Dimension and Location-domination on Interval and Permutation Graphs, Unnamed Item, Bounding the trace function of a hypergraph with applications
Cites Work
- Unnamed Item
- On the size of identifying codes in triangle-free graphs
- Extremal cardinalities for identifying and locating-dominating codes in graphs
- On graphs having a \(V\setminus \{x\}\) set as an identifying code
- New identifying codes in the binary Hamming space
- 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.
- Approximability of identifying codes and locating-dominating codes
- Extremal graphs for the identifying code problem
- On graphs on \(n\) vertices having an identifying code of cardinality \(\lceil \log_{2}(n+1)\rceil\)
- The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
- Line perfect graphs
- The Complexity of Multiterminal Cuts
- On a new class of codes for identifying vertices in graphs
- Characterizations of derived graphs
