Graphoidal Covering Number Of Product Graphs

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, Chidambaram-608 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,

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

2. 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.

1. 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

   1. 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:

      1. 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

   1. q p

   2. There exists a graphoidal cover without exterior vertices.

   3. 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 .

2. 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(n-1)+n(m-1)

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(n-1)+n(m-1)

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

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

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

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

4. Skiena, S. "Products of Graphs." §4.1.4 in Implementing Discrete Mathematics: Combinatorics and Graph theory with Mathematica. Reading, MA: Addison-Wesley, (1990),pp. 133-135.

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

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

2. 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),1-28.

3. F. Harary, Graph Theory, Addison-Wesley, Reading, MA (1969).

International Journal of Engineering Research & Technology (IJERT)

ISSN: 2278-0181

Vol. 1 Issue 8, October – 2012