JACODESMATH / ISSN 2148-838X

J. Algebra Comb. Discrete Appl.
2(2) • 95-109

Received: 17 October 2014; Accepted: 23 February 2015
DOI 10.13069/jacodesmath.39202

Journal of Algebra Combinatorics Discrete Structures and Applications

Graphical sequences of some family of induced
subgraphs

Research Article

S. Pirzada∗, Bilal A. Chat∗∗, Farooq A. Dar

Department of Mathematics, University of Kashmir, Hazratbal Srinagar-190006, India

Abstract: The subdivision graph S(G) of a graph G is the graph obtained by inserting a new vertex into every
edge of G. The Svertex or Sver join of the graph G1 with the graph G2, denoted by G1∨̇G2, is
obtained from S(G1) and G2 by joining all vertices of G1 with all vertices of G2. The Sedge or Sed
join of G1 and G2, denoted by G1∨̄G2, is obtained from S(G1) and G2 by joining all vertices of S(G1)
corresponding to the edges of G1 with all vertices of G2. In this paper, we obtain graphical sequences
of the family of induced subgraphs of SJ = G1 ∨ G2, Sver = G1∨̇G2 and Sed = G1∨̄G2. Also we
prove that the graphic sequence of Sed is potentially K4 −e-graphical.

2010 MSC: 05C07

Keywords: Graphical sequences, Subdivision graph, Join of graphs, Split graph

1. Introduction

Let G = (V (G),E(G)) be a simple graph with n vertices and m edges having vertex set V (G) =
{v1,v2, · · · ,vn}. The set of all non-increasing non-negative integer sequences π = (d1,d2, · · · ,dn) is
denoted by NSn. A sequence π ∈ NSn is said to be graphic if it is the degree sequence of a simple graph
G on n vertices, and such a graph G is called a realization of π. The set of all graphic sequences in
NSn is denoted by GSn. There are several famous results, Havel and Hakimi [6–8] and Erdös and Gallai
[2] which give necessary and sufficient conditions for a non-negative sequence π = (d1,d2, · · · ,dn) to be
the degree sequence of a simple graph G. A graphical sequence π is potentially H-graphical if there is
a realization of π containing H as a subgraph, while π is forcibly H graphical if every realization of π
contains H as a subgraph. If π has a realization in which the r + 1 vertices of largest degree induce a
clique, then π is said to be potentially Ar+1-graphic. We know that a graphic sequence π is potentially
Kk+1-graphic if and only if π is potentially Ak+1-graphic [10, 11]. The disjoint union of the graphs G1
and G2 is defined by G1

⋃
G2. If G1 = G2 = G, we abbreviate G1

⋃
G2 as 2G. Let Kk, Ck and Pk

respectively denote a complete graph on k vertices, a cycle on k vertices and a path on k + 1 vertices.

∗ E-mail: pirzadasd@kashmiruniversity.ac.in
∗∗ E-mail: bilalchat99@gmail.com

95



Graphical sequences

A sequence π = (d1,d2, · · · ,dn) is said to be potentially Kr+1- graphic if there is a realization G
of π containing Kr+1 as a subgraph. If π is a graphic sequence with a realization G containing H as a
subgraph, then in [4], it is shown that there is a realization G of π containing H with the vertices of H
having |V (H)| largest degree of π. In 2014 [1], Bu, Yan, X. Zhou and J. Zhou obtained Resistance distance
in the subdivision vertex join and edge join type of graphs. Also conditions for r-graphic sequences to
be potentially K(r)m+1-graphic can be seen in [12].

2. Definitions and preliminary results

In the simple graph G, let di be the degree of vi for 1 ≤ i ≤ n. Then π = (d1,d2, · · · ,dn) is the
degree sequence of G. We note that the vertices have been labelled so that π is in increasing order.
The degree sequence π = (d1,d2, · · · ,dn) is said to be potentially Ar+1-graphic if it has a realization
H = (V (H),E(H)), where V (H) = {u1,u2, · · · ,un} and the degree of ui is di for 1 ≤ i ≤ n, such that
the subgraph induced by {u1,u2, · · · ,ur+1} is Kr+1. For π = (d1,d2, · · · ,dn) ∈ NSn and 1 ≤ k ≤ n, let

π′ = (d1 − 1, · · · ,dk−1 − 1, · · · ,dk + 1 − 1,dk + 2, · · · ,dn), if dk ≥ k,
= (d1 − 1, · · · ,dk − 1, · · · ,dk + 1, · · · ,dk−1,dk+1,dn), if dk < k.

Denote π′k = (d
i′

1 ,d
i′

2 , · · · ,di
′

n−1) where 1 ≤ i′ ≤ n and di
′

1 ,d
i′

2 , · · · ,di
′

n−1 is a rearrangement of the n− 1
terms of π′. Then π′ is called the residual sequence obtained by laying off dk from π.

Gould, Jacobson and Lehel [4] obtained the following result.

Theorem 2.1. If π = (d1,d2, · · · ,dn) is the graphic sequence with a realization G containing H as a
subgraph, then there exists a realization G′ of π containing H as a subgraph so that the vertices of H
have the largest degrees of π.

Throughout this paper, we take π1 = (d11,d
1
2, · · · ,d1m) and π2 = (d21,d22, · · · ,d2n) respectively to be

the graphical sequence of the graphs G1 and G2. Let σ(π) = d1 + d2 + · · · + dn and dt in the graphic
sequence π means d occurs t-times.

The following definitions will be required for obtaining the main results.

Definition 2.2. The join of G1 and G2 is a graph SJ = G1 ∨ G2 with vertex set V (G1) ∪ V (G2) and
an edge set consisting of all edges of G1 and G2, together with the edges joining each vertex of G1 with
every vertex of G2.

Definition 2.3. The subdivision graph S(G) of a graph G is the graph obtained by inserting a new vertex
into every edge of G. Equivalently, each edge of G is replaced by a path of length 2. Figure 1 shows the
subdivision graph S(G) of the graph G. The vertices inserted are denoted by open circles.

D
D
D
D
D
D
D
D
D
D

@
@
@
@

@
@
@
@
@@
�

�
�

�
��

u

u
u

u

u u
u

u
e e
e ee

e

G
S(G)

Figure 1.

96



S. Pirzada, B. A. Chat, F. A. Dar

Definition 2.4. The subdivision vertex join of G1 onto G2, denoted by Sver = G1∨̇G2, is the graph
obtained from S(G1) ∪ G2 by joining every vertex of V (G1) to every vertex of V (G2). Figure 2 gives
Sver = K4∨̇K4.

@
@
@
@

u
u u

u

u
u

u
ue

e
e e e

e
��

��
��

��
��
�

Sver = K4∨̇K4

Figure 2.

Definition 2.5. Let G1 and G2 be two graphs, let S(G1) be the subdivision graph of G1 and let I(G1)
be the set of new inserted vertices of S(G1). The subdivision edge join of G1 and G2 denoted by Sed =
G1∨̄G2, is the graph obtained from S(G1)∪G2 by joining every vertex of I(G1) to every vertex of V (G2).
Figure 3 below illustrates this operation by taking Sed = K4∨̄K4.

@
@
@
@

u
u u

u

u
u

u
u

Sed = K4∨̄K4

e
e
e e e

e

Figure 3.

Definition 2.6. If the vertex set of a graph can be partitioned into a clique and an independent set, then
it is called a split graph [5]. Let Kr and Ks be complete graphs on r and s vertices. Clearly Kr ∨Ks is
one type of split graph on r + s vertices and is denoted by Sr,s.

Pirzada and Bilal [9] defined new types of graphical operations and obtained graphical sequences of
some derived graphs.

Definition 2.7. Let Kr and Ks be any two graphs. Let Kṙ be the subdivision graph of Kr and Ks be
the complement of Ks. The graphs

(
Bṙ,s

)
= Kṙ∨̇Ks is called the r-vertex sub-division-Sr,s-graph and the

graph
(
Br,s

)
= Kṙ∨Ks is called the r-edge sub-division-Sr,s-graph. These are illustrated in Figures 4, 5,

6 and 7 below by taking the graphs K4 and K2.

97



Graphical sequences

@
@
@
@
@
@@

u

u

u

u

u

u
K4 K2

Figure 4.

u

u u

ue
e eee

u

u
K4̇ K2

e

Figure 5.

In 2014, Pirzada and Bilal [9] proved the following assertion.

Theorem 2.8. If G1 is a realization of π1 = (d11, . . . ,d
1
m) containing Kp as a subgraph and G2 is a

realization of π2 = (d21, . . . ,d
2
n) containing Kq as a subgraph, then the degree sequence π = (d1, . . . ,dm+n)

of the join of G1 and G2 is Kp+q-graphic.

The purpose of this paper is to find the graphic sequence of the family of induced subgraphs of
SJ, Sver and Sed. We also give the characterization for a graphic sequence of Sed to be potentially
K4 −e-graphical.

Now we have the following observations.

Remark 2.9. Let Lr = Ka1,a2,··· ,ar and Mr = Kb1,b2,··· ,br respectively be the r-partite graphs on
r∑

i=1

ai

and
r∑

i=1

bi vertices. Let l1 =
r∑

i=1

ai and l′1 =
r∑

i=1

bi and define

l =

r∑
i=1

(
ai + bi

)
, m =

r∑
i=1

(
a2i + b

2
i

)
.

Clearly, the number of edges in Ka1,a2,··· ,ar = |ELr| =
(r2)∑

i,j=1,i6=j
aiaj and the number of edges

in Kb1,b2,··· ,br = |EMr| =
(r2)∑

i,j=1,i6=j
bibj.

Remark 2.10. Let cl2m be the circular ladder with 2m vertices, m ≥ 3. The circular ladder is the graph
formed by taking two copies of the cycle Cm with corresponding vertices from each copy of Cm being
adjacent. A ladder graph on 8 vertices is shown in Figure 8. Let (K2m − cl2m) be the graph obtained
from K2m by removing the edges of cl2m. For m ≥ 3, it can be easily seen that (K2m −cl2m) is a 2m−4
regular graph on 2m vertices and the number of edges in this graph being 2m(m− 2).

98



S. Pirzada, B. A. Chat, F. A. Dar

u

u u

u

u

u
e

e
e
e

e
e

(B4̇,2) = K4̇∨̇K2

Figure 6.

u

u u

u
ee

e
e

e

e
u

u
(B4̄,2) = K4̇∨̄K2

Figure 7.

Remark 2.11. In the split graph Sr,s, the number of vertices is r + s and number of edges is
r(r−1)

2
+ rs.

That is, |V (Sr,s)| = r + s and |E(Sr,s)| =
r(r−1)

2
+ rs. Figure 9 ilustrates S3,2 and S4,1.

Remark 2.12. If π1 and π2 respectively are the graphic sequences of G1 and G2, the graphic sequence
of Sver = G1∨̇G2 is π = (d11 + n,d12 + n, · · · ,d1m + n,d21 + m, · · · ,d2n + m, 2|E1|) and the graphic sequence
of Sed = G1∨̄G2 is π = (d11,d12, · · · ,d1m,d21 + |E1|, · · · ,d2n + |E1|, (2 + n)|E1|).

3. Main results

In the following result, we find the graphic sequence of the induced subgraph (K2m′−cl2m′)∨̇(K2n′−
cl2n′) of the graph Sver = G1∨̇G2.

Theorem 3.1. If π1 and π2 respectively are potentially (K2m′ − cl2m′) and (K2n′ − cl2n′)-graphic se-
quences, m′ ≥ 3, n′ ≥ 3, m ≥ 2m′, n ≥ 2n′, then the graphic sequence of (K2m′ −cl2m′)∨̇(K2n′ −cl2n′)
is
(
(2(m′ + n′ − 2))2(m

′+n′), 22m
′(m′−2)

)
.

Proof. By Remark 2.12 and Theorem 2.1, the graphic sequence of Sver is π = (d11 +n,d
1
2 +n, · · · ,d1m +

n,d21 + m, · · · ,d2n + m, 2|E1|). Now let π∗ be the graphic sequence of the induced subgraph (K2m′ −
cl2m′)∨̇(K2n′ − cl2n′) of Sver. By taking |E(K2m′ − cl2m′)| = 2m′(m′ − 2), we have

π∗ =
(
d1
′

1 + 2n
′,d1

′

2 + 2n
′, · · · ,d1

′

2m′ + 2n
′,d2

′

1 + 2m
′,d2

′

2 + 2m
′,

99



Graphical sequences

s s
s s

C4

r r
r s

C4

-

s s
s s

@
@

#
##

�
�

s

s s

s

cl8

Figure 8.

�
�
�
�
�

s
s s s

s s
s

s
s

s
v2 v3 v2 v3

S3,2 S4,1

v1
v1 v4

u1

u2

u1

Figure 9.

· · · ,d2
′

2n′ + 2m
′, 22m

′(m′−2))
= (2m′ − 4 + 2n′, 2m′ − 4 + 2n′, · · · , 2m′ − 4 + 2n′, 2n′ − 4 + 2m′,

· · · , 2n′ − 4 + 2m′, 22m
′(m′−2))

=
(
(2(m′ + n′ − 2))2

(m′+n′)
, 22m

′(m′−2)).
Corollary 3.2. If π1 and π2 are potentially (K2m′ − cl2m′)-graphic sequences, where m′ ≥ 3, m ≥
2m′, n ≥ 2m′, then the graphic sequence of the induced subgraph (K2m′ −cl2m′)∨̇(K2m′ −cl2m′) of Sver
is
(
(4(m′ − 1))4m

′
, 22m

′(m′−2)
)
and σ(π∗) = 4m′(5m′ − 6).

Proof. Put m′ = n′ in Theorem 3.1, we get

π∗ = (2m′ − 4 + 2m′, 2m′ − 4 + 2m′, · · · , 2m′ − 4 + 2m′, 2m′ − 4 + 2m′,

· · · , 2m′ − 4 + 2m′, 22m
′(m′−2))

=
(
(4(m′ − 1))4m

′
, 22m

′(m′−2))
Also σ(π∗) = 4m′(4(m′ − 1)) + 2m′(m′ − 2)2 = 4m′(5m′ − 6).

The following result shows that the graphic sequence π of Sed = G1∨̄G2 is potentially K4 − e-
graphical.

Theorem 3.3. If π1 and π2 respectively are potentially Kp1 and Kp2-graphic sequences, where m ≥
3, n ≥ 2, p1 ≤ m and p2 ≤ n, then the graphical sequence π of Sed is potentially K4 −e-graphical.

Proof. Let π1 and π2 respectively be potentially Kp1 and Kp2-graphic sequences, where m ≥ 3, n ≥
2, p1 ≤ m and p2 ≤ n. Let Sed = G1∨̄G2 and π be its graphic sequence. Then π =

(
d11,d

1
2, · · · ,d1m,d21 +

100



S. Pirzada, B. A. Chat, F. A. Dar

|E1|,d22 + |E1|, · · · ,d2n + |E1|). Clearly there are at-least three vertices and at least two edges in G1 and
there are at least two vertices and at least one edge in G2, since G1 and G2 are connected. Let vi,vj
and vk be any three vertices in G1 and ui and uj be any two vertices in G2. Since there are at least
two edges in G1 and at least one edge in G2, without loss of generality we take vivj,vjvk ∈ E(G1) and
uiuj ∈ E(G2). By construction, it can easily be seen that the graph G formed from G1 and G2 contains
a subgraph on u′i,u

′
j,ui and uj vertices (where u

′
i and u

′
j are the two inserted vertices in vivj and vjvk

of G1) which is K4 −e. Thus π is potentially K4 −e graphical.

Now we obtain the graphic sequence of the induced subgraph Sr1,s1∨̄Sr2,s2 of Sed = G1∨̄G2.
Theorem 3.4. If π1 and π2 respectively are potentially Sr1,s1 and Sr2,s2-graphic, then the graphic se-
quence of the induced subgraph Sr1,s1∨̄Sr2,s2 of Sed is

π∗ =

((
2(r2 + s2 − 1) + r1(2s1 + r1 − 1)

2

)r2
,

(
2r2 + r1(2s1 + r1 − 1)

2

)s2
,

(2 + r2 + s2)
r1(2s1+r1−1)

2 , (r1 + s1 − 1)r1,rs11
)
.

Proof. Let π∗ be the graphic sequence of the induced subgraph Sr1,s1∨̄Sr2,s2 of Sed. By Remark 2.11
and Theorem 2.1, we have

π∗ =
(
d1
′

1 ,d
1′

2 , · · · ,d
1′

r1
,d1

′

r1+1
,d1

′

r1+2
, · · · ,d1

′

r1+s1
,d2

′

1 ,d
2′

2 , · · · ,d
2′

r2+s2
, (2 + r2 + s2)

|E(Sr1,s1 )|
)

=
(
r1 + s1 − 1,r1 + s1 − 1, · · · ,r1 + s1 − 1,r1,r1, · · · ,r1,r2 + s2 − 1 +

r1(r1 − 1)
2

+ (r1s1),

· · · ,r2 + s2 − 1 +
r1(r1 − 1)

2
+ (r1s1), (r2 + |E(Sr1,s1 )|),

· · · , (r2 + |E(Sr1,s1 )|), (2 + r2 + s2)
|E(Sr1,s1 )|

)
=

(
(r1 + s1 − 1)r1,rs11 ,

(
2(r2 + s2 − 1) + r1(r1 − 1) + 2r1s1

2

)r2
,(

2r2 + r1(r1 − 1) + 2r1s1
2

)s2
, (2 + r2 + s2)

r1(r1−1)+2r1s1
2

)
=

((
2(r2 + s2 − 1) + r1(2s1 + r1 − 1)

2

)r2
,

(
2r2 + r1(2s1 + r1 − 1)

2

)s2
,

(2 + r2 + s2)
r1(2s1+r1−1)

2 , (r1 + s1 − 1)r1,rs11
)
.

Next we obtain the graphic sequence of the induced subgraph Kp1∨̄Kp2 and Sr2,s2∨̄Sr1,s1 of Sed =
G1∨̄G2.
Theorem 3.5. If π1 and π2 respectively are potentially Kp1 and Kp2-graphic, then the graphic sequence
of the induced subgraph Kp1∨̄Kp2 of Sed is

π∗ =

(
(p1 − 1)p1,

(
p1(p1 − 1) + 2(p2 − 1)

2

)p2
, (2 + p2)

p1(p1−1)
2

)
,

where p1 ≥ 2, p2 ≥ 1.

Proof. By Theorem 2.1, in the graphic sequence of the induced subgraph Kp1∨̄Kp1 of Sed, we have
d1
′

1 = p1 − 1,d1
′

2 = p1 − 1, · · · ,d1
′

p1
= p1 − 1,d2

′

1 = p2 − 1, · · · ,d2
′

p2
= p2 − 1, |E(KP1 )| =

p1(p1−1)
2

and
n = p2. Thus the graphic sequence π∗ of the induced subgraph Kp1∨̄Kp1 of Sed is

π∗ =

(
p1 − 1, · · · ,p1 − 1,p2 − 1 +

p1(p1 − 1)
2

, · · · ,p2 − 1 +
p1(p1 − 1)

2
, (2 + p2)

p1(p1−1)
2

)

101



Graphical sequences

=

(
(p1 − 1)p1,

(
p1(p1 − 1) + 2(p2 − 1)

2

)p2
, (2 + p2)

p1(p1−1)
2

)
.

Theorem 3.6. If π1 and π2 respectively are potentially (K2m′ −cl2m′) and (K2n′ −cl2n′)-graphic, where
m′,n′ ≥ 3, then the graphic sequence of the induced subgraph (K2m′−cl2m′)∨̄(K2n′−cl2n′) of Sed = G1∨̄G2
is

π∗ =

((
2(m′ − 2)

)2m′
,
(
2(n′ + m′

2
) − 4(n′ + 1)

)2n′
, (2(1 + n′))2m

′(m′−2)
)
.

Proof. Let π∗ is the graphic sequence of (K2m′−cl2m′)∨̄(K2n′−cl2n′). Then by Theorem 2.1, we have
d1
′

1 = 2m
′−4 = d1

′

2 = d
1′

2m′,d
2′

1 + |E((K2m′ −cl2m′))| = d2
′

2 + |E((K2m′ −cl2m′))|, · · · ,d2
′

2n′ + |E((K2m′ −
cl2m′))| = 2n′−4 + (2m′−4)m′. Thus the graphic sequence π∗ of the required induced subgraph (K2m′−
cl2m′)∨̄(K2n′−cl2n′) of Sed becomes

((
2(m′−2)

)2m′
,
(
2(n′+m′

2
)−4(n′+1)

)2n′
, (2(1+n′))2m

′(m′−2)
)
.

Theorem 3.7. If π1 and π2 respectively are potentially Lr = Ka1,a2,··· ,ar and Mr = Kb1,b2,··· ,br graphic,
then
(a) the graphic sequence of induced subgraph Lr∨̇Mr of Sver = G1∨̇G2 is

π∗ =

((
l−a1

)a1
,
(
l−a2

)a2
, · · · ,

(
l−ar

)ar
,
(
l− b1

)b1
, · · · ,

(
l− br

)br
, 2(

r
2)

)
,

where
(
r
2

)
is the number of combinations of a1,a2, · · · ,ar taken two at a time.

(b) σ(π∗) =
∑r

i=1

(
ai(l−ai) + bi(l− bi)

)
+ 2
(
r
2

)
.

Proof. Let π1 and π2 respectively be potentially Lr = Ka1,a2,··· ,ar and Mr = Kb1,b2,··· ,br graphic. So
clearly the graphs G1 and G2 contain respectively Lr and Mr as a subgraph. Let Sver = G1∨̇G2 be the
graph obtained by sub-division vertex join of graphs and let π be the graphic sequence of Sver. We have

π =
(
d11 + n,d

1
2 + n, · · · ,d

1
m + n,d

2
1 + m, · · · ,d

2
n + m, 2

|E1|
)

(1)

where |E1| is the size of G1.
Let π∗ be the graphic sequence of the induced subgraph Lr∨̇Mr of Sver. To prove (a) we use

induction on r. For r = 1, the result is obvious. For r = 2, we have G′2 = Ka1,a2∨̇Kb1,b2. Let π′2 be the
graphic sequence of G′2. Therefore, by Remark 2.12, we have

π′2 =

((
a2 + b1 + b2

)a1
,
(
a1 + b1 + b2

)a2
,
(
b2 + a1 + a2

)b1
,

(
b1 + a1 + a2

)b2
, 2

(22)∑
i,j=1,i 6=j

aiaj
)

=

(( 2∑
i=1

(ai + bi) −a1
)a1

,
( 2∑

i=1

(ai + bi) −a2
)a2

,
( 2∑

i=1

(ai + bi) − b1
)b1

,

( 2∑
i=1

(ai + bi) − b2
)b2

, 2

(22)∑
i,j=1,i 6=j

aiaj
)

=

(( 2∑
i=1

(ai + bi) −ai
)ai

,
( 2∑

i=1

(ai + bi) − bi
)bi

, 2a1a2

)
.

102



S. Pirzada, B. A. Chat, F. A. Dar

This proves the result for r = 2. Assume that the result is true for r = k − 1. Therefore, we have

G′k−1 = Ka1,a2,··· ,ak−1∨̇Kb1,b2,··· ,bk−1

and let π′k−1 be the graphic sequence of G
′
k−1. Then we have

π′k−1 =

((k−1∑
i=1

(ai + bi) −a1
)a1

, · · · ,
(k−1∑

i=1

(ai + bi) −ak−1
)ak−1

,

(k−1∑
i=1

(ai + bi) − b1
)b1

, · · · ,
(k−1∑

i=1

(ai + bi) − bk−1
)bk−1

, 2

(k−12 )∑
i,j,i6=j

aiaj
)
. (2)

Now, for r = k, we have

G′k = Ka1,a2,··· ,ak−1,ak∨̇Kb1,b2,··· ,bk−1,bk
= KR,ak∨̇KS,bk,

where R = a1,a2, · · · ,ak−1 and S = b1,b2, · · · ,bk−1.
Since the result is proved for all r = k − 1 and using the fact that the result is proved for each pair

and since the result is already proved for r = 2, it follows by induction hypothesis that the result holds
for r = k also. That is,

π∗ = π′k =

((
ak + bk +

k−1∑
i=1

(ai + bi) −a1
)a1

, · · · ,
(
ak + bk +

k−1∑
i=1

(ai + bi) −ak−1
)ak−1

,

(
ak + bk +

k∑
i=1

(ai + bi) −ak
)ak

,
(
ak + bk +

k−1∑
i=1

(ai + bi) − b1
)b1

, · · · ,

(
ak + bk +

k−1∑
i=1

(ai + bi) − bk−1
)bk−1

,
(
ak + bk +

k−1∑
i=1

(ai + bi) − bk
)bk

, 2

( (k−12 )∑
i,j,i6=j

aiaj +
k−1∑
i=1

akai

))

=

((
l−a1

)a1
,
(
l−a2

)a2
, · · · ,

(
l−ar

)ar
,
(
l− b1

)b1
, · · · ,

(
l− br

)br
, 2(

r
2)

)
.

This proves part (a).

Now we have

σ(π∗) = a1(l−a1) + · · · + ar(l−ar) + b1(l− b1) + · · · + br(l− br) + 2

(
(k2)∑

i,j=1,i 6=j
aiaj

)

=

r∑
i=1

(
ai(l−ai) + bi(l− bi)

)
+ 2

(
r

2

)
.

Theorem 3.8. If π1 and π2 respectively are potentially Lr = Ka1,a2,··· ,ar and Mr = Kb1,b2,··· ,br -graphic,
then the graphic sequence of the induced subgraph L∨̄M of Sed is

π∗ =

((
(l1 −ai)ai, (l′1 + |EL|− bi

)bi)r
i=1

, (2 + l′1)
|EL|

)

and σ(π∗) = l21 + l
′
1
2 −m + 2(1 + l′1)|EL|, where l1 =

r∑
i=1

ai and l′1 =
r∑

i=1

bi.

103



Graphical sequences

Proof. Let π1 and π2 respectively be potentially Lr and Mr graphic. Then the graphs G1 and G2
contain Lr and Mr as a subgraph. Let Sed = G1∨̄G2 be the graph obtained by sub-division edge join of
graphs and let π be the graphic sequence of Sed. Then, we have

π =
(
d11,d

1
2, · · · ,d

1
m,d

2
1 + |E1|, · · · ,d

2
n + |E1|, (2 + n)

|E1|
)

(3)

where |E1| is the size of G1. Let π∗ be the graphic sequence of the induced subgraph Lr∨̄Mr of Sed. To
prove the result we use induction on r. For r = 1, the result follows by Theorem 3.5. For r = 2, we have
G′2 = Ka1,a2∨̄Kb1,b2. Let π′2 be the graphic sequence of G′2. Therefore, by Remark 2.12, we have

π′2 =

(
aa12 ,a

a2
1 ,
(
a1a2 + b2

)b1
,
(
a1a2 + b1

)b2
,
(

2 + b1 + b2

)a1a2)

=

(( 2∑
i=1

ai −a1
)a1

,
( 2∑

i=1

ai −a2
)a2

,
( (22)∑

i,j,i 6=j

aiaj + b2

)b1
,

( 2C2∑
i,j,i 6=j

aiaj + b1

)b2
,
(

2 +

2∑
i=1

bi

) (22)∑
i,j,i6=j

aiaj
)

=

((
l∗1 −a1

)a1
,
(
l∗1 −a2

)a2
,
(
|E(L2)| + b2

)b1
,
(
|E(L2)| + b1

)b2
,
(

2 + l′1

)|E(L2)|)

=

(((
l∗1 −ai

)ai
,
(
|E(L2)| + l′1 − bi

)bi)2
i=1

,
(

2 + l′1

)|E(L2)|)

where l∗1 =
2∑

i=1

ai and |E(L2)| = |E(Ka1,a2 )| = a1a2. This proves the result for r = 2. Assume that the

result is true for r = k − 1, therefore, we have

G′k−1 = Ka1,a2,··· ,ak−1∨̄Kb1,b2,··· ,bk−1.

Let π′k−1 be the graphic sequence of G
′
k−1, then we have

π′k−1 =

(((
l∗∗1 −ai

)
,
(
|E(Lk−1)| + l′1 − bi

)bi)k−1
i=1

,
(

2 + l′1

)|E(Lk−1)|)

where l∗∗1 =
k−1∑
i=1

ai.

Now we show that the result holds for r = k. We have

G′k = Ka1,a2,··· ,ak−1,ak∨̄Kb1,b2,··· ,bk−1,bk
= KR,ak∨̄KS,bk

where R = a1,a2, · · · ,ak−1 and S = b1,b2, · · · ,bk−1.
Since the result is proved for every r = k − 1 and using the fact that the result is proved for each

pair and since the result is already proved for r = 2, it follows by induction hypothesis that the result
holds for r = k also. That is,

π∗ = π′k =

((
ak +

k−1∑
i=1

ai −a1
)a1

,
(
ak +

k−1∑
i=1

ai −a2
)a2

, · · · ,
(
ak +

k−1∑
i=1

ai −ak
)ak

,

104



S. Pirzada, B. A. Chat, F. A. Dar

(
aka1 + aka2 + · · · + akak−1 +

(k−12 )∑
i,j,i 6=j

aiaj + b2

)b1
,

(
aka1 + aka2 + · · · + akak−1 +

(k−12 )∑
i,j,i 6=j

aiaj + b2

)b2
, · · · ,

(
aka1 + aka2 + · · · + akak−1 +

(k−12 )∑
i,j,i 6=j

aiaj + bk

)bk
,
(

2 + bk +

k−1∑
i=1

bi

)( (k−12 )∑
i,j,i6=j

aiaj +
k−1∑
i=1

akai

))

=

(((
l1 −ai

)ai
,
(
|ELr| + l

′
1 − b1

)bi)k
i=1

,
(
2 + l′1

)|ELr|)
Also, we have

σ(π∗) = a1(l1 −a1) + · · · + ar(l1 −ar) + b1(l′1 + |EL|− b1)

+ · · · + br(l′1 + |EL|− br) +
kC2∑

i,j=1,i6=j

aiaj(2 + 2l
′
1)

= l21 + l
′
1
2 −m + 2(1 + l′1)|EL|.

This completes the proof.

Let G1 and G2 be any two graphs. Let SJ = G1 ∨ G2 and let SJ∗ =
(
Bṁ1,n1

)
∨
(
Bṁ2,n2

)
be the

induced subgraph of SJ and let π∗ be the graphic sequence of S∗J.

Theorem 3.9. If π1 and π2 respectively be potentially Bṁ1,n1 and Bṁ2,n2, then
(a) the graphic sequence π∗ of induced subgraph

(
Bṁ1,n1

)
∨
(
Bṁ2,n2

)
of SJ is

π∗ =

((
A + |E(Km2 )|− 1

)m1
,
(
A + |E(Km1 )|− 1

)m2
,
(
A + |E(Km2 )| + 2 − (m1 + n1)

)|E(Km1 )|
,

(
A + |E(Km1 )| + 2 − (m2 + n2)

)|E(Km2 )|
,
(
A + |E(Km2 )|−n1)

)n1
,
(
A + |E(Km1 )|−n2)

)n2)
and

(b) σ(π∗) = A
(
A +

2∑
i=1

|E(Kmi )|
)

+

2∏
i,j=1,i6=j

(
mi + ni

)
|E(Kmj )|

+ 2

(
|E(Km1 )||E(Km2 )| +

2∑
i

|E(Kmi )|
)
−

2∑
i=1

(
mi +

(
mi + ni

)
|E(Kmi )|

)
−

2∑
i=1

n2i .

where A =
2∑

i=1

(mi + ni) and |E(Kmi )| =
mi(mi−1)

2
.

Proof. The graphic sequence of Bṁ1,n1 and Bṁ2,n2 respectively are

π′1 =

((
m1 + n1 − 1

)m1
, 2

m1(m1−1)
2 ,mn11

)
(4)

π′2 =

((
m2 + n2 − 1

)m2
, 2

m2(m2−1)
2 ,mn22

)
(5)

105



Graphical sequences

Clearly from (4) and (5), the graphic sequence of S∗J is

π∗ =

((
m1 + m2 + n1 + n2 − 1 +

m2(m2 − 1)
2

)m1
,
(
m1 + m2 + n1 + n2 − 1 +

m1(m1 − 1)
2

)m2
,

(
2 + m2 + n2 +

m2(m2 − 1)
2

)m1(m1−1)
2

,
(

2 + m1 + n1 +
m1(m1 − 1)

2

)m2(m2−1)
2

(
m1 + m2 + n2 +

m2(m2 − 1)
2

)n1
,
(
m1 + m2 + n1 +

m1(m1 − 1)
2

)n2)

=

((
A + |E(Km2 )|− 1

)m1
,
(
A + |E(Km1 )|− 1

)m2
,
(
A + |E(Km2 )| + 2 − (m1 + n1)

)|E(Km1 )|
,

(
A + |E(Km1 )| + 2 − (m2 + n2)

)|E(Km2 )|
,
(
A + |E(Km2 )|−n1)

)n1
,
(
A + |E(Km1 )|−n2)

)n2)

This proves (a).

Further

σ(π∗) = m1(A + |E(Km2 )|− 1) + m2(A + |E(Km1|− 1)
+ |E(Km1 )|

(
A + |E(Km2 )| + 2 −m1 −n1

)
+ |E(Km2 )|

(
A + |E(Km1 )| + 2 −m2 −n2

)
+ n1

(
A + |E(Km2|−n1

)
+ n2

(
A + |E(Km1 )|−n2

)
= m1A + m1|E(Km2 )|−m1 + |E(Km2 )|A + m2|E(Km1 )|−m2

+ |E(Km1 )|A + |E(Km1 )||E(Km2 )| + 2|E(Km1 )|− |E(Km1 )|m1 −n1|E(Km1 )|
+ A|E(Km2 )| + |E(Km2 )||E(Km1 )| + 2|E(Km2 )|−m2|E(Km2 )|−n2|E(Km2 )|
+ n1A + n1|E(Km2 )|−n

2
1 + n2A + n2|E(Km1 )|−n

2
2

= (m1 + n1 + m2 + n2)A +
(
|E(Km1 )| + |E(Km2 )|

)
A + m1|E(Km2 )|

+ m2|E(Km1 )| + n2|E(Km1 )| + n1|E(Km2 )|−m1|E(Km1 )|−n1|E(Km1 )|
−m2|E(Km2 )|−n2|E(Km2 )|− (m1 + m2)
+ 2(|E(Km1 )||E(Km2 )|) + 2

(
|E(Km1 )| + |E(Km1 )|

)
− (n21 + n

2
2)

= A2 + A

2∑
i=1

|E(Kmi )| +
2∏

i,j=1,i6=j

mi|E(Kmj )| +
2∏

i,j=1,i6=j

ni|E(Kmj )|

−
2∑

i=1

(mi + ni)|E(Kmi )|−
2∑

i=1

mi + 2
(
|E(Km1 )||E(Km2 )| +

2∑
i=1

|E(Kmi )|
)
−

2∑
i=1

n2i

= A
(
A +

2∑
i=1

|E(Kmi )|
)

+

2∏
i,j=1,i6=j

(
mi + ni

)
|E(Kmj )|

+ 2

(
|E(Km1 )||E(Km2 )| +

2∑
i

|E(Kmi )|
)
−

2∑
i=1

(
mi +

(
mi + ni

)
|E(Kmi )|

)
−

2∑
i=1

n2i .

which proves (b).

Let G1 and G2 be two graphs. Let SJ = G1 ∨G2 and let S∗∗J = (Bm̄1,n1 ) ∨ (Bm̄2,n2 ) be the induced
subgraph of SJ and let π∗∗ be the graphic sequence of S∗∗J .

106



S. Pirzada, B. A. Chat, F. A. Dar

Theorem 3.10. If π1 and π2 respectively are potentially
(
Bm̄1,n1

)
and

(
Bm̄2,n2

)
, then the graphic

sequence of induced subgraph
(
Bm̄1,n1

)
∨
(
Bm̄1,n1

)
of SJ is

π∗∗ =

((
A + |E(Km2 )|− (n1 + 1)

)m1
,
(
A + |E(Km2| + 2 −m1

)|E(Km1|
,

(
A +

2∑
i=1

|E(Kmi )|− (m1 + n1)
)n1

,
(
A + |E(Km1|− (n2 + 1)

)m2
(
A + |E(Km1| + 2 −m2

)|(Km2|
,
(
A +

2∑
i=1

|E(Kmi )|− (m2 + n2)
)n2)

.

and

σ(π∗∗) =A
(
A +

2∑
i=1

|E(Kmi )|
)

+

2∏
i,j=1,i6=j

(mi + ni)|E(Kmj )| +
2∏

i,j=1,i6=j

|E(Kmi )||E(Kmj )|

+

2∑
i=1

(2 + ni)|E(Kmi )|−
2∑

i=1

(
2ni + 1 + |E(Kmi )|

)
mi −

2∑
i=1

n2i .

Proof. The graphic sequence of Bm̄1,n1 and Bm̄2,n2 respectively are

π′1 =

((
m1 − 1

)m1
,
(m1(m1 − 1)

2

)n1
, (2 + n1)

m1(m1−1)
2

)
(6)

π′2 =

((
m2 − 1

)m2
,
(m2(m2 − 1)

2

)n2
, (2 + n2)

m2(m2−1)
2

)
. (7)

Then by (6), (7) and by Definition 2.2, we have

π∗∗ =

((
m1 − 1 + m2 + n2 +

m2(m2 − 1)
2

)m1
,
(
m2 − 1 + m1 + n1 +

m1(m1 − 1)
2

)m2
,

(m1(m1 − 1)
2

+ m2 + n2 +
m2(m2 − 1)

2

)n1
,
(m2(m2 − 1)

2
+ m1 + n1 +

m1(m1 − 1)
2

)n2
,

(
2 + n1 + m2 + n2 +

m2(m2 − 1)
2

)m1(m1−1)
2

,
(

2 + n2 + m1 + n1 +
m1(m1 − 1)

2

)m2(m2−1)
2

)

=

((
A + |E(Km2 )|− (n1 + 1)

)m1
,
(
A + |E(Km2| + 2 −m1)

)|E(Km1|
,

(
A +

2∑
i=1

|E(Kmi )|− (m1 + n1)
)n1

,
(
A + |E(Km1|− (n2 + 1)

)m2
(
A + |E(Km1| + 2 −m2

)|(Km2|
,
(
A +

2∑
i=1

|E(Kmi )|− (m2 + n2)
)n2)

.

Further

σ(π∗∗) =

((
A + |E(Km2 )|− (n1 + 1)

)m1
+
(
A + |E(Km2|2 −m1

)|E(Km1|
+

+
(
A +

2∑
i=1

|E(Kmi )|− (m1 + n1)
)n1

+
(
A + |E(Km1|− (n2 + 1)

)m2

107



Graphical sequences

(
A + |E(Km1| + 2 −m2

)|(Km2|
+
(
A +

2∑
i=1

|E(Kmi )|− (m2 + n2)
)n2)

.

= m1
(
A + |E(Km2 )|−n1 − 1

)
+ |E(Km1 )|

(
A + |E(Km2 )| + 2 −m1

)
+

n1
(
A + |E(Km1 )| + |E(Km2 )|−m1 −n1

)
+ m2

(
A + |E(Km1 )|−n2 − 1

)
+

|E(Km2 )|
(
A + |E(Km1 )| + 2 −m2

)
+ n2

(
A + |E(Km1 )| + |E(Km2 )|−m2 −n2

)
= m1A + m1|E(Km2 )|−n1m1 −m1 + |E(Km1 )|A + |E(Km1 )||E(Km2 )| + 2|E(Km1 )|
− |E(Km1 )|m1 + n1A + n1|E(Km1 )| + n1|E(Km2 )|−n1m1 −n

2
1 + m2A + m2|E(Km1 )|

−m2n2 −m2 + |E(Km2 )|A + |E(Km2 )||E(Km1 )| + 2|E(Km2 )|− |E(Km2 )|m2
+ n2A + n2|E(Km2 )|−n2m2 −n

2
2 + n2|E(Km1 )|

= (m1 + n1 + m2 + n2)A +
(
|E(Km1 )| + |E(Km2 )|

)
A + m1|E(Km2 )|

+ m2|E(Km1 )| + n1|E(Km1 )| + n2|E(Km2 )| + |E(Km1 )||E(Km2 )|
+ |E(Km2 )||E(Km1 )| + 2(|E(Km1 )| + |E(Km2 )|) + n1|E(Km2 )|
+ n2|E(Km1 )|− 2n1m1 − 2n2m2 − (m1 + m2)
−
(
|E(Km1 )|m1 + |E(Km2 )|m2

)
= A2 + A

2∑
i=1

|E(Kmi )| +
2∏

i,j=1,i6=j

mi|E(Kmj )| +
2∏

i,j=1,i6=j

ni|E(Kmj )|

+

2∏
i,j=1,i6=j

|E(Kmi )||E(Kmj )| + 2
2∑

i=1

|E(Kmi )| +
2∑

i=1

ni|E(Kmi )|

− 2
2∑

i=1

nimi −
2∑

i=1

mi −
2∑

i=1

|E(Kmi )|mi −
2∑

i=1

n2i

= A
(
A +

2∑
i=1

|E(Kmi )|
)

+

2∏
i,j=1,i6=j

(mi + ni)|E(Kmj )| +
2∑

i=1

(2 + ni)|E(Kmi )|

−
2∑

i=1

(
2ni + 1 + |E(Kmi )|

)
mi −

2∑
i=1

n2i .

This completes the proof.

Acknowledgements: The authors are grateful to the anonymous referee for his useful comments
and suggestions which improved the presentation of the paper.

References

[1] C. Bu, B. Yan, X. Zhou, J. Zhou, Resistance distance in subdivision-vertex join and subdivision-edge
join of graphs, Linear Algebria and its Applications, 458, 454-462, 2014.

[2] P. Erdős, T. Gallai, Graphs with prescribed degrees, (in Hungarian) Matemoutiki Lapor, 11, 264-274,
1960.

[3] D. R. Fulkerson, A. J. Hoffman, M. H. McAndrew, Some properties of graphs with multiple edges,
Canad. J. Math., 17, 166-177, 1965.

108



S. Pirzada, B. A. Chat, F. A. Dar

[4] R. J. Gould, M. S. Jacobson, J. Lehel, Potentially G-graphical degree sequences, in Combinatorics,
Graph Theory and Algorithms, vol. 2, (Y. Alavi et al., eds.), New Issues Press, Kalamazoo MI,
451-460, 1999.

[5] J. L. Gross, J. Yellen, P. Zhang, Handbook of graph theory, CRC Press, Boca Raton, FL, 2013.
[6] S. L. Hakimi, On the realizability of a set of integers as degrees of the vertices of a graph, J. SIAM

Appl. Math., 10, 496-506, 1962.
[7] V. Havel, A Remark on the existance of finite graphs, (Czech) Casopis Pest. Mat. 80, 477-480, 1955.
[8] S. Pirzada, An introduction to graph theory, Universities Press, Orient Blackswan, India, 2012.
[9] S. Pirzada, B. A. Chat, Potentially graphic sequences of split graphs, Kragujevac J. Math 38(1),

73-81, 2014.
[10] A. R. Rao, An Erdos-Gallai type result on the clique number of a realization of a degree sequence,

Preprint.
[11] A. R. Rao, The clique number of a graph with a given degree sequence, Proc. Symposium on Graph

Theory (ed. A. R. Rao), Macmillan and Co. India Ltd, I.S.I. Lecture Notes Series, 4, 251-267, 1979.
[12] J. H. Yin, Conditions for r-graphic sequences to be potentially K(r)m+1-graphic, Disc. Math., 309,

6271-6276, 2009.

109


	Introduction
	Definitions and preliminary results
	Main results
	References