International J.Math. Combin. Vol.

3 (2008), 94-104
Simple Path Covers in Graphs
S. Arumugam and I. Sahul Hamid
National Centre for Advanced Research in Discrete Mathematics of
Kalasalingam University, Anand Nagar, Krishnankoil-626190, INDIA.
E-mail: s arumugam [email protected]
Abstract: A simple path cover of a graph G is a collection of paths in G such that every
edge of G is in exactly one path in and any two paths in have at most one vertex in
common. More generally, for any integer k 1, a Smarandache path k-cover of a graph G
is a collection of paths in G such that each edge of G is in at least one path of and
two paths of have at most k vertices in common. Thus if k = 1 and every edge of G is
in exactly one path in , then a Smarandache path k-cover of G is a simple path cover of
G. The minimum cardinality of a simple path cover of G is called the simple path covering
number of G and is denoted by s(G). In this paper we initiate a study of this parameter.
Key Words: Smarandache path k-cover, simple path cover, simple path covering number.
AMS(2000): 05C35, 05C38.
1. Introduction
By a graph G = (V, E) we mean a nite, undirected graph with neither loops nor multiple edges.
The order and size of G are denoted by p and q respectively. For graph theoretic terminology
we refer to Harary [5]. All graphs in this paper are assumed to be connected and non-trivial.
If P = (v
0
, v
1
, v
2
, . . . , v
n
) is a path or a cycle in a graph G, then v
1
, v
2
, . . . , v
n1
are called
internal vertices of P and v
0
, v
n
are called external vertices of P. If P = (v
0
, v
1
, v
2
, . . . , v
n
) and
Q = (v
n
= w
0
, w
1
, w
2
, . . . , w
m
) are two paths in G, then the walk obtained by concatenating P
and Q at v
n
is denoted by P Q and the path (v
n
, v
n1
, . . . , v
2
, v
1
, v
0
) is denoted by P
1
. For a
unicyclic graph G with cycle C, if w is a vertex of degree greater than 2 on C with deg w = k,
let e
1
, e
2
, . . . , e
k2
be the edges of E(G) E(C) incident with w. Let T
i
, 1 i k 2, be the
maximal subtree of G such that T
i
contains the edge e
i
and w is a pendant vertex of T
i
. Then
T
1
, T
2
, . . . , T
k2
are called the branches of G at w. Also the maximal subtree T of G such that
V (T) V (C) = {w} is called the subtree rooted at w.
The concept of path cover and path covering number of a graph was introduced by Harary
[6]. Preliminary results on this parameter were obtained by Harary and Schwenk [7], Peroche
[9] and Stanton et al. [10], [11].
1
Supported by NBHM Project 48/2/2004/R&D-II/7372.
2
Received May 16, 2008. Accepted September 16, 2008.
Simple Path Covers in Graphs 95
Denition 1.1([6]) A path cover of a graph G is a collection of paths in G such that every
edge of G is in exactly one path in . The minimum cardinality of a path cover of G is called
the path covering number of G and is denoted by (G) or simply .
Theorem 1.2([10]) For any tree T with k vertices of odd degree, (T) =
k
2
.
Theorem 1.3([7]) The path covering number of the complete graph K
p
is given by (K
p
) =
_
p
2
_
.
(For any real number x, x denotes the least positive integer x.)
Theorem 1.4([4]) Let G be a unicyclic graph with unique cycle C. Let m denote the number
of vertices of degree greater than 2 on C. Let k denote the number of vertices of odd degree.
Then
(G) =
_

_
2 if m = 0
k
2
+ 1 if m = 1
k
2
otherwise
Theorem 1.5([4]) For any graph G, (G)
_

2
_
.
The concepts of graphoidal cover and acyclic graphoidal cover were introduced by Acharya
et al. [1] and Arumugam et al. [4].
Denition 1.6([1]) A graphoidal cover of a graph G is a collection of (not necessarily open)
paths in G satisfying the following conditions.
(i) Every path in has at least two vertices.
(ii) Every vertex of G is an internal vertex of at most one path in .
(iii)Every edge of G is in exactly one path in .
If further no member of is a cycle in G, then is called an acyclic graphoidal cover of G.
The minimum cardinality of a graphoidal cover of G is called the graphoidal covering number of
G and is denoted by (G). Similarly we dene the acyclic graphoidal covering number
a
(G).
An elaborate review of results in graphoidal covers with several interesting applications
and a large collection of unsolved problems is given in Arumugam et al.[2].
For any graph G = (V, E), = E is trivially an acyclic graphoidal cover and has the
interesting property that any two paths in have at most one vertex in common. Motivated
by this observation we introduced the concept of simple acyclic graphoidal covers in graphs [3].
Denition 1.7([3]) A simple acyclic graphoidal cover of a graph G is an acyclic graphoidal
cover of G such that any two paths in have at most one vertex in common. The minimum
cardinality of a simple acyclic graphoidal cover of G is called the simple acyclic graphoidal
covering number of G and is denoted by
as
(G) or simply
as
.
Denition 1.8 Let be a collection of internally disjoint paths in G. A vertex of G is said to
be an interior vertex of if it is an internal vertex of some path in , otherwise it is said to
96 S. Arumugam and I. Sahul Hamid
be an exterior vertex of .
Theorem 1.9([3]) For any simple acyclic graphoidal cover of a graph G, let t

denote the
number of exterior vertices of . Let t = min t

, where the minimum is taken over all simple

acyclic graphoidal covers of G. Then
as
(G) = q p +t.
Theorem 1.10([3]) Let G be a unicyclic graph with n pendant vertices. Let C be the unique
cycle in G and let m denote the number of vertices of degree greater than 2 on C. Then

as
(G) =
_

_
3 if m = 0
n + 2 if m = 1
n + 1 if m = 2
n if m 3
Theorem 1.11([3]) Let m and n be integers with n m 4. Then

as
(K
m,n
) =
_

_
mn mn if n
_
m
2
_
mn mn +r if n =
_
m
2
_
+r, r > 0.
In this paper we introduce the concept of simple path cover and simple path covering
number
s
of a graph G and initiate a study of this parameter. We observe that the concept
of simple path cover is a special case of Smarandache path k-cover [8]. For any integer k 1,
a Smarandache path k-cover of a graph G is a collection of paths in G such that each edge
of G is in at least one path of and two paths of have at most k vertices in common. Thus
if k = 1 and every edge of G is in exactly one path in , then a Smarandache path k-cover of
G is a simple path cover of G.
2. Main results
Denition 2.1 A simple path cover of a graph G is a path cover of G such that any two
paths in have at most one vertex in common. The minimum cardinality of a simple path
cover of G is called the simple path covering number of G and is denoted by
s
(G). Any simple
path cover of G for which || =
s
(G) is called a minimum simple path cover of G.
Example 2.2 Consider the graph G given in Fig.2.1.
Simple Path Covers in Graphs 97
v
1 v
2 v
3
v
4
v
6
v
5 v
7
v
8
Fig. 2.1
Then = {(v
1
, v
4
, v
7
, v
8
), (v
3
, v
4
, v
5
, v
6
), (v
2
, v
4
), (v
7
, v
5
)} is a minimum simple path cover of G
so that
s
(G) = 4.
Remark 2.3 Every path in a simple path cover of a graph G is an induced path.
Theorem 2.4 For any simple path cover of a graph G, let t

P
t(P), where t(P) denotes
the number of internal vertices of P and let t = max t

, where the maximum is taken over all

simple path covers of G. Then
s
(G) = q t.
Proof Let be any simple path cover of G. Then
q =

P
|E(P)|
=

P
(t(P) + 1)
= || +

P
t(P)
= || +t

Hence || = q t

so that
s
(G) = q t.
Corollary 2.5 For any graph G with k vertices of odd degree
s
(G) =
k
2
+

vV (G)
_
deg v
2
_
t.
Proof Since q =
k
2
+

vV (G)
_
deg v
2
_
the result follows.
Corollary 2.6 For any graph G,
s
(G)
k
2
where k is the number of vertices of odd degree in
G. Further, the following are equivalent.
(i)
s
(G) =
k
2
.
(ii) There exists a simple path cover of G such that every vertex v in G is an internal
vertex of
_
deg v
2
_
paths in .
(ii)There exists a simple path cover of G such that every vertex of odd degree is an
98 S. Arumugam and I. Sahul Hamid
external vertex of exactly one path in and no vertex of even degree is an external vertex of
any path in .
Remark 2.7 For any (p, q)-graph G,
s
(G) q. Further, equality holds if and only if G is
complete. Hence it follows from Theorem 1.3 that
s
(K
n
) = (K
n
) if and only if n = 2.
Remark 2.8 Since any path cover of a tree T is a simple path cover of T, it follows from
Theorem 1.2 that
s
(T) = (T) =
k
2
, where k is the number of vertices of odd degree in T.
We now proceed to determine the value of
s
for unicyclic graphs and wheels.
Theorem 2.9 Let G be a unicyclic graph with cycle C. Let m denote the number of vertices
of degree greater than 2 on C. Let k be the number of vertices of odd degree. Then

s
(G) =
_

_
3 if m = 0
k
2
+ 2 if m = 1
k
2
+ 1 if m = 2
k
2
if m 3
Proof Let C = (v
1
, v
2
, . . . , v
r
, v
1
).
Case 1. m = 0.
Then G = C so that
s
(G) = 3.
Case 2. m = 1.
Let v
1
be the unique vertex of degree greater than 2 on C. Let G
1
be the tree rooted at
v
1
. Then G
1
has k vertices of odd degree and hence
s
(G
1
) =
k
2
. Let
1
be a minimum simple
path cover of G
1
.
If deg v
1
is odd, then deg
G1
v
1
is odd. Let P be the path in
1
having v
1
as a terminal
vertex. Now, let
P
1
= P (v
1
, v
2
)
P
2
= (v
2
, v
3
, . . . , v
r
) and
P
3
= (v
r
, v
1
).
If deg v
1
is even, then deg
G1
v
1
is even. Let P = (x
1
, x
2
, . . . , x
r
, v
1
, x
r+1
, . . . , x
s
) be a path
in
1
having v
1
as an internal vertex. Now, let
P
1
= (x
1
, x
2
, . . . , x
r
, v
1
, v
2
)
P
2
= (x
s
, x
s1
, . . . , x
r+1
, v
1
, v
r
) and
P
3
= (v
2
, v
3
, . . . , v
r
).
Then = {
1
{P}} {P
1
, P
2
, P
3
} is a simple path cover of G and hence
s
(G)
|
1
| + 2 =
k
2
+ 2. Further, for any simple path cover of G, all the k vertices of odd degree
and at least two vertices on C are terminal vertices of paths in . Hence t q
k
2
2, so that

s
(G) = q t
k
2
+ 2. Thus
s
(G) =
k
2
+ 2.
Simple Path Covers in Graphs 99
Case 3. m = 2.
Let v
1
and v
i
, where 2 i r, be the vertices of degree greater than 2 on C. Let P and
Q denote respectively the (v
1
, v
i
)-section and (v
i
, v
1
)-section of C. Let v
j
be an internal vertex
of P(say). Let R
1
and R
2
be the (v
1
, v
j
)-section of P and (v
j
, v
i
)-section P respectively. Let
G
1
be the graph obtained by deleting all the internal vertices of P.
Subcase 3.1 Both deg v
1
and deg v
i
are odd.
Then both deg
G1
v
1
and deg
G1
v
i
are even. Hence G
1
is a tree with k 2 odd vertices so
that
s
(G
1
) =
k
2
1. Let
1
be a minimum simple path cover of G
1
. Then =
1
{R
1
, R
2
}
is a simple path cover of G and || =
k
2
+ 1.Hence
s
(G)
k
2
+ 1.
Subcase 3.2 Both deg v
1
and deg v
i
are even.
Then deg
G1
v
1
and deg
G1
v
i
are odd. Hence G
1
is a tree with k +2 vertices of odd degree
so that
s
(G
1
) =
k
2
+ 1. Let
1
be a minimum simple path cover of G
1
.
Suppose v
1
and v
i
are terminal vertices of two dierent paths in
1
, say P
1
and P
2
respec-
tively. Now, let
Q
1
= P
1
R
1
Q
2
= P
2
R
1
2
and
= {
1
{P
1
, P
2
}} {Q
1
, Q
2
}.
Suppose there exists a path P
1
in
1
having both v
1
and v
i
as its end vertices. Then let
P
1
= Q. Let P
2
be an u
1
-w
1
path in
1
having v
1
as an internal vertex and P
3
be an u
2
-w
2
path
in
1
having v
i
as an internal vertex. Let S
1
and S
2
be the (u
1
, v
1
)-section of P
2
and (w
1
, v
1
)-
section of P
2
respectively. Let S
3
and S
4
be the (u
2
, v
i
)-section of P
3
and (w
2
, v
i
)-section of P
3
respectively. Now, let
Q
1
= S
1
P
1
S
1
3
Q
2
= S
2
R
1
Q
3
= S
4
R
1
2
and
= {
1
{P
1
, P
2
, P
3
}} {Q
1
, Q
2
, Q
3
}.
Then is a simple path cover of G and || = |
1
| =
k
2
+ 1 and hence
s
(G)
k
2
+ 1.
Subcase 3.3 deg v
1
is odd and deg v
i
is even.
Then deg
G1
v
1
is even and deg
G1
v
i
is odd. Hence G
1
is a tree with k vertices of odd degree
so that
s
(G
1
) =
k
2
. Let
1
be a minimum simple path cover of G
1
. Let P
1
be the path in
1
having v
i
as a terminal vertex.
If E(P
1
) E(Q) = , let
Q
1
= P
1
R
1
2
Q
2
= R
1
and
= {
1
{P
1
}} {Q
1
, Q
2
}.
Suppose E(P
1
) E(Q) = . Since deg
G1
v
i
3, there exists an u
1
-w
1
path in
1
, say P
2
,
having v
i
as an internal vertex. Let S
1
and S
2
be the (w
1
, v
i
)-section of P
2
and (u
1
, v
i
)-section
of P
2
respectively. Now, let
Q
1
= P
1
S
1
1
Q
2
= S
2
R
1
2
100 S. Arumugam and I. Sahul Hamid
Q
3
= R
1
and
= {
1
{P
1
, P
2
}} {Q
1
, Q
2
, Q
3
}.
Then is a simple path cover of G and || = |
1
| + 1 =
k
2
+ 1. Hence
s
(G)
k
2
+ 1.
Thus in either of the above subcases, we have
s
(G)
k
2
+ 1. Also, for any simple path
cover of G all the k vertices of odd degree and at least one vertex on C are terminal vertices
of paths in . Hence t q
k
2
1, so that
s
(G) = q t
k
2
+ 1.
Hence
s
(G) =
k
2
+ 1.
Case 4. m 3.
Let v
i1
, v
i2
, . . . , v
is
, where 1 i
1
< i
2
< < i
s
r and s 3, be the vertices of degree
greater than 2 on C. Let
ij
, 1 j s, be a minimum simple path cover of the tree rooted
at v
ij
. Consider the vertices v
i1
, v
i2
and v
i3
. For each j, where 1 j 3, let P
j
be the
path in
ij
in which v
ij
is a terminal vertex if deg v
ij
is odd, otherwise let P
j
be an u
j
-w
j
path in
ij
in which v
ij
is an internal vertex and R
j
and S
j
be the (u
j
, v
ij
) and (w
j
, v
ij
)-
sections of P
j
respectively. Further, let P = (v
i1
, v
i1+1
, . . . , v
i2
), Q = (v
i2
, v
i2+1
, . . . , v
i3
) and
R = (v
i3
, v
i3+1
, . . . , v
i1
).
If deg v
i1
, deg v
i2
and deg v
i3
are even, let Q
1
= R
1
P R
1
2
, Q
2
= S
2
Q R
1
3
and
Q
3
= S
3
R S
1
1
.
If deg v
i1
, deg v
i2
and deg v
i3
are odd, let Q
1
= P
1
P, Q
2
= P
2
Q and Q
3
= P
3
R.
If deg v
i1
, deg v
i2
are odd and deg v
i3
is even, let Q
1
= P
1
P P
1
2
, Q
2
= R
3
Q
1
and
Q
3
= S
3
R.
If deg v
i1
, deg v
i2
are even and deg v
i3
is odd, let Q
1
= R
1
P R
1
2
, Q
2
= S
2
Q P
1
3
and Q
3
= R S
1
1
.
Then = (
s

j=1

ij
{P
1
, P
2
, P
3
}) {Q
1
, Q
2
, Q
3
} is a simple path cover of G such that
every vertex of odd degree is an external vertex of exactly one path in and no vertex of even
degree is an external vertex of any path in . Hence
s
(G) =
k
2
.
Corollary 2.10 Let G be as in Theorem 2.9. Then
s
(G) = (G) if and only if m 3.
Proof The proof follows from Theorem 2.9 and Theorem 1.4.
We observe that there are innite families of graphs such as trees and unicyclic graphs
having at least three vertices of degree greater than 2 on C for which
s
= and so the
following problem arises naturally.
Problem 2.11 Characterize graphs for which
s
= .
Theorem 2.12 For a wheel W
n
= K
1
+C
n1
, we have

s
(W
n
) =
_
_
_
6 if n = 4
_
n
2
_
+ 3 if n 5
Proof Let V (W
n
) = {v
0
, v
1
, . . . , v
n1
} and E(W
n
) = {v
0
v
i
: 1 i n 1} {v
i
v
i+1
: 1
i n 2} {v
1
v
n1
}.
Simple Path Covers in Graphs 101
If n = 4, then W
n
= K
4
and hence
s
(W
n
) = 6.
Now, suppose n 5. Let r =
_
n
2
_
If n is odd, let
P
i
= (v
i
, v
0
, v
r+i
), i = 1, 2, . . . , r.
P
r+1
= (v
1
, v
2
, . . . , v
r
),
P
r+2
= (v
1
, v
2r
, v
2r1
, . . . , v
r+2
) and
P
r+3
= (v
r
, v
r+1
, v
r+2
).
If n is even, let
P
i
= (v
i
, v
0
, v
r1+i
), i = 1, 2, . . . , r 1 .
P
r
= (v
0
, v
2r1
),
P
r+1
= (v
1
, v
2
, . . . , v
r1
),
P
r+2
= (v
1
, v
2r1
, . . . , v
r+1
) and
P
r+3
= (v
r1
, v
r
, v
r+1
).
Then = {P
1
, P
2
, . . . , P
r+3
} is a simple path cover of W
n
. Hence
s
(W
n
) r+3 =
_
n
2
_
+3.
Further, for any simple path cover of W
n
at least three vertices on C = (v
1
, v
2
, . . . , v
n1
) are
terminal vertices of paths in . Hence t q
k
2
3, so that
s
(W
n
) = q t
k
2
+3 =
_
n
2
_
+3.
Thus
s
(W
n
) =
_
n
2
_
+ 3.
Remark 2.13 Since every simple acyclic graphoidal cover of a graph G is a simple path cover
of G and every simple path cover of G is a path cover of G, we have
as

s
. These
parameters may be either equal or all distinct as shown below. For the graph G
1
given in
Figure 2,
as
(G
1
) = 7,
s
(G
1
) = 6, (G
1
) = 5 and for the graph G
2
given in Fig.2.2, we have

as
(G
2
) =
s
(G
2
) = (G
2
) = 3.
G
1
G
2
Fig.2.2
Problem 2.14 Characterize graphs for which
as
=
s
= .
We now proceed to obtain some bounds for
s
.
Theorem 2.15 For any graph G,
s
(G)
_

2
_
. Further, the following are equivalent.
(i)
s
(G) =
_

2
_
.
(ii)
as
(G) = 1.
(iii) G is homeomorphic to a star.
102 S. Arumugam and I. Sahul Hamid
Proof Since
s
, the inequality follows from Theorem 1.5.
Suppose
s
(G) =
_

2
_
. Let = {P
1
, P
2
, . . . , P
r
}, where r =
_

2
_
be a minimum simple
path cover of G. Let v be a vertex of G with deg v = . Then v lies on each P
i
and
v is an internal vertex of all the paths in except possibly for at most one path. Hence
V (P
i
) V (P
j
) = {v}, for all i = j, so that G is homeomorphic to a star. Obviously, if G is
homeomorphic to a star, then
s
(G) =
_

2
_
. Thus (i) and (iii) are equivalent. Similarly the
equivalence of (ii) and (iii) can be proved.
Theorem 2.16 For any graph G,
s
(G)
_

2
_
, where is the clique number of G.
Proof Let H be a maximum clique in G so that |E(H)| =
_

2
_
. Let be a simple path
cover of G. Since any path in covers at most one edge of H, it follows that
s
(G)
_

2
_
.
In the following theorem we characterize cubic graphs for which
s
=
_

2
_
.
Theorem 2.17 Let G be a cubic graph. Then
s
(G) =
_

2
_
if and only if G = K
4
.
Proof Let G be a cubic graph with
s
(G) =
_

2
_
. Clearly = 3 or 4. Suppose = 3.
Then it follows from Corollary 2.6 that
s
(G)
p
2
so that p = 6. Hence G is isomorphic to the
cartesian product K
3
K
2
and it can be shown that
s
(K
3
K
2
) = 6 =
_

2
_
. Thus = 4 and
consequently G = K
4
.
Problem 2.18 Characterize graphs for which
s
(G) =
_

2
_
.
If 3, then every simple path cover of G is a simple acyclic graphoidal cover of G and
hence
as
(G) =
s
(G). However, the converse is not true. For the complete graph K
p
(p 5),

s
=
as
whereas 4. We now prove that the converse is true for trees and unicyclic graphs.
Theorem 2.19 Let G be a tree. Then
as
(G) =
s
(G) if and only if 3.
Proof Let G be a tree with
as
(G) =
s
(G).
Suppose 4. Let v be a vertex of G with deg v 4.
Let be a minimum simple acyclic graphoidal cover of G. Let P
1
and P
2
be two paths in
having v as a terminal vertex. Let Q = P
1
P
1
2
. Since G is a tree, Q is an induced path
and hence
1
= ( {P
1
, P
2
}) {Q} is a simple path cover of G with |
1
| = || 1 =
as
1
so that
s
(G)
as
(G) 1, which is a contradiction. Hence 3.
Theorem 2.20 Let G be a unicyclic graph. Then
as
(G) =
s
(G) if and only if 3.
Proof Let G be a unicyclic graph with
as
(G) =
s
(G). Let k denote the number of
vertices of odd degree and n be the number of pendant vertices of G.
It follows from Theorem 1.10 and Theorem 2.9 that k = 2n. Now, suppose > 3. Then
2q =

vV (G)
deg v=1
deg v +

vV (G)
deg v>1
and is odd
deg v +

vV (G)
deg v>1
and is even
deg v
> n + 3(k n) + 2(p k)
= 2p,
Simple Path Covers in Graphs 103
which is a contradiction. Hence 3.
The above results lead to the following problem.
Problem 2.21 Characterize graphs for which
as
(G) =
s
(G).
In the following theorem we establish a relation connecting the parameters
as
and
s
.
Theorem 2.22 For any (p, q)-graph G,
as
(G)
s
(G)+qp+n
k
2
, where n and k respectively
denote the number of pendant vertices and the number of odd vertices of G. Further, equality
holds if and only if
s
(G) =
k
2
.
Proof Let be a minimum simple path cover of G. Let i(v) denote the number of paths in
having v V as an internal vertex. If i(v) 2, let P
i
, where 1 i i(v), be the u
i
-w
i
path
in having v as an internal vertex and let Q
i
and R
i
, where 2 i i(v), respectively denote
the (v, w
i
)-section and (v, u
i
)-section of P
i
. Let
1
be the collection of paths obtained from
by replacing P
2
, P
3
, . . . , P
i(v)
by Q
2
, Q
3
, . . . , Q
i(v)
and R
2
, R
3
, . . . , R
i(v)
for every v V with
i(v) 2. Then
1
is a simple acyclic graphoidal cover of G with |
1
| =
s
(G) +

vV
i(v)2
(i(v) 1).
Since i(v)
_
deg v
2
_
, it follows that

as
(G)
s
(G) +

vV
deg v4
__
deg v
2
_
1
_
=
s
(G) +

vV
deg v2
__
deg v
2
_
1
_
=
s
(G) +

vV
deg v2
_
deg v
2
_
(p n)
=
s
(G) +

vV
deg v2
and is odd
deg v1
2
+

vV
deg v2
and is even
deg v
2
p +n
=
s
(G) +

vV
deg v2
and is odd
deg v
2

kn
2
+

vV
deg v2
and is even
deg v
2
p +n
=
s
(G) +

vV
deg v2
deg v
2

k
2
+
n
2
p +n
=
s
(G) +

vV
deg v
2

k
2
p +n.
=
s
(G) +q p +n
k
2
.
Thus
as
(G)
s
(G)+qp+n
k
2
. Further, it is clear that
as
(G) =
s
(G)+qp+n
k
2
if and only if there exist a minimum simple path cover of G such that i(v) =
_
deg v
2
_
for all
v V . Hence it follows from Corollary 2.6 that
as
(G) =
s
(G) +q p + n
k
2
if and only if

s
=
k
2
.
Corollary 2.23 If
s
(G) =
k
2
, then
as
(G) = q p +n.
104 S. Arumugam and I. Sahul Hamid
Proof Suppose
s
(G) =
k
2
. By Theorem 2.22, we have
as
(G) q p+n. Hence it follows
from Theorem 1.9 that
as
(G) = q p +n.
Remark 2.24 The converse of Corollary 2.23 is not true. For example,
as
(K
4,5
) = q p = 11,
whereas
s
(K
4,5
) > 2 =
k
2
.
References
[1] B. D. Acharya and E. Sampathkumar, Graphoidal covers and graphoidal covering number
of a graph, Indian J. pure appl. Math., 18(10)(1987), 882 - 890.
[2] S. Arumugam, B. D. Acharya and E. Sampathkumar, Graphoidal covers of a graph - A
creative review, Proceedings of the National workshop on Graph Theory and its Applica-
tions, Manonmaniam Sundaranar University, Tirunelveli, Eds. S. Arumugam, B. D.
Acharya and E. Sampathkumar, Tata McGraw Hill, (1996), 1 - 28.
[3] S. Arumugam and I. Sahul Hamid, Simple Acyclic Graphoidal covers in a graph, Aus-
tralasian Journal of Combinatorics, 37(2007), 243 -255.
[4] S. Arumugam and J. Suresh Suseela, Acyclic graphoidal covers and path partitions in a
graph, Discrete Math., 190(1998),67 - 77.
[5] F. Harary, Graph Theory, Addison-Wesley, Reading, Mass, 1972.
[6] F. Harary, Covering and packing in graphs I, Ann. N. Y. Acad. Sci., 175(1970), 198 -
205.
[7] F. Harary and A. J. Schwenk, Evolution of the path number of a graph, covering and
packing in graphs II, Graph Theory and Computing, Ed. R. C. Road, Academic Press,
New York, (1972), 39 - 45.
[8] L.F. Mao, Automorphism Groups of Maps, Surfaces and Smarandache Geometries, Amer-
ican Research Press, 2005
[9] B. Peroche, The path number of some multipartite graphs, Annals of Discrete Math.,
9(1982), 193 - 197.
[10] R. G. Stanton, D. D. Cowan and L. O. James, Some results on path numbers, Proc.
Louisiana Conf. on Combinatorics, Graph Theory and computing (1970), 112 - 135.
[11] R. G. Stanton, D. D. Cowan and L. O. James, Tripartite path number, Graph Theory and
Computing, Eds. R. C. Read, Academic Press, New York, (1973), 285 - 294.