Resolving Sets And Metric Dimension For Q-Kneser Graphs And Attenuated Q-Kneser Graphs

Let G be a finite graph.A set of vertices S in a graph G is a resolving set for G if,for any two vertices u and v,there exists x ∑ S such that the distances d(u,x)≠ d(v,x).The metric dimension of G,denoted μ(G),is the smallest size of a resolving set for G.Let q be a prime power,and let V(n,q)denote the n-dimensional vector space over the finite filed Fq.We use Kq(n,k)to denote q-Kneser graph of V(n,q).Let l and k be two fixed positive integers such that l ≥ k ≥ 2.Let AKq(l,k)denote attenuated q-Kneser graph of V(l + k,q).In this paper,we study the resolving sets of q-Kneser graph Kq(n,k)and attenuated q-Kneser graph AKq(l,K),and find an upper bound on the metric dimension of them.The following are our main results:1.If(2k-1)|n,we construct the resolving set M = ∪i=1 m {U(?)Wi|dim(U)= k} of q-Kneser graph Kq(n,k)and find an upper bound on the metric dimension of it.If(2k-1)| n,we construct the resolving set M = ∪i=1 m {U(?)Wi | dim(U)=k}{∪U j=1 l{U(?)Xj(?)Z| dim(U)= k} of q-Kneser graph Kq(n,k)and find an upper bound on the metric dimension of it.2.If l ≥ 3k-2,we construct the resolving set M = ∪i=1 m {U(?)Wi|dim(U)=k,U ∩ N = 0} of attenuated q-Kneser graph AKq(l,k)and find an upper bound on the metric dimension of it.If k ≤ l ≤ 3k-3,we construct the resolving set M = ∪ i=1 m { U(?)Wi|U ∩ N=0,dim(U)= k} of attenuated q-Kneser graph AKq(l,k)and find an upper bound on the metric dimension of it.