Identifying codes in vertex-transitive graphs and strongly regular graphs

zbMath1323.05141arXiv1411.5275MaRDI QIDQ888612

Aline Parreau, Sylvain Gravier, Sara Rottey, Élise Vandomme, Storme, L.

Publication date: 2 November 2015

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

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

zbMATH Keywords

strongly regular graphsfinite geometrygeneralized quadranglesidentifying codesmetric dimensionvertex-transitive graphs

Mathematics Subject Classification ID

Association schemes, strongly regular graphs (05E30) Combinatorial aspects of finite geometries (05B25) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Theory of error-correcting codes and error-detecting codes (94B99)

Related Items (11)

Partition dimension of projective planes ⋮ Identifying codes for generalized quadrangles ⋮ Metric dimension of dual polar graphs ⋮ On the metric dimension of incidence graphs ⋮ On the metric dimension of imprimitive distance-regular graphs ⋮ On the metric dimension of incidence graph of M\"obius planes ⋮ On a conjecture regarding identification in Hamming graphs ⋮ On \(t\)-revealing codes in binary Hamming spaces ⋮ Tolerant location detection in sensor networks ⋮ Sufficient conditions for a digraph to admit a \((1, \leq \ell )\)-identifying code ⋮ On the metric dimension of affine planes, biaffine planes and generalized quadrangles

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• On the metric dimension of imprimitive distance-regular graphs
• On identifying codes in binary Hamming spaces
• On graphs having a \(V\setminus \{x\}\) set as an identifying code
• Identifying codes of cycles with odd orders
• New bounds on binary identifying codes
• Identifying codes of Cartesian product of two cliques of the same size
• On the order of uniprimitive permutation groups
• On the ratio of optimal integral and fractional covers
• Minimizing the size of an identifying or locating-dominating code in a graph is NP-hard.
• Rigidity and separation indices of Paley graphs
• Identifying and locating-dominating codes on chains and cycles
• Optimal identifying codes in cycles and paths
• Identifying codes of lexicographic product of graphs
• Extremal graphs for the identifying code problem
• Identifying codes of the direct product of two cliques
• Identifying codes of cycles
• On graphs on \(n\) vertices having an identifying code of cardinality \(\lceil \log_{2}(n+1)\rceil\)
• The metric dimension of small distance-regular and strongly regular graphs
• Base size, metric dimension and other invariants of groups and graphs
• On the Metric Dimension of Cartesian Products of Graphs
• Domination and location in acyclic graphs
• On the Complexity of Canonical Labeling of Strongly Regular Graphs
• PARTIAL QUADRANGLES
• On a new class of codes for identifying vertices in graphs
• Graphs where every k-subset of vertices is an identifying set
• Random strongly regular graphs?

This page was built for publication: Identifying codes in vertex-transitive graphs and strongly regular graphs