Introduction to Tolerance Semigraph
ABDUR ROHMANa, SURAJIT KR. NATHb*
Department of Mathematical Sciences,
Bodoland University,
Kokrajhar, 783370,
INDIA
ahttps://orcid.org/0009-0006-1353-6009
bhttps://orcid.org/0000-0002-2142-393X
*Corresponding Author
Abstract: - Tolerance semigraph comes from intersection semigraph which varies with a tolerance value in such
a way that it generalizes interval semigraph. In this paper, we introduced the concept of tolerance semigraphs.
We also present some related definitions, examples, and results of tolerance semigraphs. We also described a
real-life application of tolerance semigraph with a suitable example, which is related to the scheduling problem
and Greedy Algorithm.
Key-Words: - Semigraph, Intersection Semigraph, Interval Semigraph, Tolerance Semigraph, Interval Graph,
Intersection Graph, Pendant Dendroids.
Received: July 18, 2023. Revised: October 19, 2023. Accepted: November 2, 2023. Published: November 29, 2023.
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.
An undirected graph G = (V, E) is called a
tolerance graph, [3], if there exists a collection
of closed intervals on the real line and a
set of positive numbers satisfying
where denotes
the length of interval and the pair is called
a tolerance representation of G.
The notion of semigraph, [2], [7], 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.
The problem of characterizing tolerance graphs,
[3], [4], [5], [6], was first proposed by M.C.
Golumbic. Since the concept of semigraph was first
introduced in mathematics in the year 2000 by E.
Sampathkumar. But, within this long period, the
concept of tolerance semigraph was still not
introduced though almost all of the concepts were
generalized on semigraph.
Here, we established tolerance semigraph and
some related results.
WSEAS TRANSACTIONS on MATHEMATICS
DOI: 10.37394/23206.2023.22.96
Abdur Rohman, Surajit Kr. Nath
E-ISSN: 2224-2880
884
Volume 22, 2023
2 Preliminary
Definitions, [2], [7].
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
endpoints 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 that 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: Example of Semigraph
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 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 Figure 1 are
.
Pendant Dendroids: A pendant dendroid is a
dendroid in which every edge is a pendant.
Intersection Semigraph: Let G = (V, X) be a
semigraph and F be a set of collections of partial
edges of the semigraph G, i.e. F={Si = pi| pi is a
partial edge 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 .
(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 .
Interval Semigraph: Let G = (V, X) be a semigraph
and F be a set of collection 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 .
3 Tolerance Semigraph
Definition 3.1: Let be a semigraph and
where ’s are the partial edges and is a set
of collections of partial edges of some edge of the
semigraph . Then a semigraph
is said to be a tolerance semigraph if for edge
partial edge can be assigned to a closed
interval and a tolerance so that and
are adjacent if and only if
.This type of collection of
intervals and tolerances is called a tolerance
representation of the semigraph where
and .
Example 3.1: Let be a semigraph with
partial edges
0
v
1
v
2
v
3
v
4
v
5
v
6
v
7
v
8
v
WSEAS TRANSACTIONS on MATHEMATICS
DOI: 10.37394/23206.2023.22.96
Abdur Rohman, Surajit Kr. Nath
E-ISSN: 2224-2880
885
Volume 22, 2023
as shown in Figure 2 and let F be a set
which is a collection of the partial edges. Now,
according to the definition, there exist
corresponding intervals for each partial edge. Let
be the corresponding intervals of
the partial edges where
as shown in Figure 3 .
Fig. 2: Semigraph
Fig. 3: Tolerance representation on the real line
Theorem 3.1: If is an interval
semigraph then is a tolerance semigraph with
constant tolerances.
Proof: Let be an interval semigraph
with a representation in which the interval is
assigned to a partial edge . Let be any positive
number less than
. Then the intervals
related to the tolerances for all gives a
tolerance representation of the semigraph with
constant tolerances.
Definition 3.2: A semigraph has a
representation with , for all where
is the partial edge then is called a bounded
tolerance semigraph.
Regular representation of a tolerance semigraph:
A tolerance semigraph is called a regular
representation if it satisfies one or more of the
following properties-
I. If all the tolerance values of the interval
semigraph are different from each other.
II. If no two distinct intervals share an
endpoint.
III. Any interval is set to infinity if any
tolerance is greater than its corresponding
interval.
IV. The tolerances are strictly positive.
V. The intersection of all the intervals should
be a non-empty intersection.
Then a tolerance a tolerance representation that
satisfies these properties is called regular
representation.
Theorem 3.2: If is a tolerance representation with
constant tolerances then is a bounded tolerance
graph with constant tolerances.
Proof: Let be a tolerance semigraph and
be a tolerance representation of the tolerance
semigraph with for all ,
where is the partial edge of the tolerance
semigraph .
Now, for the partial edge with for all
,
then define
.
If then is a pendent dendroid of and we
define to be an interval of breadth on a real
line that cannot intersect any other intervals and
this defines a bounded tolerance semigraph
representation of with constant tolerant
values.
Theorem 3.3: If is a bounded tolerance
semigraph with constant tolerances then
is an interval semigraph.
Proof: Let be a bounded tolerance semigraph
representation of the semigraph with
for all .
Now, if we denote the interval by
then the partial edges with
0
1
2
3
4
5
6
7
8
9
1
p
I
2
p
I
3
p
I
4
p
I
5
p
I
2
p
t
3
p
t
1
1
p
t
4
p
t
6
5
p
t
3
b
a
c
d
e
f
g
h
WSEAS TRANSACTIONS on MATHEMATICS
DOI: 10.37394/23206.2023.22.96
Abdur Rohman, Surajit Kr. Nath
E-ISSN: 2224-2880
886
Volume 22, 2023
and define
.
Otherwise, if then the
partial edge is a pendant dendroid of the
semigraph and the interval
be a point
that lies on the real line and that interval doesn’t
intersect any other intervals on the real line and the
intervals
gives an interval semigraph
representation of the semigraph .
4 Application
Use of Common Classroom Problems in Teaching
at the College Level
Tolerance semigraphs are among the most helpful
mathematical structures for modeling real-world
problems. In interval semigraph, we see the objects
are conflicted because of overlapping in time or like
any other. Generally, there are lots of applications
available in the areas of scheduling, biology, data
storage, chemistry, etc. As an example, here we
consider a classroom scheduling problem that arises
at a College. In a College, professors are each
assigned to a single classroom for their entire
teaching interval. But sometimes a conflict arises
because, at the same time and same classroom, there
are assigned meetings and teaching the classroom.
In that time, tolerance arises naturally. We face one
of the main problems that are within different
courses, we use one common classroom for
meetings as well as for teaching in the College.
When this type of situation or coincidence arises in
the scheduling of classrooms, we must be assigned
to make minimal possible classrooms for various
courses so that one can tolerate a certain amount of
overlap time with their classrooms.
This model of the problem is solvable by using
a Greedy Algorithm on the concept of Tolerance
Semigraph. Here we give a tolerance to each
interval of time and upon these tolerances we apply
the Greedy Algorithm.
5 Conclusion
This paper studied the tolerance semigraph where
tolerance semigraph is a special class of intersection
semigraph. There are lots of tolerance graph
theoretic concepts still waiting for investigation in
the structure of tolerance semigraph. So, the study
of tolerance semigraph is expected to bring
significant results in the near future.
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
Mathematics and Applications, India, 2000
[3] M.C. Golumbic, Tolerance Graphs, Discrete
Applied Mathematics , North-Holland 9, 157-
170, 1984
[4] M.C. Golumbic, Algorithmic Graph Theory
and Perfect Graphs, Annals of Discrete
Mathematics
[5] M.C. Golumbic, “Interval graphs and related
topics”, Discrete Mathematics 55,pp.113-121,
1985
[6] M. Golumbic and C. Monma, “A
Generalization of Interval Graphs with
Tolerances”, Congressus Numeratum 35,
pp.321-331, 1982
[7] S.K.Nath and P.Das, “Matching in
Semigraph”, International Journal of
Computer Application,Vol 6, No.3, 2013.
Contribution of Individual Authors to the
Creation of a Scientific Article (Ghostwriting
Policy)
The authors equally contributed in the present
research, at all stages from the formulation of the
problem to the final findings and solution.
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
WSEAS TRANSACTIONS on MATHEMATICS
DOI: 10.37394/23206.2023.22.96
Abdur Rohman, Surajit Kr. Nath
E-ISSN: 2224-2880
887
Volume 22, 2023
