 Open Access
 Total Downloads : 395
 Authors : D. Narmatha, Dr. N. Murugesan
 Paper ID : IJERTV3IS051169
 Volume & Issue : Volume 03, Issue 05 (May 2014)
 Published (First Online): 24052014
 ISSN (Online) : 22780181
 Publisher Name : IJERT
 License: This work is licensed under a Creative Commons Attribution 4.0 International License
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.

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.

SEMIGRAPH
represented by small circles, a small tangent is drawn at the small circles to represent middleend 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 ntuples
n 2
, called edges of S
satisfying the following conditions [4]:

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

Any two edges have at most one vertex in common.

Two edges
E1 (u1 ,u2 ,……um ) and
E2 (v1 , v2 ,….vn ) are said to be equal iff

m n and
Fig.1 A Semigraph
In the semigraph S , given in fig.1

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 middleend 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

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:

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

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 .

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

adjacent if they belong to the same edge.

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

eadjacent if they are end vertices of an edge.

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

Adjacent degree of a vertex da (v) , is the number of
vertices adjacent to v .

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
–
MiddleEnd 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 eadjacent, and v , v
1 3 1 2
are 1eadjacent.
Also from the above example, the following can be observed:



Observations

The number of adjacent vertices to a vertex
v in an edge E is E 1.

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

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

The number of eadjacent vertices to a middle vertex is always zero.

Let v be an end vertex, then the number of

vertices 1eadjacent 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

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 middleend 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 middleend vertex. In particular, if v is a
vertices
u1,u2 ,…un
are all adjacent vertices to v
middleend 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 .

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


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.

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

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 .

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 .

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

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


Example
n Ej m , then Hence the theorem.

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

Theorem
End vertex graph associated with a given semigraph is connected if the semigraph has no middle and middleend vertices.
Proof:
Fig. 3 Sa
In an end vertex graph, only the end vertices of an edge are adjacent. Also, if there are two middleend 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 middleend vertices.

Note

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.

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


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.

Theorem
The size of Sca is edge in S .

Theorem
Ei
i
1, where Ei
is an
Fig. 5
S1e
The size of Se
is same as the size of S .

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
middleend vertices in .


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.

REFERENCES

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

S. Gomathi, Studies in Semigraphs and
Domination, Ph.D Thesis, Madurai Kamaraj University, 2008.

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

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

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