Formulation, Proposition and Application of Interval Semigraph
ABDUR ROHMAN1,a, SURAJIT KR. NATH1,b,*, SHEETAL SONAWANE2,c
1Department of Mathematical Sciences,
Bodoland University,
Kokrajhar, 783370,
INDIA
2Department of Computer Engineering,
Pune Institute of Computer Technology,
Dhankawadi, Pune, 411043
INDIA
aORCiD: https://orcid.org/0009-0006-1353-6009
bORCiD: https://orcid.org/0000-0002-2142-393X
cORCiD: https://orcid.org/0000-0002-8733-8340
*Corresponding Author
Abstract: - Semigraph represents a versatile extension within graph theory, offering a broader framework for
exploration. Among these, intersection graphs hold pivotal roles, serving as essential analytical tools with wide-
ranging applications. In this study, we introduce the integration of intersection graphs into the generalized
structure of semigraphs, aiming to invigorate researchers’ interest and encourage further advancements in this
domain. This paper introduces two novel concepts: edge intersection semigraphs and interval semigraphs.
Additionally, foundational results pertaining to these concepts are established, elucidating their fundamental
properties. Furthermore, we illustrate the practical utility of interval semigraphs through an illustrative example
involving their application in optimizing road traffic management systems.
Key-Words: - Semigraph, Intersection Semigraph, Interval Semigraph, Interval Graph, Intersection Graph,
Optimization.
Received: March 23, 2023. Revised: November 9, 2023. Accepted: February 12, 2024. Published: March 29, 2024.
1 Introduction
A graph G = (V, E) is called an intersection graph,
[1], for a finite family F of a non-empty set if there
is a one-to-one correspondence between F and V
such that two sets in F have a non-empty
intersection if and only if their corresponding
vertices in V are adjacent. We call F an intersection
model of G. For an intersection model F, we use
G(F) to denote the intersection for F.
An undirected graph G = (V, E) is said to be an
interval graph, [1], if the vertex set V can be put into
one-to-one correspondence with a set I of intervals
on the real line such that two vertices are adjacent in
G if and only if their corresponding intervals have
non-empty intersection. That is, there is a bijective
mapping . The set I is called an interval
representation of G.
The notion of semigraph, [2], is a generalization
of that of a graph. While generalizing a structure,
one naturally looks for one in which every concept
in the structure has a natural generalization.
Semigraph is such a natural generalization of the
graph and it resembles a graph when drawn in a
plane.
In a graph, one edge contains two vertices i.e.
the graph is represented in a situation where these
involve only two objects in a relation. But when
there is a relation contained among the objects more
than two it is not possible to explain in terms of
graph. So, to handle this type of relation situation
we need a generalized graph and this generalized
structure is Semigraph. In semigraph, we see that all
properties enjoyed by vertices are also enjoyed by
edges.
[2], introduced a new generalization of graphs
called semigraphs. In 1994, after being confirmed
that the new generalization was natural and worthy
of applications, to a wider variety of situations and
WSEAS TRANSACTIONS on COMPUTER RESEARCH
DOI: 10.37394/232018.2024.12.25
Abdur Rohman, Surajit Kr. Nath, Sheetal Sonawane
E-ISSN: 2415-1521
264
Volume 12, 2024
decided to build a structural foundation for it. His
immediate task was to examine and see how the
new idea worked and what impact it had on the
existing terminology of graph theory. The
immediate impact was overwhelming. Graph
theoretic terms and definitions seemed to rally one
after another to be accommodated in a semigraph
setting either for their extensions or new
interpretations. With a generalized graph structure
allowing an unusually long list of terms and
definitions that were algebraically screened with
positive outcomes, it was natural to eye upon its
topological aspects, and expectations were fruitfully
rewarded. Within a very short period after
contributed the new generalization of the graph to
the world of Mathematics in 2000, Indian graph
theorists took up keen interest in this new area and
they began attempting to complete the untouched
and unfinished works of its originator. Encouraged
by new developments in various directions of
semigraph structure new faces are attracted into its
fold day by day.
In some situations, where more than two
objects/elements are involved in the same relation,
e.g. buying or selling goods. A goods we cannot buy
directly from a factory or company. To buy goods
there is a retailer and distributor between a
consumer and a company (factory). At this time, we
cannot represent this in graph theory but with the
help of semigraph we can easily express the
situation.
The quest to characterize interval graphs
originated independently in different fields, [3], [4],
in combinatorics and, [5], in genetics during 1957-
1959. However, the introduction of the semigraph
concept in mathematics came later, in the year 2000.
Despite this period, the introduction of the interval
semigraph remained unaddressed, despite the
comprehensive generalization of concept onto
semigraphs. This paper addresses this gap by
introducing the notions of edge intersection
semigraphs, interval semigraphs, and several
associated results.
2 Preliminary
Definitions, [2], [6], [7], [8]
Semigraph: A semigraph G is a pair (V, X) where V
is a non-empty set whose elements are called
vertices of G and X is a set of n-tuples, called edges
of G, of distinct vertices, for various ,
satisfying the following conditions.
(a) Any two edges have at most one vertex in
common.
(b) Two edges (u1,u2,…,un) and (v1,v2,…,vm) are
considered to be equal if and only if
(i) m= n and
(ii) either ui = vi for ,
or ui = vn-i+1 for .
An edge e is represented by a simple open
Jordan curve which is drawn as a straight line whose
end points are called the end vertices of the edge e
and the m-vertices of the edge e each of which is not
an m-vertex of any other edge of the semigraph G
are denoted by small circles placed on the curve in
between the end vertices, in the order specified by e.
The end vertices of edges which are not m-vertices
are specially represented by thick dots. If an m-
vertex of an edge e is an end vertex of an edge e՛
i.e. an (m, e) vertex, we draw a small tangent to the
circle at the end of the edge e՛.
Example 2.1: Let be a semigraph. Then
the edges of the semigraph in Figure 1 are
Fig. 1: Semigraph Example
Subedges: A subedge of an edge E= (v1, v2 ,…, vn)
is a k-tuple
),...,,( 21 k
iii vvvE
where
or .
We say that the subedge E is induced by the set of
vertices
},...,,{ 21 k
iii vvv
.
Example 2.2: Let be a semigraph. Then
the sub edges of the semigraph from the Figure 1 are
.
Partial edge: A partial edge of E is a -
tuple where .
Thus a subedge E of an edge
E
is a partial edge if
and only if , any two consecutive vertices in E
are also consecutive vertices of E .
Example 2.3: Let be a semigraph. Then
the partial edges of the semigraph from the Figure 1
are .
Subsemigraph: A semigraph
),( EVG
is a
subsemigraph of a semigraph if
and the edges in are subedges of .
Induced subsemigraph: A semigraph
),( EVG
is an induced subsemigraph of a
0
v
1
v
2
v
3
v
4
v
5
v
6
v
7
v
8
v
WSEAS TRANSACTIONS on COMPUTER RESEARCH
DOI: 10.37394/232018.2024.12.25
Abdur Rohman, Surajit Kr. Nath, Sheetal Sonawane
E-ISSN: 2415-1521
265
Volume 12, 2024
semigraph if the edges in are
subedges of induced by the vertices .
Consecutive ones property: Consecutive ones
property, [9], is a property of two-dimensional
matrices whose entries are only 0 and 1. These
matrices are called binary matrices and the binary
matrix has the consecutive ones property (C1P) for
columns when its rows can be permuted so that in
each of its columns the 1’s appear consecutively.
3 Intersection and Interval Semigraph
Definition 3.1: Let G = (V, X) be a semigraph and
F be a set of collection of partial edges of the
semigraph G, i.e. F={Si = pi| pi is a partial edges of
some edge in G}. Then is said to edge
intersection semigraph in G where the edge set of
consists of the edge of the types:
(a)
2),,...,,( 21
rpppE r
iii
,where
11,, 1
rjpp jj ii
are the consecutive
partial edges of the same s-edge
XE
*
.
(b)
),(
*ji ppE
, where pi and pj are not the
partial edges of the same s-edge and they
have a vertex in common and also
.
Example 3.1: Consider G = (V, X) be a semigraph
and clearly from the Figure 2, the edges of the
semigraph are (1, 2, 3, 4, 5), (3, 6, 7), (4, 8, 9, 10).
Now, if F is the collection of partial edges of G then
F= {S1, S2,…, Sn}, where
S1 = {(1, 2, 3), (3, 4), (4, 5)}
S2 = {(4, 8), (8, 9, 10)}
S3 = {(3, 6), (6, 7)}
Clearly, we can say that . Thus G is an
edge intersection semigraph.
Fig. 2: Intersection Semigraph Example
Definition 3.2: Let G = (V, X) be a semigraph and F
be a set of collections of partial edges of some edge
E of the semigraph G, i.e. F ={Si = pi| pi is a partial
edge of some edge E of G}. Then pi corresponds to
an interval [a, b] in
, provided that if pi and pj
are adjacent then our corresponding interval is
.
Example 3.2: Consider G = (V, X) be a semigraph
then from Figure 2, the partial edges of G
correspond to an interval on a real line where two
partial edges are adjacent. Thus, G is an interval
semigraph.
Definition 3.3: An undirected semigraph
),( XVG
is called a triangulated semigraph if
every cycle of length strictly greater than 3
possesses a chord that is an edge joining two non-
consecutive vertices of the cycle.
Theorem 3.1: Every semigraph is an edge
intersection semigraph.
Proof: Let G = (V, X) be a semigraph and S be any
non-empty set and F = {Si = pi| pi is a partial edge
of some edge E of G}, where i S,
Then each edge of G is adjacent to the partial edges
pi . Thus, every semigraph is an edge intersection
semigraph.
Theorem 3.2: Every edge intersection semigraph is
an interval semigraph and conversely.
Proof: Let G = (V, X) be an edge intersection
semigraph, where V=V(G) and X=X(G) and let S be
a non-empty set of closed intervals on the real line
with each vertex corresponding to a closed interval.
Then the set of collections of partial edges of some
edge in G is isomorphic to G. By the definition of
interval semigraph, the set of intervals is also
isomorphic to G. Therefore, every edge intersection
semigraph is an interval semigraph.
Conversely, let us assume that G = (V, X) is an
interval semigraph where V=V(G) and X=X(G).
By the definition of interval semigraph, there
exists intervals on a real line and the set of intervals
is isomorphic to G. Since, the set of intervals is
isomorphic to G so the set of collection of partial
edges of some edge in G is also isomorphic to G.
Therefore, an interval semigraph is also an edge
intersection semigraph.
Theorem 3.3: An induced subsemigraph of an
interval semigraph is an interval semigraph.
Proof: Let
),( EVG
be an induced
subsemigraph of an interval semigraph
),,( XVG
then by the definition of interval semigraph there
exist an interval representation for the
semigraph . Also then
)(
}{ GEee
I
is
an interval representation for the induced
1
2
3
4
5
6
7
8
9
10
WSEAS TRANSACTIONS on COMPUTER RESEARCH
DOI: 10.37394/232018.2024.12.25
Abdur Rohman, Surajit Kr. Nath, Sheetal Sonawane
E-ISSN: 2415-1521
266
Volume 12, 2024
subsemigraph
),( EVG
. Therefore, an induced
subsemigraph of an interval semigraph is an interval
semigraph.
Theorem 3.4: An interval semigraph satisfies the
triangulated semigraph property.
Proof: Let the interval semigraph
contains a chordless cycle
with . Suppose denotes the interval
corresponding to the partial edge . Now
for , consider an interval for
the interval semigraph . Since,
do not intersect so the interval
constitutes an increasing or decreasing sequence.
Therefore, it is not possible for and to
intersect, contradicting the fact that is a
partial edge of the interval semigraph.
Theorem 3.5: A connected semigraph is an interval
semigraph if and only if, for every three partial
edges, one of them lies between the other two.
Proof: Let
),( XVG
be a connected semigraph
and there is a set F of collection of partial edges of
the semigraph. Then there is a partial edge
i
p
for
which each
i
S
belongs to
X
corresponds to the
partial edge
i
p
of
F
. Then, a partial edge
j
p
lies
between any two partial edge
i
p
and
k
p
.
Conversely, suppose that
),( XVG
satisfies
the condition that for every three partial edges, one
of them lies between the other two partial edges. We
have to show that
),( XVG
is a connected
interval semigraph. Consider a semigraph
),( XV
with
XX
such that the semigraph satisfies the
condition in the theorem and
X
is maximal.
Let
i
p
and
j
p
are two distinct partial edges in
the semigraph
),( XVG
. If
i
p
and
j
p
do not
belongs to
S
then
Xpp ji ,
and the semigraph
does not satisfy the condition in the statement. Let
the semigraph contain distinct
x
p
,
y
p
and
z
p
partial
edges with the length of shortest path of the partial
edges
),,...,,( 1yux pEEp
with
)...(1uz EEp
),,...,,( 1zvy pEEp
with
)...(1vx EEp
),,...,,( 1zwx pEEp
with
)...(1wy EEp
Where the set of partial edge
},...,,,...,,,...,{},{ 111 wvuji EEEEEEppS
But if each occurrence of
},{ ji pp
among
u
E
’s,
v
E
’s and
w
E
’s is replaced by
XS
, then by
condition in theorem one of
x
p
,
y
p
and
z
p
will be
between other two. Without loss of generality, let
the partial edge
y
p
is between the partial edge
x
p
and
z
p
. That means that
tji Epp
},{
for some
wt 1
and so
jyi ppp
and
Spy
.
Without loss of generality, using minimality of lenth
of partial edge
zwx pEEp ,,...,,1
, suppose that
1
ti Ep
.By assumed maximality of
X
, we can
assume
XEEP t
11 ...
. Thus there exists
XP
such that
Ppp xi ,
and
Ppp yj ,
.
Similarly, there exists
XQ
such that
Qpp zj ,
and
Qpp yi ,
. Again, using maximality of
X
,
we assume
XQSPS
\,\
and so
i
p
and
j
p
are
connected by partial edge
jyi pPSpQSp ,\,,\,
in
),( XV
. Thus, every partial edges
XS
are
linked by a partial edge in
),( XV
whose partial
edges are subsets of
S
and that every partial edge
*
XS
has cardinality two otherwise
*
\XQS
would contradicts
S
’s assumed minimality.
Therefore
),( *
XV
is a semigraph and the assumed
maximality of
X
implies
XV
so
),( *
XV
is
connected and the condition implies that
),( *
XV
is
a path and every partial edge
XS
can be seen as
a connected subset of
),( XV
by the argument on
cardinality of
S
.
4 Application
To minimize traffic with minimum time interval:
Let be the set of places such as villages,
towns, cities, etc. in a state interconnected by a road
network. Consider a State Transport Corporation
running its buses to various destinations with a
minimum time interval in the state. For the purposes
of economy, to reduce running time and to avoid the
stretch of any road being traversed by the buses
plying on two different routes can minimize the
traffic with a minimum time.
The corporation can plan its routes in such a
way that any two routes may be planned as an
interval semigraph on the available road network
where the vertices represent the village, towns,
WSEAS TRANSACTIONS on COMPUTER RESEARCH
DOI: 10.37394/232018.2024.12.25
Abdur Rohman, Surajit Kr. Nath, Sheetal Sonawane
E-ISSN: 2415-1521
267
Volume 12, 2024
cities, etc. and the partial edges are determined with
the corresponding time intervals. From the Figure 3,
we can define the end vertices as
the terminal of the road network and the middle
vertices as through destinations. The
partial edges , etc.
are defined as the corresponding time interval of the
interval semigraph. Now by the definition of
interval semigraph, if any two partial edges are
adjacent then their corresponding interval has a non-
empty intersection. Thus, for any two partially
connected routes their running time interval must be
non-empty from one destination to another
destination. If the corporation has planned their
routes in this way then they can minimize their
traffic problem and also they can reduce the running
time from one terminal to another.
Fig. 3: Semigraphical Model
5 Conclusion
In this research, we delve into the intricate
relationship between intersection semigraphs and
their specialized subset, the interval semigraphs.
The interval semigraph, a distinctive category
within intersection semigraph theory, serves as a
focal point for our investigation. Our exploration
highlights the uncharted terrain within interval
graph theory, indicating ample opportunities to
unravel the underlying structures of interval
semigraphs. Through this study, we anticipate the
emergence of substantial findings that will
significantly contribute to the evolving landscape of
interval semigraph theory.
References:
[1] M.Pal, “Intersection Graphs-An Introduction”,
Annals of Pure and Applied Mathematics,
vol.4, No.1, pp. 43-91, 2013.
[2] E. Sampathkumar, “Semigraph and Their
Applications”, Academy of Discrete
Mathematicsand Applications, India, 2000.
[3] G. Hajos, “ Uber eine Art von Graphen”,
Intern.Math. Nachr.11, Problem 65, 1957.
[4] M.C. Golumbic, “Interval Graphs and Related
Topics”, Discrete Mathematics 55, 113-121,
1985.
[5] S. Benzer, “On the topology of the genetic
fine structure”, Proc. Nat. Acad. Sci. U.S.A.,
45, 1607- 1620, 1959.
[6] S.K. Nath and P. Das, “Matching in
Semigraphs”, International Journal of
ComputerApplication, Vol 6, No.3, 2013.
[7] S.S. Kamath, R.S. Bhat, “Domination in
Semigraphs”, Electronic Notes in Discrete
Mathematics, Vol.15, 106-111, 2003.
[8] B.Y. Bam, C.M. Deshpande, N.S. Bhave,
“Line semigraph of a semigraph”, Korean
Journal Adv. Studies Contem. Math.,
Vol.18(2), 2009.
[9] J. Meidanis, O. Porto, G. P. Telles, “On the
consecutive ones property”, Discrete Applied
Mathematics, 88, 325-354, 1998.
Contribution of Individual Authors to the
Creation of a Scientific Article (Ghostwriting
Policy)
- Abdur Rohman and Surajit Kr. Nath conceived of
the presented idea and developed the theory.
- Surajit Kr. Nath and Sheetal Sonawane verified
the analytical methods and contributed to the
design and implementation of the research to write
the manuscript.
Sources of Funding for Research Presented in a
Scientific Article or Scientific Article Itself
No funding was received for conducting this study.
Conflict of Interest
The authors have no conflicts of interest to declare.
Creative Commons Attribution License 4.0
(Attribution 4.0 International, CC BY 4.0)
This article is published under the terms of the
Creative Commons Attribution License 4.0
https://creativecommons.org/licenses/by/4.0/deed.en
_US
1
v
2
v
3
v
4
v
5
v
6
v
7
v
8
v
9
v
WSEAS TRANSACTIONS on COMPUTER RESEARCH
DOI: 10.37394/232018.2024.12.25
Abdur Rohman, Surajit Kr. Nath, Sheetal Sonawane
E-ISSN: 2415-1521
268
Volume 12, 2024
