Semi Graph

Download as docx, pdf, or txt
Download as docx, pdf, or txt
You are on page 1of 46

Contents

List of Figures iii

Introduction 1
1 Preliminaries 3
1.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
1.2 Basic Graph Theory . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .6
2 Semi graph 8
2.1 Semi graph . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
2.2 Adjacent Vertices in Semi graphs . . . . . . . . . . . . . . . . . . . . . . . . . . .12
2.3 Various Degrees of Vertices in Semi graphs . . . . . . . . . . . . . ……..14
3 Connectedness in Semi graphs20
4 Types of Semi graphs and Associated Graphs26
4.1 Types of Semi graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .23
4.2 Associated Graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .29
4.3 Applications of Semi graph . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31
5.e- homomorphism of Semi graphs . . . . . . . . . . . . . . . . . . . . . . . . . 34
5.1 Definitions. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35
Conclusion 41
Bibliography 42

1
Introduction

The graph theory emerged while solving a problem associated with a bridge in
Konigsberg, which was situated in Russia. In the year 1735 Euler considered this
problem and constructed a structure to solve this problem .As a result the first
formal ’graph’ structure had been drawn, and a new branch of mathematics started
its journey.Over the years, the theory of graphs have a tremendous growth in
various directions. The structures-the graphs possessing special properties got
attention of graph theorists as they found these graphs are very useful in studying
many concepts in social and scientific scenario. The complete graphs and bipartite
graphs introduced by A.F. Mobius have more recreational problems. Trees are
useful in the calculation of currents in electrical works. Cayley studied particular
analytical forms from differential calculus to study the trees. Based on the
characterizations and applications of graphs, new areas of graph theory such as
extremal graph theory, enumerative graph theory and random graph theory have
been developed. It is quite natural among the scientific community to view every
scientific entity in its most general form. The hyper graphs are considered as the
most general form of graphs. But the generalization of some vital graph theory
concepts such as Planar graphs, Hamiltonian and Euler graphs do not contain the
very existence properties available in these graphs. This difficulty arise only
because that the edges are considered as sets in the hyper graphs. The semi graphs
introduced by E.Sampathkumar become the most general structure of a graph
where the edges are considered as line segments. In this project, the structural
properties and some graph theoretical concepts of semi graphs have been studied.
This work entitled A study on Semi graphs introduces the concept of semi graphs

2
and its various properties. Study on Semi graphs introduces the concept of semi
graphs and its various properties.

3
Chapter 1
Preliminaries
1.1 Introduction
The semi graph generalization is more closely related to the axiom that the two
edges in a semi graph have at most one vertex in common, where as the hyper
graph generalization is based on the consideration of an edge as a subset of two
elements of the set of vertices of graphs. In this section, we highlight some of the
important works carried out by many researchers in the field of semi graphs. The
concept of semi graphs is introduced by E.Sampathkumar in the year 2000. Since
then, various works have been carried out on semi graphs. B.D. Acharya
formulated a method to construct semi graphs from square matrices satisfying
certain properties. B.Y. Bamand N.S. Bhave studied different types of degree
sequences in semi graphs. They also introduced the concept of middle-end degree
of a vertex in a semi graphs. S.P. studied the relationship between topologies and
directed semi graphs.V.Swaminathan and Gomati studied Basic Graph Theory and
dominations. E.S.S. Kamath and R.S.Bhat discussed adjacency domination in semi
graphs. R. Gera et.al studied a dominator coloring in graphs, and this concept was
extended to semi graphs by V.Swaminathan and S.Gomathi. D.K. Thakkar and
A.A. Prajapati studied consecutive adjacent domination number in semi graphs,
and proved certain conditions under which the consecutive adjacent number of
semi graph increases or decreases. E.Sampathkumar, L.Pusha Latha, N.S. Bhave,
C.M.Deshpande studied semi graphs and their applications. S.S. Kamath and S.R
Hebbar studied dominations in critical semi graphs , in the year 2010. Y.B
Venakatkrishnan and V.Swaminathan studied bipartite theory of semi graphs. H.N.
Ramasamy and K.S. Shanmugalingaiah studied the spectral properties of semi
graphs. C.M.Deshpande and Y.S. Gaidhani studied about adjacency matrix of semi

4
graphs. NS. Bhave, C.M. Deshpande and B.Y. Bam studied characterization of
potentially Hamiltonian graph in terms of dual semi graph. Matching in semi
graphs were studied by Surjit K.R. Nath and P.S. Das in 2013. They studied the
relation between the domination and matching in semi graphs.

The purpose of this chapter is to list the terminology and notation that we shall
use in this work. Much of the terms used are standard graph theoretic terminology,
a few terms will be introduced later when their turn comes.

1.2 Basic Definition in Graph Theory

In this chapter, definitions of the basic concepts in graphs which are needed in
the subsequent chapters are listed.

Definition 1.1
A graphG = (V, E) consists of a finite nonempty set V = V (G) with points
together with a prescribed set E of q unordered pairs of distinct points of V . Each
pair x = {u, v} of points in E is called a line of G.
An element of V is called a vertex, an element of E is called an edge, V is the
vertex set and E is the edge set of G. The number of vertices is called the order of
G, denoted by n and the number of edges is called the size of G, denoted by m.

5
EXAMPLE 1.1

Figure 1.1
V(G) = {v1, v2, v3, v4} and E(G) = {e1, e2, e3, e4} and G  (e1) =(v1, v2),
G  (e2) =(v2, v3), G  (e3) =(v3, v4), G  (e1) =(v4, v1).

Definition1.2
If e = uv, then the two vertices u and v are said to adjacent each other and
the edge e is said to incident with (incident to or incident at) u and v. Two edges
are said to be adjacent if they have a common vertex.

EXAMPLE 1.2

Figure 1.2
For the graph G in Figure 1.2, V(G) = {v1, v2, v3, v4} and E(G) = {e1, e2, e3}.

6
Here the vertices v1 and v2 are adjacent vertices, since there is an edge e1
between v1 and v2. And v2 and v3 are non - adjacent vertices, since there is no edge
between v2 and v3
Definition 1.3
The number of vertices in V(G) is called the order of G, which is
denoted by V(G) and the number of the edges in E(G) is the size of the
graph G, which is denoted by E(G) .

EXAMPLE 1.3

Figure 1.3
For the graph G in Figure 1.2, V(G) = {v1, v2, v3, v4} and E(G) = {e1, e2, e3,
e4, e5, e6 } and hence V(G) = 4 and E(G) = 6

Definition 1.4
An edge with identical ends is called a loop

7
EXAMPLE 1.4

Figure 1.4
For the graph G in Figure 1.4, e1 is a loop

Definition 1.5
An empty graph is a graph with no edge
Definition 1.6
If two or more edges of G have the same end vertices, then these edges are called
parallel edges or multiple edges
EXAMPLE 1.6

Figure 1.6
In the graph G in Figure 1.6, e1 and e2 are parallel edges, since they have the same
end vertices v1 and v2
8
Definition 1.7
A graph G which has no loops and parallel edges is called simple graph

EXAMPLE 1.7

Figure1.7

The graph G in Figure 1.7 is a simple graph

Definition 1.8

A graph with just one vertex is called a trivial graph and all other graph are called
non – trivial graph.
EXAMPLE 1.8

Figure 1.8

In the graph in Figure 1.8, G is a trivial graph and H is a non – trivial graph

Definition 1.9
A graph G is said to be finite if both its vertex set and edge set are finite.

9
EXAMPLE 1.9

Figure 1.9

For the graph G in Figure 1.7, vertex set and edge set are finite and hence the graph
G is finite
Definition 1.10

The degree d(v) of a vertex v in G is the number of edges in G is incident with v

EXAMPLE 1.10

Figure 1.10
For the graph G in Figure 1.9, d(v1) = 1, d(v2) = 3, d(v3) = 2, d(v4) = 2.
Definition 1.11
A vertex v is an isolated vertex if the degree of v is 0. A vertex v is an
End point vertex if the degree of v is 1

Definition 1.12
A simple graph in which each pair of distinct vertices is joined by an edge is called
a complete graph

10
Notation 1.26:

Complete graph on n vertices is denoted by Kn


EXAMPLE 1.11

Figure 1.11

Definition 1.13

A bipartite graph is one whose vertex set can be partitioned into two sets X and Y
so that every edge has one end in X and another end in Y
Such a partition {X, Y} is called the bipartition of the graph.
EXAMPLE 1.12

Figure 1.12

For the graph G in Figure 1.11, if X = {v2, v4} and Y = {v1, v3, v5}, then {X, Y} is a
partition of the graph G and hence G is bipartite graph

11
EXAMPLE 1.13

Figure 1.13

For the graph G in Figure 1.12, there is no partition of the G and hence G is not a
bipartite graph

Definition 1.14
A graph H is a subgraph of G if V(H)V(G) and E(H)E(G) and H  is a
restriction of G  to E(H).
EXAMPLE 1.14

Figure 1.14
One of the sub graph of the graph G in Figure 1.14 is the graph H in the same
Figure
Definition 1.15
A walk in G is finite and non - null sequence W =v0e1v1e2,........,ekvk
whose terms are alternating sequence of vertices and edges such that for

12
1  i  k , the ends of ei’s are vi-1 and vi.
If the edges e1, e2, ......,ek of the walk are distinct, then W is called trail

If the edges e1, e2, ......,ek and the vertices v1, v2, ......,vk of the walk are
distinct, then W is called path
The number of edges in a walk is called the length of that walk.

EXAMPLE 1.15

Figure 1.15
For the graph G in the Figure 1.19, one of the
v1 – v4 walk is v1e5v4e4v3e1v4,
v1 – v4 trail is v1e1v3e4v4 and
v1 – v4 path is v1e1v3e4v4

Definition 1.16
A walk is said to be closed if it has positive length and its initial and terminal
vertices are same.
A closed trail whose initial and internal vertices are distinct is called a cycle.

13
EXAMPLE 1.16

Figure 1.16

For the graph G in Figure 1.21, v1e1v2e3v3e4v4e4v3e2v1 is a closed walk


and v1e1v2e3v3e2v1 is a cycle

Notation 1.52:

A cycle on n vertices is denoted by Cn.

14
Chapter 2
Semi graphs
2.1 Semi graph
The notion of semi graph is a generalization of that of a graph. While
generalizing a structure, one naturally looks for one in which every concept/idea in
the structure has a natural generalization. Semi graph is such a natural
generalization of graph, and it resembles graph when drawn in a plane. Semi graph
are defined, illustrated by a number of examples. We have a variety of definitions
of each concept like adjacency, degrees etc. In fact, the beauty of semi graphs lies
in the variety of definitions/concepts, all of which coincide for graphs. It is a
combinatorial structure in which the edges are considered to have many
components, and vertices are categorized according to their locations.

Definition 2.1.1.
A semi graph S is a pair (V, X) where V is a nonempty set whose elements
are observed as vertices of S and X is a set of ordered n-tuples n ≥ 2 of prescribed

vertices called edges of S satisfying the following conditions:

(i)any two edges have at most one vertex in common place.


(ii) two edges E1=( v1 , v 2 , … v n )and E2=(u1 , u2 , … , un ) are said to be identical
iff
(a) m = n and
(b) either ui=v ior ui=v n−i+1 for 1 ≤ i ≤ n
The vertices in a semi graph are spitted into three types namely end vertices,
middle vertices and middle-end vertices, based on their positions in an edge. The
end vertices are represented by thick dots, middle vertices are represented by small
circles, a small tangent is drawn at small circles to represent middle-end vertices.

15
Example 2.1.1.
Let S = (V, X) be a semi graph where V = { v1 , v 2 , … , v 9 } and X=n

Figure2.1
({v ¿ ¿ 1 , v 8), ( v 1 , v 2 , v 3 ) , ( v 3 , v 4 , v 5 , v 6 ) , ( v 6 , v 7 , v 8 ) , ( v 3 , v 9 , v 8 ) , ( v1 , v 9 , v 6 ) , ( v 9 , v 7 ) , ¿

(v 2 , v 6 )}.

The vertices v1 , v 3∧v 6and v 8are end vertices, v 4, v5 are middle vertices and
v 2 , v 7 ,∧v 9are middle-end vertices. The order and size of a semi graph S is

respectively denoted by the symbols |V | and X|. The number of vertices in an edge
E denoted by |E|, we also note down, V = V e U V m U V me where V e ,V mand V me
respectively describe the set of end vertices, middle vertices and middle-end
vertices.
Remark: A semi graph with no middle and middle-end vertices is a graph.
Hence every graph is a semi graph in which each edge is of cardinality two.
Definition 2.1.2.
Let X = { x 1 , x 2 , … , x n} be a finite set of points and Y = { Ei , i∈ N} be a family
of subsets of X. The pair H = (X, Y ) is called a hypergraph of order n on X if Ei ≠ ∅
and S Ei = X. A hypergraph is simple, if the edges Ei , i∈ N are all distinct, and
multiple otherwise. If | Ei | ≤ 2 for all i∈N, then a multiple hypergraph is a
multigraph with isolated vertices and if | Ei | = 2, for all i∈N, then the simple

16
hypergraph is a graph without isolated vertices. Hypergraphs is a generalization of
a graph where an edge may contain more than two vertices.

Remark: A semi graph is an ordered linear hypergraph.


Observations:
(i) The edges {u1 ,u 2 , … , um} and {um , um−1 , … ,u 2 , u1} are same and

u1 ,u mare end vertices of the edge.

(ii) A semi graph with | Ei | ≤ 2, where i = 1, 2, ..., |X| is a graph.

2.2 Adjacent Vertices in Semi graphs


The graphical representation of graphs describe quite clearly how a set of
points which may be any thing in real situations, are related with one another, and
also how long one point is located from the other, than the mathematical
description of a graph. The end points of an edge in a graph are said to be incident
with the edge and the points-the vertices which are incident with a common edge
are said to be adjacent vertices. In the semi graphs we define four types of
adjacency among the ,vertices as there are three classes of vertices present in the
semi graphs.

17
Definition 2.2.1.
Two vertices u and v in a semi graph S are called
(i) adjacent if they be a part of the same edge.

(ii) consecutively adjacent if they are neighboring and consecutive in order as


well.
(iii) e-adjacent if they are the end vertices of an edge.

(iv) 1e-adjacent if both the vertices u and v belong to the similar edge and at
least one of them is an end vertex of that edge.

For an example, consider the semi graph S given in fig.2.1. The vertices
v1 , v 2, v3 are adjacent, v 2 , v 3 are consecutively adjacent, v1 v 3 are e-adjacent,

v 1 , v 2are 1e-adjacent.

The following can be observed from the example 2.1


Observations
(i) The number of adjacent vertices to a vertex v with respect to an edge E is
|E| − 1.
(ii) The adjacency of two vertices need not imply the consecutive adjacent,
the converse is always true.
(iii) In a semi graph the number of e-adjacent vertices to an end vertex v is
same as the number of edges for which v acts as an end vertex.
(iv) For a middle vertex the number of e-adjacent vertices is always zero.

(v) Let v be an end vertex, then the number of vertices 1e-adjacent to v is


∑i =1 =1 | Ei | − m, where v is an end vetex to the edge E1 . E2 , … , E m.
m

18
Two edges in a semi graph are adjacent if they have vertex in common. The
cardinality of an edge is the number of vertices lying on that edge. A semi graph
is an edge complete semi graph if any two edges in S are adjacent. A semi graph
is a claw semi graph if it contains exactly three edges having a common vertex
and no two vertices in distinct edges are adjacent.

2.3 Various Degrees of Vertices in Semi graphs


In general, the degree of a vertex in a graph is the number of edges of the graph
incident with that vertex. The presence of three types of vertices make us to
define the degrees of vertices in different ways. It can be seen later that each
type of the degree of a vertex has its own significance.

Definition 2.3.1.
In a semi graphS = (V, X), for a vertex v, various kinds of degrees are
defined as follows:
(i) The number of edges having v as an end vertex is called the degree of a
vertex v. It is denoted as deg(v)
(ii) The number of edges containing v is called the edge degree of a vertex v.
It is denoted as d e (v).
(iii) The number of vertices adjacent to v is called the adjacent degree of a
vertex v. It is denoted as d a(v).
(iv) The number of vertices consecutively adjacent to v is called the
consecutive adjacent degree of a vertex v. It is denoted as d ca (v).

The degree, edge degree, adjacent degree and consecutively adjacent degree of
all the vertices of the semi graph given in example 2.1.1. are given in the following

19
table. It can be easily observed that deg(v) ≤ d e ( v)≤ d ca(v) ≤ d a (v).
A vertex in a semi graph S is called a pendent vertex if deg(v) = de(v) = 1.
A pendent edge E is an edge containing a pendent vertex.
Definition 2.3.2. ∆a(S) =max v ∈V (S ) d a(v)
Theorem 2.3.1.
For any semi graph S = (V, X), and v ∈ V
(i) ∑deg(v) = 2|X|.
(ii) ∑de(v) = ∑deg(v) + |V m| + |V me | = 2|X| + |V m| + |V me |.
Proof.
(i) It is very simple observation that if v ∈V m, then deg(v) = 0.
is an end vertex for all such m edges.
Every edge also encloses another end vertex other than v.
Hence every edge calculated twice respectively for each end vertex. The same is
true for each vertex v∈V me . This proves (i)
(ii) Note that every edge is calculated twice while calculating edge degree of
an end vertex, and middle-end vertex of that edge.
Further every edge is again calculated once for each middle vertex and middle-
end vertex. Specifically, if v is a middle-end vertex, such that it is a middle vertex
for E1, and an end vertex for E2, both E1and E2 are counted once each
similar to the vertex v.
The computation of E1 is incorporated in the sum |V me | where as the count of E1
is included in the sum ∑deg(v) = 2|X|.This proves (ii).

20
End vertices v1 v3 v6 v8
deg(v) 3 3 4 3
de 3 3 4 3
da 5 7 8 5
d ca 3 3 5 3
Middle v4 v5 _ _
vertices
deg(v) 0 0 - -
d e (v) 1 1 - -
d a (v) 3 3 - -
d ca (v ) 2 2 - -
Middle end v2 v7 v9
_
vertices
deg(v) 1 1 1 _-
d e (v) 2 2 3 -
d a (v) 3 3 5 -
d ca (v ) 5 3 5 -

Figure 2.2: Various degrees of vertices of a semi graph

Theorem 2.3.2.
If S is a semi graph, and v∈V e , then deg(v) = d e (v) = d ca (v)
Proof.
Since, a vertex v∈V e performing as an end vetex for the number of edges is
same as the number of edges containing in it.
Therefore deg(v) = de(v). Also if v is an end vertex for n edges E1 , E2 ,… E n,
then there is absolutely one vertex vi in each Ei consecutively adjacent to v.
Therefore the number of vertices consecutively adjacent to v is equal to the
number of edges for which v performing as an end vertex.
Therefore deg(v) = d e (v) = d ca (v).
Theorem 2.3.3.

21
If S is a semi graph, and v∈V m, then
(i) deg(v) = 0
(ii) d e (v) ≥ 1
(iii) d a (v) = ∑d e (v) i=1 | Ei | − d e (v)
(iv) ∑d ca (v) = 2n if |V m| = n
(v) (v) d ca (v) = 2d e (v)
Proof.
The proof of (i) is clear, because deg(v) is the number of edges containing v as
an end vertex.
Since v∈V m, no such edge exists.
Therefore deg(v) = 0. It is also easy to observe that the middle vertices in a
semi graph S correspond to at least one edge in X.
Hence d e (v) ≥ 1. Hence (ii).
Let us assume that v∈E=¿, u2 , .., um ¿. Then the vertices u1 ,u 2 , .. ,u n are
all adjacent to v corresponding to the edge E.
Hence d a (v) = n = |E| − 1. Similarly, if d e (v) = m then there are m edges containing
v. Then by generalizing the above statement for these m edges
we have, d a (v) = ∑d e (v) i=1 | Ei | − d a (v). Thus (iii) is proved.
Let us assume that v∈V m. Then the vertex v∈Eu1 ,u 2 , … , ui−1 ,u 1 , ui , … ,u n ¿
for some E in X.
Note that the vertices ui−1and uiare consecutively adjacent to the vertex v. Since
v∈V m, existence of vertices such as ui−1 and ui are must to v.
Therefored ca (v) = 2, equivalent to the edge E consisting v.
Furthermore, if there are n middle vertices in S, then the sum of consecutively
adjacent degree of all n vertices is 2n. This proves (iv).
If v∈V m, and E contains v, then v has two consecutively adjacent vertices in E.
This is true for each edge containing v. In particular, if there are m edges
22
containing v, then d ca(v) = 2m and d e (v) = m. Hence d ca(v) = 2d e (v).
This proves (v). Hence the theorem.
Theorem 2.3.4.
If S is a semi graph, and v∈V me , then
(i) d e (v) >deg(v)
(ii) d ca = 2n( Ei ) +n( E j ), where n( Ei ) indicates number of edge in S at which

v is a middle vertex, and n( E j) indicates the number of edges in S at which v is


an end vertex in S.
Proof.
The proof (i) follows from the fact that deg(v) is calculated by assuming only
the edges for which v is an end vertex, whereas the d e (v) is calculated by assuming
all the edges enclosing v.
Hence d e (v) >deg(v). Let v∈V m. Then the edges Ei , i = 1, 2, ..., n and E j ,
j = 1, 2, ..., m such that v is a middle vertex for every Ei and end vertex for all E j .
For each Ei , d ca (v) = 2 and for each E j , d ca (v) = 1.
Therefore if n( Ei ¿= n, and n( E j ) = m, then d ca (v) = 2n( Ei) + n( E J ).
Hence the theorem.

Theorem 2.3.5.
Let S = (V, X) be a semi graph, and v ∈ V , then ∑v∈Vd a (v) = ∑| Ei |(| Ei | − 1)
Proof.
Let S = (V, X) be a semi graph, and v ∈ V . Also let v∈ Ei , for some Ei in X.
If | Ei | = n, then for each v ∈i, d a (v) = n − 1.
Hence for every v∈ Ei , ∑ v∈V d a (v )= n(n − 1).
On generalizing the above case, we can write down
∑v∈V d a(v) = ∑ | Ei |(| Ei | − 1).
23
This proves the theorem.

Chapter 3
Connectedness in Semi graphs

24
Connectedness is one of the basic properties of graphs. Whenever, graphs
are modelled to study the behavior of individual entities with reference to all other
entities in a real-time application, connectedness came into picture in the way of
finding connections between one another. In general, the necessary and sufficient
condition for a graph to be connected is that the vertex set can’t be partitioned into
two sets such that there is no edge connecting a vertex from one set into a vertex of
another set. This is applicable to semi graphs also. Since the complexity of semi
graphs interms the structures comparing to general graphs, different types of edges
have been introduced in semi graphs, and then the basic constituents of
connectedness namely walk, trial, path are defined analogously.

Definition 3.0.1.
In a semi graph S, an edge having cardinality at least three is known as s-
edge in S. A sub edge of an edge E = ( v1 , v 2 , … , v n) is a k-tuple, k ≥ 2, E = ( vi 1, vi 2,..,
vik ), where 1 ≤ i 1<i 2< ... <i k ≤ n. We say that E is a sub edge of E induced by the

vertices vi 1 , v i 2 ,… , vik . We denote the set of all subedges of E as P(E).

A partial edge of E is a (k−j+1)- tuple E = ( vij , v ij+1 , … , v ik), 1 ≤ j ≤ n. In a

partial edge the vertices are adjacent and consecutive as well, but in a subedge the

vertices are adjacent but need not be consecutive. Hence every partial edge in a

semi graph S is also a sub edge in S but not the converse.

25
Example 3.0.1.
Consider the semi graph in figure below

Figure 3.1: A semi graph with partial and sub edges

The semi graph given in the fig.3.1, the list ( v1 , v 3 , v 5 , v 6) is a subedge, and the
list ( v3 , v 4 , v 5) is a partial edge. The following are observations.
Observations
(i) Every semi graph containing only s-edges is a graph.
(ii) Every edge is sub edge to itself.

Definition 3.0.2.
An edge or a sub edge of an edge in a semi graph S is called an fs-edge in S.
Similarly, an edge or a partial edge is called a fp-edge in S.

26
Definition 3.0.3.
A v ¿walk in a semi graph S is a sequence of vertices v 0 , v1 , .., v nsuch
that( vi , v i +1) for i = 0 to n−1 is an fs-edge of cardinality two.
A v 0 − v n walkis a trail if any two fs-edges in it are distinct. A v 0 − v n trail in
which all the vertices are distinct is a v n − v npath.
A cycle is a closed path. A trail, path or walk is said to be strong if all the fs-
edges in it are fp-edges. A semi graph S is connected iff any two vertices are
connected by a path in S. We can easily observe the following lemma.
Lemma 3.0.1.
A semi graph is connected iff Sa and Sc aare connected.
Lemma 3.0.2.
Let E is an edge in a semi graph S. If |E| = n, then |P(E)| = 2 n − (n + 1).
Proof.
Since, any subset of cardinality greater than or equal to two of the set of vertices
of E form a sub edge of E, the number of such subsets is the total number of subset
of the set of vertices of E minus the singleton subsets and empty set.
Hence, it is easy to see that |P(E)| = 2n − (n + 1).
Definition 3.0.4.
Let S be a semi graph. Ina sub edge semi graph S E, e = ( v1 , … , v n) is an edge in
S Eiff e is a sub edge of an edge E in S, such that v1 and v nare end vertices of E. In

this case we say that e is covered by v1and v n.

Example 3.0.2.
Consider the semi graph S given in the example 2.1.1.
The sub edges of each edge in S, covered by their end vertices are given in the

27
Hence, the sub edge semi graph S E of S is given in the below figure.

Figure 3.3: A sub edge semi graph

We say that a sub edge semi graph S E is also a semi graph generated by S.
Note that if a semi graph S has only s-edges then, S = . S E

Definition 3.0.5.
A semi graph S = (V , X ) is a sub semi graph of a semi graph S = (V, X) if
V⊂ V , and the edges in S are the sub edges of the edges of S. Similarly, one can
define the partial semi graph of a semi graph. A sub semi graph S of a semi graph
S is a spanning sub semi graph if v = V`.

A semi graph S`= (V ` , X`) is an induced sub semi graph of S = (V, X) if V


`⊂ V and the edges in S` are the maximal sub edges induced by the vertices in V`.

Similarly, if the edges are maximal partial edges then the semi graph is called

induced partial semi graph of the graph S.

28
Figure 3.4: A semi graph and partial, spanning semi graphs.
Lemma 3.0.3.
A semi graph S is a spanning sub semi graph of the sub edge semi graph SE.
Proof.
Let S = (V, X) be a semi graph, and S E = (V `, X` ) is the sub edge semi graph of
S. Since, the vertex set of S and S E are same.
To prove this lemma, it is enough if we show that every edge of S is also an edge
of S E. This is obvious from the fact that every edge in a semi graph is also a
sub edge to itself. Hence the lemma.

29
Chapter 4
Types of Semi graphs and Associated Graphs
4.1 Types of Semi graphs
The nature of connectivity in graphs, categorize the graphs in one way.
Path graphs, cycle graphs, regular graphs, complete graphs, bipartite graphs, and so
on., are all special types of graphs, each varies from the other based on the nature
of connectivity present in the graph. In semi graphs too, there are such
classifications. In this section, we discuss some of such special semi graphs.

Definition 4.1.1.
A semi graph containing m edges with no middle-end vertices is path semi graph
Ps (m) , iff there are exactly two end vertices of degree one and all the other end

vertices are of degree 2.


Definition 4.1.2.
A semi graph containing m edges with no middle-end vertices is cycle semi graph
C s(m ) if the degree of each end vertex is 2. It can be observed that the path Semi

graph Ps(n) has n + 1 end vertices, among which n − 1 vertices are of degree 2, and
2 vertices are of degree 1. The degree of all middle vertices are 0, but the edge
degree of all these vertices is 1. The adjacent degree is same for all vertices of an
edge. The consecutive adjacent degree is 2 for all vertices in Ps (n) , except the two
end vertices which have degree 1. A path semi graph with no middle vertices is
simply the path Pn+1. In C s(n) , the degree and edge degree of all end vertices is 2
and the edge degree of all middle vertices is 1. Also the number of end vertices in
C s(n) is 0n 0.

Definition 4.1.3.Independent Sets: Let S = (V, X) be a semi graph. A subset U of


V is independent if no edge of S is a subset of U. The subset U of V is e-

30
independent if no two end vertices of an edge belong to S. The set U is strongly
independent if no two adjacent vertices belong to U. The set U is ca-independent if
no two vertices in U are consecutively adjacent in S.
The maximum cardinality of the independent set is called the corresponding
independence number of the semi graph.
As an example, consider the semi graph in fig.2.1. In that semi graph, the subset
U 1= {, v 1 , v 2 , v 5 } of the vertex set V is an independent set, where as the subset

U 2= { v1 , v 2 , v 4 , v 8 } is not an independent set because the subset {v1, v8} of U 2

forms an edge in S. The subset U 2 is also not an e-independent set for the same
reason. The subset U 1 is independent but not strongly independent, because the
vertices V 1 and V 2are adjacent in S. The subset U 1is also not a ca-independent set
for the same reason.
Definition 4.1.4. Bipartite Semi graph: A semi graph S is
(i) bipartite semi graph if its vertex set V can be partitioned into sets {X, Y }
such that both X and Y are independent sets.
(ii) e-bipartite semi graph if its vertex set V can be partitioned into sets
{X,Y}such that both X and Y are e-independent sets.
iii) strongly bipartite semi graph if its vertex set V can be partitioned into sets
{X, Y} such that both X and Y are strongly independent sets.
The following graph is an e-bipartite semi graph where e-independent sets are
X = { v1 , v 2 , v 5 , v 9 } Y = { v3 , v 4 , v 6 , v 7}.

31
Figure 4.1: An e-bipartite semi graph

Lemma 4.1.1.
If three end vertices form a triangle in a semi graph S, then semi graph S cannot
be an e-bipartite semi graph. The graph below is not an e-bipartite semi graph,
because v1, v3 , v 4 form a triangle.

Figure 4.2: A non e-bipartite semi graph

32
Definition 4.1.5. r-Uniform Semi graph:
A semi graph S is said to be r uniform if cardinality of each edge in S is r.
The first theorem of graph theory (Degree - Sum Formula) holds good for semi
graphs also, with regard to the definition that the number of edges having v as an
end vertex is called degree of a vertex v, which is denoted as deg(v), as given in
theorem 2.3.1. This is true only because that the degree of all middle vertices is
zero, and each edge is counted twice while summing up the degrees of end vertices
and middle-end vertices.

Lemma 4.1.2.
In a r-uniform semi graph S, ∑de(v) = |X|(r − 2) + ∑deg(v).
Proof.
In an r-uniform semi graph S, there are |X|(r − 2) number of middle vertices and
edge degree of each middle vertex is1.
Also, it is easy to observe that the degree and edge degree of the end vertices are
same. But for the middle-end vertices, de(v) = deg(v) + 1.
The value 1 appeared in the relation is counted while counting |X|(r − 2).
Hence the lemma
Definition 4.1.6.
Dendroid Semi graph: In general, graph theory contain a number of special
graphs. Each such special graph has their own properties, and differ from other
graphs with relation to structures and characteristics. In semi graphs also, a variety
of special semi graphs have been defined. A dendroid is a connected semi graph
without strong cycles, and a forest is a semi graph in which every component is a
dendroid. Analytically, the maximal connected induced sub semi graph is a
component of the semi graph. A star is a dendroid in which all edge have a
common vertex. A pendent dendroid is a dendroid in which every edge is pendent.

33
It can be seen that a strong cycle in a semi graph is a cycle in Sca and vice versa. A
weak cycle in a semi graph is a cycle in Sa and vice versa.

A wounded spider semi graph is the semi graph formed by subdividing at most
(t − 1) pendent edges of a star semi graph with t pendent edges
4.2 Associated Graphs
Every graph is also a semi graph. A semi graph in which the cardinality of
each edge set is exactly two is a graph. But in order to transform the semi graph
structures into usual graph structures, in a broader view, four types of associated
graphs has been defined in the theory of semi graphs.

Definition 4.2.1.
(i) End Vertex Graph ( Se ) : Two vertices in the graph
Se are said to be adjacent if they are the end vertices of an edge in S.
(ii)Adjacency Graph ( Sa ) : Two vertices in the graph Sa are said to be adjacent if
they are adjacent in S.
(iii)Consecutive adjacency Graph ( Sca ): Two vertices in the graph Sca are said to
be adjacent if they are the consecutively adjacent in S.
(iv)One end vertex Graph ( S1 e): Two vertices in the graph S1 e are said to be
adjacent if atleast one of them is an end vertex in S of an edge containing the two
vertices.

34
Example 4.2.1.
The following figure shows the associated graphs for the semi graph given in
example 2.1.1.

Figure 4.3 Adjacency Graph

Figure 4.4

35
Figure 4.5 Consecutive adjacency graph

Figure 4.6: The one end vertex graph

36
Lemma 4.2.1.
End vertex graph associated with a given semi graph is connected if the
Semi graph is a graph.
Proof.
In an end vertex graph Se , only the end vertices of an edge are adjacent. Also, if
there are two middle-end vertices connected by an edge, then they yield a
component in the end vertex graph.
Furthermore, the middle vertex is not adjacent to any other vertex in the end
vertex graph Se .
This leads to the fact that the middle vertices in S are isolated vertices in Se .
Hence the end vertex graph Se of the corresponding semi graph S is connected if
it has no middle and middle-end vertices,
i.e., the semi graph is a graph.
Lemma 4.2.2.
The size of adjacency graph Sa is , ∑n C 2where Ei is an edge in S, when n = | Ei |.
Proof.
In a semi graph S, two vertices are said to be adjacent if they belong tothe same
edge.
Therefore all the vertices belonging to an edge in S, become adjacent to each
other in adjacency graph Sa.
i.e., the vertices of each edge Ei in S form a clique in adjacency graph Sa
consisting nc 2 edges.
Therefore the total number of edges in Sa is ∑nC 2.

37
Lemma 4.2.3.
The size of consecutive adjacency graph Sca is P(| Ei |−1), where Ei is an edge in
S.
Lemma 4.2.4.
The size of an end vertex graph Sea is same as the size of the semi graph S.

38
Chapter 5

Characterization of e-homomorphism of Semi Graphs

Homomorphism can be viewed as a generalization of graph colorings. In Semi


graphs edge having three kind of vertices on it, which are end vertex, middle end
vertex and middle vertex. This leads to various types of adjacencies between
vertices.e-homomorphism of graphs is associate to End adjacency of vertices.
Color characteristic of homomorphism between graphs motivate us to establish the
color characteristic of e-homomorphism of semi graph. We had also investigated
the effect of various parameter like Clique number, Independence number under e-
homomorphism.

Definition 5.1: Coloring of semi graph:


Colors assign to vertices such that not all vertices in an edge are colored the
same. Minimum number of colors required for coloring the semi graph known as
chromatic number 𝜒(𝐺).
Definition 5.2: e-coloring :
A coloring of vertices of semi graph G such that no two end vertices of an
edge are colored the same. Minimum number of colors required for e-coloring the
semi graph known as e- chromatic number 𝜒𝑒(𝐺).

Definition 5.3: Complete graph :


A semi graph G is said to be complete if any two vertices in G are adjacent.
Complete graph on n vertices is denoted by k n.

39
Definition 5.4: Clique number :
A set S of vertices in a semi graph is said to form a clique if any two vertices
in S are Pair wise Adjacent. The maximum cardinality of the set S is clique number
.It is denoted by 𝜔(𝐺).

Definition 5.5: e-independence number :


A set S of vertices is e-Independent if no two end vertices of an edge belong to
S. Maximum cardinality of an e-independent set is e-independence number. Now
we are introducing similar concepts of external graph theory in semi graph.
According to end vertex adjacency we have introduced e-homomorphism.
Definition 5.6 :e- homomorphism of semi graphs:
A mapping from vertex set of semi graphs G to H is said to be e-homomorphism
if it preserve the end vertex adjacency of any two end vertices of G to end vertices
of graph H.
Example: 5.1
e-homomorphism between two graphs is shown below.

Figure 1:e-homomorphism
Definition 5.6:e- clique in semi graphs:
We have introduced e–clique in a semi graph is a subset S of V(G) which is a
collection of e-vertices if any two vertices in set S are Pair wise adjacent.
Maximum cardinality of the set S is e-clique number.𝜔𝑒 (G)

40
Theorem 5.1:
For any semi graph G𝜒𝑒 (𝐺) = 𝑛iff there exist e-homomorphism 𝑓: 𝐺 → k n,
for minimum 𝑛.
Proof:
If 𝜒𝑒 (𝐺) = 𝑛then there exist e-homomorphism 𝑓: 𝐺 → k n for minimum 𝑛. 𝐾𝑛,
is a complete Graph. Let n1 = {a 1 , a2 , … , an},
n2 = {b 1 , b2 , … , bn} .

::
n n= {t 1 , t 2 , … , t n} be the e-chromatic partition

of n vertices of graph G.
Clearly, each partition is e-independent and semi edge joining two end vertices lies
in different partition. Construct a map 𝑓: 𝐺→ k n Such that each partition is fiber of
different vertices of K n. Clearly, 𝑓 is e-homomorphism from 𝐺 to K nfor minimum
n.
Let 𝑓: 𝐺 → k n be e-homomorphism where K n is a complete graph with n-
vertices .
Suppose(a 1 , a2 , … , an) are n-end vertices which are adjacent in k n as there is in
e-homomorphism from 𝑓: 𝐺 → k n there fibers are adjacent in G. So We have 𝑛-
color class in G.
Hence , 𝜒𝑒 (𝐺) = 𝑛.

41
Corollary:
Let G and H be any two semi graphs if there is e- homomorphism from G to H
then𝜒𝑒 (𝐺) ≤ 𝜒𝑒 (𝐻).
Proof:
We know well known result that if 𝜒𝑒 (𝐺) = 𝑛 then there exist e-homomorphism,
𝑓: 𝐺 → k nfor minimum 𝑛. Let𝑔: 𝐺 → 𝐻 be e-homomorphism and
let 𝜒𝑒 (𝐻) = 𝑛.
Thenthere exist e-homomorphism ℎ: 𝐻 → k n but ℎ𝑔: 𝐺 → k n which is e-
homomorphism which implies 𝜒𝑒 (𝐺) = 𝑛 .
Hence 𝜒𝑒 (𝐺) ≤ 𝜒𝑒 (𝐻).
Theorem 5.2:
If there exist onto e-homomorphism 𝑓: 𝐺 → 𝐻 then 𝜔𝑒(𝐺) ≤ 𝜔𝑒(𝐻).
Proof:
Let 𝑓: 𝐺 → 𝐻be onto e-homomorphism. Suppose e-clique number of G is 𝑛 and
e-clique number of H is 𝑚 .
Suppose 𝑛>𝑚 Then there are 𝑛 different vertices (𝑎1 , 𝑎2 , … … , 𝑎𝑛 ) in graph
G which are pair wise adjacent to each other then we must get 𝑓(𝑎𝑖 ) is adjacent to
𝑓(a j) for 𝑖 ≠ 𝑗 in H.
which Contradict our assumption that 𝑛>𝑚.
Hence𝑛 ≤ 𝑚.i.e.𝜔𝑒 (𝐺) ≤ 𝜔𝑒 (𝐻).

Theorem 5.3:
A Mapping 𝑓∶𝑉(𝐺 ) 𝑉 (𝐻) is e-homomorphism if and only if each fiber is e-
Independent set.

42
Proof:
Let 𝑓: 𝑉(𝐺 ) →𝑉 (𝐻) be e-homomorphism.
Assume that the end vertices x and y of fiber 𝑓−1(𝑎)For some 𝑎𝜖𝑉(𝐻) are
adjacent in G.
But 𝑓(𝑥) and 𝑓(𝑦) are equal in H.As 𝑓: 𝐺→𝐻 is e-homomorphism
𝑓(𝑥)≠𝑓(𝑦).
Thus, each fiber is e-independent.
Let 𝑓: 𝐺→𝐻 is a function such that each fiber is e-independent set. Let 𝑥 and 𝑦
be end vertices of semi edge in G.
Then x and y must be in different fiber set as each fiber is e-independent
Hence 𝑥∈𝑓−1(𝑎)𝑎𝑛𝑑𝑦∈𝑓−1(𝑏). Hence 𝑓(𝑥) and 𝑓(𝑦) are adjacent in H.

43
Applications of Semi graph

Semi graph has different types of edges like sub edge and partial edges, these
types of edges play an important role in modelling road networks and also useful in
resolving traffic problems .The concept of semi graphs has a wide application in
molecular biology and its application in DNA splicing has been studied by K
Thiagarajan, J Padmashree and S Jeyabharathi. The concept of domination in
bipartite semi graph is introduced by Venkatakrishan Y B, Swaminathan V.
Domination in semi graph can be used to study the traffic routing and traffic
density at junctions of road networks. Also the concept of dominating set of semi
graph is used for clustering in wireless networks like adjacent dominating set is
used in algorithm for cluster head selection in wireless network.

44
Chapter 6
Conclusion

Semi graphs are the most appropriate generalization of graphs, in which


each edge contains a set of vertices. The existence of different types of vertices
pave the way to define different types of adjacencies between vertices, and hence,
every graph theoretical concept can be viewed in different ways. This enables one
to enlarge the existing theories to a greatest extent. The basic structural properties
of these general graphs-semi graphs have been studied in this project.

45
Bibliography
[1] Rang swami Balakrishnan and Kanna Ranganathan. A textbook of graph
theory. Springer Science & Business Media, 2012.
[2] B.Y Bam. On some problems of graph theory in semi graphs. PhD thesis,
Savitribai Phule Pune University, 2005.
[3] Ambika K Biradar. Review paper on a semi graph. International Journal of
Innovations in Engineering and Technology(IJIET), 12, 2018.
[4] N Murugesan and D Narmatha. Some properties of semi graph and its
associated graphs. International Journal of Engineering Research and Technology,
3(5):898–903, 2014.
[5] N Murugesan and D Narmatha. Characteristic polynomial of r-adjacency
matrix of path semi graph. International Journal of Innovative Research in Science,
Engineering and Technology, 5(7):1111–1119, 2016.
[6] N Murugesan and D Narmatha. a–domination of Cartesian product of path
Semi graphs. In Journal of Physics: Conference Series, volume 1543, page 012006.
IOP Publishing, 2020.

46

You might also like