Graph Realizations Constrained by Connected Local Dimensions and
Connected Local Bases
VARANOOT KHEMMANI1, WITSARUT PHO-ON2, SUPACHOKE ISARIYAPALAKUL3
1,2,3Department of Mathematics, Srinakharinwirot University,
Sukhumvit 23, Bangkok 10110, THAILAND
Abstract: For an ordered set W={w1, w2, ..., wk}of kdistinct vertices in a connected graph G, the represen-
tation of a vertex vof Gwith respect to Wis the k-vector r(v|W)=(d(v, w1), d(v, w2), ..., d(v, wk)), where
d(v, wi)is the distance from vto wifor 1≤i≤k. The set Wis called a connected local resolving set of Gif the
representations of every two adjacent vertices of Gwith respect to Ware distinct and the subgraph ⟨W⟩induced
by Wis connected. A connected local resolving set of Gof minimum cardinality is a connected local basis of
G. The connected local dimension cld(G)of Gis the cardinality of a connected local basis of G. In this paper,
the connected local dimensions of some well-known graphs are determined. We study the relationship between
connected local bases and local bases in a connected graph, and also present some realization results.
Key-Words: representation, connected local resolving set, connected local basis, connected local dimension.
Received: March 5, 2021. Revised: October 6, 2021. Accepted: December 19. Published: January 2, 2022.
1 Introduction
For an ordered set W={w1, w2, ..., wk}of kdistinct
vertices of a connected graph G, the representation of
a vertex vof Gwith respect to Wis the k-vector
r(v|W) = (d(v, w1), d(v, w2), ..., d(v, wk)),
where d(v, wi)is the distance between vand wifor
each integer iwith 1≤i≤k. If representations of
any pairs of vertices uand vwith respect to Ware dis-
tinct, then Wis called a resolving set of G. A resolv-
ing set of minimum cardinality is a minimum resolv-
ing set or a basis of G. The cardinality of basis of Gis
the dimension of G, which is denoted by dim(G). To
illustrate this concept, consider the graph Gof Fig. 1.
We consider the representations of vertices of Gwith
Figure 1: A connected graph G
respect to the ordered set W1={v1, v3}. Therefore,
their representations with respect to W1are
r(v1|W1) = (0,2), r(v2|W1) = (2,2),
r(v3|W1) = (2,0), r(v4|W1) = (2,1),
r(v5|W1) = (2,2), r(v6|W1) = (1,2),
r(v7|W1) = (1,1).
Since r(v2|W1) = (2,2) = r(v5|W1), it follows that
W1is not a resolving set of G. By considering the
ordered set W2={v1, v2, v3}, the representations of
vertices of Gwith respect to W2are
r(v1|W2) = (0,2,2), r(v2|W2) = (2,0,2),
r(v3|W2) = (2,2,0), r(v4|W2) = (2,2,1),
r(v5|W2) = (2,2,2), r(v6|W2) = (1,2,2),
r(v7|W2) = (1,1,1).
Since these representations are distinct, it follows that
W2is a resolving set of G. In fact, W2is a basis of G
and so dim(G) = 3.
The concept of resolving sets was introduced by
Slater in [13] and [14]. He used a locating set for
what we have called a resolving set and referred to
the cardinality of a basis of a connected graph as its
location number. He described the usefulness of this
idea when working with U.S. sonar and coast guard
LORAN (long range aids to navigation) stations. Fol-
lowing Slater and others [4], [5] and [6], we can think
of a resolving set as the set Wof vertices in a con-
nected graph Gso that each vertex in Gis uniquely
determined by its distances to the vertices of W. Inde-
pendently, Harary and Melter [3] discovered this con-
cept as well but used the term metric dimension rather
than location number. This concept was rediscovered
WSEAS TRANSACTIONS on MATHEMATICS
DOI: 10.37394/23206.2022.21.1
Varanoot Khemmani, Witsarut Pho-On,
Supachoke Isariyapalakul
E-ISSN: 2224-2880
1
Volume 21, 2022
by Johnson [8] of the Pharmacia Company while at-
tempting to develop a capability of large datasets of
chemical graphs. In [1], Chartrand and others used
the term resolving set for locating set and used metric
dimension for location number. Wang, Miao and Liu
[15] characterized connected graphs of order nwith
dimension n−3by using metric matrix. An appli-
cation of resolving set was presented in [11]. Resolv-
ing sets in graphs have been studied further in [7], [9]
and [10].
Let Wbe an ordered set of vertices of a connected
graph G. For every pair of adjacent vertices uand vin
G, if the representations of uand vwith respect to W
are distinct, then Wis called a local resolving set of
G. A local resolving set of Ghaving minimum cardi-
nality is a minimum local resolving set or a local basis
of Gand this cardinality is the local dimension of G,
which is denoted by ld(G). A subgraph Hof a graph
Gis called an induced subgraph of Gif whenever u
and vare vertices of Hand uv is an edge of G, then
uv is an edge of Has well. If Sis a nonempty set of
vertices of G, then the subgraph of Ginduced by Sis
the induced subgraph with vertex set S. This induced
subgraph is denoted by ⟨S⟩. A resolving set Wof a
connected graph Gis called a connected resolving set
of Gif the induced subgraph ⟨W⟩is connected. The
minimum cardinality of a connected resolving set of
Gis the connected dimension of G, which is denoted
by cd(G), and a resolving set of Ghaving this car-
dinality is called a minimum connected resolving set
of a connected basis of G. To illustrate these con-
cepts, consider the graph Gof Fig. 1. Recall that
W1={v1, v3}is not a resolving set of G. However,
since the representations of any two adjacent vertices
of Gwith respect to W1are distinct, it follows that W1
is a local resolving set of G. Clearly, there is no a lo-
cal resolving set of Gconsisting of one vertex. There-
fore, W1is a local basis of Gand so ld(G) = 2. For
an ordered set W2={v1, v2, v3}, we know that W2
is a resolving set of G. Since ⟨W2⟩is not connected,
it follows that W2is not a connected resolving set of
G. It is routine to verify that W3={v1, v2, v3, v7}
is a connected resolving set of G. Indeed, W3is a
connected basis of G, that is, cd(G) = 4.
The concept of local resolving sets was introduced
by Okamoto and others in [2]. They characterized all
nontrivial connected graphs of order nhaving the lo-
cal dimension 1,n−2or n−1. The idea of con-
nected resolving sets has appeared in [12] and used
the connected resolving number cr(G)of a connected
graph Gfor what we have called the connected di-
mension of G. The local dimension and the connected
dimension of some well-known graphs have been de-
termined in [2] and [12], respectively. We state these
results in the next three theorems.
Theorem 1.1 ([2]).Let Gbe a nontrivial connected
graph of order n. Then
(i) ld(G) = n−1if and only if G=Knand
(ii) ld(G) = 1 if and only if Gis bipartite.
Theorem 1.2 ([12]).Let Gbe a nontrivial connected
graph of order n. Then
(i) cd(G) = 1 if and only if G=Pnand
(ii) if G=Cn, then cd(G) = 2.
Theorem 1.3 ([12]).Let Gbe a connected graph of
order n≥3. Then cd(G) = n−1if and only if
G=Knor G=K1,n−1.
In this paper, we study a local resolving set Wof
a connected graph Gsuch that the induced subgraph
⟨W⟩is connected in G. In order to do this, let us in-
troduce some definitions and notation. Let Wbe an
ordered set of vertices of a connected graph G. Then
Wis called a connected local resolving set of Gif
Wis a local resolving set of Gsuch that the induced
subgraph ⟨W⟩of Gis connected. A connected local
resolving set of Ghaving minimum cardinality is a
minimum connected local resolving set or a connected
local basis of Gand this cardinality is the connected
local dimension of G, which is denoted by cld(G). To
illustrate this concept, consider the graph Gof Fig. 1.
We know that W1={v1, v3}is a local resolving set
of G. However, since the induced subgraph ⟨W1⟩of
Gis not connected, it follows that W1is not a con-
nected local resolving set of G. Then consider the
ordered set W′={v1, v3, v7}. The representations
of vertices of Gwith respect to W′are
r(v1|W′) = (0,2,1), r(v2|W′) = (2,2,1),
r(v3|W′) = (2,0,1), r(v4|W′) = (2,1,1),
r(v5|W′) = (2,2,1), r(v6|W′) = (1,2,1),
r(v7|W′) = (1,1,0).
Since the representations of any two adjacent vertices
of Gwith respect to W′are distinct, if follows that W′
is a local resolving set of G. Moreover, the induced
subgraph ⟨W′⟩is connected and so W′is a connected
local resolving set of G. By a case-by-case analysis,
it can be shown that every connected local resolving
set of Gmust contain at least two vertices, that is,
one of {v1, v6}and one of {v3, v4}. Thus, there is
no connected resolving set of Ghaving cardinality 2
and so W′is a connected local basis of G. Hence,
cld(G) = 3.
Observe that every connected local resolving set
of a connected graph Gis also a local resolving set of
Gbut every local resolving set of Gmay or may not
be a connected local resolving set of G. This implies
that
1≤ld(G)≤cld(G)≤n−1.(1.1)
WSEAS TRANSACTIONS on MATHEMATICS
DOI: 10.37394/23206.2022.21.1
Varanoot Khemmani, Witsarut Pho-On,
Supachoke Isariyapalakul
E-ISSN: 2224-2880
2
Volume 21, 2022
If Wis a connected local resolving set of G, then ⟨W⟩
is connected. However, since the representations of
any two vertices of Gwith respect to Wneed not be
distinct, it follows that Wis not necessarily a con-
nected resolving set of G. In fact, every connected
resolving set of Gis a connected local resolving set
of G, that is,
1≤cld(G)≤cd(G)≤n−1.(1.2)
From Eq.(1.1) and Eq.(1.2), we obtain that
1≤ld(G)≤cld(G)≤cd(G)≤n−1.(1.3)
For every ordered set W={w1, w2, . . . , wk}of
vertices of a connected graph G, recall that the only
vertex of Gwhose representation with respect to W
contains 0in its ith coordinate is wi, that it, the ver-
tices of Wnecessarily have distinct representations
with respect to W. On the other hand, the represen-
tations of vertices of Gthat do not belong to Whave
elements, all of which are positive. Indeed, to deter-
mine whether an ordered set Wis a connected local
resolving set of G, we only need to show that any two
adjacent vertices in V(G)−Whave distinct repre-
sentations with respect to Wand ⟨W⟩is connected.
2 The connected local dimensions of
some well-known graphs
In this section, we determined the connected local di-
mensions of some well-known graphs.
Theorem 2.1. Let Gbe a connected graph of order
n≥2. Then
(i) cld(G) = 1 if and only if Gis a bipartite graph,
(ii) cld(G) = n−1if and only if G=Kn, a com-
plete graph of order n.
Proof. (i) Assume that cld(G) = 1. Then ld(G) = 1
by Eq.(1.3). Therefore, Gis bipartite by The-
orem 1.1 (ii). For converse, suppose that Gis
bipartite. By Theorem 1.1 (ii), ld(G) = 1 and so
there is a 1-element local basis Wof G. Indeed, W
is also connected local basis of G, that is, cld(G) = 1.
(ii) Suppose that cld(G) = n−1. Eq.(1.2) implies
that cd(G) = n−1. Thus, by Theorem 1.3, Gis
complete or star. If Gis a star that is not complete,
then Gis bipartite of order at least 3. By (i), cld(G) =
1, a contradiction. Hence, Gis complete. On the other
hand, if G=Kn, then by Theorem 1.1, ld(G) =
n−1, and so cld(G) = n−1by Eq.(1.3).
Since every bipartite graph contains no odd cycle,
it follows that the connected local dimension of an
even cycle is 1. In fact, the connected local dimension
of an odd cycle is 2, as we present next.
Theorem 2.2. For an integer n≥3, the connected
local dimension of a cycle Cnis
cld(Cn) = {1if nis even,
2if nis odd.
Proof. If nis even, then Cnis bipartite. By Theo-
rem 2.1 (i), cld(G) = 1. We may assume that n
is odd. Let Cn= (v1, v2, ..., vn, v1)and let W=
{v1, v2}. Consider the representations of vertices in
V(Cn)−W. If 3≤i≤n+1
2,r(vi|W) = (i−1, i−2).
If i=n+3
2,r(vi|W) = (n−1
2,n−1
2). If n+5
2≤i≤n,
r(vi|W)=(n−i+ 1, n −i+ 2). Thus, Wis a
local resolving set of Cn. Since ⟨W⟩is connected, it
follows that Wis a connected local resolving set of
Cnand so cld(Cn)≤2. Since Cnis not bipartite, it
follows by Theorem 2.1 (i) that cld(Cn)≥2. Hence,
cld(Cn) = 2.
Observe that if G′is a graph obtained by adding a
pendant edge to a connected graph G, then it is easy
to verify that cld(G′) = cld(G). However, if a vertex
vis added to a connected graph Gsuch that more than
one edge is incident with v, then the connected local
dimension of the resulting graph can stay the same,
decrease, or increase significantly. For example, for
n≥3,1≤cld(Cn)≤2. Consider the connected
local dimension of a wheel Wn=Cn+K1, where
n≥3. Clearly, cld(W3) = 3, cld(W4) = cld(W5) =
2and cld(W6) = 3. However, for n≥7, the con-
nected local dimension of a wheel Wnincreases with
nas we show next.
In Wn=Cn+K1, let Cn= (v1, v2, ..., vn, v1),
where n≥7, and let vbe the central vertex of Wn.
Let Sbe a set of two or more vertices of Cn, let viand
vjbe two distinct vertices of S, and let Pand P′de-
note the two distinct vi−vjpaths determined by Cn.
If either Por P′, say P, contains only two vertices of
S(namely, viand vj), then we refer to viand vjas
neighboring vertices of Sand the set of vertices of P
that belong to Cn− {vi, vj}as the gap of S(deter-
mined by viand vj). The two gaps of Sdetermined
by a vertex of Sand its two neighboring vertices will
be referred to as neighboring gaps. Consequently, if
|S|=r, then Shas rgaps, some of which may be
empty.
The next theorem presents a necessary and suffi-
cient condition for a set Wto be a local resolving set
of Wn.
Theorem 2.3. Let Wbe a set of vertices of a wheel
Wn=Cn+K1, where n≥7. Then Wis a local
resolving set of Wnif and only if every gap of Wcon-
tains at most three vertices of Cn.
Proof. Assume, to the contrary, that there is a gap of
Wcontaining at least four vertices of Cn. Then there
WSEAS TRANSACTIONS on MATHEMATICS
DOI: 10.37394/23206.2022.21.1
Varanoot Khemmani, Witsarut Pho-On,
Supachoke Isariyapalakul
E-ISSN: 2224-2880
3
Volume 21, 2022
are two adjacent vertices uand u′in this gap such
that d(u, w) = d(u′, w) = 2 for all w∈W− {v}.
Therefore, r(u|W) = r(u′|W), which is impossible.
To show the converse, suppose that every gap of W
contains at most three vertices of Cn. Since n≥7,
it follows that Wcontains at least two vertices of Cn.
For any two adjacent vertices xand ycontained in a
gap of W, there exists a vertex in Wadjacent to only
one of {x, y}. Hence the representation of xand y
with respect to Ware distinct. If the central vertex
v∈W, we are done. Suppose that v/∈W.
Case 1. |W| ≥ 3.
Since vis adjacent to every vertex of Cn, it follows
that the representations of vand any vertices of Cn
with respect to Ware distinct.
Case 2. |W|= 2.
Suppose that there is a vertex w′∈V(Cn)such that
r(w′|W) = (1,1) = r(v|W). Since n≥7,Wcon-
tains a gap of at least four vertices, which is impossi-
ble. Hence the representations of vand any vertices
of Cnwith respect to Ware distinct.
An immediate consequence from Theorem 2.3 is
that if Wis a local resolving of Wn, where n≥7,
W− {v}is also a local resolving set. It follows that,
for n≥7, every local basis of Wncontains no central
vertex. However, every connected local basis of Wn
must contain the central vertex. It is shown in the next
result.
Lemma 2.4. Every connected local basis of a wheel
Wn, where n≥7must contain the central vertex.
Proof. Assume, to the contrary, that there is a con-
nected local basis Wof Wnnot containing the cen-
tral vertex v. Then Wconsists of consecutive ver-
tices in Cn. Without loss of generality, let W=
{v1, v2, ..., vk}. By Theorem 2.3, it implies that
k≥n−3. By the argument similar to the one
used for the proof of Theorem 2.3, the set W′=
{v, v1, v4, v5, ..., vk}is a local resolving set of Wn.
Moreover, ⟨W′⟩is connected, that is, W′is also a
connected local resolving set of Wnhaving cardinal-
ity k−1, contradicting the assumption that Wis a
connected local basis of Wn.
We are now prepared to present the connected lo-
cal dimension of a wheel Wn, where n≥7.
Theorem 2.5. Let Wnbe a wheel, where n≥7, Then
cld(Wn) = ⌈n
4⌉+ 1.
Proof. By Theorem 2.3 and Lemma 2.4, we obtain
that cld(Wn)≥ ⌈n
4⌉+ 1. It remains to verify that
cld(Wn)≤ ⌈n
4⌉+ 1. Let W={vi∈V(Cn)|i≡
1(mod4)} ∪ {v}with |W|=⌈n
4⌉+ 1. Since every
gap of Wcontains at most three vertices from Cn, it
follows by Theorem 2.3 that Wis a local resolving
set of Wn. Moreover, since Wcontains the central
vertex v, it follows that ⟨W⟩is connected and so W
is a connected local resolving set of Wn. Therefore,
cld(Wn)≤ ⌈n
4⌉+1. Hence, cld(Wn) = ⌈n
4⌉+1.
3 Graphs with prescribed connected
local dimensions and other
parameters
The open neighborhood or the neighborhood of a
vertex uof a connected graph Gis the set of all
vertices that are adjacent to u, which is denoted by
N(u) = {v∈V(G)|uv ∈E(G)}. The closed
neighborhood N[u]of uis defined as N(u)∪ {u}.
Two vertices uand vof Gare twins if either (i)
uv /∈E(G)and N(u) = N(v)or (ii) uv ∈E(G)and
N[u] = N[v]. In particular, if the condition (ii) holds,
then uand vare called true twins. Consequently, the
relations twin and true twin are equivalence relations
on V(G)and, as such, these relations partition V(G)
into equivalence classes which are called twin equiv-
alence classes and true twin equivalence classes, re-
spectively or, more simply, twin classes and true twin
classes, respectively. Observe that if Gcontains ldis-
tinct true twin classes U1, U2, ..., Ulof G, then every
local resolving set of Gmust contain at least |Ui| − 1
vertices from each Ui, where 1≤i≤l. This obser-
vation has been described in [2] as we state next.
Proposition 3.1 ([2]).Let Gbe a connected graph
having ltrue twin classes U1, U2, ..., Ul. Then every
local resolving set of Gmust contain |Ui| − 1vertices
from each Ui, where 1≤i≤l. Moreover, ld(G)≥
l
∑
i=1
|Ui| − l.
We have seen that if Gis a connected graph of
order nwith ld(G) = aand cld(G) = b, then
1≤a≤b≤n−1by Eq.(1.1). In fact, any integers
a, b and nwith 1≤a≤b≤n−1are realizable as
the local dimension, connected local dimension and
order of some graphs as we show next.
Theorem 3.2. Let a, b, n be integers with n≥4.
Then there exists a connected graph Gof order nwith
ld(G) = aand cld(G) = bif and only if a, b, n satisfy
one of the following:
(i) a=b=n−1,
(ii) a=b= 1, and
(iii) 2≤a≤b≤n−2.
Proof. Assume that there exists a connected graph G
of order nwith ld(G) = aand cld(G) = b. By
Eq.(1.1), we obtain that 1≤a≤b≤n−1. If
b=n−1, then Gis a complete graph Kn. Thus,
WSEAS TRANSACTIONS on MATHEMATICS
DOI: 10.37394/23206.2022.21.1
Varanoot Khemmani, Witsarut Pho-On,
Supachoke Isariyapalakul
E-ISSN: 2224-2880
4
Volume 21, 2022
a=b=n−1. If a= 1, then Gis a bipar-
tite graph. Therefore, a=b= 1. For otherwise,
2≤a≤b≤c≤n−2. Hence, if Gis a connected
graph of order nwith ld(G) = aand cld(G) = b,
then a, b and nmust satisfy one of (i), (ii) and (iii). It
remains to verify the converse. If a=b=n−1,
then let Gbe a complete graph Knand the result is
true. If a=b= 1, then let Gbe a path Pn. Thus, the
graph Ghas the desired properties. We may assume
that 2≤a≤b≤n−2. We consider two cases.
Case 1. a=b.
Let G′be a graph obtained from a complete graph Ka
with vertex set {u1, u2, ..., ua}and a path Pn−a=
(v1, v2, ..., vn−a)by joining v1to every vertex of Ka.
Since V(Ka)is a true twin class of G′, every local
resolving set of G′must contain at least a−1ver-
tices from V(Ka). However, if a set Wcontains only
a−1vertices from V(Ka), then Wdoes not con-
tain uifor some integer iwith 1≤i≤aand so
r(ui|W) = r(v1|W) = (1,1, ..., 1). Therefore, G
contains no local resolving set of cardinality a−1, that
is, ld(G′)≥a. Since r(vj|V(Ka)) = (j, j, ..., j),
where 1≤j≤n−a, it follows that V(Ka)is a
local resolving set of G′having cardinality a, that is,
V(Ka)is a local basis of G′. Moreover, V(Ka)is
also a connected local basis of G′. Hence, ld(G′) =
cld(G′) = a.
Case 2. a < b.
Let Gbe a graph obtained from a complete graph
Kawith vertex set {u1, u2, ..., ua}and two paths
Pb−a+1 = (v1, v2, ..., vb−a+1)and Pn−b−1=
(w1, w2, ..., wn−b−1)by joining v1to every vertex of
Ka, and w1to both vb−aand vb−a+1. Since V(Ka)is
a true twin class of G, it follows by Proposition 3.1
that every local resolving set of Gmust contain at
least a−1vertices from V(Ka). However, ev-
ery set consisting of a−1vertices from V(Ka)is
not a local resolving set of Gsince the representa-
tions of vb−a+1 and w1with respect to this set are
the same. Thus, every local resolving set of Gcon-
tains at least avertices. It is routine to verify that
every local resolving set of Gmust contain at least
one vertex from {vb−a+1} ∪ V(Pn−b−1). Then the
set (V(Ka)− {u1})∪ {vb−a+1}is a minimum local
resolving set of G. Hence, ld(G) = a. Since ev-
ery connected local resolving set of Gis also a lo-
cal resolving set of G, it follows that every connected
local resolving set of Gmust contain at least a−1
vertices from V(Ka)and at least one vertex from
{vb−a+1} ∪ V(Pn−b−1). Therefore, every connected
local resolving set of Gcontains v1, v2, ..., vb−a. In
fact, the set (V(Ka)− {u1})∪V(Pb−a+1)is a con-
nected local basis of G, that is, cld(G) = b.
We know by Eq.(1.2) that if Gis a connected graph
of order nwith cld(G) = band cd(G) = c, then 1≤
b≤c≤n−1. Next, we show that for any integers
b, c and nwith 1≤b≤c≤n−1are realizable as
the connected local dimension, connected dimension
and order of some graphs.
Theorem 3.3. Let b, c, n be integers with n≥4.
Then there exists a connected graph Gof order nwith
cld(G) = band cd(G) = cif and only if b, c, n satisfy
one of the following:
(i) b=c=n−1,
(ii) b= 1 and 1≤c≤n−1, and
(iii) 2≤b≤c≤n−2.
Proof. Assume that there exists a connected graph
of order nwith cld(G) = band cd(G) = c. By
Eq.(1.2), we obtain that 1≤b≤c≤n−1. If
b=n−1, then c=n−1by Eq.(1.2). If b= 1,
then 1≤c≤n−1by Eq.(1.2). If 2≤b≤n−2,
then Gis neither a star nor a complete graph, and so
2≤b≤c≤n−2. Hence, if Gis a connected
graph of order nwith cld(G) = band cd(G) = c,
then b, c and nmust satisfy one of (i), (ii) and (iii). It
remains to verify the converse. If b=c=n−1,
then let Gbe a complete graph Knand the result is
true. Next, assume that b= 1 and 1≤c≤n−1.
For c= 1, let Gbe a path Pn; while for c=n−1
let Gbe a star K1,n−1. Since cld(Pn) = cd(Pn) = 1,
and cld(K1,n−1) = 1 and cd(K1,n−1) = n−1, it fol-
lows that the result holds for b= 1 and c= 1, n −1.
For 2≤c≤n−2, let Gbe a graph obtained
from a complete bipartite graph K2,c−1with partite
sets U={u1, u2}and U′={w1, w2, ..., wc−1}, and
a path Pn−c−1= (v1, v2, ..., vn−c−1)by joining v1
to both u1and u2. Since Gis bipartite, it follows
that cld(G) = 1. It is routine to show that the set
V(K2,c−1)− {u2}is a connected basis of G. There-
fore, cd(G) = c. Hence, the result holds for b= 1 and
2≤c≤n−2. Now assume that 2≤b≤c≤n−2.
We consider two cases.
Case 1. b=c.
The graph G′of the proof for Theorem 3.2 has
cld(G′) = bwith a connected local basis V(Kb). In
fact, V(Kb)is also a connected basis of G′, that is,
cd(G′) = b.
Case 2. b < c.
Let Gbe a graph obtained from a complete graph
Kbwith vertex set {u1, u2, ..., ub}, a star K1,c−bwith
vertex set {v, v1, v2, ..., vc−b}and a path Pn−c−1=
(w1, w2, ..., wn−c−1)by joining the central vertex v
of K1,c−bto w1and every vertex of Kb. It is im-
mediate that the set V(Kb)is a connected local ba-
sis of G. Therefore, cld(G) = b. Moreover, the set
(V(Kb)− {u1})∪V(K1,c−b)is a connected basis of
G, that is, cd(G) = c.
WSEAS TRANSACTIONS on MATHEMATICS
DOI: 10.37394/23206.2022.21.1
Varanoot Khemmani, Witsarut Pho-On,
Supachoke Isariyapalakul
E-ISSN: 2224-2880
5
Volume 21, 2022
4 Connected local bases and local
bases in graphs
In this section, we study the relationship between
connected local bases and local bases in a connected
graph G. Certainly, if Wis a local resolving set of G,
then a set W′containing Wis also a local resolving
set of G. Therefore, if Wis a local basis of Gsuch
that ⟨W⟩is disconnected, then surely there is a small-
est superset W′of Wfor which ⟨W′⟩is connected.
This suggests the following question: Does there ex-
ist a graph with a connected local basis not containing
any local bases? The answer to this question is given
in the next result.
Theorem 4.1. There is an infinite class of connected
graphs Gsuch that some connected local bases of G
contain a local basis of Gand others contain no local
basis of G.
Proof. Let Gbe a graph obtained from a com-
plete graph Kaof order a≥2with vertex set
{u1, u2, ..., ua}, a cycle C4= (v1, v2, v3, v4, v1)and
a path P3= (w1, w2, w3)by joining v1to every ver-
tex of Kaand joining w1and w3to v1, v4and v2, v3,
respectively. A graph Gis shown in Fig. 2. We first
Figure 2: A graph G
verify that the set B={u1, u2, ..., ua−1} ∪ {w2}is
a local basis of G. We can show, by a case-by-case
analysis, that Bis a local resolving set of G. Next,
we claim that Bis a local resolving set of minimum
cardinality. Assume, to the contrary, that there is a
local resolving set Wof Ghaving cardinality at most
a−1. Since V(Ka)is a true twin class of G, it fol-
lows that every local resolving set of Gmust contain
at least a−1vertices of Ka. Therefore, Wconsists
of a−1vertices of Ka. However, v4and w1are ad-
jacent and d(v4, ui) = d(w1, ui)for each integer i
with 1≤i≤a. This is a contradiction. Hence, B
is a local basis of Gand so ld(G) = a. Second, we
determine that cld(G) = a+ 2. In order to do this,
we claim that cld(G)≥a+ 2. Suppose, contrary to
our claim, that there is a connected local resolving set
W′of Ghaving cardinality a+ 1. Recall that every
connected local basis of Gmust contain at least a−1
vertices of Ka. We consider two cases.
Case 1. V(Ka)⊆W′.
Since ⟨W′⟩is connected and |W′|=a+ 1, it follows
that W′=V(Ka)∪ {v1}. However, since v4is adja-
cent to w1and r(v4|W′) = r(w1|W′), it follows that
W′is not a connected resolving set of G, which is a
contradiction.
Case 2. V(Ka)*W′.
Since ⟨W′⟩is connected and |W′|=a+ 1, it follows
that W′contains v1and one vertex from {v2, v4, w1}.
If W′contains v2or w1, then r(v3|W′) = r(w3|W′).
If W′contains v4, then r(w2|W′) = r(w3|W′).
Therefore, W′is not a connected local resolving set
of G. This is also a contradiction.
Therefore, cld(G)≥a+ 2. On the other hand,
the sets S1={u1, u2, ..., ua−1}∪{v1, w1, w2}and
S2={u1, u2, ..., ua−1} ∪ {v1, v4, w1}are connected
local resolving sets of G. Therefore, cld(G)≤a+ 2.
Hence, cld(G) = a+ 2.
Last, it can be verified that every local basis of G
contains exactly a−1vertices of Kaand exactly one
vertex from {v3, w2}. Observe that the connected lo-
cal basis S1contains the local basis Bof G, while
the connected local basis S2contains no local basis
of G.
From the previous theorem, there is a connected
graph having many connected local bases. This leads
us to determine a connected graph Ghaving a unique
connected local basis. It has been shown in [2] that
there is a connected graph with a unique local basis.
In fact, there is a connected graph with a unique con-
nected local basis as we show next.
Theorem 4.2. For k≥3, there exists a graph with a
unique connected local basis of cardinality k+ 1.
Proof. Let G1be a complete graph K2kwith vertex
set U={u0, u1, ..., u2k−1}, and let G2be a empty
graph Kkwith vertex set W={wk−1, wk−2, ..., w0}.
Then the graph Gis obtained from G1and G2by
adding edges between Uand Was follows. Let each
integer jfor 1≤j≤2k−1be expressed in its base
2(binary) representation. Thus, each such jcan be
expressed as a sequence of kcoordinates, that is, a k-
vector, where the rightmost coordinate represents the
value (either 0or 1) in the 20position, the coordinate
to its immediate left is the value in the 21position,
etc. For integers iand jwith 0≤i≤k−1and
0≤j≤2k−1, we join wiand ujif and only if the
value in the 2iposition in the binary representation
of jis 1. For example, Fig. 3 shows the edges join-
ing between Uand Win the graph Gfor k= 3. It
was shown in [2] that Wis a unique local basis of G.
Therefore, there is no connected local basis of Ghav-
ing cardinality k, that is, cld(G)≥k+ 1. Since Wis
a local basis of G, it follows that W′=W∪ {u2k−1}
WSEAS TRANSACTIONS on MATHEMATICS
DOI: 10.37394/23206.2022.21.1
Varanoot Khemmani, Witsarut Pho-On,
Supachoke Isariyapalakul
E-ISSN: 2224-2880
6
Volume 21, 2022
Figure 3: A graph Gfor k= 3
is a connected local resolving set of G. In fact, W′is
a connected local basis of G.
It remains only to show that Ghas no other con-
nected local basis. If U′⊆Uand |U′|=k+ 1, then
|U−U′|= 2k−k−1≥2. Since the distance of
every two vertices of Uis 1, it follows that there are at
least two adjacent vertices of U−U′having the same
representation with respect to U′, and so U′is not a
connected local resolving set of G. Thus, every con-
nected local resolving set of Gmust contain at least
one vertex of W. Suppose that B=W′is a con-
nected local basis of G. Therefore, B=U′′ ∪W′′,
where U′′ ⊆Uand W′′ ⊆W. If |W′′ |=k, then
Bdoes not contain u2k−1. Therefore, ⟨B⟩is not con-
nected, which is impossible. If |W′′ | ≤ k−1, then
U′′ contains at least two vertices. We may therefore
assume that |U′′|=i≥2. Then |W′′ |=k−i+ 1.
Since every vertex of U−U′′ has distance 1from
every vertex of U′′, it follows that there are at most
2k−i+1 distinct representations of vertices of U−U′′
with respect to B. However, since 2k−i > 2k−i+1,
there are two vertices of U−U′′ such that their repre-
sentation with respect to Bare the same, contradicting
the fact that Bis a connected local basis of G. Hence,
W′is a unique connected local basis of G.
5 Discussion and conclusions
By Eq.(1.3), it suggests the following question: For
which quadruples a, b, c, n of integers with 1≤a≤
b≤c≤n−1, does there exist a connected graph Gof
order nwith ld(G) = a, cld(G) = band cd(G) = c?
In this research, we have investigated the con-
nected local dimensions of bipartite graphs, complete
graphs, cycles and wheels. We show the realiza-
tion results that any integers a,band nwith 1≤
a≤b≤n−1are realizable as the local dimen-
sion, connected local dimension and order of some
graphs. Moreover, for any integers b, c and nwith
1≤b≤c≤n−1are realizable as the connected
local dimension, connected dimension and order of
some graphs. We present the relationship between
connected local bases and local bases in a connected
graph, that is, there is an infinite class of connected
graphs Gsuch that some connected local bases of G
contain a local basis of Gand others contain no lo-
cal basis of G. We determine the stronger result that
there is a connected graph with a unique connected
local basis.
References:
[1] G. Chartrand, L. Eroh, M. Johnson & O.R
Oellermann. (2000). Resolvability in graphs and
the metric dimension of a graph. Discrete Ap-
plied Mathematics, 105, 99–113.
[2] F. Okamoto, B. Phinezy & P. Zhang. (2010). The
local metric dimension of a graph. Mathematical
Bohemica, 135(3), 239–255.
[3] F. Harary & R. A. Melter. (1976). On the met-
ric dimension of a graph. Ars Combinatoria, 2,
191–195.
[4] B. L. Hulme, A. W. Shiver & P. J. Slater. (1981).
FIRE: a subroutine for fire protection network
analysis (SAND 81–1261). New Mexico: San-
dia National Laboratories.
[5] B. L. Hulme, A. W. Shiver & P. J. Slater.
(1982) Computing minimum cost fire protection
(SAND 82–0809). New Mexico: Sandia Na-
tional Laboratories.
[6] B. L. Hulme, A. W. Shiver & P. J. Slater. (1984).
A Boolean algebraic analysis of fire protection.
North-Holland Mathematics Studies, 95, 215–
227.
[7] S. Isariyapalakul, V. Khemmani & S. W.
Pho-on. (2020). The multibases of symmet-
ric caterpillars. Journal of Mathematics, 2020
doi:10.1155/2020/5210628
[8] M. A. Johnson. (1998). Browsable structure-
activity datasets. Advances in Molecular Simi-
larity, 2, 153–170.
[9] V. Khemmani & S. Isariyapalakul. (2018). Mul-
tiresolving sets of graphs with prescribed multi-
similar equivalence classes. International Jour-
nal of Mathematics and Mathematical Sciences,
2018 doi:10.1155/2018/8978193
[10] V. Khemmani & S. Isariyapalakul. (2020). The
characterization of caterpillars with multidimen-
sion 3. Thai Journal of Mathematics, 2020(Spe-
cial Issue), 247–259.
WSEAS TRANSACTIONS on MATHEMATICS
DOI: 10.37394/23206.2022.21.1
Varanoot Khemmani, Witsarut Pho-On,
Supachoke Isariyapalakul
E-ISSN: 2224-2880
7
Volume 21, 2022
[11] S. Khuller, B. Rsghavachari & A. Rosenfeld.
(1994). Localization in graphs (CS-TR-3326).
Maryland: University of Maryland.
[12] V. Saenpholphat & P. Zhang. (2003). Connected
resolvability of graphs. Czechoslovak Mathe-
matical Journal, 53, 827–840.
[13] P. J. Slater. (1975). Leaves of trees. Congressus
Numerantium, 14, 549–559.
[14] P. J. Slater. (1998). Dominating and reference
sets in graphs. Journal of Mathematical Physics,
Sci, 22, 445–455.
[15] J. Wang, L. Miao & Y. Liu. (2019) Character-
ization of n-vertex graphs of metric dimension
n−3by metric matrix. Mathematics, 7(479),
1–13.
Sources of funding for research
presented in a scientific article or
scientific article itself
This research was supported by Faculty of Science,
Srinakharinwirot University.
Creative Commons Attribution
License 4.0 (Attribution 4.0
International , CC BY 4.0)
This article is published under the terms of the
Creative Commons Attribution License 4.0
https://creativecommons.org/licenses/by/4.0/deed.en_US
WSEAS TRANSACTIONS on MATHEMATICS
DOI: 10.37394/23206.2022.21.1
Varanoot Khemmani, Witsarut Pho-On,
Supachoke Isariyapalakul
E-ISSN: 2224-2880
8
Volume 21, 2022
