Some Properties of Semigraph and its Associated Graphs

Some Properties of Semigraph and its Associated Graphs

N. Murugesan D. Narmatha

Assistant Professor Department of Mathematics Assistant Professor Department of Mathematics Government Arts College Sri Ramakrishna Engineering College Coimbatore, Tamilnadu Coimbatore ,Tamilnadu

Abstract In this paper, some properties of degrees of vertices of a semigraph have been discussed. Four types of graphs associated to a given semigraph have been defined, and size of each graph has also been discussed.

Keywords Semigraph, Adjacency and Degrees in Semigraph, Associated graphs.

1. INTRODUCTION

   Semigraph is a generalization of the concept of graph [3,5]. In a semigraph the edges are assumed to have many parts, and vertices are classified according to their positions [1,2]. In this paper, the basic characteristics of all types of vertices have been discussed in detail. In particular, four types of degrees have been defined for each vertex and relationship among them have been studied in detail. It has also been discussed four types of associated graphs and size of each of them corresponding to the given semigraph.

2. SEMIGRAPH

represented by small circles, a small tangent is drawn at the small circles to represent middle-end vertices.

B. Example

A. Definition

A semigraph S is a pair

(V , X ) where V is a

nonempty set whose elements are called vertices of S and

X is a set of ordered n-tuples

n 2

, called edges of S

satisfying the following conditions [4]:

1. The components of an edge E in X are distinct vertices from V .

2. Any two edges have at most one vertex in common.

3. Two edges

   E1 (u1 ,u2 ,……um ) and

   E2 (v1 , v2 ,….vn ) are said to be equal iff

   1. m n and

      Fig.1 A Semigraph

      In the semigraph S , given in fig.1

   2. Either

ui vi

or ui

vni1

for

V {v1, v2 ,….v10 , v11, v12}and

1 i n .

The vertices in a semigraph are divided into three

X {v1, v8 , (v1, v2 , v3 ), (v3 , v4 , v5 , v6 ), (v6 , v7 , v8 ),

(v6 , v10 , v1 ), (v6 , v9 , v2 ), (v6 , v11, v12 ), v5 , v11 , (v3 , v10 , v8 )}.

types namely end vertices, middle vertices and middle-end vertices, depending upon their positions in an edge. The end

The vertices

v1, v3 , v6 , v8

and

v12

are end vertices,

vertices are represented by thick dots, middle vertices are

v4 , v7 , v9 , v10

end vertices.

are middle vertices and

v2 , v5 , v11

are middle-

The order and size of a semigraph S is respectively denoted by the numbers V and E . The number of components in an edge E is denoted by E , we also write

1. VARIOUS DEGREES OF VERTICES

   A. Definition

   For a vertex v in a semigraph S (V , X ) , the

   V V1 V2 V3 , where

   V1 ,V2 and V3 respectively

   various types of degrees are defined as follows:

   1. Degree of a vertex v , is the number of edges having

      represent the set of end vertices, middle vertices and middle- end vertices.

      v as an end vertex. It is denoted as deg( v) .

      III. ADJACENT VERTICES

   2. Edge degree of a vertex edges containing v .

   de (v) , is the number of

   There are four types of adjacency is defined between any two vertices in a semigraph S .

   1. Definition

      Two vertices u and v in a semigraph S are said to be

      1. adjacent if they belong to the same edge.

      2. consecutively adjacent if they are adjacent and consecutive in order as well.

      3. e-adjacent if they are end vertices of an edge.

      4. 1e-adjacent if both the vertices u and v belong to the same edge and atleast one of them is an end vertex of that edge.

         As an example, consider the semigraph S given in

         1. Adjacent degree of a vertex da (v) , is the number of

            vertices adjacent to v .

         2. Consecutive adjacent degree of a vertex dca (v) , is the number of vertices consecutively adjacent to v .

         The following table gives the degree, edge degree, adjacent degree and consecutively adjacent degree of all the vertices of the semigraph given in fig.1

         End Vertices	v1	v3	v6	v8	v12
         deg( v)	3	3	5	3	1
         de (v)	3	3	5	3	1
         da (v)	5	7	11	5	2
         dca (v)	2	3	5	3	1
         Middle Vertices	v4	v7	v9	v10	–
         deg( v)	0	0	0	0	–
         de (v)	1	1	1	2	–
         da (v)	3	2	2	4	–
         dca (v)	2	2	2	4	–
         Middle-End Vertices	v2	v5	v11	–	–
         deg( v)	1	1	1	–	–
         de (v)	2	2	2	–	–
         da (v)	4	4	3	–	–
         dca (v)	3	3	3	–	–

         TABLE I

         fig 1. The vertices

         v1 ,

         v2 , v3

         are adjacent,

         v2 , v3

         are

         consecutively adjacent, v , v are e-adjacent, and v , v

         1 3 1 2

         are 1e-adjacent.

         Also from the above example, the following can be observed:

   2. Observations

      1. The number of adjacent vertices to a vertex

         v in an edge E is E 1.

      2. The adjacency of two vertices does not imply the consecutive adjacent, but the converse is always true.

      3. The number of e-adjacent vertices to an end vertex v in a semigraph is equal to the number of edges for which v acts as an end vertex.

      4. The number of e-adjacent vertices to a middle vertex is always zero.

      5. Let v be an end vertex, then the number of

   vertices 1e-adjacent to v is

   n

   Ei

   i 1

   • 2n , where v is an end vertex

   to the edges E1 , E2 ,…En .

   The following theorems give the properties of various degrees of vertices and relationship between one another.

   D. Theorem

   If S (V , X ) is a semigraph, and v V2

   , then

   1. Theorem.

      For any semigraph S V , X , and v V

      i.

      ii.

      deg v 0

      de v 1

      i. deg v 2 X .

      iii.

      da v E 1, provided v E , an edge in X

      ii.

      de v deg v X2 X3 2 X

      X2 X3

      iv.

      dca

      v 2n,if X2 n

      Proof:

      i. It is simple observation that if v V2 , then

      deg v 0 . Suppose if v V1 , and deg v m , then

      there are m edges in X , such that v is an end vertex for all such m edges. Each edge also contains another end vertex other than v . Hence each edge counted twice respectively for

      v. dca v 2de v

      Proof:

      The proof of (i) is obvious, because deg v is defined as the number of edges containing v as end vertex. Since v V2 , no such edge exists. Hence deg v 0 .

      each end vertex. The same is true for every vertex

      v V3 .

      It is also easy to see that middle vertices in a

      semigraph S belong to atleast one edge in X . Hence

      This proves (i).

      ii. Note that each edge is counted twice while calculating edge degree of end vertex, and middle-end vertex of that edge. Further each edge is again counted once for each

      de v 1. This proves (ii).

      Let v E u1,u2 ,…., v,…un . Then the

      middle vertex and middle-end vertex. In particular, if v is a

      vertices

      u1,u2 ,…un

      are all adjacent vertices to v

      middle-end vertex, such that it is a middle vertex for E1 , and

      corresponding to the edge E . Therefore

      an end vertex for E2 , both E1 and E2 are counted once each

      da v n E 1. This proves (iii).

      corresponding to the vertex v . The count of

      E1 is included in

      Let v V2 .Then

      the sum V3

      where as the count of

      E2 is included in the

      v E u1,u2 ,….,ui1, v,ui ,…un

      for some E in

      sum deg v 2 X

      . This proves (ii).

      X . Note that ui1 and ui

      are consecutively adjacent to v .

   2. Theorem

   Since

   v V2 , existence of two vertices such as

   ui1

   and

   If S (V , X ) is a semigraph, and

   deg(v) de (v) dca (v) .

   Proof:

   v V1

   , then

   ui are must to v . Therefore dca v 2 , corresponding to the edge E containing v . Moreover, if there are n middle vertices in S , then the sum of consecutively adjacent degree of all n vertices is 2n . This proves (iv).

   Since, the number of edges for which a vertex v V1 acts as an end vertex is same as the number of edges containing it.

   Hence deg(v) d (v) . Also if v is an end vertex for n

   If v V2 , and E contains v , then v has two

   consecutively adjacent vertices in E . This is true for every edge containing v . In particular, if there are n edges

   edges

   E , E

   e

   ,…..E , then there is exactly one vertex v

   containing v , then

   dca

   v 2n , and

   de v n .

   1 2 n

   i Hence d

   v 2d

   v . This proves (v).

   in each Ei consecutively adjacent to v . Hence the number of

   ca e

   vertices consecutively adjacent to v is same as the number of edges for which v acts as an end vertex. Hence deg(v) de (v) dca (v) .

   Hence the theorem.

   E. Theorem

   If S (V , X ) be a semigraph, and v V3 , then

   e

   d v deg v

   i.

   ii.

   dca v 2n Ei n Ej

   , where

2. ASSOCIATED GRAPHS

   Let S V , X be a semigraph. We define four new

   n Ei denotes number of edges in S at which v

   is a middle vertex, and n E j denotes the number of edges in S at which v is an end vertex in S .

   Proof:

   graphs associated to the given semigraph each having same vertex set.

   1. Definition

      The proof (i) follows from the fact that deg v is

      1. End Vertex Graph Se

         : Two vertices in Se

         are

         calculated by considering only the edges for which v is an

         adjacent if they are the end vertices of an edge in

         end vertex, where as the

         de v

         is calculated by considering

         S .

      2. Adjacency Graph

         Sa : Two vertices in

         Sa are

         all the edges containing v . Therefore de v deg v.

         adjacent if they are adjacent in S .

      3. Consecutive adjacency Graph Sca : Two vertices in

         Let v V3 . Then there are edges

         Sca are adjacent if they are the consecutively

         Ei ,i 1, 2,…., n

         and

         Ej , j 1, 2,…., m

         such that v is

         adjacent in S .

         a middle vertex for all

         Ei , and end vertex for all

         E j . For

      4. One end vertex Graph

         S1e : Two vertices in

         S1e are

         every

         Ei ,

         dca v 2

         and for every

         adjacent if atleast one of them is an end vertex in S

         of an edge containing the two vertices.

         E j , dca v 1. Therefore if

         n Ei n , and

   2. Example

   n Ej m , then Hence the theorem.

   1. Theorem

      If S (V , X )

      dca v 2n Ei n Ej .

      is a semigraph, and v V , then

      The above four types of associated graphs for the semigraph given fig.1 are shown below.

      da v Ei

      vV Ei

      Proof:

      Ei

      1 .

      Let

      S V , X

      is a semigraph, and v V . Also

      let v Ei , for some

      Ei in X . If

      Ei n , then for every

      v Ei ,

      da v n 1. Hence for all

      v Ei ,

      da v n n 1 . On generalizing the above fact, we

      vEi

      can write da v Ei

      vV Ei

      This proves the theorem.

      Ei

      1 .

      Fig 2. Se

      1. Theorem

         End vertex graph associated with a given semigraph is connected if the semigraph has no middle and middle-end vertices.

         Proof:

         Fig. 3 Sa

         In an end vertex graph, only the end vertices of an edge are adjacent. Also, if there are two middle-end vertices joined by an edge, then they produce a component in the end vertex graph. Moreover, the middle vertex is not adjacent to any other vertex in the end vertex graph. This leads to fact that the middle vertices in the semigraph are isolated vertices in the end vertex graph. Hence the end vertex graph of the corresponding semigraph is connected if it has no middle vertices and middle-end vertices.

      2. Note

         1. Every graph can be considered as a semigraph with no middle and middle end vertices. In this case the end vertex graph is the same graph.

         2. Let S be a semigraph containing end vertices, and middle-end vertices but not middle vertices. Then the end vertex graph G associated with S has pendent vertices, components but not isolated vertices.

      3. Theorem

         The size of Sa

         S .

         Proof:

         is Ei

         i

         C2 , where Ei

         is an edge in

         In a semigraph S , two vertices are adjacent if they belong to same edge. Therefore all vertices belonging to an

         Fig.4 Sca

         edge in S , become adjacent to each other in

         Sa . i.e., the

         vertices of each edge Ei

         in S form a clique in Sa

         consisting

         Ei C2 edges. Hence the total number of edges in

         Sa is Ei

         i

         C2 .

         As in the proof of above theorem we can also prove the following theorem.

      4. Theorem

         The size of Sca is edge in S .

      5. Theorem

         Ei

         i

         1, where Ei

         is an

         Fig. 5

         S1e

         The size of Se

         is same as the size of S .

      6. Theorem

   The size of

   S1e

   is Ei

   i

   C2 Fi

   C2 , where Ei

   is an edge in S , and Fi

   is a set consisting the middle, and

   middle-end vertices in .

3. CONCLUSION

   The concept of adjacency between vertices in a semigraph plays a vital role in the domination theory. There are four types of adjacency have been discussed as far as a semigraph is concerned. Hence, it may be interesting to study the variations of domination properties based on the adjacency under consideration.

4. REFERENCES

1. B. Y. Bam and N. S. Bhave, On Some Problems of Graph Theory in Smigraphs, Ph.D Thesis, University of Pune.

2. S. Gomathi, Studies in Semigraphs and

   Domination, Ph.D Thesis, Madurai Kamaraj University, 2008.

3. F. Harary, Graph Theory, Addition Wesley, Reading Mass, 1972.

4. E. Sampath Kumar, Semigraphs and their Applications, Report on the DST Project, May 2000.

5. S. P. Subbaih, A Study of Graph Theory: Topology, Steiner Domination and Semigraph Concepts, Ph.D Thesis, Madurai Kamaraj University, 2007.