On unicyclic graphs of metric dimension 2 with vertices of degree 4
We show that if G is a unicyclic graph with metric dimension 2 and {a, b} is a metric basis of G then the degree of any vertex v of G is at most 4 and degrees of both a and b are at most 2. The constructions of unispider and semiunispider graphs and their knittings are introduced. Using these constr...
Saved in:
| Published in: | Algebra and Discrete Mathematics |
|---|---|
| Date: | 2018 |
| Main Authors: | , |
| Format: | Article |
| Language: | English |
| Published: |
Інститут прикладної математики і механіки НАН України
2018
|
| Online Access: | https://nasplib.isofts.kiev.ua/handle/123456789/188412 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| Journal Title: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Cite this: | On unicyclic graphs of metric dimension 2 with vertices of degree 4 / M. Dudenko, B. Oliynyk // Algebra and Discrete Mathematics. — 2018. — Vol. 26, № 2. — С. 256–269. — Бібліогр.: 13 назв. — англ. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| id |
nasplib_isofts_kiev_ua-123456789-188412 |
|---|---|
| record_format |
dspace |
| spelling |
Dudenko, M. Oliynyk, B. 2023-02-27T16:01:35Z 2023-02-27T16:01:35Z 2018 On unicyclic graphs of metric dimension 2 with vertices of degree 4 / M. Dudenko, B. Oliynyk // Algebra and Discrete Mathematics. — 2018. — Vol. 26, № 2. — С. 256–269. — Бібліогр.: 13 назв. — англ. 1726-3255 2010 MSC: 05C12. https://nasplib.isofts.kiev.ua/handle/123456789/188412 We show that if G is a unicyclic graph with metric dimension 2 and {a, b} is a metric basis of G then the degree of any vertex v of G is at most 4 and degrees of both a and b are at most 2. The constructions of unispider and semiunispider graphs and their knittings are introduced. Using these constructions all unicyclic graphs of metric dimension 2 with vertices of degree 4 are characterized. The authors thank to the International Charitable Foundation for Renaissance of the Kyiv-Mohyla Academy for the financial support of their research. en Інститут прикладної математики і механіки НАН України Algebra and Discrete Mathematics On unicyclic graphs of metric dimension 2 with vertices of degree 4 Article published earlier |
| institution |
Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| collection |
DSpace DC |
| title |
On unicyclic graphs of metric dimension 2 with vertices of degree 4 |
| spellingShingle |
On unicyclic graphs of metric dimension 2 with vertices of degree 4 Dudenko, M. Oliynyk, B. |
| title_short |
On unicyclic graphs of metric dimension 2 with vertices of degree 4 |
| title_full |
On unicyclic graphs of metric dimension 2 with vertices of degree 4 |
| title_fullStr |
On unicyclic graphs of metric dimension 2 with vertices of degree 4 |
| title_full_unstemmed |
On unicyclic graphs of metric dimension 2 with vertices of degree 4 |
| title_sort |
on unicyclic graphs of metric dimension 2 with vertices of degree 4 |
| author |
Dudenko, M. Oliynyk, B. |
| author_facet |
Dudenko, M. Oliynyk, B. |
| publishDate |
2018 |
| language |
English |
| container_title |
Algebra and Discrete Mathematics |
| publisher |
Інститут прикладної математики і механіки НАН України |
| format |
Article |
| description |
We show that if G is a unicyclic graph with metric dimension 2 and {a, b} is a metric basis of G then the degree of any vertex v of G is at most 4 and degrees of both a and b are at most 2. The constructions of unispider and semiunispider graphs and their knittings are introduced. Using these constructions all unicyclic graphs of metric dimension 2 with vertices of degree 4 are characterized.
|
| issn |
1726-3255 |
| url |
https://nasplib.isofts.kiev.ua/handle/123456789/188412 |
| citation_txt |
On unicyclic graphs of metric dimension 2 with vertices of degree 4 / M. Dudenko, B. Oliynyk // Algebra and Discrete Mathematics. — 2018. — Vol. 26, № 2. — С. 256–269. — Бібліогр.: 13 назв. — англ. |
| work_keys_str_mv |
AT dudenkom onunicyclicgraphsofmetricdimension2withverticesofdegree4 AT oliynykb onunicyclicgraphsofmetricdimension2withverticesofdegree4 |
| first_indexed |
2025-11-25T21:04:25Z |
| last_indexed |
2025-11-25T21:04:25Z |
| _version_ |
1850543872915013632 |
| fulltext |
“adm-n4” — 2019/1/24 — 10:02 — page 256 — #106
Algebra and Discrete Mathematics RESEARCH ARTICLE
Volume 26 (2018). Number 2, pp. 256–269
c© Journal “Algebra and Discrete Mathematics”
On unicyclic graphs of metric dimension 2 with
vertices of degree 4
Marharyta Dudenko and Bogdana Oliynyk
Communicated by A. P. Petravchuk
Abstract. We show that if G is a unicyclic graph with
metric dimension 2 and {a, b} is a metric basis of G then the degree
of any vertex v of G is at most 4 and degrees of both a and b are at
most 2. The constructions of unispider and semiunispider graphs
and their knittings are introduced. Using these constructions all
unicyclic graphs of metric dimension 2 with vertices of degree 4 are
characterized.
Introduction
The concept of metric dimension of a connected graph was introduced
by Harary and Melter [1]. Slater [2] described the usefulness of this concept
in connection to the long range aids to navigation.
A metric dimension as a graph parameter has numerous applications.
In particular, to the representation of chemical compounds [3] in chemistry
and to the problems of pattern recognition and image processing. Some
of them involve hierarchical data structures [4]. Also, it is used in sonar
[2] and combinatorial optimization [5].
The metric dimension decision problem is among the classical NP-hard
problems [6], but for some families of graphs, for example, for trees [7], the
polynomial algorithm can be built. It is easy to see, that if G has n vertices
The authors thank to the International Charitable Foundation for Renaissance of
the Kyiv-Mohyla Academy for the financial support of their research.
2010 MSC: 05C12.
Key words and phrases: graph, distance, metric dimension, unicyclic graph.
“adm-n4” — 2019/1/24 — 10:02 — page 257 — #107
M. Dudenko, B. Oliynyk 257
then 1 6 dimG 6 n− 1. There are results describing graphs having a
given value of metric dimension. In particular, in [1] it is proved that a
graph has metric dimension 1 if and only if it is a path. Moreover, metric
dimensions of the cycle Cn, the complete graph Kn and the complete
bipartite graph Ks,t are 2, n− 1 and n− 2, respectively [1], [8].
S. Khuller, B. Raghavachari and A. Rosenfeld [7] considered some
properties of graphs with metric dimension 2. They proved that if {a, b}
is a metric basis of G with metric dimension 2 then degrees of both a and
b are at most 3 and the maximum degree of any vertex u in the shortest
path between a and b is 5. Later G. Sudhakara and A. R. Hemanth Kumar
[9] evolved these properties and showed that the maximum degree of
any vertex in a graph G with metric dimension 2 is 8. For unicyclic
graphs, i.e. graphs containing exactly one cycle, these estimates can be
determined more precisely. We prove that if G is a unicyclic graph with
metric dimension 2 and {a, b} is a metric basis of G then for any vertex v
from G the following condition holds: deg(v) 6 4 and degrees of both a
and b are at most 2. Moreover, a vertex v such that deg(v) = 4 exists only
for odd graphs.
In [10] and [11] all unicyclic graphs that have metric dimension 2 and
vertices of degree at most 3 were widely studied.
In this paper we characterize all unicyclic graphs of metric dimension 2
with vertices of degree 4. For this purpose we introduce the constructions
of unispider and semiunispider graphs and their knittings. We show that
if a unicyclic graph G with dimG = 2 has a vertex of degree 4 then G is
unispider or a semiunispider graph or a knitting of one of graphs of such
type.
1. Preliminaries
Throughout this article, we consider only simple, finite, undirected,
connected and nontrivial graphs.
For a graph G = (V,E) we define a distance dG(u, v) between two
vertices u and v as the length of the shortest path between u and v; we
put dG(u, v) = 0 when u = v.
A vertex u of G resolves vertices v1 and v2 of G, if dG(u, v1) 6= dG(u, v2).
A resolving set is an ordered vertex subset S of V such that every two
distinct vertices of G are resolved by some vertex of S. A resolving set
also is called a metric generator. A resolving set of minimum cardinality
is said to be a metric basis of G. A metric dimension, dimG, of G is the
cardinality of its metric basis.
“adm-n4” — 2019/1/24 — 10:02 — page 258 — #108
258 Unicyclic graphs with vertices of degree 4
�
�
r
r
u1
r
❅
❅
✂
✂✂
r✂
✂✂
r
r
❆
❆
❆
✟✟r✟✟r
u3
b❆
❆
r❆
❆
r❆
❆
r
✁
✁
r
u5 u4
u
r❍❍❍r
a ✏✏✏✏
r
u2
Figure 1.
We use the standard notation: by the symbols Cn and Ln we denote
a cycle and a path on n vertices respectively. For unspecified notions in
graph theory we refer to [12].
Denote by Ĝ = (V̂ , Ê) a subgraph of a unicyclic graph G = (V,E),
which is isomorphic to a cycle Cm for some positive integer m. The
subgraph Ĝ is called the cycle of a graph G.
In [7] S. Khuller, B. Raghavachari and A. Rosenfeld considered some
properties of graphs with metric dimension 2. In particular, they proved,
that if G = (V,E) is a graph with metric dimension 2 and {a, b} is a
metric basis in G, then the degrees of a and b are at most 3 and every
other node u has the degree at most 5.
For unicyclic graphs there are some more accurate estimates.
Proposition 1 ([10]). Let G = (V,E) be a unicyclic graph. If metric
dimension of G is 2, then degG(v) 6 3 for any v ∈ V \ V̂ .
For the following proposition we need some definitions.
Following [10], a vertex u ∈ V \ V̂ of a unicyclic graph G is said to be
projected to a vertex w ∈ V̂ if
dG(u,w) < dG(u, q)
for any q ∈ V̂ , q 6= w.
Proposition 2. Let G = (V,E) be a unicyclic graph. If the metric di-
mension of G is 2, then degG(v) 6 4 for any v ∈ V̂ .
Proof. Assume that a unicyclic graph G with dimG = 2 has a vertex u
such that deg(u) > 5. Let u1, u2, u3, u4 and u5 be the vertices adjacent
“adm-n4” — 2019/1/24 — 10:02 — page 259 — #109
M. Dudenko, B. Oliynyk 259
to u, and u1, u2 ∈ V̂ , u3, u4, u5 ∈ V \ V̂ (see Figure 1). Suppose that a
metric basis of G consists of vertices a, b. As {a, b} is a basis, vertices ui,
1 6 i 6 5, are resolved by a, b. But u1, u2 ∈ V̂ , so one of vertices a, b is
projected to some vertex w ∈ V̂ , w 6= u (may be a = w or b = w). We may
assert that a ∈ V̂ or a is projected to w and resolves u1 and u2. Hence,
dG(a, u3) = dG(a, u4) = dG(a, u5) = dG(a, u) + 1.
In other words, a does not resolve u3, u4, u5. Then b is projected to u.
Without loss of generality we may assert that the shortest path, which
connects vertices b and u, contains u3. But in this case, we have
dG(b, u4) = dG(b, u5) = dG(b, u) + 1.
So, b does not resolve u4, u5. Therefore, our assumption is incorrect.
Note, that from Proposition 1 and Proposition 2 it follows that if
a unicyclic graph has metric dimension 2, then the degree of any vertex
from a cycle of G is less than 5 and the degree of any vertex out of the
cycle of G is less than 4. In the next section, we describe in detail the
structure of such graphs.
Recall that the inner vertices are the vertices of degree at least 3. An
inner vertex v ∈ V̂ is called a main vertex if there is an inner vertex
w ∈ V \ V̂ that is projected to v.
An inner vertex v is close to a leaf a (see [2]) if there is no other inner
vertex w in the unique path between v and a in G, i.e. for every other
inner vertex w of G the inequality
dG(a, v) < dG(a, w)
holds. If an inner vertex v is close to two different leaves, then we say that
v is a two-leaf vertex.
We need the lemma from [13].
Lemma 1 ([13]). Let G = (V,E) be a unicyclic graph and dimG = 2.
Then there exist at most two main vertices in G.
2. Odd and even unicyclic graphs with vertices of
degree 4
Following [10], a unicyclic graph G is even, if |V̂ | = 2k for some positive
integer k. If there is some positive integer k, such that |V̂ | = 2k + 1, then
the unicyclic graph G is odd.
“adm-n4” — 2019/1/24 — 10:02 — page 260 — #110
260 Unicyclic graphs with vertices of degree 4
Theorem 1. Let G = (V,E) be a unicyclic graph and dimG = 2. If G is
even, then the degree of any vertex of G is less than 4. If G is odd, then
the maximum number of its vertices of degree 4 is 2.
�
�
r
r
u1
r
❅
❅
✂
✂✂
r✂
✂✂
r
r
❆
❆
❆
✟✟r✟✟r
u3
au4
u
r❍❍❍r✏✏✏✏
r
b = w
u2
Figure 2.
Proof. Assume that a vertex u of G has the degree 4. Let u1, u2, u3 and
u4 be the vertices adjacent to u, and u1, u2 ∈ V̂ , u3, u4 ∈ V \ V̂ (see
Figure 2). Denote by symbols {a, b} the metric basis of G. As {a, b} is a
basis, the vertices a, b resolve ui, 1 6 i 6 4. But u3 and u4 are projected
to the single vertex u. Then one of the basis vertices is also projected to u.
Without loss of generality we may assume that it is a. We may assert that
the shortest path, which connects a and u, contains u3. Then
dG(a, u1) = dG(a, u2) = dG(a, u4) = dG(a, u) + 1.
Hence, a does not resolve u1, u2, u4. So, u1, u2, u4 are resolved by b.
Let b is projected to w, w ∈ V̂ (may be b = w). As
dG(b, ui) = dG(b, w) + dG(w, ui), 1 6 i 6 4,
vertices u1, u2, u4 are resolved by b if and only if they are resolved by w.
Hence, w resolves vertices u1, u2, u4, and dG(w, u1) 6= dG(w, u2). Assume
that dG(w, u1) < dG(w, u2). If the shortest path, which connects w and
u2, contains u1, then its length equals the length of the shortest path
between w and u4. In other words, in this case w does not resolve u2 and
u4. Therefore, the shortest path between w and u2 does not contain u1.
So, if m is a number of vertices in the cycle of G, we obtain
dG(w, u2) + dG(w, u1) + 2 = m.
“adm-n4” — 2019/1/24 — 10:02 — page 261 — #111
M. Dudenko, B. Oliynyk 261
Moreover, dG(w, u2) < m
2
, dG(w, u1) < m
2
. But, dG(w, u1) < dG(w, u2),
then from direct calculations we obtain that
m− 2
2
< dG(w, u2) <
m
2
.
If m = 2k, for some positive integer k, then
2k − 2
2
= k − 1 < dG(w, u2) < k.
So, these inequalities never hold. Hence, if G is even, G does not have
vertices of degree 4.
If m = 2k + 1, for some positive integer k, then
2k + 1− 2
2
= k −
1
2
< dG(w, u2) < k +
1
2
.
Hence,
dG(w, u2) = k, dG(w, u1) = k − 1, dG(w, u4) = k + 1.
Similarly, we can show that in this case w can also be a vertex of degree 4.
Note in addition, if G has a vertex of degree 4, then one of the vertices
from the metric basis of G is projected to this vertex. Therefore, if G is
odd, then the maximum number of its vertices of degree 4 is 2.
3. Unispider and semiunispider graphs
Definition 1. An odd unicyclic graph G with |V̂ | = 2k + 1 is said to be
a unispider graph if the following conditions hold (see Figures 3–7):
1) for any vertex v from V \ V̂ , degG(v) 6 3;
2) for any main vertex w of G there exists exactly one two-leaf vertex,
that is projected to w;
3) in the cycle Ĝ of G there are exactly two vertices w and u with the
degree greater than 2, moreover, at least one of w and u has the
degree 4, each of w and u is the main vertex or (and) a vertex of
degree 4 and
dG(w, u) = k.
Note, that from the definition of unispider graphs it follows that for
any unispider graph G one of the following cases holds:
1) the vertices w and u are the main vertices of degree 4 (see Figure 3);
“adm-n4” — 2019/1/24 — 10:02 — page 262 — #112
262 Unicyclic graphs with vertices of degree 4
�
�
rw❍❍r✟✟r
❍❍r❍❍r
✟✟r
✟✟r✟✟r✟✟r
r r
❅
❅ru ✏✏r✏✏r
❅r
✏✏r✏✏r
PPr
❍❍r❍❍r❍❍r
❆
❆
❆r❍❍❍r✏✏✏✏
r
Figure 3. Two main vertices that are vertices of degree 4
�
�
rw❍❍r❍❍r❍❍r
✟✟r
r r
❅
❅ru ✏✏r✏✏r✏✏r✏✏r
PPr
❍❍r❍❍r❍❍r
❆
❆
❆r❍❍❍r✏✏✏✏
r
Figure 4. Two main vertices, one of them is vertex of degree 4
2) the vertices w and u are main vertices, but one of them is a vertex
of degree 4 (see Figure 4);
3) the vertices w and u are vertices of degree 4, but only one of them
is a main vertex (see Figure 5);
4) one of vertices w and u is a vertex of degree 4 and the other one is
a main vertex (see Figure 6).
5) the vertices w and u are vertices of degree 4, but G does not have
main vertices (see Figure 7);
Proposition 3. Let G = (V,E) be a unispider graph. Then
dimG = 2.
Proof. Let G be unispider graph with two main vertices u and w, that
are vertices of degree 4 (see Figure 8). For the other types of unispider
graphs proof is very similar. Denote the leaves that are projected to u
and w by a and b, respectively. Moreover, if there are inner vertices that
are projected to u, then one of them is close to a. Similar, if there are
inner vertices that are projected to w, then one of them is close to b (see
Figure 8).
“adm-n4” — 2019/1/24 — 10:02 — page 263 — #113
M. Dudenko, B. Oliynyk 263
�
�
r❍❍r
✟✟
r
❍❍r❍❍r
w
r r
❅
❅ru ✏✏r✏✏r✏✏r✏✏r
PPr
❍❍r❍❍r❍❍r
❆
❆
❆r❍❍❍r✏✏✏✏
r
Figure 5. Two vertices of degree 4, one of them is the main vertex
�
�
rw❍❍r❍❍r❍❍r
✟✟r
r r
❅
❅ru ✏✏r✏✏r✏✏r✏✏r
❍❍r❍❍r❍❍r
❆
❆
❆r❍❍❍r✏✏✏✏
r
Figure 6. One main vertex and one vertex of degree 4
We need to show, that {a, b} is a metric basis of G.
Note, that a resolves all vertices that are adjacent to b, and vice versa.
In addition, if some pair of vertices from a subgraph Ĝ is not resolved
by the vertex b, say w3 and w4, then this pair is resolved by a, because
G is odd, |V̂ | = 2k + 1, a and b are projected to u and w, respectively,
and dG(w, u) = k by the definition of unispider graphs. Similar, if some
pair of vertices from Ĝ is not resolved by a, say u3 and u4, then this pair
is resolved by b. Moreover, from the proof of Theorem 1 it follows that
b resolves any pair of vertices from the set {u1, u2, u3, u4} and a resolves
any pair of vertices from the set {w1, w2, w3, w4}. So, any pair of vertices
from G is resolved by a or b. Therefore, {a, b} is a metric basis of G.
Definition 2. An odd unicyclic graph G with |V̂ | = 2k + 1 is said to
be a semiunispider graph if the following conditions hold (see Figures 9
and 10):
1) degG(v) 6 3 for any v from V \ V̂ ;
“adm-n4” — 2019/1/24 — 10:02 — page 264 — #114
264 Unicyclic graphs with vertices of degree 4
�
�
r❍❍r❍❍r❍❍r
✟✟r✟✟r✟✟r
r r
❅
❅r
❆
❆
❆r❍❍❍r✏✏✏✏
r✏✏r✏✏r✏✏r✏✏r
❍❍r❍❍r❍❍r❍❍r
Figure 7. There are two vertices of degree 4, but the graph without main
vertices
�
�
rw❍❍r
w1
✟✟r
❍❍r❍❍r
b
✟✟r
✟✟r
w2
✟✟r✟✟r
r
w4
r
❅
❅
u3
ru ✏✏r
u1
✏✏r
❅r
✏✏r✏✏r
PPra
❍❍r
u2
❍❍r❍❍r
❆
❆
❆r❍❍❍w3
r✏✏✏✏
r
u4
Figure 8.
2) in the cycle Ĝ of G there is exactly one vertex w with the degree
greater than two, moreover, deg(w) = 4;
3) the vertex w may be the main vertex, in this case there exists exactly
one two-leaf vertex, that is projected to w.
Proposition 4. Let G = (V,E) be a semiunispider graph. Then
dimG = 2.
Proof. Let G be a semiunispider graph with one main vertex w of degree 4.
For the other type of semiunispider graphs the proof is similar. Denote
the leaf that is projected to w by a (see Figure 9). Some inner vertex is
close to a. Let b be a vertex of cycle V̂ such that dG(w, b) = k.
“adm-n4” — 2019/1/24 — 10:02 — page 265 — #115
M. Dudenko, B. Oliynyk 265
�
�
r
b
r r
❅
❅
a
r
❆
❆
❆r❍❍❍r✏✏✏✏
r✏✏r✏✏r✏✏r✏✏r
❍❍r❍❍r
❅
❅r
�
�r
❅
❅
w
r
✏✏✏ r
Figure 9. Semiunispider graphs with the main vertex
�
�
r
b
r r
❅
❅r
❆
❆
❆r❍❍❍r✏✏✏✏
r✏✏r✏✏r✏✏r✏✏r
❍❍r❍❍r❍❍r
a
❍❍r
Figure 10. Semiunispider graphs without the main vertex
Similarly to the proof of Proposition 3 the set of vertices {a, b} is a
metric basis of G.
4. The main result
The main result is based on the notion of a knitting of a graph ([10]).
To introduce it we need the following definition.
Let G1 = (V1, E1) and G2 = (V2, E2) be simple graphs. Assume that
v1 ∈ V1 and v2 ∈ V2. Define the equivalence relation ∼ on the set V1 ∪ V2
by the following way: the vertex u is equivalent to the vertex w if and
only if v1 = u and v2 = w for all u ∈ V1 and w ∈ V2.
A graph G = (V1 ∪ V2\∼, E1 ∪ E2) is built from G1 and G2 by gluing
along vertices v1 and v2. Roughly speaking, the vertex v2 is replaced by
the vertex v1 for all edges of G2.
“adm-n4” — 2019/1/24 — 10:02 — page 266 — #116
266 Unicyclic graphs with vertices of degree 4
Definition 3. Let G1 be a unispider graph. Denote by u and w the
vertices of the degree greater than 2 of G1. A unicyclic graph G is called
a knitting of G1 by chains L1, . . . , Lr if G is obtained from G1 by gluing
vertices of degree 2 from the cycle of G1 and the leaves of chains L1, . . . , Lr
such that any vertex of degree 2 from the cycle G1 may be glued with one
leaf of one chain Lj , 1 6 j 6 r (see Figure 11).
Note that, if G1 is a unispider graph with one vertex u of degree 4,
then we can glue the vertex w of degree 3 with the leaf of the chain L0. In
this case we have a knitting of the unispider graph G2 with two vertices
of degree 4 (G2 is from Figures 3 or 5) by chains L1, . . . , Lr.
�
�
rw❍❍r✟✟r
❍❍r❍❍r
b
✟✟r
✟✟r✟✟r✟✟r
r❅
❅
r❅
❅
r
L1
x
z
y
r
❅
❅ru ✏✏r✏✏r
❅r
✏✏r✏✏r
PPra
❍❍r❍❍r❍❍r
❆
❆
❆r❍❍❍r
rL3
✏✏✏✏
r
❅
❅r
L2
Figure 11. Knitting of a unispider graph
Let now G1 be a semiunispider graph with the vertex w of degree 4.
Assume that b is a vertex from a cycle of G1 such that deg(b) = 2 and
dG1
(w, b) = k, where 2k + 1 is the number of vertices in the cycle of G1.
Definition 4. A unicyclic graph G is called a knitting of G1 by chains
L1, . . . , Lr if G is obtained from G1 by gluing vertices with degree 2 from
the cycle of G1 and leaves of the chains L1, . . . , Lr such that any vertex
with degree 2 of the cycle of G1 may be glued with the leaf of exactly one
chain.
Note that, if the vertex b is glued with the leaves of two chains, then
graph G is a knitting of the unispider graph G1 (see Figure 5 or Figure 7)
by some chains.
The main result of this paper is the following.
Theorem 2. Let G = (V,E) be a unicyclic graph with vertices of degree 4.
Then dimG = 2 if and only if one of the following conditions holds:
“adm-n4” — 2019/1/24 — 10:02 — page 267 — #117
M. Dudenko, B. Oliynyk 267
(1) G is a unispider graph;
(2) G is a knitting of some unispider graph;
(3) G is a semiunispider graph;
(4) G is a knitting of some semiunispider graph;
Proof. Let G = (V,E) be a unicyclic graph with vertices of degree 4. We
need to show that if one of the conditions (1)–(4) holds then dimG = 2.
From Propositions 3 and 4 it follows that unispider and semiunispider
graphs have metric dimension 2. So, if G satisfies (1) or (3) then dimG = 2.
Let G be a knitting of some unispider graph. Denote the vertices of G
with degree 4 by u and w and let a and b be the leaves that are projected
to u and w, respectively (see Figure 11).
As dG(w, u) = k and 2k+1 is the number of all vertices in the cycle Ĝ
of G, a and b resolve all pairs of vertices from Ĝ. Moreover, from the proofs
of Propositions 3 and 4 it follows that a resolves all the pairs vertices that
are adjacent to b, and vice versa.
Let a chain Lj , 1 6 j 6 n be glued with unicyclic graph G in point z.
Without loss of generality, we may claim that this is L1 (see Figure 11).
Assume that vertices x, y and w are adjacent to z. Moreover, x belongs
to L1, and y is a vertex of Ĝ. Then x and y are not resolved by the basis
vertex b. But they are resolved by another basis vertex a. Hence, any pair
of vertices from G is resolved by a or b. Therefore, {a, b} is a metric basis
of G.
Let G be a knitting of some semiunispider graph, i. e. G satisfies
condition (4). Assume that w is a vertex of G with deg(w) = 4. Denote
the leaf that is projected to w by a. Let b be a vertex of the cycle V̂ such
that dG(w, b) = k. Similarly to the case of a unispider graph, {a, b} is a
metric basis of G.
Therefore, if G is a knitting of a unispider or semiunispider graph,
then dimG = 2.
Now let G = (V,E) be a unicyclic graph with vertices of degree 4 and
dimG = 2. From Theorem 1 it follows that G is odd and the maximum
number of vertices of degree 4 is two. From Lemma 1 (see [13]) we have,
that G can contain at most two main vertices. Moreover, from the proofs
of Lemma 1 and Theorem 1 it follows that a and b are projected to main
vertices and to vertices of degree 4, if they exist. Note that G has no less
than one vertex of degree 4, then if basis vertices are projected to u and
w, then u or w (may be u and w) has degree 4 and
dG(w, u) = k.
“adm-n4” — 2019/1/24 — 10:02 — page 268 — #118
268 Unicyclic graphs with vertices of degree 4
Hence, G is unispider, or semiunispider, or a knitting of some unispider
graph, or a knitting of some semiunispider graph.
For example, if G has exactly two vertices u and w of degree 4 and
two main vertices, then any vertex of degree 4 is the main vertex. Hence,
G is a unispider graph or its knitting (see Figure 3, Figure 11).
For the other number of vertices of degree 4 and main vertices the
proof is very similar.
Corollary 1. Let G = (V,E) be a unicyclic graph with vertices of degree 4,
and let {a, b} be a metric basis of G. Then the degrees of a and b are no
greater than 2.
The proof of Corollary 1 directly follows from the proof of Theorem 2.
References
[1] Frank Harary, Robert A.Melter, On the metric dimension of a graph, Ars Comb.,
V.2, 1976, pp.191–195.
[2] P. J. Slater, Leaves of trees, Congress. Numer., V.14, 1975, pp.549–559.
[3] M. Johnson Structure-activity maps for visualizing the graph variables arising in
drug design, J.Biopharm. Stat., 3 (2), 1993, pp 203-236.
[4] Robert A. Melter, I. Tomescu, Metric bases in digital geometry, Comput.Vision,
Graph. Image Process, 25 (1), 1984, pp 113-121.
[5] A.Sebo, E.Tannier, On metric generators of graphs, Math.of Operations Research,
29, 2004, pp.383-393.
[6] Michael R. Garey, David S. Johnson, Computers and intractability. A guide to the
theory of NP-completeness, San Francisco: W. H. Freeman and Company, 1979.
[7] S.Khuller, B. Raghavachari and A. Rosenfeld, Landmarks in graphs, Disc.
Appl.Math., 70, 1996, pp. 217-229.
[8] Gary Chartrand, Linda Eroh, Mark A. Johnson, Ortrud R. Oellermann, Resolv-
ability in graphs and the metric dimension of a graph, Discrete Appl. Math., V.
105, N. 1–3, 2000, pp. 99–113.
[9] G. Sudhakara, A. R. Hemanth Kumar, Graphs with metric dimension two — a
characterization, Adv. and Appl. in Disc. Math., 4 (2), 2009, pp.169–186.
[10] Marharyta Dudenko, Bogdana Oliynyk, On unicyclic graphs of metric dimension 2,
Algebra Discrete Math. 23 (2), 2017, pp. 216–222.
[11] Marharyta Dudenko, Metric dimension of unicyclic graphs with at most one main
vertex, Visnyk of Lviv University, V. 83, 2017, pp. 189–195.
[12] Reinhard Diestel, Graph Theory (3rd ed.), Berlin, New York: Springer-Verlag,
2005.
[13] Marharyta Dudenko, Unicyclic graphs with metric dimension 2, Nauk. Zapysky
NaUKMA, V. 165, 2015, pp. 7–10.
“adm-n4” — 2019/1/24 — 10:02 — page 269 — #119
M. Dudenko, B. Oliynyk 269
Contact information
M. Dudenko Department of Mathematics, National
University of Kyiv-Mohyla Academy, Skovorody
St. 2, Kyiv, 04070, Ukraine
E-Mail(s): rita.dudenko@gmail.com
B. Oliynyk Department of Mathematics, National
University of Kyiv-Mohyla Academy, Skovorody
St. 2, Kyiv, 04070, Ukraine
E-Mail(s): oliynyk@ukma.edu.ua
Received by the editors: 14.10.2018
and in final form 18.12.2018.
|