# Minimum Partition of anr−Independence System

Authors: Zill-e-Shams; Muhammad Salman; Zafar Ullah; Usman Ali
Journal: Journal of Mathematics
 (2021)

---

## Abstract

Graph partitioning has been studied in the discipline between computer science and applied mathematics. It is a technique to distribute the whole graph data as a disjoint subset to a different device. The minimum graph partition problem with respect to an independence system of a graph has been studied in this paper. The considered independence system consists of one of the independent sets defined by Boutin. We solve the minimum partition problem in path graphs, cycle graphs, and wheel graphs. We supply a relation of twin vertices of a graph with its independence system. We see that a maximal independent set is not always a minimal set in some situations. We also provide realizations about the maximum cardinality of a minimum partition of the independence system. Furthermore, we study the comparison of the metric dimension problem of a graph with the minimum partition problem of that graph.


---

## Body

## 1. Introduction

An abstract idea of representing any objects which are connected to each other in a form of relation is a graph. In this representation, the object is called as a vertex and their relation denotes as an edge. Partition of a graph is the distribution of the whole graph data into disjoint subsets to different devices. The need of distributing huge graph data set is to process data efficiently and faster process of any graph related applications. Where graph partitioning is essential and applicable are given as follows:(1)
Complex networks which include biological networks (in solving biological interaction problem in a huge a biological network), social networks (Facebook, Twitter, and LinkedIn etc., and graph partitioning technology is used to process user query efficiently, as replying a query in a distributed manner is very handy and effective) [1], and transportation networks (graph partitioning can speed up and could be effective in planning a route by using a GPS (global positioning system) tool in the digital era).(2)
PageRank, which is an application used to compute the rank of web rank from web network.(3)
VLSI design: Very large-scale integration (VLSI) system is one of the graph partitioning problems in order to reduce the connection between circuits in designing VLSI. The main objective of this partitioning is to reduce the VLSI design complexity by splitting them into a smaller component.(4)
Image processing: Graph partitioning is one of the most attractive tools to split into several components of a picture, where pixels are denoted by vertices and if there are similarities between pixels are represented as edges [2].Inspired by these interesting applications of graph partition, we consider a graph partition in the context of resolving set of a graph, which is a well-known parameter in graph theory and having remarkable application in network discovery and verification.Aset system is a finite set S together with a family ℱ of subsets of S and is denoted by the pair S,ℱ. A set system S,P is said to be an independence system if for every subset X of S possessing property P, each proper subset of X also possesses the property P, i.e., for each X⊂S such that X∈P, Y∈P for all Y⊂X. Actually, in an independence system S,P, P identified with the family of subsets of S possessing the property P. A subset X of S which possess the property P is said to be an independent set and dependent set otherwise. The chromatic number of S,P is the smallest natural number n such that S can be partitioned into n independent sets and is denoted by χS,P. Clearly, a partition of S into n independent sets of S,P can be identified by a coloring λ:S⟶1,2,…,n of S such that for each color c∈1,2,…,n, the color class s∈S,λs=c has the property P, and vice versa. The coloring λ of S is called a P−coloring of S. Thus, χS,P is the least number of colors required by a P−coloring of S and is also called the P−chromatic number of S [3].TheP−chromatic number χS,P has been extensively studied by various graph theorists. Remarkable work has been done when S is V or E for a graph G having vertex set V and edge set E, and P is a hereditary graphical property. For example, if P is the property ℐ of being a vertex independent set, then χV,ℐ is the ordinary chromatic number of G; if P is the property E of being an edge independent set, then χE,E is the edge chromatic number of G; if P is the property ℱ of being a forest, then χE,ℱ is the arboricity of G. In the next section, we consider P as the property ℛ of being a resolving set for G and define the ℛ−chromatic number of G associated with an r−independence system V,ℛ.


## 2.r−Independence System

Hereafter, we consider nontrivial, simple, and connected graphG with vertex set V and edge set E. We denote two adjacent vertices u and v in G by u∼v and nonadjacent vertices by u≁v. The distance d:V×V⟶ℤ+∪0 is the length of a shortest path between two vertices in the pair u,v∈V×V and is denoted by du,v. The maximum distance between the vertices of G is called the diameter of G, denoted by diamG. Two vertices u and v in G are antipodal or diametral if du,v=diamG; otherwise, they are nonantipodal.LetG be a graph. For any vertex v of G, the metric code or code of v with respect to an ordered k−subset W=w1,w2,…,wk of V is defined as(1)cWv=dv,w1,dv,w2,…,dv,wk.An orderedk−subset W of V is a resolving set for G if cWu≠cWv for every pair of vertices u,v∈V×V. The cardinality of a minimum resolving set for G is called the metric dimension of G, denoted by dimG or βG. A resolving set for G of cardinality dimG is called a metric basis or a basis of G [4–8]. In [9], it was found and, in [6], an explicit construction was given that finding the metric dimension of a graph is NP-hard. The concept of a resolving set, other than graph theory, is applied in many other areas such as coin-weighing problems [10], network discovery and verification [2], strategies for mastermind games [11], pharmaceutical chemistry [12], robot navigation [6], connected joins in graphs and combinatorial optimization [13], and sonar and coast guard Loran [8].A subsetS of the vertex set V of a graph G is an r−independent set if no proper subset of S is a resolving set for G. We denote ℛ as the property of being an r−independent set. That is, a subset S of V possesses the property ℛ if and only if S is an r−independent set. This concept was firstly introduced by Boutin and used the term res-independent set [14]. For simplicity, we use the term r−independent set rather than res-independent set. A family of subsets of V possessing the property ℛ is defined as(2)V,ℛ=S⊂V|Spossesses the propertyℛ.Thus, we have a set systemV,ℛ consisting of those subsets of V which are possessing the property ℛ and is called the r−independence system. All the subsets possessing the property ℛ may or may not be resolving. This was an error made by Boutin in [14], and we rectified it in [15].Remark 1.
For a setS⊂V, the following assertions are equivalent:(1)
S∈V,ℛ(2)
S possesses the property ℛ(3)
S is an r−independent setRemark 2.
LetG be a graph with vertex set V of order n. Then,(1)
v∈V,ℛ for each v∈V obviously(2)
V∉V,ℛ, because every n−1−subset of V is a resolving set for G(3)
a minimal resolving set forG is a maximal r−independent set, but converse is not always true [15]


### 2.1. Minimum Partition Problem

For a connected graphG=V,E and the r-independence system V,ℛ, the minimum partition problem is to make a partition of V into the minimum number of subsets possessing the property ℛ.The least natural numberk, such that V can be partitioned into k subsets possessing the property ℛ, is called the resolving chromatic number of G associated with V,ℛ, denoted by χrV,ℛ. A coloring λ:V⟶1,2,…,k of V such that for each color c∈1,2,…,k, the color class v∈V,λv=c possesses the property ℛ is called an ℛ−coloring of V. Thus, χrV,ℛ is the least number of colors required by an ℛ−coloring of V and is also called the ℛ−chromatic number of G.Example 1.
LetG be a graph with V=v1,v2,v3,v4 and E=v1∼v2,v2∼v3,v3∼v4,v4∼v1. Then only two colors are needed to properly color V, and it follows that the ordinary chromatic number χG=2 with color classes v1,v3 and v2,v4. The metric dimension of G is 2 and two nonantipodal vertices of G form a basis of G [4]. Accordingly, no 3−element subset of V possess the property ℛ and so the r−independence system is(3)V,ℛ=vi,v1,v2,v2,v3,v3,v4,v4,v1,v1,v3,v2,v4;1≤i≤4.
The minimum partition ofV according to ℛ−coloring of V consists of two 2−element subsets of V from V,ℛ, and hence, χrV,ℛ=2.In the above example, we obtained that the chromatic number andℛ−chromatic number of a graph G are same. But, it is not necessary that these numbers are always same.Example 2.
LetG be a graph with V=v1,v2,v3,v4 and E=v1∼v2,v2∼v3,v3∼v4. Then only two colors are needed to properly color V, and it follows that the ordinary chromatic number χG=2 with color classes v1,v3 and v2,v4. The metric dimension of G is 1, and v1,v4 are the only two bases of G [4, 6]. Accordingly, each 2−element subset of V is a resolving set for G, and so no 3−element subset of V possess the property ℛ. Thus, the r−independence system is(4)V,ℛ=vi,v2,v3;1≤i≤4.
The minimum partition ofV according to ℛ−coloring of V consists of two bases sets and the set v2,v3 from V,ℛ. Hence, χrV,ℛ=3.It is observed, from Examples1 and 2, that χG≤χrV,ℛ. But, it is not true generally as, in the next example, we have a have a graph G such that χG>χrV,ℛ.Example 3.
LetG be a graph with V=v1,v2,v3 and E=v1∼v2,v2∼v3,v3∼v1. Then, three colors are required to properly color V, and it follows that the ordinary chromatic number χG=3 with color classes v1,v2 and v3. The metric dimension of G is 2 and any two vertices of G can form a basis of G [4]. Accordingly, the 3−element set V does not possess the property ℛ and so the r−independence system is(5)V,ℛ=vi,v1,v2,v2,v3,v3,v1;1≤i≤3.
The minimum partition ofV according to ℛ−coloring of V consists of one singleton set v and one 2−element set V−v from V,ℛ, and hence χrV,ℛ=2.Example 4.
LetG be a graph with V=v1,v2,v3,v4,v5 and E=v1∼v2,v2∼v3,v3∼v4,v3∼v5. Then two colors are required to properly color V, and it follows that the ordinary chromatic number χG=2 with color classes v2,v4,v5 and v1,v3. The metric dimension of G is 2 and v4,v5 is a set of basis of G [4]. But the set of three elements v1,v2,v3 which is not resolving set of G possess the property ℛ and so the r−independence system is(6)V,ℛ=vi,v1,v2,v1,v3,v1,v4,v1,v5,v2,v3,v2,v4,v2,v5,v1,v2,v3;1≤i≤5.
The minimum partition ofV according to ℛ−coloring of V consists of one 2−element set and one 3−element set V−v from V,ℛ, and hence χrV,ℛ=2.


## 2.1. Minimum Partition Problem

For a connected graphG=V,E and the r-independence system V,ℛ, the minimum partition problem is to make a partition of V into the minimum number of subsets possessing the property ℛ.The least natural numberk, such that V can be partitioned into k subsets possessing the property ℛ, is called the resolving chromatic number of G associated with V,ℛ, denoted by χrV,ℛ. A coloring λ:V⟶1,2,…,k of V such that for each color c∈1,2,…,k, the color class v∈V,λv=c possesses the property ℛ is called an ℛ−coloring of V. Thus, χrV,ℛ is the least number of colors required by an ℛ−coloring of V and is also called the ℛ−chromatic number of G.Example 1.
LetG be a graph with V=v1,v2,v3,v4 and E=v1∼v2,v2∼v3,v3∼v4,v4∼v1. Then only two colors are needed to properly color V, and it follows that the ordinary chromatic number χG=2 with color classes v1,v3 and v2,v4. The metric dimension of G is 2 and two nonantipodal vertices of G form a basis of G [4]. Accordingly, no 3−element subset of V possess the property ℛ and so the r−independence system is(3)V,ℛ=vi,v1,v2,v2,v3,v3,v4,v4,v1,v1,v3,v2,v4;1≤i≤4.
The minimum partition ofV according to ℛ−coloring of V consists of two 2−element subsets of V from V,ℛ, and hence, χrV,ℛ=2.In the above example, we obtained that the chromatic number andℛ−chromatic number of a graph G are same. But, it is not necessary that these numbers are always same.Example 2.
LetG be a graph with V=v1,v2,v3,v4 and E=v1∼v2,v2∼v3,v3∼v4. Then only two colors are needed to properly color V, and it follows that the ordinary chromatic number χG=2 with color classes v1,v3 and v2,v4. The metric dimension of G is 1, and v1,v4 are the only two bases of G [4, 6]. Accordingly, each 2−element subset of V is a resolving set for G, and so no 3−element subset of V possess the property ℛ. Thus, the r−independence system is(4)V,ℛ=vi,v2,v3;1≤i≤4.
The minimum partition ofV according to ℛ−coloring of V consists of two bases sets and the set v2,v3 from V,ℛ. Hence, χrV,ℛ=3.It is observed, from Examples1 and 2, that χG≤χrV,ℛ. But, it is not true generally as, in the next example, we have a have a graph G such that χG>χrV,ℛ.Example 3.
LetG be a graph with V=v1,v2,v3 and E=v1∼v2,v2∼v3,v3∼v1. Then, three colors are required to properly color V, and it follows that the ordinary chromatic number χG=3 with color classes v1,v2 and v3. The metric dimension of G is 2 and any two vertices of G can form a basis of G [4]. Accordingly, the 3−element set V does not possess the property ℛ and so the r−independence system is(5)V,ℛ=vi,v1,v2,v2,v3,v3,v1;1≤i≤3.
The minimum partition ofV according to ℛ−coloring of V consists of one singleton set v and one 2−element set V−v from V,ℛ, and hence χrV,ℛ=2.Example 4.
LetG be a graph with V=v1,v2,v3,v4,v5 and E=v1∼v2,v2∼v3,v3∼v4,v3∼v5. Then two colors are required to properly color V, and it follows that the ordinary chromatic number χG=2 with color classes v2,v4,v5 and v1,v3. The metric dimension of G is 2 and v4,v5 is a set of basis of G [4]. But the set of three elements v1,v2,v3 which is not resolving set of G possess the property ℛ and so the r−independence system is(6)V,ℛ=vi,v1,v2,v1,v3,v1,v4,v1,v5,v2,v3,v2,v4,v2,v5,v1,v2,v3;1≤i≤5.
The minimum partition ofV according to ℛ−coloring of V consists of one 2−element set and one 3−element set V−v from V,ℛ, and hence χrV,ℛ=2.


## 3. Three Well-Known Families

In this section, we consider families of path graphs, cycle graphs, and wheel graphs and solve the minimum partition problem for each family.


### 3.1. Path Graphs

A path graphPn, for n≥2, has vertex set V=v1,v2,…,vn and edge set E=vi∼vi+1;1≤i≤n−1. The following result describes which subset of the vertex set of a path graph possesses the property ℛ.Lemma 1.
No3−element subset of the vertex set V of a path graph G possess the property ℛ.Proof.
AsdimG=1 and only each end vertex of G forms a basis of G [6], every 2−element subset of V is a resolving set for G. Consequently, no 3−element subset of V possess the property ℛ.The next result investigates the number of subsets of the vertex set of a path graph possessing the propertyℛ.Lemma 2.
For alln≥2, if G is a path graph with vertex set V, then V,ℛ=1/2n2−3n+6.Proof.
According to Lemma1, each singleton subset of V as well as each 2−element subset of V−v1,vn possesses the property ℛ. It follows that for n=2,3, V,ℛ=vi;1≤i≤n, and for all n>3,(7)V,ℛ=vi;1≤i≤n∪V2,where V2 denotes the collection of all the n−22 and 2−element subsets of V−v1,vn. Hence,(8)V,ℛ=n+n−22=12n2−3n+6.The following result solves the minimum partition problem for a path graph.Theorem 1.
For alln≥2, the vertex set V of a path graph can be partitioned into ⌊n+3/2⌋ minimum number of subsets possessing the property ℛ.Proof.
Let the color classes, due to a coloringλ:V⟶1,2,…,⌊n+3/2⌋ of V, areWhenn is even, then C1=v1,C2=vn and Ci+1=vi,vn−i+1; 2≤i≤n−2/2Whenn is odd, then C1=v1,C2=vn+1/2,C3=vn and Ci+2=vi,vn−i+1; 2≤i≤n−3/2
In both cases, all these color classes are lying inV,ℛ, by Lemma 2. It follows that λ is an ℛ−coloring of V, and these color classes define a partition of V into the sets possessing the property ℛ. Further, any partition of V of cardinality less than ⌊n+3/2⌋ contains at least one 2−element or 3−element subset S of V such that S∈V,ℛ. Thus, a minimum partition of V has ⌊n+3/2⌋ subsets of V possessing the property ℛ.


### 3.2. Cycle Graphs

A cycle graphCn, for n≥3, has vertex set V=v1,v2,…,vn and edge set E=vi∼vi+1,vn∼v1;1≤i≤n−1. In the next result, we investigate which subset of the vertex set of a cycle graph possesses the property ℛ is.Lemma 3.
A subset of the vertex setV of a cycle graph G which possess the property ℛ is a singleton set or a 2−element set.Proof.
In [4, 5], it was shown that dimG=2 and any two nonantipodal vertices of G form a basis of G. Further note that, a 3−element subset S of V, whether containing two antipodal vertices or not, is not an r−independent set. It completes the proof.The number of subsets of the vertex set of a cycle graph possessing the propertyℛ is counted in the following result.Lemma 4.
For alln≥3, if G is a cycle graph with vertex set V, then V,ℛ=1/2n2+n.Proof.
Lemma3 yields that each singleton subset of V as well as each 2−element subset of V possesses the property ℛ. It follows that for all n≥3,(9)V,ℛ=vi;1≤i≤n∪V2,where V2 denotes the collection of all the n2, 2−element subsets of V. Hence,(10)V,ℛ=n+n2=12n2+n.The minimum partition problem for a cycle graph is solved in the following result.Theorem 2.
For alln≥3, the vertex set V of a cycle graph can be partitioned into ⌈n/2⌉ minimum number of subsets possessing the property ℛ.Proof.
Let the color classes, due to a coloringλ:V⟶1,2,…,⌈n/2⌉ of V, are as follows:Whenn is even, then Ci=vi,vn−i+1; 1≤i≤n/2.Whenn is odd, then C1=v1 and Ci=vi,vn−i+2; 2≤i≤n+1/2.
In both the cases, all these color classes are lying inV,ℛ, by Lemma 4. It follows that λ is an ℛ−coloring of V, and these color classes define a partition of V into the sets possessing the property ℛ. Further, any partition of V of cardinality less than ⌈n/2⌉ contains at least one 3−element subset S of V such that S∈V,ℛ. Thus, a minimum partition of V has ⌈n/2⌉ subsets of V possessing the property ℛ.


### 3.3. Wheel Graphs

Forn≥3, let Cn:v1∼v2∼⋯∼vn∼v1 be a cycle and K1 be the trivial graph with vertex v. Then a wheel graph is the sum Wn=K1+Cn with vertex set V=v,vi;1≤i≤n and edge set E=v∼vi;1≤i≤n∪ECn. For fixed i; 1≤i≤n, let a path P:vi∼vi+1∼⋯∼vi+n−5 of order n−4 on the cycle Cn of Wn, where the indices greater than n or less than zero will be take modulo n. The following result describes the sets in Wn possessing the property ℛ for n≥8.Remark 3.
Forn≥8, let Wn be a wheel graph with vertex set u. Let V be set of any vi,i=1,…,n−4 consecutive vertices of wheel graph, then V is a maximal independent set which is not a minimal resolving set.Lemma 5.
Forn≥8, let Wn be a wheel graph with vertex set V. Then,(1)
everyk−element subset of the set S=VP∪v belongs to V,ℛ for 1≤k≤n−3(2)
everyk−element subset of the set V−S belongs to V,ℛ for 1≤k≤4Proof.
(1)
For fixedi; 1≤i≤n, S=v,vj;i≤j≤i+n−5. Since dvi+n−2,v=1=dvi+n−3,v and dvi+n−2,u=1=dvi+n−3,u for each u∈VP, cWvi+n−2=cWvi+n−3 for any W⊆S. It follows the required result.
(2)
Note thatV−S=vi+n−1,vi+n−2,vi+n−3,vi+n−4. For any x,y∈S−v,vi,vi+n−5 and dx,w=2=dy,w for each w∈V−S. This implies that cWx=cWy for any W⊆V−S. Hence, the required result followed.For wheel graphs, the following result solves the minimum partition problem.Theorem 3.
Forn≥3, let Wn be a wheel graph with vertex set V. Then,(11)χrV,ℛ=2,whenn≠5,6,7,3,whenn=5,6,7.Proof.
It can be easily seen that a partition(i)
v1,v2,v3,v is a minimum partition of V having sets possessing the property ℛ in W3,(ii)
v1,v3,v,v2,v4 is a minimum partition of V having sets possessing the property ℛ in W4,(iii)
v1,v2,v3,v4,v5,v is a minimum partition of V having sets possessing the property ℛ in W5,(iv)
v,v1,v2,v3,v4,v5,v6 is a minimum partition of V having sets possessing the property ℛ in W6, and(v)
v1,v2,v3,v4,v5,v6,v7,v is a minimum partition of V having sets possessing the property ℛ in W7.
It follows thatχrV,ℛ is 2 when n=3,4 and is 3 when n=5,6,7.
For alln≥8, let λ:V⟶1,2 be a coloring of V and let the corresponding color classes are C1=VP∪v, where P:vi∼vi+1∼⋯∼vi+n−5 for any fixed 1≤i≤n, and C2=V−C1. Then C1 and C2 define a partition of V. Also, Lemma 5 yields that both C1 and C2 possess the property ℛ. Therefore, λ is an ℛ−coloring of V, and hence χrV,ℛ=2.


## 3.1. Path Graphs

A path graphPn, for n≥2, has vertex set V=v1,v2,…,vn and edge set E=vi∼vi+1;1≤i≤n−1. The following result describes which subset of the vertex set of a path graph possesses the property ℛ.Lemma 1.
No3−element subset of the vertex set V of a path graph G possess the property ℛ.Proof.
AsdimG=1 and only each end vertex of G forms a basis of G [6], every 2−element subset of V is a resolving set for G. Consequently, no 3−element subset of V possess the property ℛ.The next result investigates the number of subsets of the vertex set of a path graph possessing the propertyℛ.Lemma 2.
For alln≥2, if G is a path graph with vertex set V, then V,ℛ=1/2n2−3n+6.Proof.
According to Lemma1, each singleton subset of V as well as each 2−element subset of V−v1,vn possesses the property ℛ. It follows that for n=2,3, V,ℛ=vi;1≤i≤n, and for all n>3,(7)V,ℛ=vi;1≤i≤n∪V2,where V2 denotes the collection of all the n−22 and 2−element subsets of V−v1,vn. Hence,(8)V,ℛ=n+n−22=12n2−3n+6.The following result solves the minimum partition problem for a path graph.Theorem 1.
For alln≥2, the vertex set V of a path graph can be partitioned into ⌊n+3/2⌋ minimum number of subsets possessing the property ℛ.Proof.
Let the color classes, due to a coloringλ:V⟶1,2,…,⌊n+3/2⌋ of V, areWhenn is even, then C1=v1,C2=vn and Ci+1=vi,vn−i+1; 2≤i≤n−2/2Whenn is odd, then C1=v1,C2=vn+1/2,C3=vn and Ci+2=vi,vn−i+1; 2≤i≤n−3/2
In both cases, all these color classes are lying inV,ℛ, by Lemma 2. It follows that λ is an ℛ−coloring of V, and these color classes define a partition of V into the sets possessing the property ℛ. Further, any partition of V of cardinality less than ⌊n+3/2⌋ contains at least one 2−element or 3−element subset S of V such that S∈V,ℛ. Thus, a minimum partition of V has ⌊n+3/2⌋ subsets of V possessing the property ℛ.


## 3.2. Cycle Graphs

A cycle graphCn, for n≥3, has vertex set V=v1,v2,…,vn and edge set E=vi∼vi+1,vn∼v1;1≤i≤n−1. In the next result, we investigate which subset of the vertex set of a cycle graph possesses the property ℛ is.Lemma 3.
A subset of the vertex setV of a cycle graph G which possess the property ℛ is a singleton set or a 2−element set.Proof.
In [4, 5], it was shown that dimG=2 and any two nonantipodal vertices of G form a basis of G. Further note that, a 3−element subset S of V, whether containing two antipodal vertices or not, is not an r−independent set. It completes the proof.The number of subsets of the vertex set of a cycle graph possessing the propertyℛ is counted in the following result.Lemma 4.
For alln≥3, if G is a cycle graph with vertex set V, then V,ℛ=1/2n2+n.Proof.
Lemma3 yields that each singleton subset of V as well as each 2−element subset of V possesses the property ℛ. It follows that for all n≥3,(9)V,ℛ=vi;1≤i≤n∪V2,where V2 denotes the collection of all the n2, 2−element subsets of V. Hence,(10)V,ℛ=n+n2=12n2+n.The minimum partition problem for a cycle graph is solved in the following result.Theorem 2.
For alln≥3, the vertex set V of a cycle graph can be partitioned into ⌈n/2⌉ minimum number of subsets possessing the property ℛ.Proof.
Let the color classes, due to a coloringλ:V⟶1,2,…,⌈n/2⌉ of V, are as follows:Whenn is even, then Ci=vi,vn−i+1; 1≤i≤n/2.Whenn is odd, then C1=v1 and Ci=vi,vn−i+2; 2≤i≤n+1/2.
In both the cases, all these color classes are lying inV,ℛ, by Lemma 4. It follows that λ is an ℛ−coloring of V, and these color classes define a partition of V into the sets possessing the property ℛ. Further, any partition of V of cardinality less than ⌈n/2⌉ contains at least one 3−element subset S of V such that S∈V,ℛ. Thus, a minimum partition of V has ⌈n/2⌉ subsets of V possessing the property ℛ.


## 3.3. Wheel Graphs

Forn≥3, let Cn:v1∼v2∼⋯∼vn∼v1 be a cycle and K1 be the trivial graph with vertex v. Then a wheel graph is the sum Wn=K1+Cn with vertex set V=v,vi;1≤i≤n and edge set E=v∼vi;1≤i≤n∪ECn. For fixed i; 1≤i≤n, let a path P:vi∼vi+1∼⋯∼vi+n−5 of order n−4 on the cycle Cn of Wn, where the indices greater than n or less than zero will be take modulo n. The following result describes the sets in Wn possessing the property ℛ for n≥8.Remark 3.
Forn≥8, let Wn be a wheel graph with vertex set u. Let V be set of any vi,i=1,…,n−4 consecutive vertices of wheel graph, then V is a maximal independent set which is not a minimal resolving set.Lemma 5.
Forn≥8, let Wn be a wheel graph with vertex set V. Then,(1)
everyk−element subset of the set S=VP∪v belongs to V,ℛ for 1≤k≤n−3(2)
everyk−element subset of the set V−S belongs to V,ℛ for 1≤k≤4Proof.
(1)
For fixedi; 1≤i≤n, S=v,vj;i≤j≤i+n−5. Since dvi+n−2,v=1=dvi+n−3,v and dvi+n−2,u=1=dvi+n−3,u for each u∈VP, cWvi+n−2=cWvi+n−3 for any W⊆S. It follows the required result.
(2)
Note thatV−S=vi+n−1,vi+n−2,vi+n−3,vi+n−4. For any x,y∈S−v,vi,vi+n−5 and dx,w=2=dy,w for each w∈V−S. This implies that cWx=cWy for any W⊆V−S. Hence, the required result followed.For wheel graphs, the following result solves the minimum partition problem.Theorem 3.
Forn≥3, let Wn be a wheel graph with vertex set V. Then,(11)χrV,ℛ=2,whenn≠5,6,7,3,whenn=5,6,7.Proof.
It can be easily seen that a partition(i)
v1,v2,v3,v is a minimum partition of V having sets possessing the property ℛ in W3,(ii)
v1,v3,v,v2,v4 is a minimum partition of V having sets possessing the property ℛ in W4,(iii)
v1,v2,v3,v4,v5,v is a minimum partition of V having sets possessing the property ℛ in W5,(iv)
v,v1,v2,v3,v4,v5,v6 is a minimum partition of V having sets possessing the property ℛ in W6, and(v)
v1,v2,v3,v4,v5,v6,v7,v is a minimum partition of V having sets possessing the property ℛ in W7.
It follows thatχrV,ℛ is 2 when n=3,4 and is 3 when n=5,6,7.
For alln≥8, let λ:V⟶1,2 be a coloring of V and let the corresponding color classes are C1=VP∪v, where P:vi∼vi+1∼⋯∼vi+n−5 for any fixed 1≤i≤n, and C2=V−C1. Then C1 and C2 define a partition of V. Also, Lemma 5 yields that both C1 and C2 possess the property ℛ. Therefore, λ is an ℛ−coloring of V, and hence χrV,ℛ=2.


## 4. Twins andr−Independence

Letv be a vertex of a graph G having vertex set V. Then the open neighborhood of v is Nv=u∈V:u∼vinG and the closed neighborhood of v is Nv=Nv∪v. Two distinct vertices u and v of G are adjacent twins if Nu=Nv and nonadjacent twins if Nu=Nv. Observe that if u,v are adjacent twins, then u∼v in G and if u,v are nonadjacent twins, then u∼v in G. Adjacent twins are called true twins and nonadjacent twins are called false twins. Either u,v are adjacent or nonadjacent twins, they are called twins. A vertex v is called self twin if neither Nu=Nv nor Nv=Nu, for all u∈V. Each self twin in a graph makes a set of singleton twins. A set T⊆V is called a twin set in G if u,v are twins in G for every pair of distinct vertices u,v∈T. The next lemma follows from the above definitions [16].Lemma 6 (see [16]).
Ifu and v are twins in a graph G, then du,x=dv,x for every vertex x∈V−u,v.Due to Lemma6, we have the following remark.Remark 4.
(1)
Ifu and v are twins in a graph G and W is a resolving set for G. Then either u∈W or v∈W.
(2)
IfT is a twin set in a graph G of order t≥2, then every resolving set for G contains at least t−1 elements of T.Removal of two twins from the vertex set makes itr−independent as given in the next result.Lemma 7.
LetT be a twin set of order t≥2 in a graph G having the vertex set V. Then, for any two elements u,v∈T, the set V−u,v possesses the property ℛ.Proof.
Sincedu,x=dv,x for all x∈V−u,v, by Lemma 6, so no subset of V−u,v is a resolving set for G. It follows the result.Remarks2 and 4 yield the following two results.Lemma 8.
LetT be a twin set of order t≥2 in a graph G. Then, for each 1≤k≤t−1, any k−element subset S of T and the set T−S both possess the property ℛ.Proof.
Ift=2, then each subset S of T of order less that T as well as the set T−S both are singleton, and so Remark 2(1) yields the result. If t≥3, then as t−1 vertices of T must belong to any resolving set for G, by Remark 4(2), so no subset of T of order ≤t−2 is not a resolving set, because there are at least two twins are remained in T form that one of them must belong to a resolving set for G, by Remark 4(1). It follows that any k−element subset S of T possesses the property ℛ for each 1≤k≤t−1. Further, since the set T−S is either singleton or contains at least more than one twins from T, no subset of T−S is a resolving set for G. Thus, it must possess the property ℛ.Lemma8 can be generalized with the similar proof when a graph G has more than one twin sets of order at least two, and this generalization is stated in the following result.Theorem 4.
Forl≥2, let T1,T2,…,Tl are twin sets in a graph G of orders t1,t2,…,tl, respectively, where each ti≥2. If Si is a ki−element subset of Ti for 1≤ki≤ti−1, then(1)
eachSi possesses the property ℛ,(2)
∪i=1lSi possesses the property ℛ, and(3)
∪i=1lTi−∪i=1lSi possesses the property ℛ.Remark 5.
LetG be a family of graph and G∈G. For l≥2, let T1,T2,…,Tl are twin sets in a graph G of orders t1,t2,…,tl, respectively, where each ti≥2. Let a nonempty set S is union of singleton twin sets in G, and let v1,v2 belong to any one of T1,T2,…,Tl, then S∪Ti−v1,v2 is a maximal independent set which is not minimal resolving set.The following result states the relationship between twins andr−independence.Theorem 5.
Theℛ−chromatic number of a graph G (except P3) of order n≥3 having a nonsingleton twin set is two.Proof.
LetG be a graph of order n≥4 with vertex set V, and let T be a twin set in G. Let λ:V⟶1,2 be a coloring of V, and let the corresponding color classes are C1=V−u,v for any u,v∈T and C2=u,v. Then C1 and C2 define a partition of V. Also, Lemma 7 implies that C1∈V,ℛ. Further, since no path graph of order more than three has a twin set, so G is not a path graph. It follows that no singleton subset of C2 is resolving, because a path graph only has a singleton resolving set [4]. Thus, C2∈V,ℛ. Hence, λ is an ℛ−coloring of V, and so χrV,ℛ=2.Remark 6.
(1)
The converse of Theorem5 is not true generally. Theorem 3 describes that the ℛ−chromatic number of a wheel graph Wn is two, but Wn has no twin class for any n≥8.
(2)
In Theorem5, if G is P3, then G has one twin set containing two end vertices. But, the ℛ−chromatic number of G is three, by Theorem 1.Next, we provide two well-known families of graphs as in the favor of Theorem5.


### 4.1. Complete Multipartite Graphs

LetG be a complete multipartite graph with k≥2 partite sets V1,V2,…,Vk of cardinality m1,m2,…,mk, respectively, where each mi≥1.(i)
Ifmi=1 for all 1≤i≤k, then G is a complete graph Kk having vertex as the twin set.(ii)
If some ofmi is not equal to one. Let us suppose, without loss of generality, that mi=1 for 1≤i≤l and 2≤l<k. Then, G has k−l+1 twin sets Vl+1,Vl+2,…,Vk and ∪i=1lVi.(iii)
Ifk=2,m1=1 and m2=2, then G is K1,2≅P3.As, theℛ−chromatic number of P3 is 3, by Theorem 1, so we receive the following consequence from Theorem 5.Corollary 1.
Theℛ−chromatic number of a complete multipartite graph (which is not K1,2) is two.Example 5.
(Circulant networks).
The family of circulant networks is an important family of graphs, which is useful in the design of local area networks [17]. These networks are the special case of Cayley graphs CayG;S when the group G is Zn (an additive group of integers modulo n) and S⊆Zn\0 [18]. These graphs are defined as follows: let n,m and a1,a2,…,am be positive integers, 1≤ai≤⌊n/2⌋ and ai≠aj for all 1≤i<j≤m. An undirected graph with the set of vertices vi+1;i∈Zn, and the set of edges vj∼vj+al:1≤j≤n,1≤l≤m is called a circulant graph, denoted by Cna1,a2,…,am. The numbers a1,a2,…,am are called the generators, and we say that the edge vj∼vj+al is of type al. The indices after n will be taken modulo n. The cycle v1∼v2∼…∼vn∼v1 in Cna1,a2,…,am is called the principal cycle. Consider a class of circulant networks C2n+21,n, for n≥1. Then there are n+1 twin sets Ti=vi,vi+n+1 for 1≤i≤n+1. Thus, as a consequence of Theorem 5, the ℛ−chromatic number of C2n+21,n is two.


## 4.1. Complete Multipartite Graphs

LetG be a complete multipartite graph with k≥2 partite sets V1,V2,…,Vk of cardinality m1,m2,…,mk, respectively, where each mi≥1.(i)
Ifmi=1 for all 1≤i≤k, then G is a complete graph Kk having vertex as the twin set.(ii)
If some ofmi is not equal to one. Let us suppose, without loss of generality, that mi=1 for 1≤i≤l and 2≤l<k. Then, G has k−l+1 twin sets Vl+1,Vl+2,…,Vk and ∪i=1lVi.(iii)
Ifk=2,m1=1 and m2=2, then G is K1,2≅P3.As, theℛ−chromatic number of P3 is 3, by Theorem 1, so we receive the following consequence from Theorem 5.Corollary 1.
Theℛ−chromatic number of a complete multipartite graph (which is not K1,2) is two.Example 5.
(Circulant networks).
The family of circulant networks is an important family of graphs, which is useful in the design of local area networks [17]. These networks are the special case of Cayley graphs CayG;S when the group G is Zn (an additive group of integers modulo n) and S⊆Zn\0 [18]. These graphs are defined as follows: let n,m and a1,a2,…,am be positive integers, 1≤ai≤⌊n/2⌋ and ai≠aj for all 1≤i<j≤m. An undirected graph with the set of vertices vi+1;i∈Zn, and the set of edges vj∼vj+al:1≤j≤n,1≤l≤m is called a circulant graph, denoted by Cna1,a2,…,am. The numbers a1,a2,…,am are called the generators, and we say that the edge vj∼vj+al is of type al. The indices after n will be taken modulo n. The cycle v1∼v2∼…∼vn∼v1 in Cna1,a2,…,am is called the principal cycle. Consider a class of circulant networks C2n+21,n, for n≥1. Then there are n+1 twin sets Ti=vi,vi+n+1 for 1≤i≤n+1. Thus, as a consequence of Theorem 5, the ℛ−chromatic number of C2n+21,n is two.


## 5. Some Realizations

Remark2(3) describes that there is no n−element r−independent set in a connected graph of order n≥2. Lemma 7 illustrates that a connected graph G of order n≥3 having twins (other than self twins) can have an n−2−element set as an r−independent set. In the result to follow, we characterize all the connected graphs of order n≥2 in which every n−1−element subset of the vertex set is r−independent.Theorem 6.
LetG be a connected graph of order n≥2 with vertex set V. Then any n−1−element subset of V possesses the property ℛ if and only if G is a complete graph.Proof.
Suppose thatG is a complete graph. Then every two vertices of G are twins and V itself is the twin set in G. So Lemma 8 yields the required result.
Conversely, suppose that anyn−1−element subset, say S=s1,s1,…,sn−1, of V possesses the property ℛ. Then S is a resolving set for G, because for any si∈S, 0 lies at the ith position in the code cSsi, whereas the code cSv of the element v∈V−S has all nonzero coordinates. Further, S is a minimum resolving set for G, because no k−element subset of S is a resolving set for any 1≤k≤n−2, by our supposition. Thus, dimG=n−1. In [4, 6], it was shown that a graph G of order n has dimG=n−1 if and only if G is a complete graph. It completes the proof.Since any singleton set is anr−independent, so we have the following consequences for a complete graphs.Corollary 2.
Theℛ−chromatic number of a complete graph is two.IfG is a connected graph of order n≥2 with vertex set V, then 2≤χrV,R≤n, by Remark 2(3). The next result characterizes all the connected graphs of order n≥2 having ℛ−chromatic number n.Theorem 7.
LetG be a connected graph of order n≥2 with vertex set V. Then, χrV,ℛ=n if and only if G is either K2≅P2 or P3≅K1,2.Proof.
IfG≅K2≅P2, then χrV,ℛ=2, by Corollary 2.
IfG≅P3≅K1,2, then χrV,ℛ=3, by Theorem 1.
Conversely, suppose that for a connected graphG of order n≥2 with vertex set V, we have χrV,ℛ=n. Then,(i)
forn=2, the only connected graph is K2≅P2 such that χrV,ℛ=2=n, by Corollary 2,(ii)
forn=3, G is either C3≅K3 or P3≅K1,2. Since the ℛ−chromatic number of C3 is 2=n−1, by Theorem 2, and the ℛ−chromatic number of P3 is 3=n, by Theorem 1, so G≅P3 in this case.(ii)
forn≥4, either G has a twin set or no twin set exists in G. In the former case, χrV,ℛ=2≠n, by Theorem 5. In the latter case, let V=v1,v2,…,vn. Then, χrV,ℛ=n implies that the minimum partition of the r−independence system V,ℛ is v1,v2,…,vn. It follows that no k−element subset of V belongs to V,ℛ for k≥2. Otherwise, χrV,ℛ≤n−1. But, in every connected graph of order n≥4, at least one 2−element subset of V must possess the property ℛ, because singleton resolving sets exist in a path graph only (and in the case of path graph Pn,n≥4, we have 2−element subsets of V in V,ℛ, by Lemma 2). Therefore, no connected graph G of order n≥4 exists such that χrV,ℛ=n.
From the above three cases, we conclude thatG is either K2≅P2 or P3≅K1,2.From Theorem7, it concludes that if G is a connected graph of order n≥3 with vertex set V and G≅P3≅K1,2, then 2≤χrV,ℛ≤n−1. All the connected graphs of order n≥3 having ℛ−chromatic number n−1 are characterized in the following result.Theorem 8.
LetG be a connected graph of order n≥3 with vertex set V. Then, χrV,ℛ=n−1 if and only if G is either C3≅K3 or P4 or P5.Proof.
IfG≅C3≅K3, then Theorem 2 yields that χrV,ℛ=n−1.
IfG≅P4 or P5, then χrV,ℛ=n−1, by Theorem 1.
Conversely, suppose that for a connected graphG of order n≥3 with vertex set V, we have χrV,ℛ=n−1. Then,(i)
forn=3, G is either P3≅K1,2 or C3≅K3. G≅P3 is not true, by Theorem 7. So G≅C3, by Theorem 2,(ii)
forn=4, G≅P4,K1,3,K4≅W3,K4−e,K4−2e≅P4andC4,C4≅K2,2, where K4−e and K4−2e can be obtained by deleting one and two edges from K4, respectively. In this case, except P4, all the graphs has a twin set and so χrV,ℛ=2≠n−1, by Theorem 5. Thus G≅P4, by Theorem 1.(iii)
forn≥5, either G has no twin set or G has a twin set. χrV,ℛ=2≠n−1 in the latter case, by Theorem 5. In the former case, except G≅Pn, a minimum resolving set for G is of at least two order, which implies that every 2−element subset of V belongs to V,ℛ. It follows that a minimum partition of V according to the r−independence system contains at least two 2−element subsets of V, which implies that χrV,ℛ≤n−2, a contradiction. However, when G≅Pn, then χrV,ℛ=4=n−1 only for n=5 and χrV,ℛ≤n−2 for n≥6, by Theorem 1.
From the above three case, we conclude thatG is either C3≅K3 or P4 or P5.Theorem8 concludes that if G is a connected graph of order n≥4 with vertex set V and G≅P4,P5, then 2≤χrV,ℛ≤n−2.


## 6. Metric Dimension andr−Independence

In this section, we develop a relationship between the metric dimension andℛ−chromatic number of a connected graph by providing three existing type results.There exists a connected graph whose metric dimension is different from itsℛ−chromatic number by one.Theorem 9.
For evenn≥4, there exists a connected graph G with vertex set V such that dimG−χrV,ℛ=1.Proof.
LetCn be a cycle graph on even n≥4 vertices and a path P2. Then G is a graph obtained by taking the product of Cn and P2. Let the vertex set of G be V=vi,ui;1≤i≤n, and the edge set is E=vi∼vi+1,ui∼ui+1,uj∼vj;1≤i≤n−1∧1≤j≤n. The resultant graph G consists of two n cycles: one is outer cycle v1∼v2∼⋯∼vn∼v1, and the other one is inner cycle u1∼u2∼⋯∼un∼u1. It is shown, in [19], that dimG=3. Next, we investigate the ℛ−chromatic number of G with the help of the following five claims:Claim 1.
Every singleton,2−element and 3−element subset of V possesses the property ℛ. Based on Remark 2(1) and due to dimG=3 [19], this claim is true, because a minimum resolving set for G is of cardinality 3, and so no singleton and 2−element subset of V is a resolving set for G.Claim 2.
For fixed1≤i≤n, the sets X=vi,vi+n/2,v and Y=ui,ui+n/2,v are minimum resolving sets for G only when v∈V−vi,vi+n/2,ui,ui+n/2. Otherwise, cXvi−1=cXvi+1 and cYvi−1=cYvi+1.Claim 3.
For fixed1≤i≤n, the set Z=vi,vi+n/2,ui,ui+n/2⊂V possesses the property ℛ. By Claim 2, no subset of Z is a resolving set for G. It follows the required claim.Claim 4.
Nor−independent set (other than Z) in G of cardinality greater than 3 contains any of the pairs vi,vi+n/2 and ui,ui+n/2.LetS be an r−independent set in G of cardinality greater than 3. Suppose, without loss of generality, S contains the pair vi,vi+n/2. Then a subset vi,vi+n/2,v of S for v∈S−vi,vi+n/2 is a resolving set for G, by Claim 2, which contradicts the r−independence of S. Thus, S cannot contain the pair vi,vi+n/2. Similarly, the pair ui,ui+n/2 will not contained in S.Claim 5.
For each1≤k≤n, there is a k−element subset of V possessing the property ℛ. Claim 1 yields the result of k=1,2,3. For k=4, we have a set in V,ℛ, by Claim 3. Next, keeping Claim 4 in mind, let us consider two subset of V of cardinality n as follows: for fixed 1≤i≤n,(12)S1i=uj,vl;j=i+1,i+2,…,i+n2∧l=i,i−1,…,i−n2+1,S2i=vj,ul;j=i+1,i+2,…,i+n2∧l=i,i−1,…,i−n2+1,where the indices greater thann or less than or equal to zero will be taken modulo n. Then dui,x=dvi+1,x for all x∈S1i and dvi,y=dui+1,y for all y∈S2i.It follows thatcWui=cWvi+1 for any W⊆S1i and cWvi=cWui+1 for any W⊆S2i. Hence, both the S1i,S2i and each subset of any cardinality all are the subsets of V possessing the property ℛ, and of course, they are k−element subsets of V for 1≤k≤n.Now, letλ:V⟶1,2 be a coloring of V, and let the corresponding color classes are, for fixed 1≤i≤n,(13)C1=uj,vl;j=i+1,i+2,…,i+n2∧l=i,i−1,…,i−n2+1,C2=vj,ul;j=i+1,i+2,…,i+n2∧l=i,i−1,…,i−n2+1,where the indices greater thann or less than or equal to zero will be taken modulo n. Then C1 and C2 define a partition of V. Also, Claim 5 yields that C1,C2∈V,ℛ. Hence, λ is an ℛ−coloring of V, and so χrV,ℛ=2. Therefore, dimG−χrV,ℛ=1 for every even value of n≥4.Remark 7.
It is not necessary that the differencedimG−χrV,ℛ is constant (fixed) always. It can arbitrarily large depending upon the order of the graph. For instance, let G be a wheel graph of order n≥8, then dimG=⌊2/5n+1⌋ [20], and χrV,ℛ=2, by Theorem 3. So, it can be seen that the difference dimG−χrV,ℛ=⌊2/5n−4⌋, which is depending upon n and is not fixed.The next result shows that there exists a connected graph whoseℛ−chromatic number is different from its metric dimension by one.Theorem 10.
For oddn≥3, there exists a connected graph G with vertex set V such that χrV,ℛ−dimG=1.Proof.
Let a cycle graphCn on odd n≥3 vertices and a path P2. Then G is a graph obtained by taking the product of Cn and P2. Let the vertex set of G be V=vi,ui;1≤i≤n and the edge set is E=vi∼vi+1,ui∼ui+1,uj∼vj;1≤i≤n−1∧1≤j≤n. The resultant graph G consists of two n−cycles: one is outer cycle v1∼v2∼⋯∼vn∼v1, and the other one is inner cycle u1∼u2∼⋯∼un∼u1. Note that diamG=n+1/2, and it was show, in [19], that dimG=2, so a minimum resolving set for G consists of two vertices of G. Next, we investigate the ℛ−chromatic number of G on the base of the following six claims:Claim 1.
Every singleton and2−element subset of V possesses the property ℛ. Based on Remark 2(1) and due to dimG=2 [19], this claim is true, because a minimum resolving set for G is of cardinality 2, and so no singleton subset of V is a resolving set for G.Claim 2.
A minimum resolving set forG contains both the vertices either from the outer cycle or from the inner cycle of G.LetW be a minimum resolving set for G. For fixed 1≤i≤n, let W=vi,uj, where 1≤j≤n. Then,cWvi+1=cWvi−1 when j=i,cWvi+1=cWui when j=i+1,i+2,…,i+n−1/2, andcWvj=cWuj+1 when j=i+n−1/2+1,…,i+n,where the indices greater thann or less than zero will be taken modulo n. It follows that W is not a resolving set for G, a contradiction.Claim 3.
For fixed1≤i≤n, a minimum resolving set for G contains both the vertices:(14)x,y∈vi,vi+n−1/2,vi+n−1/2+1,ui,ui+n−1/2,ui+n−1/2+1,such thatdx,y=diamG−1.LetW be a minimum resolving set for G, then W must contain both the vertices from the same cycle of G, by Claim 2. Let W=vi,v and dvi,v<diamG−1 (in G, no two vertices u,v belonging to a same cycle have du,v=diamG). Then, v≠vi+n−1/2,vi+n−1/2+1 andcWui+n−1/2−1=cWvi+n−1/2 if v∈vi+1,…,vi+n−1/2−1, andcWvi+n−1/2+1=cWui+n−1/2+2 if v∈vi+n−1/2+2,…,vi+n,where the indices greater thann or less than or equal to zero will be taken modulo n. A contradiction to the fact that W is a resolving set for G.Claim 4.
Nor−independent set in G of cardinality greater than 2 contains two vertices x,y from a same cycle (outer or inner) of G such that dx,y=diamG−1. Otherwise, the set x,y is such a subset of that r−independent set which is resolving for G, by Claim 3.Claim 5.
For each1≤k≤n−1, there is a k−element subset of V possessing the property ℛ.Claim 1 follows the claim fork=1,2. Next, keeping Claim 4 in mind, let us consider two subset of V of cardinality n−1 as follows: for fixed 1≤i≤n,(15)S1i=uj,vl;j=i+1,i+2,…,i+n−12∧l=i,i−1,…,i−n−12+1,S2i=vj,ul;j=i+1,i+2,…,i+n−12∧l=i,i−1,…,i−n−12+1,where the indices greater thann or less than or equal to zero will be taken modulo n. Then, dui,x=dvi+1,x for all x∈S1i and dvi,y=dui+1,y for all y∈S2i.It follows thatcWui=cWvi+1 for any W⊆S1i and cWvi=cWui+1 for any W⊆S2i. Hence, both the set S1i,S2i and each subset of any cardinality all are the subsets of V possessing the property ℛ, and of course, they are k−element subsets of V for 1≤k≤n−1.Claim 6.
Nor−independent set of cardinality greater than n−1 exists in G. Otherwise, Claim 4 will be contradicted.Now, letλ:V⟶1,2,3 be a coloring of V, and let the corresponding color classes are: for fixed 1≤i≤n, C1=vi+diamG,ui+diamG,(16)C2=uj,vl;j=i+1,i+2,…,i+n−12∧l=i,i−1,…,i−n−12+1,C3=vj,ul;j=i+1,i+2,…,i+n−12∧l=i,i−1,…,i−n−12+1,where the indices greater thann or less than or equal to zero will be taken modulo n. Then C1,C2, and C3 define a partition of V. Also, Claims 1 and 5 yield that C1,C2,C3∈V,ℛ. Hence, λ is an ℛ−coloring of V, and so χrV,ℛ=3. Therefore, χrV,ℛ−dimG=1 for every odd value of n≥3.Remark 8.
It is not necessary that the differenceχrV,ℛ−dimG is constant (fixed) always. It can arbitrarily large by depending upon the order of the graph. For instance, let G be a cycle graph of order n≥3, then dimG=2 [4] and χrV,ℛ=⌈n/2⌉, by Theorem 2. It can be seen that the difference χrV,ℛ−dimG=⌊n−3/2⌋, which is depending upon n and is not fixed.The following result provides the existence of a connected graph whose metric dimension is equal to itsℛ−chromatic number.Theorem 11.
For oddn≥3, there exists a connected graph G with vertex set V such that χrV,ℛ=dimG.Proof.
LetG be a circulant network C2n+11,n for odd n≥3 with vertex set V=vi+1;i∈Zn (defined in Example 5), where the indices will be taken modulo n. The distance between vi and vj,j≠i on the principal is denoted by d∗ui,vj (for instance, in a circulant network Cn1,3, dvi,vi+3=1 where as d∗vi,vi+3=3 for any 1≤i≤n). The metric dimension, dimG, of G is 3 as shown in [21]. On the basis of the following three claims, we investigate the ℛ−chromatic number of G.Claim 1.
Everyk−element subset of V possesses the property ℛ for 1≤k≤3.As a minimum resolving set forG is of cardinality three, so no singleton and 2−element subset of V resolves G. It follows the claim.Claim 2.
Nor−independent set in G of cardinality greater than three contains two vertices u and v such that d∗u,v=n.IfS is an r−independent set in G containing two vertices u and v such that d∗u,v=n, then the set u,v,w⊂S, for any w∈S−u,v, is a resolving set for G, a contradiction.Claim 3.
A maximumr−independent set in G consists of n consecutive vertices form the principal cycle.Firstly, for fixed1≤i≤n, we show that a set S=vi,vi+1,…,vi+n−1⊂V of n consecutive vertices form the principal cycle possesses the property ℛ. Note that, dvi+n,s=dvi−1,s for all s∈S. It follows that cWvi+n=cWvi−1 for each W⊆S. Hence, no subset of S is a resolving set for G. Secondly, if an r−independent set S either contains n nonconsecutive vertices or contains more than n vertices (consecutive or nonconsecutive) form the principal cycle, then S must contradict Claim 2.Now, letλ:V⟶1,2,3 be a coloring of V, and let the corresponding color classes are: for fixed 1≤i≤n, C1=vi+2n, C2=vi,vi+1,…,vi+n−1, and C3=vi+n,vi+n+1,…,vi+2n−1, where the indices will be taken modulo n. Then C1,C2 and C3 define a partition of V. Also, Claims 1 and 3 yield that C1,C2,C3∈V,ℛ. Hence, λ is an ℛ−coloring of V, and so χrV,ℛ=3. Therefore, χrV,ℛ=dimG for every odd value of n≥3.



---

*Source: 7163840-2021-08-21.xml*