TWMS J. App. and Eng. Math. V.13, N.2, 2023, pp.

765-772

MIDDLE GRAPH OF SEMIRING VALUED GRAPHS

A. TAMILSELVI1∗ , M. PONNI1 , §

Abstract. In this paper, we define middle graph of semiring valued graph M (GS ) and
study the regularity of M (GS ) where GS is the semiring valued graph (or simply S-
valued graph).

Keywords: Middle graph, S-valued graph, regularity.

AMS Subject Classification: 05C22, 05C25, 05C38.

1. Introduction
The middle graph M (G) of a graph G is an intersection graph Ω(F ) on the vertex set
V (G) of any graph G. Let E(G) be an edge set of G and F = V 0 (G) ∪ E(G), where V 0 (G)
indicates the family of all one vertex subsets of the set V (G). This concept was introduced
by T. Hamada and I. Yoshimura [1] and studied by V.R. Kulli and H.P. Patil.
Jonathan S. Golan, was the first person who introduced the notion of S-valued graphs
where he defined a function g : V ×V → S such that g(v1 , v2 ) 6= ∅. Here V is the vertex set
of a graph G and S is a semiring. Golan consider the S-valued graph by assinging values
to the edges only. Further, M.Rajkumar, S. Jeyalakshmi and M. Chandramouleeswaran
precisely studied the graphs whose vertices and edges are assigned values from the semiring.
However, they assign values to every vertex of G and the edges of G are assigned values
according to the minimum value of vertices incident with the edges.
This motivated us to study the middle graph of graphs whose vertices and edges are
assigned values from the semiring S. However, we assign values to every vertex of a middle
graph of S-valued graph as same as in S-valued graph whenever vertex lies in G. Otherwise
we assign the value of the vertex to be the value of its corresponding edge. We also assign
the value for edges in M (G) in relation to values of vertices incident with that edges.

2. Basic definitions
In this section, we recall some basic definitions from the theory of semirings and S-
valued graphs. [2].
1
Ramanujan Institute for Advanced Study in Mathematics, University of Madras, Chennai, India.
e-mail: tamilselvi.riasm@gmail.com; ORCID: https://orcid.org/0000-0002-0682-2705.
∗
Corresponding author.
e-mail: kumarponniinc.ttm@gmail.com; ORCID: https://orcid.org/0000-0002-3409-7109.
§ Manuscript received: February 15, 2021; accepted: May 11, 2021.
TWMS Journal of Applied and Engineering Mathematics, Vol.13, No.2 © Işık University, Department
of Mathematics, 2023; all rights reserved.

765
766 TWMS J. APP. AND ENG. MATH. V.13, N.2, 2023

Definition 2.1. [1] Let G = (V, E) be a graph with E 6= ∅. The middle graph of a graph
G, denoted by M (G), is the graph whose vertex set is VM and edge set is EM , where
VM = V ∪ {eji = [vi , vj ] : (vi , vj ) ∈ E} and EM = {(e, f ) : e and f are adjacent}.
Note: Adjacent in the sense that the corresponding edges are adjacent in G (in case of
both vertices are edges). Otherwise, one is a vertex and the other is an edge incident with
it.
Example 2.1. Middle graph of the graph G.

G M (G)

Definition 2.2. A semiring (S, +, ·) is an algebraic system with a non-empty set S to-
gether with two binary operation + and . such that
1. (S, +) is a commutative monoid.
2. (S, ·) is a semigroup.
3. For all a, b, c ∈ S, a · (b + c) = a · b + a · c and (a + b) · c = a · c + b · c.
4. 0 · x = x · 0 = 0, ∀x ∈ S.
Example 2.2. (M2×2 (R+ ), +, ·) - Set of all 2 × 2 matrices whose entires are positive real
numbers forms semiring under matrix addition and matrix multiplication which is not a
ring.
Definition 2.3. Let (S, +, ·) be a semiring.  is said to be a Canonical preorder if for
a, b ∈ S, a  b if and only if there exist c ∈ S such that a + c = b.
Example 2.3. Let us take a semiring N ∪ {0}. 1  2 because there exists 1 ∈ N ∪ {0}
such that 1 + 1 = 2. But 1  0.
Example 2.4. Let (S, +, ·) be a semiring with binary operations ‘+’and ‘.’defined by the
following Cayley tables.
+ 0 a b c · 0 a b c
0 0 a b c 0 0 0 0 0
a a a b c a 0 a a a
b b b b c b 0 a a a
c c c c b c 0 a a a
Clearly, 0  0, 0  a, 0  b, 0  c, a  a, a  b, a  c, b  b, b  c, c  c, c  b.
Definition 2.4. Let G = (V ,E) be given graph with both V ,E 6= ∅. For any semiring
(S,+,·), a semiring-valued graph (or a S- valued graph), GS , is defined to be the graph
GS = (V, E, σ, ψ), where σ : V → S and ψ : E → S is defined to be
(
min{σ(x), σ(y)} if σ(x)  σ(y) or σ(y)  σ(x)
ψ(x, y) =
0 otherwise
 A. TAMILSELVI, M. PONNI: MIDDLE GRAPH OF SEMIRING VALUED GRAPHS 767

Remark 2.1. The vertices and edges of GS are the vertices and edges as in its underlying
graph G. Since every semiring posses a canonical pre-order, σ, ψ are well defined. In
general, both vertices and edges of a S-valued graph have values in the semiring S, called
S-values. We call σ, a S-vertex set and ψ, a S-edge set of S-valued graph GS .
Example 2.5. Consider the semiring with the canonical pre-order  given in Example
2.4. Let G = (V, E) be the graph with V = {v1 , v2 , v3 , v4 } and E = {(v1 , v2 ), (v1 , v3 ),
(v3 , v4 )}. Corresponding to the graph G, we define the S-graph GS as follows:
Define σ : V → S and ψ : E → S by σ(v1 ) = σ(v3 ) = a; σ(v2 ) = b; σ(v4 ) = c and
ψ(v1 , v2 ) = ψ(v1 , v3 ) = ψ(v3 , v4 ) = a.
v1 v1 (a)
a a
a
v2 v3 v4 v2 (b) v3 (a) v4 (c)
G GS

Definition 2.5. Let GS = (V, E, σ, ψ) be S-valued graph. A S-walk v0 − vn in GS is an

alternating sequence of vertices and edges (v0 , σ(v0 )), (e10 , ψ(e10 )), (v1 , σ(v1 )), (e21 , ψ(e21 )),
· · · , (vn−1 , σ(vn−1 )), (enn−1 , ψ(enn−1 )), (vn , σ(vn )), beginning and ending with vertices v0 and
vn respectively, such that vi−1 and vi are end vertices of the edge eii−1 , 1 ≤ i ≤ n.
If (v0 , σ(v0 )) = (vn , σ(vn )), then the v0 − vn S-walk is said to be a closed S-walk.
A v0 − vn S-walk is a S-trial if any two edges in it are distinct. That is, in a S-trial,
vertices may be repeated but all the edges are different.
A v0 − vn S-walk is a closed S-trial (or a S-tour) if (v0 , σ(v0 )) = (vn , σ(vn )) and any
two edges in it are distinct.
A v0 − vn S-path in GS is a S-trial in which all the vertices are distinct.
A S-closed path, that is (v0 , σ(v0 )) = (vn , σ(vn )) in a S-path, is called a S-cycle.
Definition 2.6. [2] If σ(v) = a, ∀v ∈ V and some a ∈ S, then the corresponding S-valued
graph GS is called vertex regular S-valued graph. If ψ(vi , vj ) = a, ∀(vi , vj ) ∈ E and some
a ∈ S, then the corresponding S- valued graph GS is called edge regular S-valued graph.
An S-valued graph GS is said to be S-regular if it is both a vertex regular and an edge
regular S-valued graph.
Lemma 2.1. [2] If GS is vertex regular S-valued graph, then GS is edge regular S-valued
graph.

3. Middle graph of S-valued graphs M (GS )

In this section, we define the middle graph of S-valued graph and discuss some of its
properties.
Definition 3.1. Let G = (V, E) be a graph, GS = (V, E, σ, ψ) be a semiring valued graph
and M (G) = (VM , EM ) be a middle graph of G. Define M (GS ) = (VM , EM , σM , ψM )
where σM : VM → S and ψM : EM → S are defined by
(
σ(v) if v ∈ V
σM (v) =
ψ(vi , vj ) if v = eji ∈ VM \ V
(
min{σM (e), σM (f )} if σM (e)  σM (f ) or σM (f )  σM (e)
ψM (e, f ) =
0 otherwise
768 TWMS J. APP. AND ENG. MATH. V.13, N.2, 2023

Remark 3.1. (1) The vertices and edges of M (GS ) are the vertices and edges as in
its underlying middle graph M (G). Since every semiring posses a canonical pre-
order, σM , ψM are well defined. In general, both vertices and edges of a S-valued
graph have values in the semiring S, called S-values. We call σM , a S-vertex set
and ψM , a S-edge set of S-valued graph M (GS ).
(2) The number of vertices of the middle graph of S-valued graph G is twice the number
of vertices of G. i.e., |VM |S = 2|V |.
(3) The number of edjes of the middle graph of S-valued graph G is twice the number
of edjes of G. i.e., |EM |S = 2|E|.
Example 3.1. Consider a semiring as in Example 2.4. The middle graph M (GS ) of the
S-valued graph GS is given by:
v1 (a) v1 (a)
a a
a a a a
a a
c a a c
c v (c)
v2 (b) v3 (c) v4 (c) v2 (b) v3 (c) c 4

GS M (GS )

Theorem 3.1. The middle graph of S-cycle has atleast two S-cycles.
Proof. Consider the cycle Cn = v1 , (v1 , v2 ), v2 , . . . , vn , (v1 , vn ), v1 . Then we can construct
the cycles in M (Cn ) as follows:
A = v1 , (v1 , e21 ), e21 , (e21 , v2 ), v2 , (v2 , e32 ), · · · , (enn−1 , vn ), vn , (vn , en1 ), en1 , (en1 , v1 ), v1 and
B = e21 , (e21 , e32 ), e32 , (e32 , e43 ), e43 , · · · , enn−1 , (enn−1 , en1 ), en1 , (en1 , e21 ), e21 .
It is easy to observe that the S-cycle AS corresponding to the cycle A is a C2n S , S-cycle

and the S-cycle B corresponding to the cycle B is a Cn , S-cycle. Therefore M (CnS ) has
S S

atleast two S-cycles. 

Theorem 3.2. The middle graph of S-path has atleast two S-path.
Proof. Consider the path Pn = v1 , (v1 , v2 ), v2 , · · · , (vn−1 , vn ), vn . Then we can construct
the paths in M (Pn ) as follows:
Q = v1 , (v1 , e21 ), e21 , (e21 , v2 ), v2 , (v2 , e32 ), · · · , (enn−1 , vn ), vn and
n−1 n
R = e21 , (e21 , e32 ), e32 , (e32 , e43 ), e43 , · · · , (en−2 , en−1 ), enn−1
S S
Let us take the S-paths Q and R corresponding to the paths Q and R. It is easy
to observe that QS is a P2n−1 S , S-path and RS is a Pn−1 S , S-path. Therefore M (P S ) has
n
atleast two S-paths. 
Definition 3.2. Let M (GS ) = (VM , EM , σM , ψM ) be the middle graph of S-valued graph
GS = (V, E, σ, ψ). A S-valued graph M (H S ) = (PM , LM , τM , γM ) is said to be S-subgraph
of M (GS ) if H = (P, L) is a subgraph of G with τM ⊂ σM and γM ⊂ ψM .
That is, τM ⊂ σM ⇒ τM (v)  σM (v), ∀v ∈ PM and γM ⊂ ψM ⇒ γM (vi , vj ) 
ψM (vi , vj ), ∀(vi , vj ) ∈ LM .
Definition 3.3. Let M (GS ) = (VM , EM , σM , ψM ) be a middle graph of S-valued graph.
A S-valued graph M (H S ) = (PM , LM , τM , γM ) is said to be S-subgraph of M (GS ) induced
by PM if H is a subgraph of G with PM ⊂ VM , LM ⊂ EM , τM (v) = σM (v), ∀v ∈ PM and
γM (vi , vj ) = ψM (vi , vj ), ∀(vi , vj ) ∈ LM .
Example 3.2. Consider the S-valued graph GS and its corresponding its middle graph
M (GS ).
 A. TAMILSELVI, M. PONNI: MIDDLE GRAPH OF SEMIRING VALUED GRAPHS 769

v1 (a) a v2 (a) v1 (a)a a a v2 (a)

a a a a
a a a a
a a
a a

v3 (b) b v4 (b) v3 (b) b b b v4 (b)

GS M (GS )
Consider the semiring with canonical pre-order  as given in Example 2.4. Let
M (G) = (VM , EM ), where VM = {v1 , v2 , v3 , v4 , e21 , e32 , e43 , e41 } and
EM = {(v1 , e21 ), (e21 , v2 ), (v2 , e32 ), (e32 , v3 ), (v3 , e43 ), (e43 , v4 ), (v4 , e41 ), (e41 , v1 ), (e21 , e32 ), (e32 ,
e43 ), (e21 , e41 )}.
Consider the subgraph M (H) of M (G) such that PM = {v1 , v3 , v4 , e41 , e43 } and
LM = {(v1 , e41 ), (e41 , v4 ), (v3 , e43 ), (e43 , v4 )}.
Define τM (v1 ) = τM (v4 ) = a, τM (v3 ) = b and τM (e41 ) = τM (e43 ) = a. Therefore,
τM (v)  σM (v) for every v ∈ PM . Hence τM ⊂ σM .
Now define γM : L → S as follow γM (v1 , e41 ) = min{σM (v1 ), σM (e41 )} = min{a, a}.
Similarly, γM (e41 , v4 ) = γM (v3 , e43 ) = γM (e43 , v4 ) = a. Therefore γM  ψM .
Thus the S-subgraph M (H S ) = (PM , LM , τM , ψM ) is given by

v1 (a)
a
a
a a
v3 (b) a a v4 (a)

Definition 3.4. Let GS = (V, E, σ, ψ) be a S-valued graph and M (H S ) = (PM , LM , τM , γM )

be a S-subgraph of M (GS ) = (VM , EM , σM , ψM ). M (H S ) is said to be a spanning S-
subgraph of M (GS ) if PM = VM , LM ⊂ EM , τM (v) = σM (v), ∀v ∈ PM and γM (vi , vj ) =
ψM (vi , vj ), ∀(vi , vj ) ∈ LM .
Example 3.3. Consider the middle graph M (GS ) of S-valued graph as in Example 3.2.
The spanning S-subgraph M (H S ) of M (GS ) is given by:
v1 (a) a v2 (a)
a a
a a
a a
a a
b b
v3 (b) b v4 (b)

Definition 3.5. Let GS = (V, E, σ, ψ) be a S-valued graph where (S, +, .) is a semiring

s , ψ s ) is a crisp graph with vertex
with canonical preorder . For any s ∈ S, Ms (G) = (σM M
s = {v ∈ V s
set σM M : s  σM (v)} and edge set ψM = {(vi , vj ) ∈ EM : s  ψM (vi , vj )}.
770 TWMS J. APP. AND ENG. MATH. V.13, N.2, 2023

Example 3.4. Let S be the semiring as in Example 2.4 and let M (GS ) is given by:
v1 (a) v2 (c) v1 (a) e21 (a) v2 (c)

e31 (a) e42 (c)

e32 (c)

v3 (c) v4 (c) v3 (c) e43 (c) v4 (c)

GS M (GS )

Suppose s = b. Then
b
σM = {v ∈ VM : b  σM (v)} = {v2 , v3 , v4 , e32 , e42 , e43 }
b
ψM = {(e, f ) ∈ EM : b  ψM (e, f )}
= {(v2 , e32 ), (e32 , v3 ), (v3 , e43 ), (e43 , v4 ), (e42 , v4 ), (v2 , e42 ), (e42 , e32 ), (e42 , e43 ), (e32 , e43 )}
Therefore the required crisp graph Mb (G) corresponding to M (GS ) is
v3

e32 e42

v2 e43 v4

Theorem 3.3. Let GS = (V, E, σ, ψ) be a S-valued graph. If M (H S ) is a S-subgraph of

M (GS ), then Ms (H) is a S-subgraph of Ms (G), for any s ∈ S.
Proof. Let GS = (V, E, σ, ψ) be a S-valued graph. Let M (H S ) = (PM , LM , τM , γM ) be
a S-subgraph of M (GS ) = (VM , EM , σM , ψM ) such that PM ⊂ VM , LM ⊂ EM , τM ⊂ σM
and γM ⊂ ψM . i.e., τM (v)  σM (v), for all v ∈ PM , and γM (vi , vj )  ψM (vi , vj ) for all
s , γ s ) and M (G) = (σ s , ψ s ), where
(vi , vj ) ∈ LM . Let s ∈ S, Ms (H) = (τM M s M M
s s
τM = {v ∈ PM : s  τM (v)}, γM = {(e, f ) ∈ LM : s  γM (e, f )}
s = {v ∈ V s
σM M : s  σM (v)} and ψM = {(e, f ) ∈ E : s  γM (e, f )}.
s
Let v ∈ τM ⇒ s  τM (v)  σM (v) ⇒ s  σM (v) ⇒ v ∈ σM s . Therefore τ s ⊂ σ s .
M M
Let (e, f ) ∈ γM s ⇒ s  γ (e, f )  ψ (e, f ) ⇒ s  ψ (e, f ) ⇒ (e, f ) ∈ ψ s . Therefore
M M M M
s ⊂ ψs .
γM M
Hence Ms (H) is a S-subgraph of Ms (G). 

4. Regularity of M (GS )
In this section, we study the regularity on M (GS ).
Lemma 4.1. If M (GS ) is vertex regular S-valued graph, then M (GS ) is edge regular
S-valued graph.
Proof. Since M (GS ) = (VM , EM , σM , ψM ) is vertex regular S-valued graph, σM (v) = a
for all v ∈ VM and for some a ∈ S. Let (u, v) ∈ EM be arbitrary. Then ψM (u, v) =
min{σM (u), σM (v)} = min{a, a} = a. This proves M (GS ) is an edge regular S-valued
graph. 
 A. TAMILSELVI, M. PONNI: MIDDLE GRAPH OF SEMIRING VALUED GRAPHS 771

Remark 4.1. Converse of above lemma is not true. The following M (GS ) is an edge
regular S-valued graph but not vertex regular S-valued graph.
v1 (a)
a a
e21 (a) e31 (a)
a
a a a e43 (a)
a
v2 (b) v3 (c) a v4 (a)

Lemma 4.2. M (GS ) is vertex regular S-valued graph if and only if GS is vertex regular
S-valued graph.
Proof. Assume M (GS ) is vertex regular S-valued graph. Then σM (v) = a, ∀v ∈ VM . In
particular, σ(v) = a, ∀v ∈ V . Therefore GS is vertex regular S-valued graph.
Conversely assume that GS = (V, E, σ, ψ) is a vertex regular S-valued graph, σ(v) = a
for all v ∈ V and for some a ∈ S. By lemma 2.1, GS is an edge regular S-valued graph and
ψ(vi , vj ) = a for all (vi , vj ) ∈ E. By definition 3.1, σM (v) = a for all v ∈ VM . Therefore
M (GS ) is vertex regular S-valued graph. 
Lemma 4.3. M (GS ) is edge regular S-valued graph if and only if GS is edge regular
S-valued graph.
Proof. Assume M (GS ) is edge regular S-valued graph. Then ψM (e, f ) = a, ∀(e, f ) ∈ EM .
By definition 3.1,
(
min{σ(e), ψ(f )} if e ∈ V, f ∈ VM \ V
ψM (e, f ) = min{σM (e), σM (f )} =
min{ψ(e), ψ(f )} if e, f ∈ VM \ V
By the hypothesis, we have min{σ(e), ψ(f )} = a, ∀e ∈ V, f ∈ VM \ V . Since e and f are
adjacent in M (GS ), f is an edge incident with e. So we have ψ(f )  σ(e). This implies
ψ(u, v) = a, ∀(u, v) ∈ E. Hence GS is an edge regular S-valued graph.
Conversely assume that GS is edge regular S-valued graph. Then ψ(u, v) = a, ∀(u, v) ∈
E and for some a ∈ S. Let (e, f ) ∈ EM , where e, f ∈ VM .
Case(i) If e ∈ VM \V, f ∈ VM \V , then ψM (e, f ) = min{σM (e), σM (f )} = min{ψ(e), ψ(f )} =
min{a, a} = a.
Case(ii) Let e ∈ V, f ∈ VM \ V. f is an edge incident with e, since e and f are adja-
cent in M (GS ). So we have ψ(f )  σ(e). Consider ψM (e, f ) = min{σM (e), σM (f )} =
min{σ(e), ψ(f )} = ψ(f ) = a.
In all cases, we have ψM (e, f ) = a. Hence M (GS ) is edge regular S-valued graph. 
Theorem 4.1. M (GS ) is S-regular if and only if GS is S-regular.
Proof. Assume M (GS ) is S- regular. Then σM (v) = a for all v ∈ VM and for some a ∈ S.
That is, σ(v) = a for all v ∈ V. Therefore GS is vertex regular S-valued graph. By lemma
2.1, GS is edge regular S-valued graph. Hence GS is S-regular.
Conversely if GS is S-regular graph, then σ(v) = a for all v ∈ V and by lemma 2.1,
( a for all (vi , vj ) ∈ E and for some a ∈ S. By definition 3.1,
ψ(vi , vj ) =
σ(v) for v ∈ V
σM (v) =
ψ(vi , vj ) for v = eji ∈ VM \ V
σM (v) = a for all v ∈ VM . This implies M (GS ) is vertex regular S- graph. By lemma 4.1,
M (GS ) is an edge regular S- graph. Hence M (GS ) is a S- regular graph. 
772 TWMS J. APP. AND ENG. MATH. V.13, N.2, 2023

References
[1] Hamada. T and Yoshimura. I, (1976), Traversability and Connectivity of the middle graph of a graph,
Discrete Mathematics, 14, pp. 247-255.
[2] Rajkumar. M., Jeyalakshmi. S. and Chandramouleeswaran. M., (2015) Semiring Valued Graphs, Inter-
national Journal of Math. Sci. and Engg. Appls., 9(3), pp. 141-152.
[3] Shriprakash. T.V.G. and Chandramouleeswaran. M, (2018), Line Graph of S-Valued Graphs, Interna-
tional Journal of Math. Sci. and Engg. Appls., 12(1), pp. 113-122.

Dr. A. Tamilselvi is working as an assistant professor at Ramanujan Institute for

Advanced Study in Mathematics, University of Madras, Chennai, Tamilnadu, India.
She completed her at the same university. She worked as an Assistant Professor in
Anna University for four years. Her research interest is combinatorial representation
theory, diagram algebras, algebraic graph theory.

M. Ponni is an M. Phil. scholar at Ramanujan Institute for Advanced Study in

Mathematics, University of Madras. She completed her MSc. degree at Bharathi-
dasan University. Her research interest is algebra and graph theory