Resolving sets for Johnson and Kneser graphs

Details Resolving sets for Johnson and Kneser graphs Resolving sets for Johnson and Kneser graphs

2012-03-12

arxiv.org/abs/1203.2660v1

Mathematics

Combinatorics

23 pages, 4 figues, 1 table

Scientific paper

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\in S$ such that the distances $d(u,x) \neq 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) Hadamard matrices, Steiner systems, partial geometries and toroidal grids.

Affiliated with

Also associated with

No associations

Rating

Resolving sets for Johnson and Kneser graphs does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Resolving sets for Johnson and Kneser graphs, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Resolving sets for Johnson and Kneser graphs will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-143194