2012/03/31 by Robert F. Bailey, R. A. Bailey, José Cáceres +5
Computer Science · Engineering · Mathematics · #1-planar graph #Chordal graph #Combinatorics #Discrete mathematics #Finite Group Theory Research #Graph #Graph Labeling and Dimension Problems #Indifference graph #Mathematics #Metric dimension #graph theory and CDMA systems #math.CO #msc:05B05 #msc:05C12 #msc:05E30 #msc:51E14
paper · pdf · doi:10.1016/j.ejc.2012.10.008
published as European Journal of Combinatorics 34 (2013), 736--751 · 23 pages, 2 figures, 1 table
arxiv created 2012/10/24 · openalex publication_date 2012/12/05 · arxiv updated 2014/02/10 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/05
A set of vertices S in a graph G is a \em resolving set for G if, for any two vertices u,v, there exists x∈ S such that the distances d(u,x) ≠ d(v,x). In this paper, we consider the Johnson graphs J(n,k) and Kneser graphs K(n,k), and obtain various constructions of resolving sets for these graphs. As well as general constructions, we show that various interesting combinatorial objects can be used to obtain resolving sets in these graphs, including (for Johnson graphs) projective planes and symmetric designs, as well as (for Kneser graphs) partial geometries, Hadamard matrices, Steiner systems and toroidal grids.