# Stepwise Irregular Graphs and Their Metric-Based Resolvability Parameters

Authors: Nahid Akhter; Al-Nashri Al-Hossain Ahmad
Journal: Mathematical Problems in Engineering
 (2022)

---

## Abstract

If the degrees of any two consecutive vertices differ by exactly one, the graph is called a stepwise irregular graph. The study of choosing specific vertices in an ordered subset of the vertex set such that no two vertices have the same representations with regard to the chosen subset is known as resolving parameters. This concept has been expanded for edges as well as a combined version of both. We examine a unique unicyclic stepwise irregular graph and an extended structure of stepwise irregular graph in terms of resolvability parameters to connect the stepwise irregular graph and resolving parameter concepts.


---

## Body

## 1. Introduction

Letλ be a simple, connected, undirected graph with V as the vertex set and E as the edge set. The degree of a vertex x∈V, which is the count of edges related to a, is denoted by χx. If every vertex in V has the same χx, the graph belongs to a regular class of graphs; otherwise, it is irregular. Regular graphs have a history that may be traced back to either theoretical or practical applications.In 1988, a question was aroused by Chartrand et al. [1] that “what if the graph vertices do not have the same degree? In which class of graphs it will be considered?” Although in 1987 the idea of highly irregular graphs was posed in [2], this idea begins with the new thoughts of studying graphs. To answer the question that “how irregular a graph is?”, the Albertson index [3] was introduced, which is defined as follows:(1)irrλ=∑a1a2∈Eλimba1a2,where imba1a2=χa1−χa2 is the imbalance of an edge a1a2. The updated version of this index is the Mostar index [4]. Motivated by the Albertson index, Gutman in 2018 proposed a new idea which is known as a stepwise irregular graph and is defined as imbab=χa1−χa2=1 for each a1a2∈E [5]. To count the number of cycles in a graph, the cyclomatic number of a graph λ is γ=Eλ−Vλ+1 [5].Researchers of [6] proposed the concept of metric dimension, which was based on the idea of identifying the location of invaders in networks first and foremost and called the metric generators as locating sets. The idea of metric dimension for trees is defined in [6] and for any graph in [7]. The resolving sets are also known as metric generators, using a similar technique. Radar or loran terminals were classified as components of the metric base set. If a single station fails to work, then the entire set ℵ resulted in failures to serve as a station hub. To overcome this problem, in 2008, the authors of [8] proposed an idea of a fault-tolerant resolving set. The idea of the adjacency generator was established in [9]; it was introduced to explain the metric dimension of composition of two networks.Putting natural thinking on the pattern of recognizing the vertices of a graph by a subset (resolving set) of the vertex set, the edge metric dimension defined in [10], and later analogous to this definition, the authors of [11] proposed a mixed metric dimension in which both concepts (recognising vertices and edges) are combined, with the additional condition that no two elements (vertices and edges) have the same distances with respect to a chosen subset.Forη1,η2∈V, the distance (also called as geodesics) dη1,η2 between vertices η1 and η2 is the count of edges between η1 and η2. Let η∈V be a vertex for distinguished two vertices η1 and η2, if dη,η1≠dη,η2. A set ℵ⊂V is called a resolving set for λ, if any pair of distinct vertices of λ is uniquely determined by some vertices of ℵ. The minimum cardinality of ℵ is named as a resolving set, and its cardinality is the metric dimension of λ, denoted by dimλ. If for each u∈ℵf, ℵf\u remains a resolving set for λ, then ℵf is named as a fault-tolerant resolving set and the minimum count of elements of ℵf is called as a fault-tolerant metric dimension. For a vertex η and an edge e=η1η2, the distance between η and e is measured as de,η=mindη1,η,dη2,η. A vertex η∈V identifies two edges e1,e2∈E, if dη,e1≠dη,e2. A subset ℵe having minimum vertices from a graph λ is an edge resolving set for λ, if each pair of two distinct edges of λ are distinguished by some vertex of ℵe. The minimum cardinality of an edge resolving set for a graph λ is called the edge metric dimension and is denoted by dimeλ. A vertex η of a graph λ distinguishes two elements (vertices or edges) η1,η2 of λ, if dη1,η≠dη2,η. A subset ℵm is a mixed resolving set, if any vertex and edge of λ are distinguished by some vertex of ℵm. The smallest cardinality of a mixed resolving set for λ is called the mixed metric dimension and is denoted by dimmλ. Moreover, the mixed metric dimension is a blended version of metric and edge metric dimension.Computational complexity and NP hardness of the metric dimension problem was discussed in [12, 13]. The metric dimension has a range of useful uses in our everyday lives, which motivates scholars to study it. The metric dimension is extensively used in the varied fields such as combinatorial optimization [14], pharmaceutical chemistry [15], robot navigation [16], sonar and coastguard loran, facility location problems, image processing [6] weighing problems [17], and computer networks [18]; for more practical applications, see the literature [19, 20].The concept of metric dimension has a wide range of applications due to its versatility and also its generalizations which are edge, fault-tolerant, and mixed metric dimension are widely used to solve many difficult problems. The study of metric dimension on some cycle-based graphs are discussed in [21]. The preprint on the application of metric dimension and its algorithm is available at [22]. The metric dimension of chemical structures are discussed in [23]. The upper bounds for some chemical networks, one can find at [24]. The metric dimension and its related parameters are discussed in [25]. Generalized classes of some basic graphs are discussed in [26]. For the recent work on the computer 3D network ,we refer to [27]. For a detailed study on these parameters of metric dimensions, see [28]. The fault-tolerance of chemical topologies are discussed in [29]. The generalized resolving set for the circulant graph is available at [30, 31]. The famous convex structure’s resolving set can be seen at [32, 33]. The fault-tolerant of some computer networks are available at [34]. Some rotationally symmetric, extremal structures, and generalized Peterson graph are discussed in [35–37]. For the edge metric of polytopes structure, we refer to [38]. Th seminal works on edge and mixed metric are available at [10, 11]. All the resolvability parameters of graph theory on the polycyclic aromatic hydrocarbons are discussed in [39]. For the recent study of stepwise irregular graph, we refer to [40–43] and some important applications of irregular graphs and their measures [44–46]. For some topological work on this topic, one can find it in [47, 48].Following are some important results which are very helpful to prove our main work.Theorem 1.
Reference [11]: Letdimλanddimfλbe the metric and fault-tolerant metric dimension of graphλ, respectively. Then,(2)dimfλ≥dimλ+1.Theorem 2.
Reference [11]: Ifλis a simple connected graph; then,dimmλ≥maxdimλ,dimeλ.Theorem 3.
Reference [15]: Ifλis a simple, undirected connected graph; then, (1) dimλ=1 if λ=Pn.Theorem 4.
Reference [10]: For integersn,r,t≥2,dimePn=1,dimeCn=2, anddimeKn=n−1. Moreover,dimeλ=1ifλis a pathPn.Theorem 5.
Reference [11]: Ifλis a graph with orderλ; then,dimmλ=2ifλis a path.Figure1 is the stepwise irregular unicyclic graphs having a minimum number of vertices and the maximum degree of a vertex is Δ=3 and due to equal order and size, its cyclomatic number is γ=1. It is the only graph having γ=1 with even order and size. It is a unique graph in terms of even order of a stepwise irregular unicyclic graph [5]. To check the resolvability of the stepwise irregular graph, we consider this the minimum order and a special graph. The following lemmas start the discussion of the resolvability of the stepwise irregular graph.Figure 1
Stepwise irregular unicyclic graph.Lemma 1.
IfG1is a unicyclic stepwise irregular graph with order 8, then(3)dimG1=2.Proof.
To prove thatdimG1=2, we will use the double inequality method. Let dimG1≤2 and the resolving set ℵ=ξ1,ξ4. In Table 1, we provide with regard to ℵ, the representations of whole vertex set are given as follows:
Since the representations in the above table are distinct and there are no two vertices with same representations, we can say thatdimG1≤2.
On the contrary, letdimG1=1. By Theorem.3, it is not possible, which concludes that the stepwise irregular graph in Figure 1 with(4)dimG1=2.Table 1
Representations of all vertices w.r.t.ℵ.
rξi|ℵrξi|ξ1rξi|ξ4rξ1|ℵ03rξ2|ℵ12rξ3|ℵ21rξ4|ℵ30rξ5|ℵ41rξ6|ℵ32rξ7|ℵ52rξ8|ℵ63Lemma 2.
LetG1be a unicyclic stepwise irregular graph with order 8. Then,(5)dimfG1=3.Proof.
On the contrary to prove thatdimfG1=3, first we will show that dimfG1≤3 and the fault-tolerant resolving set ℵf=ξ2∪ℵ. In Table 2, we provide with regard to ℵf, the representations of whole vertex set are given as follows:
Since, the representations in the above table are distinct and there are two vertices with same representations, we can say thatdimfG1≤3.
On contrary to prove thatdimfG1≥3 we resulted to dimfG1=2 which is not possible by Theorem 1. It proves that the stepwise irregular graph that is defined in Figure 1 has(6)dimfG1=3.Table 2
Representations of all vertices w.r.t.ℵf.
rξi|ℵfrξi|ξ1rξi|ξ2rξi|ξ4rξ1|ℵf013rξ2|ℵf102rξ3|ℵf211rξ4|ℵf320rξ5|ℵf431rξ6|ℵf322rξ7|ℵf542rξ8|ℵf653Lemma 3.
LetG1be a unicyclic stepwise irregular graph with order 8. Then,(7)dimeG1=2.Proof.
On the contrary to prove thatdimeG1=2, let dimeG1≤2, and the edge resolving set ℵe=ℵ. In Table 3, we provide with regard to ℵe, the representations of whole edge set are given as follows:
Since, the representations in the above table are distinct and we cannot see any two edges with same representations, we can say thatdimeG1≤2.
Now, to prove the reverse inequality,dimeG1≥2 on contrary dimeG1=1 and it is not possible by Theorem 1. It is concluded that the stepwise irregular graph in Figure 1 with(8)dimeG1=2.Table 3
Representations of all edges w.r.t.ℵe.
rξiξj|ℵerξiξj|ξ1rξiξj|ξ4rξ1ξ2|ℵe02rξ2ξ3|ℵe11rξ3ξ4|ℵe20rξ3ξ6|ℵe21rξ4ξ5|ℵe30rξ5ξ6|ℵe31rξ5ξ7|ℵe41rξ7ξ8|ℵe52Lemma 4.
LetG1be a unicyclic stepwise irregular graph with order 8. Then(9)dimmG1=3.Proof.
On the contrary to prove thatdimmG1=3, let dimmG1≤3, and the mixed metric resolving set ℵm=ξ8∪ℵ. In Table 4, we provide with regard to ℵm, the representations of whole edge and vertex sets are given as follows:
Since, the representations in Table4 are distinct and we cannot see any two components of the graph with same representations, we can say that dimmG1≤3.
Now, to prove reverse inequalitydimmG1≥3, on contrary dimmG1=2 which is not possible by Theorem 5.
It is concluded that the stepwise irregular graph in Figure1 with(10)dimmG1=3.Table 4
Representations of all vertices and edges w.r.t.ℵm.
rξi|ℵmrξi|ξ1rξi|ξ4rξi|ξ8rξ1|ℵm036rξ2|ℵm125rξ3|ℵm214rξ4|ℵm303rξ5|ℵm412rξ6|ℵm323rξ7|ℵm521rξ8|ℵm630rξiξj|ℵmrξiξj|ξ1rξiξj|ξ4rξiξj|ξ8rξ1ξ2|ℵm025rξ2ξ3|ℵm114rξ3ξ4|ℵm203rξ3ξ6|ℵm213rξ4ξ5|ℵm302rξ5ξ6|ℵm312rξ5ξ7|ℵm411rξ7ξ8|ℵm520The graph shown in Figure2 is the stepwise irregular graph C4β with order 5β and size 6β. Its cyclomatic number is γ=6β−5β+1=β+1. As shown in Figure 3, if we use β=3, it create three cycles with order 4 and one cycle with order 4β and it adds up to 3+1=4-cycles in a graph. In the following sections, we discuss different resolvability parameters of the stepwise irregular graph such as resolving of vertices (metric dimension) or edges (edge metric dimension) and also resolving of vertices along edges (mixed metric dimension). Moreover, the updated version of the resolving set, which is a fault-tolerant resolving set, is also discussed.Figure 2
Stepwise irregular graph.C43.Figure 3
Edge representations of.C43.


## 2. Metric Dimension of a Stepwise Irregular GraphC4β

This section refers to the resolving of vertices and computation of metric dimension of stepwise irregular graphC4β.Theorem 6.
LetC4βbe a stepwise irregular graph withβ=3. Then,(11)dimC4β=3.Proof 5.
To prove thatdimC4β≤3 when β=3, we assume a resolving set ℵ=v4,v9,v14. On the vertex set of VC4β, we build the following examples:(12)rvi|ℵ=4−i,4+i,i;ifi=1,2;4−i,8−i,i;ifi=3,4;7−i,9−i,i+1;ifi=5,6;i−5,9−i,13−i;ifi=7,8,9;i−6,12−i,14−i;ifi=10,11;18−i,i−10,14−i;ifi=12,13,14;4,4,2;ifi=15.
From this representation, we obtaindimC4β≤3, that shows all the vertices of C4β have unique representations with respect to resolving set ℵ.
For reverse inequality which isdimC4β≥3, by contradiction, it becomes dimC4β=2. Following are some discussion for this claim.Case 1.
Consider the resolving set withϕ=v1,vi where i=2,3,…,15, then the same representations are either in rv4|ϕ=rv5|ϕ or rv9|ϕ=rv10|ϕ.Case 2.
Consider the resolving setϕ=vi,vj where i=2,3,j=2,3,…,15 and i≠j, then the same representations are either in rv4|ϕ=rv5|ϕ or rv9|ϕ=rv10|ϕ.Case 3.
By assuming the resolving setϕ=vi,vj where i,j=4,5,…,15 and i≠j, then the same representations are either in rv4|ϕ=rv5|ϕ or rv9|ϕ=rv10|ϕ or rv14|ϕ=rv15|ϕ.
All discussion resulting in same representations of vertices. Hence, forβ=3,(13)dimC4β=3.Theorem 7.
LetC4βbe a stepwise irregular graph withβ≥3. Then,(14)dimC4β=β.Proof.
Assume that the resolving setℵ=vi+4:i≡0mod5,ℵ=β. To show that dimC4β=β, the induction will be applied to β the number of copies of the C4 graph. Assume that the assumption is valid for β=α and that the base case is β=3, as demonstrated in Theorem 6.(15)dimC4β=α.
We will prove that it is true forβ=α+1. We assume the following:(16)dimC4α+1=dimC4α+dimC43−2.
Then, by using (13) and (15) in (16), we will obtain the following:(17)dimC4α+1=α+3−2=α+1.
Hence, it is true for all positive values ofβ≥3


## 3. Fault-Tolerant Metric Dimension ofC4β

This section refers to the resolving of vertices with possibility of choosing one vertex extra for the replacement of faulty vertex in resolving set and also the computation of fault-tolerant metric dimension of stepwise irregular graphC4β.Theorem 7.
LetC4βbe a stepwise irregular graph withβ=3. Then,(18)dimfC4β=4.Proof.
To prove thatdimfC4β≤4 when β=3, we assume a fault-tolerant resolving set ℵf=v1,v4,v9,v14. We construct the following cases on vertex set of VC4β(19)rvi|ℵf=i−1,4−i,4+i,i;ifi=1,2;i−1,4−i,8−i,i;ifi=3,4;i−2,7−i,9−i,i+1;ifi=5,6;i−2−2i9,i−5,9−i,13−i;ifi=7,8,9;15−i,i−6,12−i,14−i;ifi=10,11;15−i,18−i,i−10,14−i;ifi=12,13,14;1,4,4,2;ifi=15.
As a result of the preceding reasoning in the form of representations thatdimfC4β≤4, all the vertices of C4β have unique representations with respect to fault-tolerant resolving set ℵf.
FordimfC4β≥4, our claim becomes contradictory as a result of the conflict dimfC4β=3 which is not possible by Theorem 1. Hence, for β=3,(20)dimfC4β=4.Theorem 8.
LetC4βbe a stepwise irregular graph withβ≥3. Then,(21)dimfC4β=β+1.Proof.
The fault-tolerant resolving setℵf=v1∪ℵ. Now to show that dimfC4β=β+1, the induction will be applied to β the number of copies of the C4 graph. We assume that the assumption is valid for β=α and that the base case is β=3, as demonstrated in Theorem 7.(22)dimfC4β=α.
We will show that it is true forβ=α+1. Suppose(23)dimfC4α+1=dimfC4α+dimfC43−2.
Using (19) and (22) in (23), we obtain the following:(24)dimfC4α+1=α+4−2=α+2.
Hence, it is true for all positive values ofβ≥3


## 4. Edge Metric Dimension ofC4β

This section refers to the resolving of edges of stepwise irregular graphC4β; it also for the computation of edge metric dimension of that graph.Theorem 9.
IfC4βbe a stepwise irregular graph of order5β, then(25)dimeC4β=3
forβ=3.Proof.
To prove thatdimeC4β≤3 when β=3, we assume an edge resolving set ℵe=v4,v9,v14. We can see edge representations in Figure 2 and it has a distinct representation with respect to edge metric resolving set ℵe.
Hence, it follows thatdimeC4β≤3 because all the edges of C4β have unique representations with respect to edge resolving set ℵe.
FordimeC4β≥3, our claim becomes contradictory as a result of the conflict dimeC4β=2. Following are some cases for this claim.Case 4.
Consider the edge resolving set with 2-cardinalityℵe′=v1,vi where i=2,3,…,15, then the same representations are either in rv1v14|ℵe′=rv1v15|ℵe′ or rv1v2|ℵe′=rv1v14|ℵe′.Case 5.
Consider the edge resolving set again with 2-cardinalityℵe′=vi,vj where i,j=2,3,…,15 and i≠j, then the same representations are either in rv1v14|ℵe′=rv1v15|ℵe′ or rv1v2|ℵe′=rv1v14|ℵe′. All the cases resulted in contradiction, so this concludes that when β=3,(26)dimeC4β=3.Theorem 10.
IfC4βis a stepwise irregular graph of order5β, then(27)dimeC4β=β,
forβ≥3.Proof.
The vertex and edge resolving set have similar vertices and same cardinality so thatℵe=ℵ. To show that dimeC4β=β, the induction will be applied to β the number of copies of the C4 graph. Assuming that the assumption is valid for β=α and that the base case is β=3, as demonstrated in Theorem 9,(28)dimeC4β=α.
We will show that it is true forβ=α+1. Suppose(29)dimeC4α+1=dimeC4α+dimeC43−2.
Then, by using (26) and (28) in (29), we obtain the following:(30)dimeC4α+1=α+3−2=α+1.
Hence, it is true for all positive values ofβ≥3.


## 5. Mixed Metric Dimension ofC4β

The mixed version of vertex and edge resolving is the mixed metric resolvability parameter. This section deals with resolving vertices as well as edges at a time.Theorem 11.
LetC4βbe a stepwise irregular graph withβ=3. Then,(31)dimmC4β=3.Proof.
To prove thatdimmC4β≤3 when β=3, we assume a mixed metric resolving set ℵm=v4,v9,v14. We can see vertex representations from Theorem 6 and edge representations from Figure 3 which are showing that every vertex and edge has a distinct representation with respect to mixed metric resolving set ℵm.
Hence, it follows thatdimmC4β≤3, because all the vertices and edges of C4β have unique representations with respect to mixed metric resolving set ℵm.
FordimmC4β≥3, our claim becomes contradictory as a result of the conflict dimmC4β=2 which is not possible by Theorem 2. So, all discussion concludes that when β=3,(32)dimmC4β=3.Theorem 12.
LetC4βbe a stepwise irregular graph withβ≥3. Then,(33)dimmC4β=β.Proof.
The mixed metric resolving set is same as the vertex resolving set and edge resolving set with same cardinality so thatℵm=ℵ. To show that dimmC4β=β, the induction will be applied to β the number of copies of the C4 graph. We assume that the assumption is valid for β=α and that the base case is β=3, as demonstrated in Theorem 11.(34)dimmC4β=α.
We will show that it is true forβ=α+1. Suppose(35)dimmC4α+1=dimmC4α+dimmC43−2.
Using (32) and (34) in (35), we obtain(36)dimmC4α+1=α+3−2=α+1.
Hence, it is true for all positive values ofβ≥3.Figure2 is the stepwise irregular graph C4β with β=3, the labeling of vertices can be extended similarly to define in the figure and β can be any natural number greater than 2. Moreover, the dark black vertices show the vertex, edge, and mixed metric resolving set when β=3 and the position of resolving set vertices remains the same while increasing the number of copies of β’s.


## 6. Conclusion

Recently, the generalized class of graphs known as stepwise irregular graphs was introduced. In this research, we initiate to discuss the resolvability parameters of this new type of graphs. One of the generalized stepwise irregular graphs isC4β as shown in Figure 3. Each resolving parameter of C4β is not constant, the cardinality of each resolving parameter ℵ,ℵf,ℵe,ℵm increases with increasing graph’s cyclomatic number which is γ=β+1. As we have seen that the resolving parameters are also dependent on the degree of vertices of a graph and the stepwise irregular class of graphs is purely dependent on the degree of vertices, so the discussion of resolvability parameters of stepwise irregular graphs is interesting and opens the way of thinking on either stepwise irregular graphs or resolvability parameters of graphs. To extend this idea, we provide the following open problems at the end of this work. [50, 51].Open problem 1.
Do all the stepwise irregular graphs have varying resolving parametersℵ,ℵf,ℵe,ℵm?Open problem 2.
Is there any class of stepwise irregular graph with constant resolving parameters(ℵ,ℵf,ℵe,ℵm?



---

*Source: 3752298-2022-05-26.xml*