Electronic Journal of Graph Theory and Applications 14 .
, 215Ae230 Some properties of stepwise irregular graphs Somnath Beraa .
Prithwineel Paulb .
Subramanianc Department of Mathematics.
School of Advanced Sciences.
Vellore Institute of Technology.
Chennai.
India b Department of Computer Science and Engineering.
Centre of Excellence for Quantum Computing.
Institute of Engineering & Management.
University of Engineering & Management.
Kolkata.
India c Department of Mathematics.
Computer Science and Engineering.
Liverpool Hope University.
UK bera@vit.
in, prithwineel.
paul@iem.
in, kgsmani1948@gmail.
Abstract Graphs in which the absolute difference between the degrees of any two adjacent vertices is exactly one, are called stepwise irregular (SI) graphs.
We establish several properties of SI graphs.
particular, we show that SI graphs of different order and cyclomatic numbers can be constructed from an SI graph with a vertex of degree 1 or 2.
Necessary conditions and sufficient conditions for a degree sequence to be SI graphic are obtained.
Moreover, a necessary condition comparing the sum of the terms of a partition of SI graph and its conjugate partition is obtained.
Properties of SI graphs under certain elementary graph operations are also investigated.
Keywords: graph irregularity, stepwise irregular graph.
Albertson index, partition Mathematics Subject Classification : 05C76 DOI: 10.
5614/ejgta.
Introduction The study of irregularity of a graph has been an important direction of research in graph theory.
In fact there are several works .
, 2, 8, 13, 15, .
investigating irregularity measures of a graph.
Also, irregularity of graphs has been widely used for analyzing topological structures of deterministic and random networks occurring in chemistry, bioinformatics and in social networks .
, .
this work we are concerned with an interesting class of irregular graphs, called step-wise irregular Received: 2 May 2020.
Revised: 18 January 2026.
Accepted: 1 March 2026 Some properties of stepwise irregular graphs Bera.
Paul.
Subramanian graphs introduced by Gutman in .
Unless mentioned otherwise, we consider only simple connected graphs G = G(V.
E) with the vertex set V (G) = V and edge set E(G) = E.
The order of a graph G is the cardinality |V (G)| of the vertex set of G.
The neighbourhood nbd.
of a vertex v in G is the set of vertices adjacent to v and the degree dG .
of the vertex v is the cardinality .
| of the neighbourhood of v.
The maximum and minimum degrees of the vertices in G are denoted by OI(G) and (G) respectively.
The degree sequence d(G) .
r simply .
of a graph G is the sequence of degrees of all the vertices in G arranged in decreasing order.
A sequence of numbers is said to be a graphic sequence if there exists a graph having the sequence as its degree sequence.
A path of length .
Oe .
with n vertices is denoted by Pn .
A graph is said to be regular if all its vertices are of the same degree.
it is called irregular.
A connected graph is called a tree if it has no cycles.
The imbalance of an edge uv in a graph G, defined by Albertson .
, is given by .
G .
Oe dG .
Based on this notion, a widely investigated irregularity measure, called irregularity of a graph G, .
lso named Albertson index in .
), is given by irr(G) = .
G .
Oe dG .
uvOOE(G) Also, among many degree based topological graph indices, the first Zagreb index
M1 (G) =
dG .
2 vOOV (G) and the second Zagreb index
M2 (G) =
dG .
dG .
uvOOE(G) are two popular indices .
, 7, 10, .
The cyclomatic number of a connected graph G of order n and with p edges, is (G) = p Oe n 1.
A tree has cyclomatic number zero.
The graphs with cyclomatic numbers 1, 2, 3, 4 are respectively called unicyclic, bicyclic, tricyclic and tetracyclic The graphs with the imbalance of every edge exactly one, are called stepwise irregular (SI) graphs in .
In other words, in a SI graph G, for every edge uv OO G, .
G .
Oe dG .
| = 1.
Several basic properties of these graphs have been obtained in .
A graphic sequence is called SI if it is the degree sequence of an SI graph.
A tree which is SI is called an SI tree.
Gutman .
has mainly focused on establishing various results relating to the order of different kinds of SI graph, besides obtaining certain basic properties.
In this work, we investigate and establish many other properties of stepwise irregular graphs.
The existence of stepwise irregular graphs having different cyclomatic numbers is shown, given a stepwise irregular graph with at least one vertex of degree 1 or 2.
A characterization on the order of vertices of a tricyclic SI graph is provided using known results.
We also show that every integer in the interval [(G).
OI(G)] must be the degree of some vertex in an SI graph G.
Moreover, necessary conditions and sufficient conditions for a degree sequence to be SI graphic are obtained.
A relationship between the sum of the Some properties of stepwise irregular graphs Bera.
Paul.
Subramanian terms of a SI graphic sequence and its conjugate is also obtained.
Finally, we show that stepwise irregular graphs are not closed under certain graph operations such as edge deletion, vertex deletion, complementation and others.
The subdivision and line graph of an SI graph are in general not SI but the conditions under which these graphs become SI are investigated.
The paper is organized as follows: First we recall certain known results on SI graphs in Section 2 while in Section 3 several properties of SI graphs are obtained besides showing the existence of SI graphs.
Necessary condition as well as sufficient condition for a degree sequence to be SI graphic are derived in Section 4.
Also a necessary condition comparing the sum of the terms of a partition of SI graphs and its conjugate is obtained.
Finally, properties of SI graphs under certain elementary graph operations are studied.
Basic Results Some important known results on stepwise irregular graphs are now recalled.
Lemma 2.
The number of edges of a stepwise irregular graph is even.
Lemma 2.
Stepwise irregular graphs are bipartite.
Lemma 2.
Let G0 be an SI graph of order n0 and cyclomatic number , possessing a vertex of degree 1.
Then for all k = 1, 2.
A A A , there exist SI graphs of order n0 4k and cyclomatic number .
Theorem 2.
The order of a stepwise irregular bicyclic graph .
raph with = .
is an odd integer.
There exist stepwise irregular bicyclic graphs whose order is any positive odd integer, except 1, 3, 5, 7, 9, and 11.
Theorem 2.
The order of a stepwise irregular tree is an odd integer.
There exist stepwise irregular trees whose order is any positive odd integer, except 1, 5, 9, 13, and 17.
Remark 2.
In .
Theorem 8.
Page .
, the exceptions stated in Theorem 2.
2 are given as 1, 5, 8, 13, and 17 whereas they should be 1, 5, 9, 13, and 17.
Properties and Construction of SI Graphs The second Zagreb index M2 (G) of a graph G is in general, a positive integer.
In this section, first we show that the second Zagreb index for a stepwise irregular graph is an even integer.
Theorem 3.
If G is an SI graph then the second Zagreb index M2 (G) is an even integer.
Proof.
Since G is an SI graph, for any edge uv OO E(G), dG .
= dG .
A 1 and therefore if dG .
is even, then dG .
is odd and P vice versa.
This implies that for any edge uv OO E(G), dG .
dG .
is even.
Thus M2 (G) = dG .
dG .
is even.
uvOOE(G) Theorem 3.
For every even positive integer n except 4, there exists a connected SI graph with n number of edges.
Some properties of stepwise irregular graphs Bera.
Paul.
Subramanian Figure 1.
Unicyclic SI graph G0 having 8 edges Proof.
P3 is the smallest SI tree with 3 vertices and 2 edges.
Now by Lemma 2.
3, there exist SI trees having 3 4k vertices and hence 2 4k, k Ou 1 edges.
Also there exists an unicyclic SI graph G0 having 8 vertices and 8 edges with two pendant vertices (Fig.
Therefore, again by Lemma 2.
3, we can construct SI graphs G having 8 4k, k Ou 1 vertices and having the same cyclomatic number as G0 following the construction in the proof of Lemma 2.
3 in .
Thus the graphs G have also only one cycle which is the same as the cycle in G0 and so have 8 4k, k Ou 1 It can be verified that there is no SI graph having 4 edges.
This proves the Theorem.
Since the irregularity of an SI graph is the same as the number of edges of the graph, we have the following corollaries.
Corollary 3.
The irregularity of a connected SI graph can be any positive even integer except 4.
Corollary 3.
The irregularity of a connected SI tree can be any positive even integer except 4, 8, 12 and 16.
In .
Albertson claimed that the irregularity of a bipartite graph is maximum if it is a complete bipartite graph.
If the bipartite graph is SI, this claim is indeed true on recalling the fact that the irregularity of an SI graph is the number of edges in the graph.
Based on this fact, we give a lower and an upper bound for the number of edges of an SI graph of given order and show that both the bounds are tight.
Theorem 3.
Let G be a connected SI graph of order n and p be the number of edges of G.
Then p is even and n Oe 1 O p O n 4Oe1 .
Moreover, for odd n, the lower and upper bounds are attained when G is an SI tree and the complete bipartite SI graph K nOe1 , n 1 respectively.
Proof.
Let G be a connected SI graph of order n and having p edges.
Since G is connected, it must have at least n Oe 1 edges so that p Ou n Oe 1.
The equality holds for all SI trees.
In order to prove the upper bound, since G is SI, it is bipartite and the irregularity of G is the same as the number of edges of G.
Hence the irregularity of a bipartite SI graph is maximum if it is a complete bipartite graph.
The maximum irregularity of G can be obtained by partitioning the n vertices into two sets in such a way that the number of edges is maximum.
Let the partition of n be n = nOek n k , for some k Ou 1.
The complete bipartite graph K nOek , n k has n Oek O n 4Oe1 .
Thus p = irr(G) O n Oek The equality holds if n is odd and k = 1.
In this case we get G = K nOe1 , n 1 which is SI.
Therefore for complete bipartite SI graph K nOe1 , n 1 , the equality holds.
Some properties of stepwise irregular graphs Bera.
Paul.
Subramanian Given an SI graph of order n with a vertex of degree one and cyclomatic number , we prove the existence of SI graphs of order n 4k i with cyclomatic number i, 0 O i O 2.
This result is a different kind of generalization of the SI graphs which is proved on the lines of Lemma 2.
order to prove the result, we need following lemmas.
Lemma 3.
Let G0 be a stepwise irregular graph with a vertex u of degree 1.
A stepwise irregular graph G1 can be constructed from G0 .
by adding 5 new vertices as shown in Fig.
by adding 6 vertices as shown in Fig.
Moreover, if G0 has cyclomatic number , then G1 as shown in Fig.
2 has cyclomatic number 1 while G1 as shown in Fig.
3 has cyclomatic number 2.
Proof.
Clearly, the graph G1 in Fig.
2 as well as in Fig.
3 is stepwise irregular, if the graph G0 is stepwise irregular.
Figure 2.
The graph considered in Lemma 3.
Figure 3.
The graph considered in Lemma 3.
We prove the following theorem based on Lemma 3.
Theorem 3.
Let G be an SI graph of order n and cyclomatic number , possessing a vertex of Then for all k = 1, 2.
A A A , there exist SI graphs of order n 4k i and cyclomatic number i, for i = 0, 1, 2.
Proof.
The case i = 0 is the same as Lemma 2.
i = 1: for k = 1 by an application of the construction in Lemma 3.
1 once we obtain the required graph.
For k Ou 2, by an application of the construction in Lemma 3.
1 once followed by an application of the construction in Lemma 2.
3, .
Oe .
times, we obtain the required Some properties of stepwise irregular graphs Bera.
Paul.
Subramanian i = 2: for k = 1, by an application of the construction in Lemma 3.
1 once and for k = 2, by an application of the construction in Lemma 3.
1 twice, we obtain the respective required For k = 3, we can obtain the required graph by an application of the construction in Lemma 1 twice followed by an application of the construction in Lemma 2.
3 respectively.
For k Ou 4, by an application twice of the construction in Lemma 3.
1 and .
Oe .
times the construction in Lemma 2.
3 we get the required graph.
Corollary 3.
Let G be an SI graph of order n and cyclomatic number , possessing a vertex of Then for all k = 2, 3.
, there exist SI graphs of order n 4k 3 and cyclomatic number 3.
Proof.
For k = 2, first applying the construction of adding 5 vertices in Lemma 3.
1 and then the construction of adding 6 vertices in Lemma 3.
1 we get the required graph.
For k = 3, the required graph can be constructed by an application of the construction in Lemma 3.
1, 3 times.
For k Ou 4, first applying the construction in lemma 3.
1, 3 times and then the construction in Lemma 2.
3, .
Oe .
times, we get the required graph.
In the results mentioned above, we proved the existence of SI graphs of different order and cyclomatic number, given an SI graph with a pendant vertex.
In the following results we prove the existence of SI graphs of order n 7k and cyclomatic number k, given an SI graph with a vertex of degree 2 having neighbours of degree 3 .
In order to prove this result, we will use the following lemma, which is straightforward to Lemma 3.
Let G0 be a stepwise irregular graph with a vertex u of degree 2 having neighbors each of which is of degree 3 (Fig.
An SI graph G1 can be constructed by adding 7 new vertices as shown in Fig.
Moreover, if G0 has cyclomatic number , then G1 has cyclomatic number 1.
Figure 4.
The graph considered in Lemma 3.
Now by repeated application of the construction in Lemma 3.
2 we obtain the following result.
Theorem 3.
Let G0 be an SI graph of order n and cyclomatic number , possessing a vertex of degree 2 that has neighbors each of which is of degree 3.
Then for all k = 1, 2.
A A A , there exist SI graphs of order n 7k and cyclomatic number k.
Some properties of stepwise irregular graphs Bera.
Paul.
Subramanian The next theorem can be shown as a consequence of the construction in Lemma 3.
2 and the construction in Lemma 2.
In fact it can be proved by an application of the construction in Lemma 3.
2 once and .
Oe .
times application of the construction in Lemma 2.
3 to the graph G0 .
Theorem 3.
Let G0 be an SI graph of order n and cyclomatic number , possessing a vertex of degree 2 that has neighbors each of which is of degree 3.
Then for all k = 1, 2.
A A A , there exist SI graphs of order n 4k 3 and cyclomatic number 1.
In .
, a characterization on the order of connected bicyclic SI graphs was given.
Here we provide a characterization on the order of connected tricyclic SI graphs.
Theorem 3.
The order of an SI tricyclic graph is an even integer.
Moreover, there exists tricyclic SI graph whose order is any positive integer except 2, 4, 6 and 8.
Proof.
By Theorem 2.
1, it can be shown that there exist bicyclic SI graphs order 13 2k, k Ou 0.
Now by applying Lemma 3.
1, it can further be shown that there exist tricyclic SI graph of order 13 2k 5, i.
, 18 2k, k Ou 0.
Also, there exist bicyclic SI graph of order 5 and 9 (Figure .
Figure 5.
Bicyclic SI graph of order 5 and 9 Hence, the Lemma 3.
2 proves the existence of tricyclic SI graph of order 12 and 16.
Gutman .
has already proved the existence of tricyclic SI graphs of order 10 and 14.
On the other hand, such tricyclic SI graph of orders 2, 4, 6 and 8 do not exist.
In the next result, we show that each integer between the minimum and maximum degree of an SI graph, must be the degree of some vertex of an SI graph.
Theorem 3.
Let G be a connected SI graph with maximum degree M and minimum degree m.
Then every integer k, m O k O M belongs to the degree sequence d(G) of G.
Proof.
The connected SI graph G has maximum degree M and minimum degree m.
Clearly m and M belong to the degree sequence d(G).
Now if possible let there exist an integer p, m < p < M such that p OO / d(G).
If p 1 OO d(G), set S to be the set of all vertices whose degrees are greater than p.
Then none of these vertices is connected to any vertex of degree less than p as otherwise the graph will not be SI.
This implies that G is disconnected which is a contradiction.
If p 1 OO / d(G), by a finite number of steps we can always find a k such that p k O M and p k OO d(G).
Using the same argument above, it can be shown that G is disconnected, again a Hence our assumption is wrong and the theorem is proved.
Remark 3.
There exist SI graphs which have only vertices of degree OI(G) and (G) = OI(G)Oe1.
The complete bipartite graph G = Km,m 1 , m Ou 1 is an example of such a graph.
Some properties of stepwise irregular graphs Bera.
Paul.
Subramanian Conditions for a Degree Sequence to be SI Graphic Degree sequence of a graph is a well-established topic of research in graph theory with wellknown conditions having been established (See, for example, the chapter 6 in .
) for a sequence of non-negative integers to be the degree sequence of a graph.
In the context of SI graphs, it is of interest to examine whether such a sequence of non-negative integers can be the degree sequence of a SI graph.
In this section we obtain necessary or sufficient conditions for degree sequences to be SI graphic.
Theorem 4.
Let G be a connected SI graph with degree sequence d = {M.
A A A .
M .
M Oe 1.
M Oe 1.
A A A .
M Oe 1.
A A A , 2, 2.
A A A , 2, 1, 1.
A A A , .
} | | .
} | .
} nM terms nM Oe1 terms n2 terms n1 terms with M Ou 3 and ni Ou 1, for 1 O i O M .
Then nM Oe1 Ou max{M, nM } and n2 Ou n1 .
Proof.
In an SI graph, all the vertices of degree M are adjacent to only vertices of degree (M Oe .
Therefore M nM number of edges must be adjacent to the vertices of degree (M Oe .
This implies > nM .
On the other hand, a vertex of degree M must have M neighbour that nM Oe1 Ou M M Oe1 vertices of degree M Oe 1.
Therefore, nM Oe1 Ou max{M, nM }.
Since G is a connected SI graph, each vertex of degree 2 is adjacent to either a vertex of degree 1 and a vertex of degree 3 or two vertices of degree 3 only.
Therefore, we have n2 Ou n1 .
Theorem 4.
Let G be a connected SI graph with degree sequence d = {M.
A A A .
M .
M Oe 1.
M Oe 1.
A A A .
M Oe 1.
A A A , m 1, m 1.
A A A , m 1, } | nM Oe1 m, m.
A A A , .
Then M nM (M Oe .
nM Oe2 (M Oe .
nM Oe4 A A A mnm = (M Oe .
nM Oe1 (M Oe .
nM Oe3 A A A .
nm 1 M nM (M Oe .
nM Oe2 (M Oe .
nM Oe4 A A A .
nm 1 = (M Oe .
nM Oe1 (M Oe .
nM Oe3 A A A mnm , depending on (M Oe .
is even or odd.
Proof.
In SI graph, the vertices of degree i are adjacent either to the vertices of degree i Oe 1 or to the vertices of degree i 1, m < i < M .
Therefore, the degree sum of the vertices of degrees M.
M Oe 2.
A A A m( or m .
is same as the degree sum of the vertices of degrees M Oe 1.
M Oe 3.
A A A m 1( or .
, depending on (M Oe .
is even or odd.
This proves the result.
Some properties of stepwise irregular graphs Bera.
Paul.
Subramanian Lemma 4.
Let the sequence d = .
n3 , 2n2 , 1n1 } be such that n1 , n2 , n3 Ou 1, n1 O n2 and n2 Ou max.
, n3 } and 3n3 n1 = 2n2 .
Then, there exists an SI graph with the degree sequence d.
Proof.
We construct an SI graph having degree sequence d.
First we have n3 vertices each of degree 3 so that there are 3n3 edges which are incident to the vertices of degree 2.
From the equation 3n3 n1 = 2n2 , we have 2n2 Oe 3n3 = n1 > 0 which implies that there are n1 number of edges connecting the vertices of degrees 2 and 1.
In fact this is done by adding n1 pendant vertices connected with vertices of degree 2.
Thus the constructed SI graph G has the degree sequence Lemma 4.
Let the sequence be d = .
n4 , 3n3 , 2n2 , 1n1 } be such that n1 , n2 , n3 , n4 Ou 1, n1 O n2 and n3 Ou max.
, n4 } and 4n4 2n2 = 3n3 n1 .
Then there exists an SI graph with with degree sequence d.
Proof.
We construct an SI graph having degree sequence d in such a way that the graph is connected.
First we have n4 vertices each of degree 4 so that there are 4n4 edges.
We also have n1 pendant vertices which are adjacent to n1 vertices among the n2 vertices of degree 2 since n1 O n2 .
Now the remaining n2 Oe n1 vertices are connected to some of the vertices of degree 3.
Now the equation 4n4 2n2 = 3n3 n1 which gives 3n3 Oe 4n4 = 2n2 Oe n1 assures that the construction of edges between the vertices of degrees 3 and 4 is possible.
We believe the following generalization of Lemma 4.
1 and Lemma 4.
2 can be proved.
Conjecture 1.
Let the sequence d = {M nM , (M Oe .
nM Oe1 .
A A A , .
nm 1 , mnm } be such that ni Ou 1, for m O i O M , and nM Oe1 Ou max{M, nM } and M nM (M Oe .
nM Oe2 (M Oe .
nM Oe4 A A A mnm = (M Oe .
nM Oe1 (M Oe .
nM Oe3 A A A .
nm 1 M nM (M Oe .
nM Oe2 (M Oe .
nM Oe4 A A A .
nm 1 = (M Oe .
nM Oe1 (M Oe .
nM Oe3 A A A mnm , depending on (M Oe .
is even or odd.
Then there exists an SI graph with the degree sequence d.
A partition of a positive integer n is a way of writing n as a sum of positive integers.
One way of representing partition of a positive integer is the Ferrers diagram .
, where each integer in the partition is represented by dots in a row, the rows ordered in a decreasing order on the number of dots with the longest on top and the smallest at the bottom.
The conjugate of a partition is the partition corresponding to the Ferrers diagram which is obtained by flipping the Ferrers diagram for the original partition across the main diagonal, thus turning rows into columns and vice versa.
In fact the degree sequence d of a graph G with p edges, can be thought of as the partition of the number 2p .
We call the conjugate partition of d as the conjugate sequence dO .
Some properties of stepwise irregular graphs Bera.
Paul.
Subramanian Let the degree sequence of an SI graph G with maximum degree M and minimum degree m be d = {M.
A A A .
M .
M Oe 1.
M Oe 1.
A A A .
M Oe 1.
A A A , } | nM Oe1 m 1, m 1.
A A A , m 1, m, m.
A A A , .
Then it can be shown that dO = {.
M nM Oe1 A A A } | nm ) , nM nM Oe1 A A A nm 1 , nM nM Oe1 A A A nm 2 .
A A A , nM nM Oe1 , nM }.
Moreover, a partition d = {M nM , (M Oe .
nM Oe1 .
A A A , mnm } is called SI graphic if there exists an SI graph with degree sequence d.
The trace .
of a degree sequence d, .
, the partition of 2.
of a graph G is defined by f .
= order of .
di Ou .
, where d = .
1 , d2 , d3 .
A A A }.
It also can be represented as the number of dots in the main diagonal of the Ferrers diagram of d.
Following is a well-known necessary and sufficient condition comparing the sum of the terms of the degree sequence of a graph and its conjugate.
Theorem 4.
The partition d of 2p is graphic if and only if .
O dOi , 1 O k O f .
In the next result, we derive a necessary condition comparing the sum of the terms of the degree sequence and its conjugate for an SI graph except for the complete bipartite graphs km,m 1 , m Ou 1.
Theorem 4.
Let d = {M.
A A A .
M .
M Oe 1.
M Oe 1.
A A A .
M Oe 1.
A A A , } | nM Oe1 m 1, m 1.
A A A , m 1, m, m.
A A A , .
be SI graphic such that M Oe m Ou 2.
Then } | di O dOi where dO is the conjugate sequence of d and k is the trace of the degree sequence d.
Proof.
There may arise two cases.
Some properties of stepwise irregular graphs If nM Ou M , then k = M .
Hence, we have 2 Bera.
Paul.
Subramanian di = 2M 2 .
On the other hand we have, dOi = M nM (M Oe .
nM Oe1 (M Oe .
nM Oe2 A A A mnm = [M nM (M Oe .
nM Oe2 A A A mnm ( or .
nm 1 )] [(M Oe .
nM Oe1 (M Oe .
nM Oe3 A A A .
nm 1 ( or mnm )] depending on M Oe m is even or odd.
= 2[M nM (M Oe .
nM Oe2 A A A mnm ( or .
nm 1 )] , using Theorem 4.
Ou 2M = 2 di , since nM Ou M .
If nM < M , k = M Oe 1.
Then we have Oe1 di = 2[M nM (M Oe 1 Oe nM )(M Oe .
] = 2[(M Oe .
2 nM ] Oe1 dOi = dOi Oe dOM = M nM (M Oe .
nM Oe1 (M Oe .
nM Oe2 A A A mnm Oe nM = [M nM (M Oe .
nM Oe2 A A A mnm ( or .
nm 1 )] [(M Oe .
nM Oe1 (M Oe .
nM Oe3 A A A .
nm 1 ( or mnm )] OenM , depending on M Oe m is even or odd.
= 2[(M Oe .
nM Oe1 (M Oe .
nM Oe3 A A A .
nm 1 ( or mnm )] OenM , using Theorem 4.
Ou 2[(M Oe .
M (M Oe .
nM Oe3 A A A .
nm 1 ( or mnm )] Oe M = 2(M Oe .
2 2(M Oe .
2[(M Oe .
nM Oe3 (M Oe .
nM Oe5 A A A .
nm 1 ( or mnm )] Oe M , for M Oe m Ou 3.
= 2(M Oe .
2 M Oe 2 2[(M Oe .
nM Oe3 (M Oe .
nM Oe5 A A A .
nm 1 ( or mnm )], for M Oe m Ou 3.
Oe1 Ou 2(M Oe .
2 M Ou 2(M Oe .
2 nM = 2 Some properties of stepwise irregular graphs Bera.
Paul.
Subramanian When M = m 2.
Oe1 dOi = M nM (M Oe .
nM Oe1 (M Oe .
nM Oe2 Oe nM 2(M Oe .
nM Oe1 Oe nM , using Theorem 4.
2(M Oe .
M Oe M 1 , since nM < M , nM O M Oe 1 (M Oe .
M Oe .
2(M Oe .
2 (M Oe .
2(M Oe .
2 nM
Oe1
= 2
Ou Ou SI Graph Under Elementary Graph Operations In this section we investigate the SI property of graphs under several graph operations such as vertex or edge deleted subgraph, complement graph and line graph.
Vertex/Edge Deletion of SI Graphs For a given graph G and a vertex v OO V (G), the vertex deleted subgraph G Oe v is obtained by deleting the vertex v and its adjacent edges from G.
Similarly, for a given graph G and an edge e OO E(G), the edge deleted subgraph G Oe e is obtained by deleting the edge e from G.
After deleting either a vertex or an edge from a given connected graph we may get a disconnected graph.
A disconnected graph G is said to be SI if each component of G is SI.
We show in the next result that edge deletion and edge deletion do not preserve the property of stepwise irregularity.
Theorem 5.
Let G be an SI graph.
Then .
for any edge e of G.
G Oe e is not SI .
for any vertex v of G.
G Oe v is not SI.
Proof.
Let e = xy be an edge of an SI graph G and H = G Oe e.
Also the order of G is at least Consider two adjacent vertices u and v in H.
Then these vertices u and v are also in G.
Therefore we have dG .
= dG .
A 1.
There may arise two cases.
Neither u nor v is x or y.
Then .
H .
Oe dH .
| = .
G .
Oe dG .
| = 1.
Either u or v .
ut not both, since we remove the edge e = xy ) is x or y.
Without loss of generality let u = x and v OO V (G)Oe.
, .
Then .
H .
OedH .
| = .
G .
Oe1OedG .
| = .
G .
A 1 Oe 1 Oe dG .
| = 0 or 2.
Some properties of stepwise irregular graphs Bera.
Paul.
Subramanian Since the SI graph G has at least 2 edges, there must exist an edge which falls under the second case, from which it follows that H is not SI.
Suppose G be an SI graph and v be a vertex of G.
Let H = G Oe v.
Consider two adjacent vertices x and y in H.
Then these vertices x and y are also in G.
Therefore we have dG .
= dG .
A 1.
There may arise two cases.
If x, y OO V (G) Oe nbd.
, then .
H .
Oe dH .
| = .
G .
Oe dG .
| = 1.
Either of x or y .
ut not bot.
is in nbd.
, because SI graphs are bipartite and if they are both in nbd.
, .
, x, .
will form a triangle.
Without loss of generality let x OO nbd.
and y OO G Oe nbd.
Then .
H .
Oe dH .
| = .
G .
Oe 1 Oe dG .
| = .
G .
A 1 Oe 1 Oe dG .
| = 0 or 2.
By the second case it follows that H is not SI.
We now show that complementation operation also does not preserve stepwise irregularity.
Lemma 5.
Let G be a connected SI graph, then G, the complement graph of G is not SI.
Proof.
Let G be a connected SI graph of order n with maximum degree M and minimum degree Then there must exist at least two vertices u, v of the same degree k, for some k, m O k O M , in G, which are not adjacent to each other.
So the vertices u and v are adjacent in G having same degree .
Oe 1 Oe .
Hence G is not SI.
Subdivision Graph of an SI Graph The subdivision graph .
of a graph G is denoted by S(G) and is obtained from G by inserting a new vertex in each of the edges of G.
In other words, for every edge uv OO E(G), a new vertex x is inserted such that x is adjacent to both u and v in S(G).
Theorem 5.
If G is an SI graph, then the subdivision graph S(G) is not SI.
Proof.
Let G be an SI graph and e = uv be an edge of G.
Then dG .
= dG .
A 1.
Now in the subdivision graph S(G), a new vertex w .
is inserted in e.
Then d.
= 2 in S(G).
Hence, either .
S(G) .
Oe dS(G) .
| = 1 or .
S(G) .
Oe dS(G) .
| = 1.
This implies that S(G) is not SI.
Remark 5.
There exist non-SI graphs whose subdivision graph is SI.
A 3-regular graph is an example of such a kind of graph.
Line Graph of an SI Graph The line graph L(G) of a graph G is the graph whose vertices correspond to the edges of G and any two vertices in L(G) are adjacent if and only if the edges corresponding to these vertices are adjacent in G .
Moreover, if e = uv is an edge of G then dL(G) .
= dG .
dG .
Oe 2.
Theorem 5.
Let G be an SI graph, then L(G), the line graph of G, is not SI.
Some properties of stepwise irregular graphs Bera.
Paul.
Subramanian Proof.
Let G be an SI graph.
Then G has at least two edges.
Let e1 = uv and e2 = uw be two adjacent edges in G.
Then we have, dG .
= dG .
A 1 and dG .
= dG .
A 1.
Since e1 and e2 are adjacent in G, they are adjacent in L(G).
We also have, dL(G) .
1 ) = dG .
dG .
Oe 2 and dL(G) .
2 ) = dG .
dG .
Oe 2.
Therefore .
L(G) .
1 ) Oe dL(G) .
2 )| = .
G .
Oe dG .
| = |.
G .
A .
Oe .
G .
A .
| = 0 or 2.
This implies that L(G) is not SI.
Remark 5.
There exist non-SI graphs whose line graph can be SI.
The graph P4 is not an SI graph, but the line graph of P4 is P3 which is an SI graph.
In the following result, we show that P4 is the only graph whose line graph is an SI graph.
Theorem 5.
G = P4 if and only if L(G) is an SI graph.
Proof.
If G = P4 , then L(G) = P3 which is SI.
To prove the converse, suppose L(G) = H is an SI graph.
If L(G) = P3 , we are done.
Assume that H = P3 .
Then we claim that H has K1,3 as an induced subgraph.
Proof of the claim: Since H is SI, there are two cases:
If H = Km,m 1 , m Ou 2, then clearly it has K1,3 as an induced subgraph.
If H = Km,m 1 , m Ou 2, then let the degree set 1 of H be .
, m 1, .
M } with minimum degree m Ou 1 and maximum degree M .
Now consider the subgraph induced by the set consisting of a vertex of degree k 1 (Ou .
where m < k < M and its any 3 adjacent We see that the induced subgraph forms K1,3 .
Therefore using the fact (.
, pp 74Ae.
that a graph having K1,3 as an induced subgraph can not be a line graph, we get a contradiction that H is a line graph.
Hence the only possibility is L(G) = P3 .
This implies that G = P4 .
Using the definition of line graph the following can be shown Theorem 5.
Let G be an SI graph.
Then the degree of each vertex of the line graph L(G) is an odd integer.
Concluding Remarks Besides constructing many SI graphs, several properties of SI graphs are established in this The SI property was studied for graphs obtained by certain graph operations but can be checked for other graph operations also.
For example, from the definition of SI graphs, it is clear that the disjoint union of SI graphs is SI.
The join of two graphs G and H, denoted by G H, is the graph obtained by V (G H) = V (G) O V (H) and E(G H) = E(G) O E(H) O .
v : u OO V (G), v OO V (H)}.
Using the definition of join of two graphs it can be shown that for any two Note that here degree set means the set of positive integers which are the degrees of vertices of the graph without Some properties of stepwise irregular graphs Bera.
Paul.
Subramanian non trivial graphs G and H, the join G H is not bipartite.
Hence the join can never be SI graph unless G = K m .
H = K m 1 .
The total graph T (G) of a SI graph G is not SI, where T (G) has vertex set V (G) O E(G) and two vertices in T (G) are adjacent if and only if the corresponding elements are adjacent or incident in G .
In fact every edge in a graph G produces at least one triangle in T (G) and so the total graph of any non trivial graph is not bipartite which implies the non-SI feature of T (G).
Product graphs are very useful to construct large graphs from small graphs and has been used to design interconnection networks.
Some of products of two graphs are lexicographic, direct.
Cartesian and strong product .
Among these products, lexicographic and strong product of two non trivial graphs is not bipartite, therefore not SI.
On the other hand, it can be shown that the direct and Cartesian product of two graphs need not be SI.
It will be of interest to investigate SI property of graphs under more general graph operations.
Graphs related to sequences of symbols, referred to as words, have been introduced and studied extensively .
It will be of interest to investigate the feature of stepwise irregularity in this class of graphs, thus contributing to and enriching the area of graphs related to words.
Acknowledgments The authors thank the reviewers for their time given in providing detailed and valuable review comments on this paper which very much helped to revise the paper.
References