 Open Access
 Total Downloads : 681
 Authors : T. Gayathri, S. Meena
 Paper ID : IJERTV1IS8548
 Volume & Issue : Volume 01, Issue 08 (October 2012)
 Published (First Online): 29102012
 ISSN (Online) : 22780181
 Publisher Name : IJERT
 License: This work is licensed under a Creative Commons Attribution 4.0 International License
Graphoidal Covering Number Of Product Graphs
T. Gayathri
Department of Mathematics, Sri Manakula Vinayagar Engineering College, Puducherry 605 107, India
S. Meena
Department of Mathematics,Government Arts and Science College, Chidambaram608 102, India
Abstract
A Graphoidal cover of a graph G is a collection
of paths in G such that every path in has at least two
vertices, every vertex of G is an internal vertex of at most one path in and every edge of G is in exactly one path in . The minimum cardinality of a
graphoidal cover of G is called the graphoidal
covering number of G and is denoted by G. Also,

Every vertex of G is an internal vertex of at most one path in .

Every edge of G is in exactly one path in The minimum cardinality of a graphoidal cover of
G is called the graphoidal covering number of G and is denoted by G .
Definition 1.2 [2] A graphoidal cover of a graph G is called an acyclic graphoidal cover if every
if every member in graphoidal cover is an open path then it is called an acyclic graphoidal cover. The minimum cardinality of an acyclic graphoidal cover of G is called the acyclic graphoidal covering number of
G and is denoted by a G ora . Here we find
member of is an open path. The minimum
cardinality of an acyclic graphoidal cover of G is called the acyclic graphoidal covering number of G and is denoted by a G ora .
minimum graphoidal covering number and minimum acyclic graphoidal covering number of Cartesian product, weak product and strong product of some graphs.

Introduction
A Graph is a pair G= (V, E) where V is the set of vertices and E is the set of edges. Here we consider only nontrivial, finite, connected and simple Graphs. V p and E q .[3]
The concept of graphoidal cover was introduced by

Acharaya and E. Sampathkumar [1].
Definition 1.1 [1] A graphoidal cover of a graph G is called a collection of (not necessarily
open) paths in G satisfying the following conditions:

Every path in has at least two vertices.

Definition 1.3 [6] A graphoidal cover of a
graph G is called an induced acyclic graphoidal cover if every member of is an induced path. The
minimum cardinality of an induced acyclic graphoidal cover of G is called the induced acyclic graphoidal covering number of G and is denoted by ia G or
ia .
Definition 1.4 [1] Let be a collection of
internally edge disjoint paths in G. A vertex of G is said to be an internal vertex of if it is an internal vertex
of some path in , otherwise it is called an external vertex of .
Definition 1.5[7] For two graphs G and H, their Cartesian product G H has vertex set V GV H in which g1, p is joined g2 , p
iff g1 g2 and pp E H or p p and
g1g2 E G.
Definition 1.6[7] For two graphs G and H,
Pn1 g2hn , g1hn , g2hn1, g3hn1,, gmhn1, gmhn
their Weak product G H
has vertex set
Pn g h , g hn , g hn , g h ,, g hn , g h
V GV H in which g1, p is joined g2 , p
2 n1 2 3 3 1
m1
m1 n1
iff g1g2 E G and pp E H .
Definition 1.7[7] For two graphs G and H, their strong product G H has vertex set V GV H and edge set is E G H E G H .
Pn1 = The remaining edges
From above we see that all the vertices of pm pn are internal vertices.
Theorem 1.8 [1] For any graphoidal cover
Therefore
a q p
of G , let t denote the number of exterior vertices of
.Let t = min t where the minimum is taken over all graphoidal covers of G. Then q p t .
Corollary 1.9 [1] For any graph G,
q p. Moreover the following are equivalent
Theorem 2.2[5] For pm pn ,the acyclic graphoidal covering number is a q p 6
Proof: Case (i): m is even
P1 g1p, g2p, g3p, g4p,, gm1p, gmp, gm1p

q p

There exists a graphoidal cover without exterior vertices.

There exists a set of internally disjoint and edge disjoint paths without exterior vertices.
P2 g2p, g1p, g2p, g3p, g4p,, gm1p, gmp, gm1h4
P3 g2p, g1p, g2h4, g3p, g4h4,, gm1p, gmh4, gm1p
Theorem 1.10[1] For any graph G,
q p .


Main Results
3 ,
Pn1 g2hn2, g1hn1, g2hn , g3hn1,, gm1hn1, gmhn
Theorem 2.1[4] For pm pn , the acyclic
graphoidal covering number is a q p .
Proof: Let p = mn and q = m(n1)+n(m1)
The acyclic graphoidal cover of pm pn is as follows:
P1 g1p, g1p, g2p, g3p,, gmp, gmp P2 g1p, g1p, g2p , g3p ,, gmp, gmp P3 g1h4, g1p, g2p, g3p,, gmp, gmh4
LP1 g3p , g4p, g5p
LP2 g5p , g6p, g7p
LPm31 gm3p , gm2p, gm1p 2
RP1 g2hn1, g3hn , g4hn1
RP2 g4hn1, g5hn , g6hn1
RPm31 gm2hn1, gm3hn , gm4hn1 2
RPm41 gm1hn1, gm2hn , gm3hn1 2
S = The remaining edges
From above we see that all the vertices of pm pn
are
S = The remaining edges
internal vertices
expect g1p, g2p, gm1p, gmp, g1hn , gmhn .
From above we see that all the vertices of pm pn are
Therefore a q p 6
internal vertices
expect g1p, g2p, gnhn,g1hn , gm1hn , gmhn .
Theorem 2.3 For pm pn
, the acyclic
Therefore
a q p 6
graphoidal covering number is a 2q 2 p 6
Case (ii): m is odd.
Theorem 2.4 For Cm pn
, the acyclic
P1 g1p, g2p, g3p, g4p,, gm1p, gmp
graphoidal covering number is a q p
Proof:
P2 g2p, g1p, g2p, g3p, g4p,, gm1p, gmp, gm1p
The acyclic graphoidal cover of cm pn
follows:
3 2 2 1 3 2 4 3 3 4 4 5 3 m1 4 m 3 mP1 2
P g h , g h , g h , g h , g h , g h ,, g h , g h , g h
1 g1p, g1p, g2p, g3p,, gmp, gmp
is as
P2 g1p, g1p, g2p , g3p ,, gmp, gmp
3 1 4 1 3 2 3 3 3 3 4
Pn1 g2hn2, g1hn1, g2hn , g3hn1, g4hn , gm1hn1, gmPhn1,gghm,1ghnp, g h , g h ,, gmh , gmh
LP g h , g h , g h
1 3 2 4 1 5 2
Pn1 g2hn , g1hn , g2hn1, g3hn1,, gmhn1, gmhn
LP2 g5p , g6p, g7p
LPm41 gm2p , gm3p, gm4p 2
RP1 g2hn1, g3hn , g4hn1
Pn g2hn1, g2hn , g3hn , g3p,, gm1hn , gm1hn1
Pn1 = The remaining edges
From above we see that all the vertices of pm pn
are internal vertices.
RP2 g4hn1, g5hn , g6hn1
Therefore
a q p
Pn1
= The remaining edges
From above we see that all the vertices of pm pn are internal vertices.
Therefore a q p
Theorem 2.5[6] For pm pn , the induced acyclic graphoidal covering number is ia q p .
Proof: Let p = mn and q = m(n1)+n(m1)
The acyclic graphoidal cover of pm pn is as follows:
P1 g1p , g1p, g2p, g3p,, gmp P2 g1p, g1p , g2p , g3p ,, gmp P3 g1h4, g1p, g2p, g3p,, gmp
Pn1 g1hn , g1hn1, g2hn1, g3hn1,, gmhn1

C.Pakkiam, S. Arumugam, On graphoidal covering number of unicyclic graphs , Indian J. Pure Appl. Math., No.2, 23(1992), 141143.

C.Pakkiam, S. Aumugam, On graphoidal covering number of a graph, Indian J. Pure Appl.Math., 20(4), (1989), 330333.

K. Ratan Singh and P. K. Das, InducedAcyclic Graphoidal Covers in a Graph, Int. J. of Comput. Math. Sci., 4:7 (2010).

Skiena, S. "Products of Graphs." Â§4.1.4 in Implementing Discrete Mathematics: Combinatorics and Graph theory with Mathematica. Reading, MA: AddisonWesley, (1990),pp. 133135.
Pn gmp, gmp, gmp,, gmhn , gm1hn ,, g1hn S = The remaining edges not covered by P1, P2, P3,, Pn1, Pn
From above we see that all the vertices of pm pn are
internal vertices expect
gmp and g1hn (t=2)
Therefore
ia q p 2
References

B. D. Acharya and E.Sampathkumar, Graphoidal covers and graphoidal covering number of a graph, Indian J. Pure. Appl. Math., No.10, 18 (1987) 882890.

S. Arumugam, E.Sampathkumar, Graphoidal covers of a graph: a creative review,In: proc.National Workshop on Graph Theoryand its applications, Manonmaniam Sundaranar University, Tirunelveli,Tata McGraw Hill,New Delhi(1997),128.

F. Harary, Graph Theory, AddisonWesley, Reading, MA (1969).
International Journal of Engineering Research & Technology (IJERT)
ISSN: 22780181
Vol. 1 Issue 8, October – 2012