On the Partition Dimension of Circulant Graphs
Open Access
- 20 October 2016
- journal article
- Published by Oxford University Press (OUP) in The Computer Journal
Abstract
For a vertex v of a connected graph G (V, E) and a subset S of V, the distance between v and S is defined by d(v,S)=min{d(v,x):x∈S}d(v,S)=min{d(v,x):x∈S} . For an ordered k-partition Π={S1,S2,…,Sk}Π={S1,S2,…,Sk} of V, the representation of v with respect to Π is the k-vector r(v∣Π)=(d(v,S1),d(v,S2),…,d(v,Sk))r(v∣Π)=(d(v,S1),d(v,S2),…,d(v,Sk)) . The k-partition Π is a resolving partition if the k-vectors r(v∣Π)r(v∣Π) , v∈Vv∈V are distinct. The minimum k for which there is a resolving k-partition of V is the partition dimension of G. In this paper, we obtain the partition dimension of circulant graphs G=C(n,±{1,2,…,j}),1<j<⌊n2⌋G=C(n,±{1,2,…,j}),1n≥(j+k)(j+1)n≥(j+k)(j+1) and n≡k(mod2j)n≡k(mod2j) as, pd(G)=j+1{whenjisevenandgcd(k,2j)=1,whenjisoddandk=2m,1≤m≤j.pd(G)=j+1{whenjisevenandgcd(k,2j)=1,whenjisoddandk=2m,1≤m≤j.Keywords
All Related Versions
This publication has 19 references indexed in Scilit:
- On the metric dimension of circulant and Harary graphsApplied Mathematics and Computation, 2014
- Packing Odd CircuitsSIAM Journal on Discrete Mathematics, 2007
- Locating and total dominating sets in treesDiscrete Applied Mathematics, 2006
- On the metric dimension of some families of graphsElectronic Notes in Discrete Mathematics, 2005
- Resolving domination in graphsMathematica Bohemica, 2003
- Resolvability in graphs and the metric dimension of a graphDiscrete Applied Mathematics, 2000
- Resolvability and the upper dimension of graphsComputers & Mathematics with Applications, 2000
- The partition dimension of a graphAequationes mathematicae, 2000
- Conditional resolvability in graphs: a surveyInternational Journal of Mathematics and Mathematical Sciences, 2000
- Structure-activity maps for visualizing the graph variables arising in drug designJournal of Biopharmaceutical Statistics, 1993