For a connected graph
G
= (
V,E
) of order at least two, a set
S
of vertices of
G
is a
monophonic set
of
G
if each vertex
v
of
G
lies on an
x
−
y
monophonic path for some elements
x
and
y
in
S
. The minimum cardinality of
a
monophonic set of
G
is the
monophonic number
of
G
, denoted by
m
(
G
). Certain general properties satisfied by the monophonic sets are studied. Graphs
G
of order
p
with
m
(
G
) = 2 or
p
or
p
− 1 are characterized. For every pair
a, b
of positive integers with 2 ≤
a
≤
b
, there is a connected graph
G
with
m
(
G
) =
a
and
g
(
G
) =
b
, where
g
(
G
) is the geodetic number of
G
. Also we study how the monophonic number of a graph is affected when pendant edges are added to the graph.
AMS Mathematics Subject Classification : 05C12.
1. Introduction
By a graph
G
= (
V,E
) we mean a finite undirected connected graph without loops or multiple edges. The order and size of
G
are denoted by
p
and
q
respectively. For basic graph theoretic terminology we refer to Harary
[5]
. For vertices
u
and
v
in a connected graph
G
, the
distance d
(
u, v
) is the length of a shortest
u
−
v
path in
G
. An
u
−
v
path of length
d
(
u, v
) is called an
u
−
v geodesic
. It is known that
d
is a metric on the vertex set
V
of
G
. The
neighborhood
of a vertex
v
is the set
N
(
v
) consisting of all vertices
u
which are adjacent with
v
. The
closed neighborhood
of a vertex
v
is the set
N
[
v
] =
N
(
v
)⋃{
v
}. A vertex
v
is an
extreme vertex
if the subgraph induced by its neighbors is complete. The
closed interval I
[
x, y
] consists of all vertices lying on some
x
−
y
geodesic of
G
, while for
A set
S
of vertices is a
geodetic set
if
I
[
S
] =
V
, and the minimum cardinality of a geodetic set is the
geodetic number g
(
G
). A geodetic set of cardinality
g
(
G
) is called a
g

set
. The geodetic number of a graph was introduced in
[1
,
6]
and further studied in
[2
,
4]
. The
detour distance D
(
u, v
) between two vertices
u
and
v
in
G
is the length of a longest
u
−
v
path in
G
. An
u
−
v
path of length
D
(
u, v
) is called an
u
−
v detour
. It is known that
D
is a metric on the vertex set
V
of
G
. The concept of detour distance was introduced and studied in
[3]
.
A graph G with rad_{m}G = 3 and diam_{m}G = 5
A
chord
of a path
P
is an edge joining two nonadjacent vertices of
P
. A path
P
is called
monophonic
if it is a chordless path. For any two vertices
u
and
v
in a connected graph
G
, the
monophonic distance d_{m}
(
u, v
) from
u
to
v
is defined as the length of a longest
u
−
v
monophonic path in
G
. The
monophonic eccentricity e_{m}
(
v
) of a vertex
v
in
G
is
e_{m}
(
v
) = max {
d_{m}
(
v, u
) :
u
∈
V
(
G
)}. The
monophonic radius
,
rad_{m}G
of
G
is
rad_{m}G
= min {
e_{m}
(
v
) :
v
∈
V
(
G
)} and the
monophonic diameter
,
diam_{m}G
of
G
is
diam_{m}G
= max {
e_{m}
(
v
) :
v
∈
V
(
G
)}. A vertex
u
in
G
is
monophonic eccentric vertex
of a vertex
v
in
G
if
e_{m}
(
u
) =
d_{m}
(
u, v
). For the graph
G
given in
Figure 1
,
d
(
v
_{1}
,
v
_{4}
) = 2,
D
(
v
_{1}
,
v
_{4}
) = 6 and
d_{m}
(
v
_{1}
,
v
_{4}
) = 4. Thus the monophonic distance is different from both the distance and the detour distance. The usual distance
d
and the detour distance
D
are metrics on the vertex set
V
of a connected graph
G
, whereas the monophonic distance
d_{m}
is not a metric on
V
. For the graph
G
given in
Figure 1
,
d_{m}
(
v
_{4}
,
v
_{6}
) = 5,
d_{m}
(
v
_{4}
,
v
_{5}
) = 1 and
d_{m}
(
v
_{5}
,
v
_{6}
) = 1. Hence
d_{m}
(
v
_{4}
,
v
_{6}
) >
d_{m}
(
v
_{4}
,
v
_{5}
) +
d_{m}
(
v
_{5}
,
v
_{6}
) and so the triangle inequality is not satisfied. It is clear that for vertices
u
and
v
in a connected graph
G
of order
p
, 0≤
d
(
u, v
)≤
d_{m}
(
u, v
)≤
D
(
u, v
)≤
p
− 1. The monophonic distance was introduced and studied in
[7]
. For the graph
G
given in
Figure 1
, the monophonic distance between vertices and the monophonic eccentricities of vertices are given in
Table 1
. Thus
rad_{m}G
= 3 and
diam_{m}G
= 5.
Monophonic eccentricities of the graphGgiven inFigure 1
Monophonic eccentricities of the graph G given in Figure 1
The following theorems will be used in the sequel.
Theorem 1.1
(
[6]
).
Each extreme vertex of a connected graph G belongs to every geodetic set of G
.
Theorem 1.2
(
[6]
).
For any tree T with k endvertices, g(T) = k
.
Throughout this paper
G
denotes a connected graph with at least two vertices.
2. Monophonic number of a graph
Definition 2.1.
A set
S
of vertices of a graph
G
is a
monophonic set
of
G
if each vertex
v
of
G
lies on an
x
−
y
monophonic path in
G
for some
x, y
∈
S
. The minimum cardinality of a monophonic set of
G
is the
monophonic number
of
G
and is denoted by
m
(
G
).
Example 2.2.
For the graph
G
given in
Figure 2
,
S
_{1}
= {
x,w
} and
S
_{2}
= {
u,w
} are the minimum monophonic sets of
G
and so
m
(
G
) = 2.
A graph G with m(G) = 2
A vertex
v
in a graph
G
is a
monophonic vertex
if
v
belongs to every minimum monophonic set of
G
. If
G
has a unique minimum monophonic set
S
, then every vertex in
S
is a monophonic vertex. In the next theorem, we show that there are certain vertices in a nontrivial connected graph
G
that are monophonic vertices of
G
.
Theorem 2.3.
Each extreme vertex of a connected graph G belongs to every monophonic set of G. Moreover, if the set S of all extreme vertices of G is a monophonic set, then S is the unique minimum monophonic set of G.
Proof
. Let
u
be an extreme vertex and let
S
be a monophonic set of
G
. Suppose that
u
∉
S
. Then
u
is an internal vertex of an
x
−
y
monophonic path, say
P
, for some
x, y
∈
S
. Let
v
and
w
be the neighbors of
u
on
P
. Then
v
and
w
are not adjacent and so
u
is not an extreme vertex, which is a contradiction. Therefore
u
belongs to every monophonic set of
G
. The second part of the theorem is clear.
Corollary 2.4.
For the complete graph K_{p}
(
p
≥ 2),
m
(
K_{p}
) =
p
.
Theorem 2.5.
Let G be a connected graph with a cutvertex v and let S be a monophonic set of G. Then every component of G
−
v contains an element of S.
Proof
. Suppose that there is a component
B
of
G
−
v
such that
B
contains no vertex of
S
. Let
u
be any vertex in
B
. Since
S
is a monophonic set, there exists a pair of vertices
x
and
y
in
S
such that
u
lies in some
x
−
y
monophonic path
P
:
x
=
u
_{0}
,
u
_{1}
,
u
_{2}
, ...,
u
, ...,
u_{n}
=
y
in
G
with
u
≠
x, y
. Since
v
is a cutvertex of
G
, the
x
−
u
subpath
P
_{1}
of
P
and the
u
−
y
subpath
P
_{2}
of
P
both contain
v
, it follows that
P
is not a path, which is a contradiction.
Theorem 2.6.
No cutvertex of a connected graph G belongs to any minimum monophonic set of G.
Proof
. Let
v
be a cutvertex of
G
and let
S
be a minimum monophonic set of
G
. Then by Theorem 2.5, every component of
G
−
v
contains an element of
S
. Let
U
and
W
be two distinct components of
G
−
v
and let
u
∈
U
and
w
∈
W
. Then
v
is an internal vertex of an
u
−
w
monophonic path. Let
S′
=
S
− {
v
}. It is clear that every vertex that lies on an
u
−
v
monophonic path also lies on an
u
−
w
monophonic path. Hence it follows that
S′
is a monophonic set of
G
, which is a contradiction to
S
a minimum monophonic set of
G
.
Corollary 2.7.
If T is a tree with k endvertices, then m
(
T
) =
k
.
Proof
. This follows from Theorem 2.3 and Theorem 2.6.
We denote the vertex connectivity of a connected graph
G
by
k
(
G
) or
k
.
Theorem 2.8.
If G is a non

complete connected graph such that it has a minimum cutset consisting of k vertices, then m
(
G
) ≤
p
−
k
.
Proof
. Since
G
is a noncomplete connected graph, it is clear that 1 ≤
k
≤
p
−2. Let
U
= {
u
_{1}
,
u
_{2}
,
u
_{3}
, ...,
u_{k}
} be a minimum cutset of
G
. Let
G
_{1}
,
G
_{2}
, ...,
G_{r}
, (
r
≥ 2) be the components of
G
−
U
and let
S
=
V
−
U
. Then every vertex
u_{i}
(1 ≤
i
≤
k
) is adjacent to at least one vertex of
G_{j}
, for each
j
(1 ≤
j
≤
r
). It is clear that
S
is a monophonic set of
G
and so
m
(
G
) ≤ 
S
 =
p
−
k
.
Remark 2.1.
The bound in Theorem 2.8 is sharp. For the cycle
C
_{4}
,
m
(
C
_{4}
) = 2. Also
k
= 2 and
p
−
k
= 2. Thus
m
(
G
) =
p
−
k
.
The following theorem is clear.
Theorem 2.9.
For any connected graph G
, 2 ≤
m
(
G
) ≤
p
.
The bounds in the above theorem are sharp. For the complete graph
K_{p}
(
p
≥ 2),
m
(
K_{p}
) =
p
. The set of two endvertices of a path
P_{n}
(
n
≥ 2) is its unique minimum monophonic set so that
m
(
P_{n}
) = 2.
Theorem 2.10.
For any integer k such that
2 ≤
k
≤
p there is a connected graph G of order p such that m
(
G
) =
k
.
Proof
. For
k
=
p
, the theorem follows from Corollary 2.4 by taking
G
=
K_{p}
. For 2 ≤
k
≤
p
−1, the tree
G
given in
Figure 3
has
p
vertices and it follows from Corollary 2.7 that
m
(
G
) =
k
.
The graph G in Theorem 2.10 with m(G) = k
Now we proceed to characterize graphs
G
for which the bounds in Theorem 2.9 are attained.
Theorem 2.11.
For any connected graph G of order p, m
(
G
) =
p if and only if G is complete.
Proof
. Let
m
(
G
) =
p
. Suppose that
G
is not a complete graph. Then there exist two vertices
u
and
v
such that
u
and
v
are not adjacent in
G
. Since
G
is connected, there is a monophonic path from
u
to
v
, say
P
, with length at least 2. Let
x
be a vertex of
P
such that
x
≠
u, v
. Then
S
=
V
−{
x
} is a monophonic set of
G
and hence
m
(
G
) ≤
p
−1, which is a contradiction. The converse follows from Corollary 2.4.
Definition 2.12.
Let
x
be any vertex in
G
. A vertex
y
in
G
is said to be an
x

monophonic superior vertex
if for any vertex
z
with
d_{m}
(
x, y
) <
d_{m}
(
x, z
),
z
lies on an
x
−
y
monophonic path.
Example 2.13.
For any vertex
x
in the cycle
C_{p}
(
p
≥ 4),
V
(
C_{p}
) −
N
[
x
] is the set of all
x
 monophonic superior vertices.
We give below a property related with monophonic eccentric vertex of
x
and
x
 monophonic superior vertex in a graph
G
.
Theorem 2.14.
Let x be any vertex in G. Then every monophonic eccentric vertex of x is an x

monophonic superior vertex
.
Proof
. Let
y
be a monophonic eccentric vertex of
x
so that
e_{m}
(
x
) =
d_{m}
(
x, y
). If
y
is not an
x
 monophonic superior vertex, then there exists a vertex
z
in
G
such that
d_{m}
(
x, y
) <
d_{m}
(
x, z
) and
z
does not lie on any
x
−
y
monophonic path and hence
e_{m}
(
x
) ≥
d_{m}
(
x, z
) >
d_{m}
(
x, y
), which is a contradiction.
Note 2.15.
The converse of Theorem 2.14 is not true. For the cycle
C
_{6}
:
v
_{1}
,
v
_{2}
,
v
_{3}
,
v
_{4}
,
v
_{5}
,
v
_{6}
,
v
_{1}
, the vertex
v
_{4}
is a
v
_{1}
 monophonic superior vertex and it is not a monophonic eccentric vertex of
v
_{1}
.
Theorem 2.16.
Let G be a connected graph. Then m
(
G
) = 2
if and only if there exist two vertices x and y such that y is an x

monophonic superior vertex and every vertex of G is on an x
−
y monophonic path
.
Proof
. Let
m
(
G
) = 2 and let
S
= {
x, y
} be a minimum monophonic set of
G
. If
y
is not an
x
 monophonic superior vertex, then there is a vertex
z
in
G
with
d_{m}
(
x, y
) <
d_{m}
(
x, z
) and
z
does not lie on any
x
−
y
monophonic path. Thus
S
is not a monophonic set of
G
, which is a contradiction. The converse is clear from the definition.
Theorem 2.17.
Let G be a connected graph of order p
≥ 3.
Then m
(
G
) =
p
−1
if and only if G
=
K
_{1}
+ ⋃
m_{j}K_{j}
,
where
Σ
m_{j}
≥ 2.
Proof
. Let
G
=
K
_{1}
+ ⋃
m_{j}
K_{j}
, where Σ
m_{j}
≥ 2. Then
G
has exactly one cutvertex and all other vertices are extreme and hence by Theorems 2.3 and 2.6,
m
(
G
) =
p
− 1. Conversely, let
m
(
G
) =
p
− 1. Let
S
be a monophonic set such that 
S
 =
p
− 1. Let
v
∉
S
. We show that
v
is a cutvertex of
G
. Otherwise,
G
−
v
has just one component. By Theorem 2.3,
v
is not an extreme vertex of
G
. Hence there exist vertices
x, y
∈
N
(
v
) such that
x
and
y
are not adjacent in
G
−
v
. Let
P
be an
x
−
y
monophonic path in
G
−
v
of length at least 2. Choose a vertex
z
on
P
such that
z
≠
x, y
. Note that
z
≠
v
. Then it is clear that
S
_{1}
=
V
− {
v, z
} is a monophonic set of
G
so that
m
(
G
) ≤
p
− 2, which is a contradiction. Hence
v
is a cutvertex of
G
and by Theorem 2.6,
v
is the only cutvertex of
G
.
Now, let
G
_{1}
,
G
_{2}
, ...,
G_{r}
be the components of
G
−
v
. First, we show that each
G_{i}
is complete. Suppose that some component, say
G
_{1}
, is not complete. Then there exist two vertices
x
and
y
in
G
_{1}
such that
x
and
y
are not adjacent. Choose a vertex
z
in an
x
−
y
geodesic such that
z
≠
x, y
. Then
S
_{2}
=
V
− {
v, z
} is a monophonic set of
G
so that
m
(
G
) ≤
p
− 2, which is a contradiction. Now, it remains to show that
v
is adjacent to every vertex of
G_{i}
for each
i
(1 ≤
i
≤
r
). Otherwise, there exists a component, say
G_{i}
, such that
v
is not adjacent to at least one vertex of
G_{i}
. Hence there is a vertex
u
in
G_{i}
such that
u
is not extreme in
G
. Then
S
_{3}
=
V
−{
v, u
} is a monophonic set of
G
so that
m
(
G
) ≤
p
−2, which is a contradiction. Hence
G
=
K
_{1}
+⋃
m_{j}K_{j}
, where
K
_{1}
= {
v
} and Σ
m_{j}
≥ 2.
3. Bounds for the monophonic number of a graph
In the following theorem we give an improved upper bound for the monophonic number of a graph in terms of its order and monophonic diameter. For convenience, we denote the monoponic diameter
diam_{m}G
by
d_{m}
itself.
Theorem 3.1.
If G is a non

trivial connected graph of order p and monophonic diameter d_{m}, then m
(
G
) ≤
p
−
d_{m}
+ 1.
Proof
. Let
u
and
v
be vertices of
G
such that
d_{m}
(
u, v
) =
d_{m}
and let
P
:
u
=
v
_{0}
,
v
_{1}
, ...,
v_{dm}
=
v
be a
u
−
v
monophonic path of length
d_{m}
. Let
S
=
V
− {
v
_{1}
,
v
_{2}
, ...,
v_{dm}
_{−1}
}. Then it is clear that
S
is a monophonic set of
G
so that
m
(
G
) ≤ 
S
 =
p
−
d_{m}
+ 1.
For the complete graph
K_{p}
(
p
≥ 2),
d_{m}
= 1 and
m
(
K_{p}
) =
p
so that the bound in Theorem 3.1 is sharp.
A
caterpillar
is a tree for which the removal of all the endvertices gives a path.
Theorem 3.2.
For every nontrivial tree T of order p and monophonic diameter d_{m}, m
(
T
) =
p
−
d_{m}
+ 1
if and only if T is a caterpillar.
Proof
. Let
T
be any nontrivial tree. Let
P
:
u
=
v
_{0}
,
v
_{1}
, ...,
v_{dm}
be a monophonic diametral path. Let
k
be the number of endvertices of
T
and
l
be the number of internal vertices of
T
other than
v
_{1}
,
v
_{2}
, ...,
v_{dm}
_{−1}
. Then
d_{m}
− 1 +
l
+
k
=
p
. By Corollary 2.7,
m
(
T
) =
k
and so
m
(
T
) =
p
−
d_{m}
−
l
+1. Hence
m
(
T
) =
p
−
d_{m}
+1 if and only if
l
= 0, if and only if all the internal vertices of
T
lie on the monophonic diametral path
P
, if and only if
T
is a caterpillar.
For any connected graph
G
,
rad_{m}G
≤
diam_{m}G
. It is shown in
[7]
that every two positive integers
a
and
b
with
a
≤
b
are realizable as the monophonic radius and monophonic diameter, respectively, of some connected graph. This theorem can also be extended so that the monophonic number can be prescribed when
rad_{m}G
<
diam_{m}G
.
Theorem 3.3.
For positive integers r, d and k
≥ 4
with r
<
d, there exists a connected graphs G such that rad_{m}G
=
r, diam_{m}G
=
d and m
(
G
) =
k
.
Proof
. We prove this theorem by considering two cases.
Case 1.
r
= 1. Then
d
≥ 2. Let
C
_{d+2}
:
v
_{1}
,
v
_{2}
, ...,
v
_{d+2}
,
v
_{1}
be a cycle of order
d
+2. Let
G
be the graph obtained by adding
k
−2 new vertices
u
_{1}
,
u
_{2}
, ...,
u
_{k−2}
to
C
_{d+2}
and joining each of the vertices
u
_{1}
,
u
_{2}
, ...,
u
_{k−2}
,
v
_{3}
,
v
_{4}
, ...,
v
_{d+1}
to the vertex
v
_{1}
. The graph
G
is shown in
Figure 4
. It is easily verified that 1 ≤
e_{m}
(
x
) ≤
d
for any vertex
x
in
G
and
e_{m}
(
v
_{1}
) = 1,
e_{m}
(
v
_{2}
) =
d
. Then
rad_{m}G
= 1 and
diam_{m}G
=
d
. Let
S
= {
u
_{1}
,
u
_{2}
, ...,
u
_{k−2}
,
v
_{2}
,
v
_{d+2}
} be the set of all extreme vertices of
G
. Since
S
is a monophonic set of
G
, it follows from Theorem 2.3 that
m
(
G
) =
k
.
Case 2.
r
≥ 2. Then
C
:
v
_{1}
,
v
_{2}
, ...,
v
_{r+2}
,
v
_{1}
be a cycle of order
r
+2 and let
W
=
K
_{1}
+
C
_{d+2}
be the wheel with
V
(
C
_{d+2}
) = {
u
_{1}
,
u
_{2}
, ...,
u
_{d+2}
},
K
_{1}
= {
v
_{1}
} and all other vertices distinct. Now, add
k
−3 new vertices
w
_{1}
,
w
_{2}
, ...,
w
_{k3}
and join each
w_{i}
(1 ≤
i
≤
k
− 3) to the vertex
v
_{1}
and obtain the graph
G
of
Figure 5
. It is easily verified that
r
≤
e_{m}
(
x
) ≤
d
for any vertex
x
in
G
and
e_{m}
(
v
_{1}
) =
r
and
e_{m}
(
u
_{1}
) =
d
. Thus
rad_{m}G
=
r
and
diam_{m}G
=
d
. Let
S
= {
w
_{1}
,
w
_{2}
, ...,
w
_{k3}
} be the set of all extreme vertices of
G
. By Theorem 2.3, every monophonic set of
G
contains
S
. It is clear that
S
is not a monophonic set of
G
. Let
T
=
S
⋃ {
u
_{1}
,
u
_{3}
,
v
_{3}
}. It is easily verified that
T
is a minimum monophonic set of
G
and so
m
(
G
) =
k
.
The graph G in Case 1 of Theorem 3.3
The graph G in Case 2 of Theorem 3.3
Problem 3.4.
For any three positive integers r, d and k
≥ 4
with r
=
d, does there exist a connected graph G with rad_{m}
=
r, diam_{m}
=
d and m
(
G
) =
k?
Theorem 3.5.
For each triple d, k, p of integers with
2 ≤
k
≤
p
−
d
+1
and d
≥
2, there is a connected graph G of order p such that diam_{m}G
=
d and m
(
G
) =
k
.
Proof
. Let
P
_{d+1}
:
u
_{1}
,
u
_{2}
, ...,
u
_{d+1}
be a path of length
d
. Add
p
−
d
−1 new vertices,
v
_{1}
,
v
_{2}
, ...,
v
_{k2}
,
w
_{1}
,
w
_{2}
, ...,
w
_{pdk+1}
to
P
_{d+1}
and join each
w_{i}
(1 ≤
i
≤
p
−
d
−
k
+1) to
u
_{1}
,
u
_{2}
and
u
_{3}
and also join each
v_{j}
(1 ≤
j
≤
k
2) to
u
_{2}
, thereby producing the graph
G
of
Figure 6
. Then
G
has order
p
and monophonic diameter
d
. If
p
−
d
−
k
+ 1 ≤ 1, then
S
= {
v
_{1}
,
v
_{2}
, ...,
v
_{k2}
,
u
_{1}
,
u
_{d+1}
} is the set of all extreme vertices of
G
. Since
S
is a monophonic set of
G
, it follows from Theorem 2.3 that
m
(
G
) =
k
. So, let
p
−
d
−
k
+ 1 ≥ 2. If
d
= 2, then
S
_{1}
= {
v
_{1}
,
v
_{2}
, ...,
v
_{k2}
} is the set of all extreme vertices of
G
. It is clear that neither
S
_{1}
nor
S
_{1}
⋃ {
x
} where
x
∉
S
_{1}
, is a monophonic set of
G
. Since
S
_{2}
=
S
_{1}
⋃ {
u
_{1}
,
u
_{3}
} is a monophonic set of
G
, it follows from Theorem 2.3 that
m
(
G
) =
k
. If
d
≥ 3, then
S
_{3}
= {
v
_{1}
,
v
_{2}
, ...,
v
_{k2}
,
u
_{d+1}
} is the set of all extreme vertices of
G
. Now,
S
_{3}
is not a monophonic set of
G
. Since
S
_{4}
=
S
_{3}
⋃ {
u
_{1}
} is a monophonic set of
G
, it follows from Theorem 2.3 that
m
(
G
) =
k
.
The graph G in Theorem 3.5 with diam_{m}G = d and m(G) = k
Theorem 3.6.
For any connected graph G of order p
, 2 ≤
m
(
G
) ≤
g
(
G
) ≤
p
.
Proof
. Since every geodesic is a monophonic path, it follows that every geodetic set is a monophonic set, and hence
m
(
G
) ≤
g
(
G
). The other inequalities are trivial.
Remark 3.1.
The bounds in Theorem 3.6 are sharp. For the complete graph
K_{p}
,
m
(
K_{p}
) =
g
(
K_{p}
) =
p
. For a nontrivial path
P_{n}
,
m
(
P_{n}
) =
g
(
P_{n}
) = 2. Also, if
G
is a nontrivial tree, or an even cycle, or a complete bipartite graph, then
m
(
G
) =
g
(
G
). All the inequalities in Theorem 3.6 are strict. For the graph
G
given in
Figure 7
,
S
= {
v
_{6}
,
v
_{7}
,
v
_{3}
} is a minimum monophonic set of
G
so that
m
(
G
) = 3 and no 3elements subset of the vertex set is a geodetic set of
G
. Since
S
∪ {
v
_{1}
} is a geodetic set of
G
, it follows that
g
(
G
) = 4. Thus we have 2 <
m
(
G
) <
g
(
G
) <
p
.
A graph G in Remark 3.1 with 2 < m(G) < g(G) < p
In view of this remark, we have the following problem.
Problem 3.7.
Characterize graphs G for which m
(
G
) =
g
(
G
)
Theorem 3.8.
For every pair a, b of positive integers with
2 ≤
a
≤
b, there is a connected graph G with m
(
G
) =
a and g
(
G
) =
b
.
Proof
. For 2 ≤
a
=
b
, any tree with
a
endvertices has the desired properties, by Theorem 1.2 and Corollary 2.7. So, assume that 2 ≤
a
<
b
. Let
P_{i}
:
x_{i}
,
w_{i}
,
y_{i}
(1 ≤
i
≤
b
−
a
) be
b
−
a
copies of a path of length 2 and
P
:
v
_{1}
,
v
_{2}
,
v
_{3}
,
v
_{4}
a path of length 3. Let
G
be the graph obtained by joining each
x_{i}
(1 ≤
i
≤
b
−
a
) in
P_{i}
and
v
_{2}
in
P
, joining each
y_{i}
(1 ≤
i
≤
b
−
a
) in
P_{i}
and
v
_{4}
in
P
; and adding
a
− 1 new vertices
u
_{1}
,
u
_{2}
, ...,
u
_{a−1}
and joining each
u_{i}
(1 ≤
i
≤
a
−1) to
v
_{4}
. The graph
G
is shown in
Figure 8
. Let
S
= {
v_{i}
,
u_{i}
, ...,
u
_{a−1}
} be the set of all extreme vertices of
G
. It is easily verified that
S
is a monophonic set of
G
and so by Theorem 2.3,
m
(
G
) = 
S
 =
a
.
The graph G in Theorem 3.8 with m(G) = a and g(G) = b
Next, we show that
g
(
G
) =
b
. By Theorem 1.1, every geodetic set of
G
contains
S
. Clearly,
S
is not a geodetic set of
G
. It is easily verified that at least one of the vertex of each
P_{i}
(1 ≤
i
≤
b
−
a
) must belong to every geodetic set of
G
. Since
T
=
S
∪ {
w
_{1}
,
w
_{2}
, ...,
w
_{b−a}
} is a geodetic set of
G
, it follows from Theorem 1.1 that
T
is a minimum geodetic set of
G
and so
g
(
G
) =
b
.
4. Monophonic number of a graph by adding some pendant edges
Theorem 4.1.
If G′ is a graph obtained by adding l pendant edges to a connected graph G, then m
(
G
) ≤
m
(
G′
) ≤
m
(
G
) +
l
.
Proof
. Let
G′
be the connected graph obtained from
G
by adding
l
pendant edges
u_{i}v_{i}
(1 ≤
i
≤
l
), where each
u_{i}
(1 ≤
i
≤
l
) is a vertex of
G
and each
v_{i}
(1 ≤
i
≤
l
) is not a vertex of
G
. Let
S
be a minimum monophonic set of
G
. Then
S
∪ {
v
_{1}
,
v
_{2}
, ...,
v_{l}
} is a monophonic set of set of
G′
and so
m
(
G′
) ≤
m
(
G
) +
l
.
Now, we claim that
m
(
G
) ≤
m
(
G′
). Suppose that
m
(
G
) >
m
(
G′
). Then let
S
′ be a monophonic set of
G′
with 
S′
 <
m
(
G
). Since each
v_{i}
(1 ≤
i
≤
l
) is an extreme vertex of
G′
, it follows from Theorem 2.3 that {
v
_{1}
,
v
_{2}
, ...,
v_{l}
} ⊆
S′
. Let
S
= (
S′
− {
v
_{1}
,
v
_{2}
, ...,
v_{l}
}) ∪ {
u
_{1}
,
u
_{2}
, ...,
u_{l}
}. Then
S
is a subset of
V
(
G
) and 
S
 = 
S′
 <
m
(
G
). Now, we show that
S
is a monophonic set of
G
. Let
w
∈
V
(
G
)−
S
. Since
S′
is a monophonic set of
G′
,
w
lies on an
x
−
y
monophonic path
P
in
G′
for some vertices
x, y
∈
S′
. If neither
x
nor
y
is
v_{i}
(1 ≤
i
≤
l
), then
x, y
∈
S
. If exactly one of
x, y
is
v_{i}
(1 ≤
i
≤
l
), say
x
=
v_{i}
. Then
w
lies on the
u_{i}
−
y
monophonic path in
G
obtained from
P
by removing
v_{i}
. If both
x, y
∈ {
v
_{1}
,
v
_{2}
, ...,
v_{l}
}, then let
x
=
v_{i}
and
y
=
v_{j}
where
i
≠
j
. Hence
w
lies on the
u_{i}
−
u_{j}
monophonic path in
G
obtained from
P
by removing
v_{i}
and
v_{j}
. Thus
S
is a monophonic set of
G
. Hence
m
(
G
) ≤ 
S
 <
m
(
G
), which is a contradiction.
Remark 4.1.
The bounds for
m
(
G′
) in Theorem 4.1 are sharp. Consider a tree
T
with number of endvertices
k
≥ 3. Let
S
= {
v
_{1}
,
v
_{2}
, ...,
v_{k}
} be the set of all endvertices of
T
. Then by Corollary 2.7,
m
(
G
) =
k
. If we add a pendant edge to an endvertex of
T
, then we obtain another tree
T′
with
k
endvertices. Hence
m
(
T
) =
m
(
T′
). On the otherhand, if we add
l
pendant edges to a cutvertex of
T
, then we obtain another tree
T′′
with
k
+
l
endvertices. Then by Corollary 2.7,
m
(
T′
) =
m
(
T
) +
l
.
Now, we proceed to characterize graphs
G
for which
m
(
G
) =
m
(
G′
), where
G′
is obtained from
G
by adding
l
pendant edges.
Theorem 4.2.
Let G′ be a graph obtained from a connected graph G by adding l pendant edges u_{i}v_{i}
(1 ≤
i
≤
l
),
where u_{i}
∈
V
(
G
)
and v_{i}
∉
V
(
G
).
Then m
(
G
) =
m
(
G′
)
if and only if l
≤
m
(
G
)
and
{
u
_{1}
,
u
_{2}
, ...,
u_{l}
}
is a subset of some minimum monophonic set of G
.
Proof
. Let
l
≤
m
(
G
) and let {
u
_{1}
,
u
_{2}
, ...,
u_{l}
} be a subset of some minimum monophonic set
S
of
G
. Let
S′
= (
S
− {
u
_{1}
,
u
_{2}
, ...,
u_{l}
}) ⋃ {
v
_{1}
,
v
_{2}
, ...,
v_{l}
}. Then 
S′
 = 
S
. We show that
S′
is a monophonic set of
G′
. Let
z
∈
V
(
G′
) −
S′
. If
z
=
u_{i}
(1 ≤
i
≤
l
), then
z
lies on every
v_{i}
−
w
monophonic path in
G′
, where
w
∈
S′
, since
u_{i}
is the only vertex adjacent to
v_{i}
. So we may assume that
z
≠
u_{i}
(1 ≤
i
≤
l
). Since
z
is a vertex of
G
and
S
is a monophonic set of
G
, it follows that
z
lies on some
x
−
y
monophonic path
P
in
G
for some
x, y
∈
S
. Then by an argument similar to the one used in the proof of Theorem 4.1, we can show that
S′
is a monophonic set of
G′
. Hence
m
(
G′
) ≤ 
S′
 = 
S
 =
m
(
G
). Now, the result follows from Theorem 4.1.
Conversely, let
m
(
G
) =
m
(
G′
). Suppose that
l
>
m
(
G
). Since each
v_{i}
(1 ≤
i
≤
l
) is an endvertex of
G′
, by Theorem 2.3,
m
(
G′
) ≥
l
. Hence
m
(
G′
) >
m
(
G
), which is a contradiction. Thus
l
≤
m
(
G′
). Now, let
S′
be a minimum monophonic set of
G′
. Since each
u_{i}
(1 ≤
i
≤
l
) is a cutvertex of
G′
, it follows from Theorem 2.6 that
u_{i}
∉
S′
for 1 ≤
i
≤
l
. Since each
v_{i}
(1 ≤
i
≤
l
) is an endvertex of
G′
, it follows from Theorem 2.3 that
v^{i}
∈
S′
for 1 ≤
i
≤
l
. Let
S
= (
S′
− {
v
_{1}
,
v
_{2}
, ...,
v_{l}
}) ⋃ {
u
_{1}
,
u
_{2}
, ...,
u_{l}
}. Then
S
is a subset of
V
(
G
) and 
S
 = 
S′
. Then, as in the proof of Theorem 4.1,
S
is a monophonic set of
G
. Since 
S
 = 
S′
 =
m
(
G′
) =
m
(
G
), it follows that
S
is a minimum monophonic set of
G
that contains {
u
_{1}
,
u
_{2}
, ...,
u_{l}
}.
Theorem 4.3.
For each triple a, b and l of integers with
2 ≤
a
≤
b
, 1 ≤
l
≤
b
,
and a
+
l
−
b
≥ 0,
there exists a connected graph G with m
(
G
) =
a and m
(
G′
) =
b
,
where G′ is a graph obtained by adding l pendant edges to G
.
Proof
. Let
G
be a tree with number of endvertices
a
. Let
G′
be a graph obtained by adding
b
−
a
pendant edges to a cutvertex of
G
and also adding
l
+
a
−
b
pendant edges each with different endvertices of
G
. Then
G′
is another tree with
b
endvertices. By Corollary 2.7,
m
(
G
) =
a
and
m
(
G′
) =
b
.
BIO
A. P. Santhakumaran received Ph.D. in Mathematics from Manonmaniam Sundaranar University, Tirunelveli. He was professor of Mathematics from 1977 to 2012 in St. Xavier’s College(Autonomous), Palayamkottai  627 002, India. He is currently Professor of Mathematics in Hindustan University, Hindustan Institue of Technology and Science, Chennai 603 103. His research interests include convexiy, centrality and domination in graphs.
Department of Mathematics, Hindustan University, Hindustan Institute of Technology and Science, Chennai  603 103, India.
email: apskumar1953@yahoo.co.in
P. Titus received Ph.D. in Mathematics from Manonmaniam Sundaranar University, Tirunelveli. He has 15 years of teaching experience in Mathematics both in Engineering Colleges and Anna University. His research interests include geodomination, detour and monophonic concepts in graphs.
Department of Mathematics, University College of Engineering Nagercoil, Anna University, Tirunelveli Region, Nagercoil  629 004, India.
email: titusvino@yahoo.com
K. Ganesamoorthy received Ph.D. in Science and Humanities from Anna University, Chennai. Since 2009 he has been at University College of Engineering Nagercoil, Anna University, Tirunelveli Region, Nagercoil  629 004, India. His research interests include detour, monophonic concepts in graphs.
Department of Mathematics, University College of Engineering Nagercoil, Anna University, Tirunelveli Region, Nagercoil  629 004, India.
email: kvgm 2005@yahoo.co.in
Buckley F.
,
Harary F.
(1990)
Distance in Graphs
AddisonWesley
Redwood City, CA
Buckley F.
,
Harary F.
,
Quintas L.U.
(1988)
Extremal results on the geodetic number of a graph
Scientia
A2
17 
26
Chartrand G.
,
Escuadro H.
,
Zhang P.
(2005)
Detour distance in graphs
J. Combin. Math. Combin. Comput.
53
75 
94
Chartrand G.
,
Harary F.
,
Zhang P.
(2002)
On the geodetic number of a graph
Networks.
39
1 
6
DOI : 10.1002/net.10007
Harary F.
1969
Graph Theory
AddisonWesley
Harary F.
,
Loukakis E.
,
Tsouros C.
(1993)
The geodetic number of a graph
Math. Comput. Modeling
17
(11)
87 
95
Santhakumaran A.P.
,
Titus P.
(2011)
Monophonic distance in graphs
Discrete Mathematics, Algorithms and Applications
3
(2)
159 
169
DOI : 10.1142/S1793830911001176