# k,l-Anonymity in Wheel-Related Social Graphs Measured on the Base of k-Metric Antidimension

Authors: Jiang-Hua Tang; Tahira Noreen; Muhammad Salman; Masood Ur Rehman; Jia-Bao Liu
Journal: Journal of Mathematics
 (2021)

---

## Abstract

For the study and valuation of social graphs, which affect an extensive range of applications such as community decision-making support and recommender systems, it is highly recommended to sustain the resistance of a social graphG to active attacks. In this regard, a novel privacy measure, called the k,l-anonymity, is used since the last few years on the base of k-metric antidimension of G in which l is the maximum number of attacker nodes defining the k-metric antidimension of G for the smallest positive integer k. The k-metric antidimension of G is the smallest number of attacker nodes less than or equal to l such that other k nodes in G cannot be uniquely identified by the attacker nodes. In this paper, we consider four families of wheel-related social graphs, namely, Jahangir graphs, helm graphs, flower graphs, and sunflower graphs. By determining their k-metric antidimension, we prove that each social graph of these families is the maximum degree metric antidimensional, where the degree of a vertex is the number of vertices linked with that vertex.


---

## Body

## 1. Introduction

Since 2016, a novel privacy measure, “thek,l anonymity,” is defined and used, for the sake of a social graph confrontation from various active attacks, in connection with the concept of k-metric antidimension. Trujillo-Rasua and Yero defined, studied in detail, and promoted the idea of k-metric antidimension, which provides a basis for the privacy measure k,l–anonymity [7]. They defined this privacy measure as follows:“Thek,l-anonymity for a social graphGwill be preserved according to active attacks if thek-metric antidimension ofGis bounded above bylfor the least positive integerk, wherelis an upper bound on the expected number of attacker nodes.”Accordingly, it can be seen that having ak-antimetric generator (a set defining the k-metric antidimension) as the set of attacker nodes, the probability of unique identification of other nodes by an adversary in a social graph is less than or equal to 1/k.Besides, providing many significant theoretical properties of thek-metric antidimension of graphs, Trujillo-Rasua and Yero also supplied the k-metric antidimension of complete graphs, paths, cycles, complete bipartite graphs, and trees [7]. This significant work of Trujillo-Rasua and Yero attracted many researchers to work on this idea, and therefore, the literature has been updated with the following remarkable contributions up till now: (i)
Trujillo-Rasua and Yero further contributed by characterizing1-metric antidimensional trees and unicyclic graphs [8](ii)
Mauw et al. contributed by providing a privacy-preserving graph transformation, which improves privacy in social network graphs by contracting active attacks [6](iii)
Čangalović et al. contributed by considering wheels and grid graphs in the context of thek−metric antidimension [1](iv)
DasGupta et al. contributed by analyzing and evaluating privacy-violation properties of eight social network graphs [4](v)
Kratica et al. contributed by investigating thek−metric antidimension of two families of generalized Petersen graphs GPn,1 (also called prism graphs) and GPn,2 [5](vi)
Zhang and Gao and, later on, Chatterjee et al. contributed by proving that the problem of finding thek-metric antidimension of a graph is, generally, an NP-complete problem [3, 9]Inspired by all these contributions and, particularly, motivated by the work done by Čangalović et al. on wheel graphs, we place our contribution by extending the study ofk,l-anonymity privacy measure based on k-metric antidimension towards four families of wheel-related social graphs.


## 2. Basic Works

LetG=VG,EG be a simple and connected graph. We denote two adjacent vertices x and y by x∼y and nonadjacent by x≁y in G. Two vertices of G are said to be neighbors of each other if there is an edge between them. The (open) neighborhood of a vertex x in G is Nx=y∈VG:y∼x∈EG. The neighborhood Nx is closed if it includes x and is denoted by Nx. The number of vertices adjacent with a vertex x is called its degree and is denoted by dx. The maximum degree in G is Δ=maxx∈VGdx. The metric on G is a mapping d:VG×VG⟶ℤ+∪0 defined by dx,y=l, where l is the length of the number of edges in the shortest path between vertices x and y in G. A vertex u of G identifies a pair x,y of vertices in G if dx,u≠dy,u. The sum G+H of two graphs G and H is obtained by joining each vertex of G with every vertex of H. We refer the book in [2] for nonmentioned graphical notations and terminologies used in this paper.LetS=s1,s2,…,st⊆VG be an ordered set. Then, the metric code, or simply code, of a vertex u∈VG with respect to S is the t-vector cSu=du,s1,du,s2,…,du,st. A chosen set S of vertices of G unique identifies each pair x,y of vertices in G if cSx≠cSy. The following concepts are defined by Trujillo-Rasua and Yero in [7]:(i)
A setS of vertices of G is called a k−antimetric generator (k-antiresolving set) for G if k is the largest positive integer such that k vertices of G, other than the vertices in S, are not uniquely identified by S; i.e., for every vertex w∈VG−S, there exist at least k−1 different vertices u1,…,uk−1∈VG−S such that cSw=cSu1=…=cSuk−1(ii)
The cardinality of the smallestk-antimetric generator for G is called the k-metric antidimension of G, denoted by adimkG, and such a smallest generator is known as k-antimetric basis of G(iii)
Ifk is the largest positive integer such that G has a k-antimetric generator, then G is said to be k-metric antidimensional graphIfS is a set of vertices of a graph G, then it has been defined as a relation on VG−S according to the vertices having equal metric codes with respect to S as follows.


### 2.1. Equivalence Relation and Classes [5, 7]

LetS⊂VG be a set of vertices of a connected graph G and let ρS be a relation on VG−S defined by(1)for allx,y∈VG−S,xρSy⇔cSa=cSb.This relation is an equivalence relation and partitionedVG−S into classes, say S1,…,Sm, called the equivalence classes corresponds to the relation ρS.Accordingly, we get the following useful property from [5].Remark 1.
(see [5]). For a fixed integer k≥1, a set S is a k-antimetric generator for G if and only if mini=1mSi=k, where each Si, 1≤i≤m, is an equivalence class defined by the relation ρS.


## 2.1. Equivalence Relation and Classes [5, 7]

LetS⊂VG be a set of vertices of a connected graph G and let ρS be a relation on VG−S defined by(1)for allx,y∈VG−S,xρSy⇔cSa=cSb.This relation is an equivalence relation and partitionedVG−S into classes, say S1,…,Sm, called the equivalence classes corresponds to the relation ρS.Accordingly, we get the following useful property from [5].Remark 1.
(see [5]). For a fixed integer k≥1, a set S is a k-antimetric generator for G if and only if mini=1mSi=k, where each Si, 1≤i≤m, is an equivalence class defined by the relation ρS.


## 3. Wheel-Related Social Graphs

In this section, we consider five wheel-related social graphs. Thek,l-anonymity of one of them, called a wheel graph, has been measured previously in [1], by investigating its k-metric antidimension. Here, we focus to investigate the k-metric antidimension of other four graphs. For n≥3, a wheel graph is W1,n=K1+Cn, where K1 is the trivial graph having only one vertex ν, and Cn is a cycle graph with vertices in V=VCn=v1,v2,…,vn. Accordingly, the vertex set of this graph is VW1,n=ν∪V and edge set is EW1,n=ν∼vi,vi∼vi+1;1≤i≤n, where the indices greater than n or less than 1 will be taken modulo n. Each edge ν∼vi is called a spoke in a wheel graph. One such graph is depicted in Figure 1.Figure 1
One wheel graphW1,8.In 2018, Čangalović et al. supplied the following investigations.Observation 1.
(see [1])(2)adimkW1,3=1,fork=3,2,fork=2,3,fork=1,(3)adimkW1,4=1,fork=1,4,2,fork=3,3,fork=2,(4)adimkW1,5=1,fork=2,5,2,fork=1.Theorem 1 (see [1]).
For alln≥6,(5)adimkW1,n=1,fork=3,n,2,fork=1,2.The rest of the section is aimed to investigate thek-metric antidimensions of Jahangir graphs, helm graphs, flower graphs, and sunflower graphs.


### 3.1. Jahangir Graphs

Forn≥2, a Jahangir (Gear) graph, J2n, is obtained from a wheel graph W1,2n=K1+C2n by deleting alternating spokes from the wheel. Let VC2n=V∪U, where V=v1,v2,…,vn and U=u1,u2,…,un. Then, the vertex set of a Jahangir graph is VJ2n=ν∪V∪U and its edge set is EJ2n=ν∼vi,vi∼ui,vi∼ui−1;1≤i≤n, where the indices greater than n or less than 1 will be taken modulo n. Figure 2 depicts graphical view of one Jahangir graph.The following observation is easy to verify forn=2,3, and 4.Figure 2
One Jahangir graphJ8.Observation 2.
(6)adimkJ4=1,fork=1,2,2,fork=3,(7)adimkJ6=1,fork=1,3,3,fork=2,and adimkJ8=1 for each k∈1,2,4.For all values ofn≥5, the following result provides the k-metric antidimension of Jahangir graphs.Theorem 2.
Forn≥5, let J2n be a Jahangir graph. Then,(8)adimkJ2n=1,fork=2,3,n,2,fork=1.Proof.
First of all, it is worthy to note thatNν=VC2n and Nvi=ν,ui,ui−1, for any vi∈V, and Nui=vi,vi+1, for any ui∈U. Now, we need to discuss the following seven claims.Claim 1: the setS=ν is an n-antimetric generator for J2n.Note thatcSx=1, for all x∈V, and cSy=2, for all y∈U. According to the relation ρS, there are only two equivalence classes each has cardinality n. So, the result followed by Remark 1.Claim 2: every singleton subset ofV is a 3-antimetric generator for J2n.LetS=vi⊂V for any fixed 1≤i≤n. Then, cSx=1, for all x∈Nvi, cSy=2, for all y∈V−vi, and cSz=3, for all z∈U−ui,ui−1. Hence, the relation ρS supplies three equivalence classes S1=Nvi, S2=V−vi, and S3=U−ui,ui−1. Thus, mini=13Si=3, and hence, S is 3-antimetric generator, by Remark 1.Claim 3: every singleton subset ofU is a 2-antimetric generator for J2n.LetS=ui⊂U; then, metric codes of the vertices are(9)cSx=1∀x∈Nui;cSui+1=2=cSui−1=cSν,(10)cSy=3∀y∈V−Nui;cSz=4∀z∈U−ui−1,ui,ui+1.Clearly, we receive four equivalence classes according to the relationρS, S1=Nui, S2=Nvi, S3=V−Nui, and S4=U−ui−1,ui,ui+1. Hence, mini=14Si=2, and S is a 2−antimetric generator, by Remark 1.Claim 4: every2 element subset of VJ2n is either 1-antimetric generator or 2-antimetric generator for J2n.LetS be a 2-element subset of VJ2n. Then, we have the following two cases to discuss.Case 1 (S contains ν): here, we have two subcases.Subcase 1.1: letS=ν,x with x∈V; then, cSp=2,1=cSq, for distinct p,q∈Nx−ν:(11)cSy=1,2∀y∈V−x;cSz=2,3∀z∈U−Nx.So, the equivalence classes corresponds to the relationρS are S1=Nx−ν, S2=V−x, and S3=U−Nx. Here, mini=13Si=2, which implies that S is a 2-antimetric generator, by Remark 1.Subcase 1.2: letS=ν,x with x∈U; then, cSt=1,1, for t∈Nx:(12)cSp=2,2=cSp′forp,p′∈Usuch thatdp,x=dp′,x=2,(13)cSy=1,3∀y∈V−Nx;cSz=2,4∀z∈U−p,x,p′.Due to the above metric coding, it is clear that we find four equivalence classes according to the relationρS, which are S1=Nx, S2=p,p′, S3=V−Nx, and S4=U−p,x,p′. Thus, mini=14Si=2, which implies that S is a 2−antimetric generator, by Remark 1.Case 2 (S does not contain ν): again, we have three subcases to discuss.Subcase 2.1: letS⊂V and S=v,v′. Then, dv,v′=2. If Nv∩Nv′=x⊂U, then a vertex y∈U, such that dy,x=2, has the unique metric code from the set 1,3,3,1 with respect to S. If no vertex from U is a common neighbor of v and v′, then the vertex ν has the unique metric code 1,1 with respect to S.Subcase 2.2: letS⊂U and S=u,u′. Then, either du,u′=2 or du,u′=4. In the former case, a vertex v∈V, such that v∈Nu∩Nu′, has the unique metric code 1,1. In the later case, we have two possibilities. If there is a vertex x∈U such that dx,u=2=dx,u′′, then a vertex y∈U, with dy,u=2 and dy,u′=4, has the unique metric code 2,4 with respect to S. If there is no such x in U, then the vertex ν has the unique metric code 2,2 with respect to S.Subcase 2.3: letS=u,v for u∈U and v∈V. Then, either du,v=1 or du,v=3. For the later case, let Nv=ν,x,y, where x,y∈U are distinct vertices. Here, we have two possibilities. If one of the neighbors x and y of v, say x, has the property that dx,u=2, then the neighbor y of v has the unique metric code 4,1 with respect to S. If dx,u=4=dy,u, then the vertex ν has the unique metric code 2,1 with respect to S. In the former case, v is a one neighbor of u from V, and the other neighbor of u from V has the unique metric code 1,2 with respect to S.In each possibility of these subcases, the relationρS proposes at least one singleton equivalence class, which follows that miniSi=1. Hence, S is an 1−antimetric generator, by Remark 1.Claim 5: forn≥7, the set A′=vi,ν,x⊆VJ2n is a 2−antimetric generator whenever x∈V∪U−ui−2,vi−1,ui−1,vi,ui,vi+1,ui+1. Otherwise, A′ is 1−antimetric generator for J2n.Ifx∈V∪U−ui−2,vi−1,ui−1,vi,ui,vi+1,ui+1, the following two cases are need to be discussed for x.Case 1: wheneverx∈U−ui−2,ui−1,ui,ui+1, metric codes with respect to A′ are(14)cA′t=1,2,4∀t∈Nvi−ν,cA′p=2,1,1∀p∈Nx,(15)cA′q=2,1,3∀q∈V−Nx,cA′ui+1=3,2,2=cA′ui+3for1≤i≤n,(16)cA′y=3,2,4∀y∈U−ui−1,ui,x,ui+2,ui+3.So, the equivalence classes corresponds to the relationρA′ are S1=Nvi−ν, S2=Nx, S3=V−Nx, S4=ui+1,ui+3, and S5=U−ui−1,ui,x,ui+1,ui+2,ui+3. Note that mini=15Si=2, so Remark 1 yields the required result.Case 2: wheneverx∈V−vi−1,vi,vi+1, metric codes with respect to A′ are(17)cA′f=1,2,3∀f∈Nvi−ν;cA′g=3,2,1∀g∈Nx−ν,(18)cA′h=2,1,2∀h∈V−vi,x;cA′m=3,2,3∀m∈U−Nvi∪Nx.Hence, the equivalence classes corresponds to relationρA′ are S1=Nvi−ν, S2=Nx−ν, S3=V−vi,x, and S4=U−Nvi∪Nx. It follows that mini=14Si=2 because n≥7. Thus, Remark 1 proves that A′ is a 2-antimetric generator.Now, ifx∈ui−2,vi−1,ui−1,ui,vi+1,ui+1, then again we have two cases.Case 1: wheneverx∈vi−1,vi+1, we have a vertex t∈Nx−ν such that cA′t≠cA′t′, for all t′∈VC2n−tCase 2: wheneverx∈ui−2,ui−1,ui,ui+1, we have a vertex t∈U with dt,x=2 and cA′t≠cA′t′, for all t′∈VC2n−tIn both the cases, we get at least one singleton equivalence classt with respect to the relation ρA′, which implies that mini|Si|=1. Hence, A′ is a 1−antimetric generator, by Remark 1.Claim 6: exceptn=5,7, the set B=ui,ν,u⊆VJ2n is a 2-antimetric generator whenever u∈U−ui−2,ui−1,ui,ui+1,ui+2. Otherwise, B is a 1−antimetric generator for J2n.Wheneveru∈U−ui−2,ui−1,ui,ui+1,ui+2, then the metric coding with respect to B is(19)cBp=1,1,3∀p∈Nui,cBui−1=2,2,4=cSui+1,cBq=3,1,1∀q∈Nu,(20)cBx′=4,2,2=cSy′, wherex′,y′∈Usuch that dx′,u=dy′,u=2,(21)cBx=3,1,3∀x∈V−Nui∪Nu,cBz=4,2,4∀z∈U−ui−1,ui,ui+1,x′,u,y′.Hence, we have the equivalence classesS1=Nui, S2=ui−1,ui+1, S3=Nu, S4=x′,y′, S5=V−Nui∪Nu, and S6=U−ui−1,ui,ui+1,x′,u,y′ in accordance with the relation ρB. Thus, mini=16Si=2, o B is a 2-antimetric generator, by Remark 1.Next, wheneveru∈ui−2,ui−1,ui+1,ui+2, then(22)cBvi=1,1,1whenu=ui−1,cBvi+1=1,1,1whenu=ui+1,(23)cBvi−1=2,2,2whenu=ui−2,cBvi+1=2,2,2whenu=ui+2.In each possibility, the given metric code is unique, which provides a singleton equivalence class according to the relationρB. Hence, miniSi=1, and B is a 1−antimetric generator, by Remark 1.Claim 7: every setS⊆VJ2n of cardinality t≥3 is a 1−antimetric generator for J2n, except the sets A′ and B discussed in Claims 5 and 6, respectively.
IfS contains the vertex ν, then there exists a vertex g∈U (or g∈V) such that g is a neighbor of some element in S, and cSg≠cSg′, for any g′∈VJ2n−g. If S does not contain the vertex ν, then ν has the unique metric code with respect to S. In both the cases, we get a singleton equivalence class according to the relation ρS. Hence, miniSi=1, and Remark 1 implies that S is a 1-antimetric generator.
All these claims conclude the proof with the following points:(i)
Fork∈4,5…,n−1, there does not exist a k-antimetric generator for J2n.(ii)
Claims1,2, and 3 provide that adim1J2n≥2. Furthermore, there exist 1-antimetric generators for J2n of cardinality at least 2, by Claims 4 to 7. It follows that adim1J2n=2.(iii)
Claim 3 provides the existence of a 2-antimetric generator forJ2n of cardinality 1, which yields that adim2J2n=1.(iv)
Claim 2 provides the existence of a 3-antimetric generator forJ2n of cardinality 1, which implies that adim3J2n=1.(v)
Ann-antimetric generator for J2n of cardinality 1 exists due to Claim 1, and hence, adimnJ2n=1.


### 3.2. Helm Graphs

Forn≥3, a helm graph, Hn, is obtained from a wheel graph W1,n=K1+Cn by attaching one leaf (a vertex of degree one) with each vertex of the cycle Cn. Let U=u1,u2,…,un be the set of leaves; then, the vertex set of a helm graph is VHn=VW1,n∪U, and its edge set is EHn=EW1,n∪vi∼ui;1≤i≤n, where the indices greater than n or less than 1 will be taken modulo n. One helm graph is shown in Figure 3.Figure 3
One helm graphH8.It is an easy task to verify the following observation.Observation 3.
Whenn∈3,5, adimkHn=1, for k=1,2,…,n. While(24)adimkH4=1,fork=1,4,5,fork=2,(25)adimkH6=1,fork=1,3,6,3,fork=2.Theorem 3.
Forn≥7, let Hn be a helm graph. Then,(26)adimkHn=1,fork=1,4,n,2,fork=3,3,fork=2.Proof.
It is significant to keep in hand the neighborhoodsNν=V and Nvi=ν,vi+1,vi−1,ui, for any vi∈V, and Nui=vi, for any leaf ui∈U. Now, we have to discuss the following eight claims.Claim 1: the setS=ν is an n−antimetric generator for Hn.Note thatcSx=1, for all x∈V, and cSy=2, for all y∈U. There are only two equivalence classes S1=V and S2=U, both of cardinality n, according to the relation ρS. Hence, mini=12Si=n, which implies that S is an n-antimetric generator, by Remark 1.Claim 2: every single leaf form a 1-antimetric generator forHn.LetS=ui be a set of one leaf ui∈U. Then, cSvi=1, where vi∈Nui, and no other vertex of Hn has the code similar to vi. It follows that there exists a singleton equivalence class due to the relation ρS. Accordingly, Remark 1 refers that S is an 1−antimetric generator.Claim 3: every singleton subset ofV is a 4-antimetric generator for Hn.LetS=vi⊂V, for any fixed 1≤i≤n; then, cSx=1, for all x∈Nvi, cSy=2, for all y∈ui−1,ui+1∪V−vi−1,vi,vi+1, and cSz=3, for all z∈U−ui−1,ui,ui+1. Thus, the relation ρS produces three equivalence classes S1=Nvi, S2=ui−1,ui+1∪V−vi−1,vi,vi+1, and S3=U−ui−1,ui,ui+1. Hence, mini=13Si=4, and S is a 4-antimetric generator for Hn, by Remark 1.Claim 4: the setS′=ui,w is a 3-antimetric generator for Hn whenever w∈Nui. Otherwise, S′ is a 1-antimetric generator.Wheneverw∈Nui, we have w=vi, and the metric codes with respect to S′ are(27)cS′x=2,1∀x∈Nvi−ui;cS′y=4,3∀y∈U−ui−1,ui,ui+1,(28)cS′z=3,2∀z∈ui−1,ui+1∪V−vi−1,vi,vi+1.The equivalence classes corresponds to the relationρS′ are S1=Nvi−ui, S2=U−ui−1,ui,ui+1, and S3=ui−1,ui+1∪V−vi−1,vi,vi+1. It follows, by Remark 1, that S′ is a 3-antimetric generator since mini=13Si=3.Whenw∈Nui, then the vertex vi∈Nui has the metric code which is not similar to the metric code of any other vertex of Hn. This creates at least one singleton equivalence class vi in accordance with the relation ρS′, which implies that S′ is a 1-antimetric generator for Hn, by Remark 1.Claim 5: every2−element subset of VHn, except the set S′ of Claim 4, is a 1-antimetric generator for Hn.LetS be a 2−element subset of VHn and S≠S′. Then, we discuss the following two cases:Case 1 (S does not contain ν): let S⊂U. When S=ui,ui+2, the vertex ui+1 has the unique metric code 3,3 with respect to S. When S=ui,ui−2, the vertex ui−1 has the unique metric code 3,3 with respect to S. Otherwise, the vertex ν has the unique metric code 2,2 with respect to S. Next, we let S⊂V. When S=vi,vi+2, the vertex vi−1 has the unique metric code 1,2 with respect to S. Otherwise, the vertex ν has the unique metric code 1,1 with respect to S.Case 2 (S contains ν): let S=vi,ν; then, the leaf ui∈Nvi has the unique metric code 1,2 with respect to S.Each possibility in both the cases yields at least one singleton equivalence class according to the relationρS, which implies that S is a 1-antimetric generator, by Remark 1.Claim 6: the setE=ui,vi,ν⊂VHn is a 2-antimetric generator for Hn.Note thatcEui−1=3,2,2=cSui+1, cEvi−1=2,1,1=cSvi+1,(29)cEx=3,2,1,∀x∈V−vi−1,vi,vi+1,cEy=4,3,2∀y∈U−ui−1,ui,ui+1.So, there are four equivalence classesS1=ui−1,ui+1, S2=vi−1,vi+1, S3=V−vi−1,vi,vi+1, and S4=U−ui−1,ui,ui+1 with respect to the relation ρE. That is, mini=14Si=2, and Remark 1 assists that E is a 2-antimetric generator.Claim 7: for even values ofn≥8, the set S=ν,vi,ui,vi+n/2,ui+n/2⊂VHn is a 2-antimetric generator for Hn.Note the metric coding of the vertices with respect toS is as follows:(30)cSvi−1=2,1,1,2,3=cSvi+1,cSui−1=3,2,2,3,4=cSui+1,(31)cSx=3,2,1,2,3∀x∈V−vi−1,vi,vi+1,vi+n/2−1,vi+n/2+1,(32)cSy=4,3,2,3,4∀y∈U−ui−1,ui,ui+1,ui+n/2−1,ui+n/2+1,(33)cSvi+n/2−1=3,2,1,1,2=cSvi+n/2+1,cSui+n/2−1=4,3,2,2,3=cSui+n/2+1.Hence, the classes according to the relationρS are S1=vi−1,vi+1, S2=ui−1,ui+1, S3=vi+n/2−1,vi+n//2+1, S4=ui+n/2−1,ui+n/2+1, S5=V−vi−1,vi,vi+1,vi+n/2−1,vi+n/2+1, and S6=U−ui−1,ui,ui+1,ui+n/2−1,ui+n/2+1. Here, mini=16Si=2, which implies that S is a 2-antimetric generator, by Remark 1.Claim 8: any subset ofVHn of cardinality t≥3 is a 1-antimetric generator for Hn, except the sets E and S considered in Claims 6 and 7, respectively.
LetW be a subset of VHn with |W|=t≥3 and W≠E,S. Then, note the following two possibilities:(1)
W contains ν: if W=3 and W=u,v,ν with u∈U, v∈V but v∈Nu (because this case is already discussed in Claim 6). Then, the vertex x∈Nu has the unique metric code from the set 1,1,1,1,1,2 with respect to W. If W≥4, then a neighbor of some w∈W−ν receives the unique metric code with respect to W.(2)
W does not contain ν: the vertex ν has the unique metric code with respect to W.
In both the possibilities, we get at least one singleton equivalence class according to the relationρW. Thus, miniSi=1, and Remark 1 provides that S is a 1-antimetric generator.
The proof will reach to its end by discussing the following points on the base of formerly discussed claims:(i)
Fork∈5,6,…,n−1, there does not exist a k-antimetric generator for Hn.(ii)
We find a 1-antimetric generator forHn of (1) cardinality 1 due to Claim 2, (2) cardinality 2 due to Claims 4 and 5, and (3) cardinality t≥3 due to Claim 8. Since a 1-antimetric generator for Hn of cardinality 1 is the smallest one, so adim1Hn=1.(iii)
Claim 6 assures the existence of a 2-antimetric generator forHn of cardinality 3 for all values of n, while Claim 7 assures the existence of a 2-antimetric generator for Hn of cardinality 5 just for even values of n. Moreover, no singleton set or 2-element set of vertices in Hn is a 2-antimetric generator for Hn due to Claims 1 to 5. It follows that adim2Hn=3.(iv)
We receive a3−antimetric generator of cardinality 2 from Claim 4, and no singleton set is a 3-antimetric generator for Hn due to Claims 1 to 3, which implies that adim3Hn=2.(v)
Claim 3 assists thatadim4Hn=1 because of the existence of a 4-antimetric generator for Hn of cardinality 1.(vi)
Finally,adimnHn=1 due to an n-antimetric generator for Hn of cardinality 1 exists by Claim 1.


### 3.3. Flower Graphs

Forn≥3, a flower graph, Fn, is obtained from a helm graph Hn by joining its each leaf ui to the vertex ν of K1. Accordingly, the vertex set of a flower graph is VFn=VHn, and its edge set is EFn=EHn∪ν∼ui;1≤i≤n, where the indices greater than n or less than 1 will be taken modulo n. Figure 4 provides graphical appearance of one flower graph.Figure 4
One flower graphF8.The following observation is easy to understand for the flower graphF3.Observation 4.
(34)adimkF3=1,fork=2,6,2,fork=1.Theorem 4.
For alln≥4, let Fn be a flower graph. Then,(35)adimkFn=1,fork=2,4,2n,2,fork=1,3.Proof.
The following listed neighborhoods of the vertices ofFn will be used in the proof: Nν=V∪U and Nvi=ν,vi+1,vi−1,ui, for any vi∈V, and Nui=ν,vi, for any ui∈U. We have to discuss the following nine claims to prove the required result.Claim 1: the setS=ν is a 2n-antimetric generator for Fn.Note thatcSx=1, for all x∈VFn. So, the only one equivalence class of cardinality 2n is produced by the relation ρS. Hence, S is a 2n-antimetric generator.Claim 2: every singleton subset ofU is a 2−antimetric generator for Fn.LetS=ui⊂U for any fixed 1≤i≤n; then, cSx=1, for all x∈Nui, and cSy=2, for all y∈VFn−Nui. The relation ρS creates two equivalence classes S1=Nui and S2=VFn−Nui. It follows that mini=12Si=2, and Remark 1 proposes that S is a 2-antimetric generator.Claim 3: every singleton subset ofV is a 4-antimetric generator for Fn.LetS=vi⊂V for any fixed 1≤i≤n; then, cSx=1, for all x∈Nvi, and cSy=2, for all y∈VFn−Nvi. Thus, we get two equivalence classes S1=Nvi and S2=VFn−Nvi by the relation ρS with mini=12Si=4. Hence, S is a 4-antimetric generator, by Remark 1.Claim 4: the setW=vi,ν⊂VFn is a 3-antimetric generator for Fn.Note the metric codes with respect toW is as follows: cWx=1,1, for all x∈Nvi−ν, and cWy=2,1, for all y∈VFn−Nvi. Here, the equivalence classes obtained through the relation ρW are S1=Nvi−ν and S2=VFn−Nvi. Hence, mini=12Si=3, and Remark 1 implies that W is a 3-antimetric generator.Claim 5: the setW′=vi,u⊂VFn is a 2-antimetric generator for Fn, where u∈ui−1,ui+1.The metric codes with respectW′ are cW′x=1,1, for all x∈Nu, cW′y=1,2, for all y∈Nvi−Nu, and cW′z=2,2, for all z∈VFn−Nvi∪Nu. Accordingly, three equivalence classes S1=Nu, S2=Nvi−Nu, and S3=VFn−Nvi∪Nu are generated by the relation ρW′ with mini=13Si=2. Therefore, Remark 1 provides that W′ is a 2−antimetric generator.Claim 6: any 2-element set,S⊆VFn, is a 1-antimetric generator for Fn, except the sets W and W′ discussed in Claims 4 and 5, respectively. We discuss the following two possibilities:(1)
EitherS⊂V or S⊂U or S=vi,uj with S≠W′. Then, cSν=1,1 is the unique metric code in Fn.(2)
IfS=ui,ν, then cSvi=1,1 is the unique metric code in Fn.In both the possibilities, we receive at least one singleton equivalence class, in accordance with the relationρS, which implies that miniSi=1. Hence, Remark 1 yields that S is a 1-antimetric generator.Claim 7: the setM=ui,vi,ν⊂VFn is a 2-antimetric generator for Fn.The metric coding with respect toM is(36)cMx=2,1,1∀x∈Nvi−ui,ν;cMy=2,2,1∀y∈VFn−vi−1,vi+1.It follows thatS1=Nvi−ui,ν and S2=VFn−Nvi are the equivalence classes produced by the relation ρM. Here, mini=12Si=2, which implies that M is a 2-antimetric generator, by Remark 1.Claim 8: the setM′=vi,ν,f⊂VFn is a 3-antimetric generator for Fn whenever f∈V−vi−2,vi−1,vi,vi+1,vi+2. Otherwise, M′ is a 1−antimetric generator for Fn.f∈V−vi−2,vi−1,vi,vi+1,vi+2, and we have the metric codes of the vertices with respect to M′ as follows:(37)cM′x=1,1,2∀x∈Nvi−ν;cM′y=2,1,1∀y∈Nf−ν,(38)cM′z=2,1,2∀z∈VFn−Nvi∪Nf.Thus, the relationρM′ partitioned VFn−M′ into three equivalence classes S1=Nvi−ν, S2=Nf−ν, and S3=VFn−Nvi∪Nf, with mini=13Si=3. It follows, by Remark 1, that M′ is a 3-antimetric generator.Wheneverf∈vi−2,vi−1,vi+1,vi+2, if f=vi+1 or vi−1, then a neighbor of f lying in U has the unique metric code 2,1,1 with respect to M′. If f=vi+2 or vi−2, then vi+1 or vi−1, respectively, has the unique metric code 1,1,1 with respect to M′. In either cases, we obtain at least one singleton equivalence class according to the relation ρM′, which implies that M′ is a 1-antimetric generator, by Remark 1.Claim 9: any setS⊆VFn of cardinality t≥3 is a 1−antimetric generator for Fn, except the sets M and M′ discussed in Claims 7 and 8, respectively.We discuss the following two cases:Case 1 (S does not contain ν): in this case, the vertex ν has the unique metric code with respect to SCase 2 (S contains ν): since S≠M,M′, there exists a vertex x∈Ns for at least one s∈S−ν such that x has the unique metric code with respect to S
In both the cases, we get at least one singleton equivalence class according to the relationρS, which implies that S is a 1−antimetric generator, by Remark 1.
We conclude the proof by discussing the following points using preceding claims:(i)
Fork∈5,6,…,2n−1, there does not exist a k-antimetric generator for Fn.(ii)
We get an1-antimetric generator for Fn of (1) cardinality 2 by Claim 6 and (2) cardinality t≥3 by Claims 8 and 9. Furthermore, no singleton set possesses the property of 1−antimetric generator in Fn, by Claims 1 to 3. It follows that adim1Fn=2.(iii)
ForFn, Claim 2 promises the existence of a 2-antimetric generator of cardinality 1, Claim 5 promises the existence of a 2-antimetric generator of cardinality 2, and Claim 7 promises the existence of a 2-antimetric generator of cardinality 3. All these promises conclude that adim2Fn=1.(iv)
There exists a 3-antimetric generator forFn of cardinality 2 due to Claim 4, and a 3-antimetric generator of cardinality 3 due to Claim 8. Thus, Claims 1 to 3 conclude that adim3Fn=2.(v)
Claim 3 declares the existence of a 4-antimetric generator forFn of cardinality 1, which implies that adim4Fn=1.(vi)
A2n-antimetric generator for Fn exists due to Claim 1, so adim2nFn=1.


### 3.4. Sunflower Graphs

Forn≥3, a sunflower graph, SFn, is obtained from a wheel graph W1,n=K1+Cn by attaching one vertex ui to every two consecutive vertices of the cycle Cn. Let U=u1,u2,…,un; then, the vertex set of a sun flower graph is VSFn=VW1,n∪U and its edge set is ESFn=EW1,n∪ui∼vi,ui∼vi+1;1≤i≤n, where the indices greater than n or less than 1 will be taken modulo n. A graphical preview of this graph is displayed in Figure 5.Figure 5
One sunflower graphSF8.The following observation is an easy exercise to understand.Observation 5.
Whenn∈3,5,6, adimkSFn=1, for k=1,2,…,n. While(39)adimkSF4=1,fork=1,3,4,3,fork=2,(40)adimkSF7=1,fork=2,3,7,2,fork=1,(41)adimkSF8=1,fork=2,4,8,2,fork=1.Theorem 5.
Forn≥9, let SFn be a sunflower graph. Then,(42)adimkSFn=1,fork=2,5,n,2,fork=1.Proof.
The neighborhoods,Nν=V and Nvi=ν,vi+1,vi−1,ui,ui−1 for any vi∈V, and Nui=vi,vi+1, for any ui∈U, of the vertices in SFn are useful to discuss the following nine claims.Claim 1: the setS=ν is an n-antimetric generator for SFn.Note thatcSx=1, for all x∈V, and cSy=2, for all y∈U. Thus, there are two equivalence classes V and U according to the relation ρS, and each class has n elements. Hence, Remark 1 yields that S is an n-antimetric generator.Claim 2: every singleton subsetS of V is a 5−antimetric generator for SFn.LetS=vi⊂V for any fixed 1≤i≤n. Then, cSx=1, for all x∈Nvi:(43)cSy=3∀y∈U−ui−2,ui−1,ui,ui+1;cSz=2∀z∈ui−2,ui+1∪V−vi−1,vi,vi+1.Therefore, the equivalence classes, corresponding to the relationρS, are S1=Nv, S2=ui−2,ui+1∪V−vi−1,vi,vi+1, and S3=U−ui−2,ui−1,ui,ui+1. It follows that mini=13Si=5, and S is a 5-antimetric generator, by Remark 1.Claim 3: every singleton subsetS of U is a 2−antimetric generator for SFn.LetS=ui⊂U, for any fixed 1≤i≤n. Then,(44)cSq=1∀q∈Nui;cSx=2∀x∈ν∪vi−1,ui−1,ui+1,vi+2,(45)cSy=3∀y∈ui−2,ui+2∪V−vi−1,vi,vi+1,vi+2,(46)cSz=4,∀z∈U−ui−2,ui−1,ui,ui+1,ui+2.We have four equivalence classesS1=Nui, S2=ν∪vi−1,ui−1,ui+1,vi+2, S3=ui−2,ui+2∪V−vi−1,vi,vi+1,vi+2, and S4=U−ui−2,ui−1,ui,ui+1,ui+2, in accordance with the relation ρS. Thus, mini=14Si=2, which implies that S is a 2-antimetric generator, by Remark 1.Claim 4: the setS=vi,ν⊂VSFn is a 2-antimetric generator for SFn.The metric coding with respect toS is listed as follows:(47)cSui−1=1,2=cSui;cSvi−1=1,1=cSvi+1;cSui−2=2,2=cSui+1,(48)cSx=2,1∀x∈V−vi−1,vi,vi+1;cSy=3,2∀y∈U−ui−2,ui−1,ui,ui+1.So, the relationρS supplies five equivalence classes S1=ui−1,ui, S2=vi−1,vi+1, S3=ui−2,ui+1, S4=V−vi−1,vi,vi+1, and S5=U−ui−2,ui−1,ui,ui+1. Hence, mini=15Si=2, and S is a 2-antimetric generator, by Remark 1.Claim 5: the setS=ui,ν⊂VSFn is a 2-antimetric generator for SFn.We have the following metric coding with respect toS: cSt=1,1, for all t∈Nui:(49)cSui−1=2,2=cSui+1;cSvi−1=2,1=cSvi+2;cSui−2=3,2=cSui+2,cSx=3,1, for all x∈V−Nui∪vi−1,vi+2, and cSy=4,2, for all y∈U−ui−2,ui−1,ui,ui+1,ui+2. So, the equivalence classes, in accordance with the relation ρS, are S1=Nui, S2=ui−1,ui+1, S3=vi−1,vi+2, s4=ui−2,ui+2, S5=V−Nui∪vi−1,vi+2, and S6=U−ui−2,ui−1,ui,ui+1,ui+2. Here, mini=16Si=2, which implies that S is a 2-antimetric generator, by Remark 1.Claim 6: each 2-element setS⊂VSFn−ν is a 1−antimetric generator for SFn.We discuss the following three possibilities:(1)
LetS=u,v for u∈U and v∈V. If either du,v=1 or du,v=2, then there is a vertex p in V such that p∈Nu∩Nv, and cSp=1,1≠cSp′, for any p′∈VSFn−p. If du,v=3, then there is a neighbor q of v from U such that cSq=4,1≠cSq′, for any q′∈VSFn−q. If du,v≥4, then the vertex ν has the unique metric code 2,1 with respect to S.(2)
LetS⊂V and S=v,v′. Then, either dv,v′=1 or dv,v′=2. In the former case, a vertex u∈U, for which du,v=2 and du,v′=3, has the unique metric code 2,3 with respect to S. In the later case, we have two discussions: If Nv∩Nv′=v′′⊂V, then a vertex u∈U, such that du,v′′=2, has the unique metric code from the set 1,3,3,1 with respect to S. If no vertex in V is a common neighbor of v and v′, then the vertex ν has the unique metric code 1,1 with respect to S.(3)
LetS⊂U; then, cSν=2,2 is the unique metric code in SFn. In all these possibilities, we get at least one singleton equivalence class according to the relation ρS, which implies that miniSi=1. Hence, S is a 1-antimetric generator, by Remark 1.Claim 7: the setE=vi,ν,x⊂VSFn is a 2-antimetric generator of SFn whenever x∈V−vi−3,vi−2,vi−1,vi,vi+1,vi+2,vi+3. Otherwise, E is a 1-antimetric generator.Wheneverx∈V−vi−3,vi−2,vi−1,vi,vi+1,vi+2,vi+3, note that cEui−2=2,2,3=cEui+1 and(50)cEui−1=1,2,3=cEui,whereui−1,ui∈Nvi−vi−1,ν,vi+1,(51)cEvi−1=1,1,2=cEvi+1,wherevi−1,vi+1∈Nvi−ν,ui−1,ui,(52)cEh=3,2,2=cEh′,whereh,h′∈Uwith dh,x=dh′,x=2,(53)cEg=2,1,1=cEg′,whereg,g′∈Vwith dg,x=dg′,x=1,(54)cEl=3,2,1=cEl′,wherel,l′∈Uwith dl,x=dl′,x=1,(55)cEy=2,1,2∀y∈V−vi−1,vi,vi+1,g,x,g′,(56)cEz=3,2,3∀z∈U−ui−2,ui−1,ui,ui+1,h,h′,l,l′.Hence, we have eight equivalence classesS1=ui−1,ui, S2=vi−1,vi+1, S3=ui−2,ui+1, S4=h,h′, S5=l,l′, S6=g,g′, s7=V−S2∪S6, and S8=U−S1∪S3∪S4∪S5 in accordance with the relation ρE. It can be seen that mini=18Si=2, which yields that E is a 2-antimetric generator, by Remark 1.Wheneverx∈vi−3,vi−2,vi−1,vi+1,vi+2,vi+3, we have a vertex u∈U such that cEu≠cEu′ for any u′∈VSFn−u. Hence, we receive at least one singleton equivalence class due to the relation ρE, which implies that E is a 1-antimetric generator, by Remark 1.Claim 8: the setE′=ui,ν,a⊂VSFn is a 2-antimetric generator for SFn whenever a∈U−ui−4,ui−3,ui−2,ui−1,ui,ui+1,ui+2,ui+3,ui+4. Otherwise, E′ is a 1-antimetric generator.Whenevera∈U−ui−4,ui−3,ui−2,ui−1,ui,ui+1,ui+2,ui+3,ui+4, we have the metric codes with respect to E′ as follows:(57)cE′t=1,1,3∀t∈Nui;cE′ui−2=3,2,4=cE′ui+2,(58)cE′ui−1=2,2,4=cE′ui+1;cE′vi−1=2,1,3=cE′vi+2,(59)cE′p=3,1,1=cE′p′,wherep,p′∈Na,(60)cE′q=4,2,2=cE′q′,whereq,q′∈Usuch that dq,a=dq′,a=2,(61)cE′r=3,1,2=cE′r′,wherer,r′∈Vsuch that dr,a=dr′,a=2,(62)cE′x=4,2,3=cE′x′,wherex,x′∈Usuch that dx,a=dx′,a=3,(63)cE′y=3,1,3∀y∈V−Nui∪Na∪vi−1,vi+2,r,r′,(64)cE′z=4,2,4∀z∈U−ui−2,ui−1,ui,ui+1,ui+2,x,q,l,q′,x′.Therefore, we get 10 equivalence classesS1=Nui, S2=ui−1,ui+1, S3=vi−1,vi+2, S4=ui−2,ui+2, S5=Na, S6=q,q′, S7=r,r′, S8=x,x′, S9=V−S1∪S3∪S5∪S7, and S10=U−S2∪S4∪S6∪S8 in accordance with the relation ρE′. It has been observed that mini=110Si=2, so E′ is a 2−antimetric generator, by Remark 1.Whenevera∈ui−4,ui−3,ui−2,ui−1,ui+1,ui+2,ui+3,ui+4, we have a vertex u∈U such that cE′u≠cE′u′, for any u′∈VSFn−u. Hence, we receive at least one singleton equivalence class by the relation ρE′, which implies that miniSi=1. Hence, E′ is a 1−antimetric generator, by Remark 1.Claim 9: except the setsE,E′⊂VSFn discussed in Claims 7 and 8, respectively, each set S⊆VSFn of cardinality k≥3 is a 1−antimetric generator for SFn.We have to discuss the following two cases:Case 1 (S contains ν): let S≥4 (because the case, when S=3, has been discussed in Claims 7 and 8). Then, there a vertex x∈V such that x is a neighbor of some s∈S whenever S∩V=∅, or there a vertex x∈U such that x is a neighbor of some s∈S whenever either S∩U=∅ or S∩V≠∅≠S∩U, and we get the unique metric code of x with respect to S.Case 2 (S does not contain ν): whenever S⊆V or S⊆U, the vertex ν has the unique metric code of x with respect to S. Whenever S∩U≠∅≠S∩V, there is a vertex x∈U (or x∈V) such that dx,s=1 for some element s∈S, and cSx≠cSx′, for any x′∈VSFn−x.
In both the cases, the relationρS supplies at least one singleton equivalence class, which yields that miniSi=1. Hence, S is a 1-antimetric generator, by Remark 1.
These claims complete the proof with the following deductions:(i)
There does not exist ak−antimetric generator for SFn when k∈3,4,6,7,…,n−1.(ii)
Claim 6 supplies a1−antimetric generator for SFn of cardinality 2, and Claims 7 to 9 supply a 1−antimetric generator for SFn of cardinality t≥3. Claims 1 to 3 provide the guaranty of nonexistence of singleton 1−antimetric generator for SFn. It follows that adim1SFn=2.(iii)
The existence of a2−antimetric generator for SFn of cardinalities 1, 2, and 3 is assured by Claim 3, by Claims 4 and 5, and by Claims 7 and 8, respectively. Accordingly, adim2SFn=1.(iv)
adim5SFn=1 because of the existence of a 5−antimetric generator for SFn of cardinality 1 in Claim 2.(v)
Claim 1 provides ann−antimetric generator for SFn of cardinality 1, which yields that adimnSFn=1.


## 3.1. Jahangir Graphs

Forn≥2, a Jahangir (Gear) graph, J2n, is obtained from a wheel graph W1,2n=K1+C2n by deleting alternating spokes from the wheel. Let VC2n=V∪U, where V=v1,v2,…,vn and U=u1,u2,…,un. Then, the vertex set of a Jahangir graph is VJ2n=ν∪V∪U and its edge set is EJ2n=ν∼vi,vi∼ui,vi∼ui−1;1≤i≤n, where the indices greater than n or less than 1 will be taken modulo n. Figure 2 depicts graphical view of one Jahangir graph.The following observation is easy to verify forn=2,3, and 4.Figure 2
One Jahangir graphJ8.Observation 2.
(6)adimkJ4=1,fork=1,2,2,fork=3,(7)adimkJ6=1,fork=1,3,3,fork=2,and adimkJ8=1 for each k∈1,2,4.For all values ofn≥5, the following result provides the k-metric antidimension of Jahangir graphs.Theorem 2.
Forn≥5, let J2n be a Jahangir graph. Then,(8)adimkJ2n=1,fork=2,3,n,2,fork=1.Proof.
First of all, it is worthy to note thatNν=VC2n and Nvi=ν,ui,ui−1, for any vi∈V, and Nui=vi,vi+1, for any ui∈U. Now, we need to discuss the following seven claims.Claim 1: the setS=ν is an n-antimetric generator for J2n.Note thatcSx=1, for all x∈V, and cSy=2, for all y∈U. According to the relation ρS, there are only two equivalence classes each has cardinality n. So, the result followed by Remark 1.Claim 2: every singleton subset ofV is a 3-antimetric generator for J2n.LetS=vi⊂V for any fixed 1≤i≤n. Then, cSx=1, for all x∈Nvi, cSy=2, for all y∈V−vi, and cSz=3, for all z∈U−ui,ui−1. Hence, the relation ρS supplies three equivalence classes S1=Nvi, S2=V−vi, and S3=U−ui,ui−1. Thus, mini=13Si=3, and hence, S is 3-antimetric generator, by Remark 1.Claim 3: every singleton subset ofU is a 2-antimetric generator for J2n.LetS=ui⊂U; then, metric codes of the vertices are(9)cSx=1∀x∈Nui;cSui+1=2=cSui−1=cSν,(10)cSy=3∀y∈V−Nui;cSz=4∀z∈U−ui−1,ui,ui+1.Clearly, we receive four equivalence classes according to the relationρS, S1=Nui, S2=Nvi, S3=V−Nui, and S4=U−ui−1,ui,ui+1. Hence, mini=14Si=2, and S is a 2−antimetric generator, by Remark 1.Claim 4: every2 element subset of VJ2n is either 1-antimetric generator or 2-antimetric generator for J2n.LetS be a 2-element subset of VJ2n. Then, we have the following two cases to discuss.Case 1 (S contains ν): here, we have two subcases.Subcase 1.1: letS=ν,x with x∈V; then, cSp=2,1=cSq, for distinct p,q∈Nx−ν:(11)cSy=1,2∀y∈V−x;cSz=2,3∀z∈U−Nx.So, the equivalence classes corresponds to the relationρS are S1=Nx−ν, S2=V−x, and S3=U−Nx. Here, mini=13Si=2, which implies that S is a 2-antimetric generator, by Remark 1.Subcase 1.2: letS=ν,x with x∈U; then, cSt=1,1, for t∈Nx:(12)cSp=2,2=cSp′forp,p′∈Usuch thatdp,x=dp′,x=2,(13)cSy=1,3∀y∈V−Nx;cSz=2,4∀z∈U−p,x,p′.Due to the above metric coding, it is clear that we find four equivalence classes according to the relationρS, which are S1=Nx, S2=p,p′, S3=V−Nx, and S4=U−p,x,p′. Thus, mini=14Si=2, which implies that S is a 2−antimetric generator, by Remark 1.Case 2 (S does not contain ν): again, we have three subcases to discuss.Subcase 2.1: letS⊂V and S=v,v′. Then, dv,v′=2. If Nv∩Nv′=x⊂U, then a vertex y∈U, such that dy,x=2, has the unique metric code from the set 1,3,3,1 with respect to S. If no vertex from U is a common neighbor of v and v′, then the vertex ν has the unique metric code 1,1 with respect to S.Subcase 2.2: letS⊂U and S=u,u′. Then, either du,u′=2 or du,u′=4. In the former case, a vertex v∈V, such that v∈Nu∩Nu′, has the unique metric code 1,1. In the later case, we have two possibilities. If there is a vertex x∈U such that dx,u=2=dx,u′′, then a vertex y∈U, with dy,u=2 and dy,u′=4, has the unique metric code 2,4 with respect to S. If there is no such x in U, then the vertex ν has the unique metric code 2,2 with respect to S.Subcase 2.3: letS=u,v for u∈U and v∈V. Then, either du,v=1 or du,v=3. For the later case, let Nv=ν,x,y, where x,y∈U are distinct vertices. Here, we have two possibilities. If one of the neighbors x and y of v, say x, has the property that dx,u=2, then the neighbor y of v has the unique metric code 4,1 with respect to S. If dx,u=4=dy,u, then the vertex ν has the unique metric code 2,1 with respect to S. In the former case, v is a one neighbor of u from V, and the other neighbor of u from V has the unique metric code 1,2 with respect to S.In each possibility of these subcases, the relationρS proposes at least one singleton equivalence class, which follows that miniSi=1. Hence, S is an 1−antimetric generator, by Remark 1.Claim 5: forn≥7, the set A′=vi,ν,x⊆VJ2n is a 2−antimetric generator whenever x∈V∪U−ui−2,vi−1,ui−1,vi,ui,vi+1,ui+1. Otherwise, A′ is 1−antimetric generator for J2n.Ifx∈V∪U−ui−2,vi−1,ui−1,vi,ui,vi+1,ui+1, the following two cases are need to be discussed for x.Case 1: wheneverx∈U−ui−2,ui−1,ui,ui+1, metric codes with respect to A′ are(14)cA′t=1,2,4∀t∈Nvi−ν,cA′p=2,1,1∀p∈Nx,(15)cA′q=2,1,3∀q∈V−Nx,cA′ui+1=3,2,2=cA′ui+3for1≤i≤n,(16)cA′y=3,2,4∀y∈U−ui−1,ui,x,ui+2,ui+3.So, the equivalence classes corresponds to the relationρA′ are S1=Nvi−ν, S2=Nx, S3=V−Nx, S4=ui+1,ui+3, and S5=U−ui−1,ui,x,ui+1,ui+2,ui+3. Note that mini=15Si=2, so Remark 1 yields the required result.Case 2: wheneverx∈V−vi−1,vi,vi+1, metric codes with respect to A′ are(17)cA′f=1,2,3∀f∈Nvi−ν;cA′g=3,2,1∀g∈Nx−ν,(18)cA′h=2,1,2∀h∈V−vi,x;cA′m=3,2,3∀m∈U−Nvi∪Nx.Hence, the equivalence classes corresponds to relationρA′ are S1=Nvi−ν, S2=Nx−ν, S3=V−vi,x, and S4=U−Nvi∪Nx. It follows that mini=14Si=2 because n≥7. Thus, Remark 1 proves that A′ is a 2-antimetric generator.Now, ifx∈ui−2,vi−1,ui−1,ui,vi+1,ui+1, then again we have two cases.Case 1: wheneverx∈vi−1,vi+1, we have a vertex t∈Nx−ν such that cA′t≠cA′t′, for all t′∈VC2n−tCase 2: wheneverx∈ui−2,ui−1,ui,ui+1, we have a vertex t∈U with dt,x=2 and cA′t≠cA′t′, for all t′∈VC2n−tIn both the cases, we get at least one singleton equivalence classt with respect to the relation ρA′, which implies that mini|Si|=1. Hence, A′ is a 1−antimetric generator, by Remark 1.Claim 6: exceptn=5,7, the set B=ui,ν,u⊆VJ2n is a 2-antimetric generator whenever u∈U−ui−2,ui−1,ui,ui+1,ui+2. Otherwise, B is a 1−antimetric generator for J2n.Wheneveru∈U−ui−2,ui−1,ui,ui+1,ui+2, then the metric coding with respect to B is(19)cBp=1,1,3∀p∈Nui,cBui−1=2,2,4=cSui+1,cBq=3,1,1∀q∈Nu,(20)cBx′=4,2,2=cSy′, wherex′,y′∈Usuch that dx′,u=dy′,u=2,(21)cBx=3,1,3∀x∈V−Nui∪Nu,cBz=4,2,4∀z∈U−ui−1,ui,ui+1,x′,u,y′.Hence, we have the equivalence classesS1=Nui, S2=ui−1,ui+1, S3=Nu, S4=x′,y′, S5=V−Nui∪Nu, and S6=U−ui−1,ui,ui+1,x′,u,y′ in accordance with the relation ρB. Thus, mini=16Si=2, o B is a 2-antimetric generator, by Remark 1.Next, wheneveru∈ui−2,ui−1,ui+1,ui+2, then(22)cBvi=1,1,1whenu=ui−1,cBvi+1=1,1,1whenu=ui+1,(23)cBvi−1=2,2,2whenu=ui−2,cBvi+1=2,2,2whenu=ui+2.In each possibility, the given metric code is unique, which provides a singleton equivalence class according to the relationρB. Hence, miniSi=1, and B is a 1−antimetric generator, by Remark 1.Claim 7: every setS⊆VJ2n of cardinality t≥3 is a 1−antimetric generator for J2n, except the sets A′ and B discussed in Claims 5 and 6, respectively.
IfS contains the vertex ν, then there exists a vertex g∈U (or g∈V) such that g is a neighbor of some element in S, and cSg≠cSg′, for any g′∈VJ2n−g. If S does not contain the vertex ν, then ν has the unique metric code with respect to S. In both the cases, we get a singleton equivalence class according to the relation ρS. Hence, miniSi=1, and Remark 1 implies that S is a 1-antimetric generator.
All these claims conclude the proof with the following points:(i)
Fork∈4,5…,n−1, there does not exist a k-antimetric generator for J2n.(ii)
Claims1,2, and 3 provide that adim1J2n≥2. Furthermore, there exist 1-antimetric generators for J2n of cardinality at least 2, by Claims 4 to 7. It follows that adim1J2n=2.(iii)
Claim 3 provides the existence of a 2-antimetric generator forJ2n of cardinality 1, which yields that adim2J2n=1.(iv)
Claim 2 provides the existence of a 3-antimetric generator forJ2n of cardinality 1, which implies that adim3J2n=1.(v)
Ann-antimetric generator for J2n of cardinality 1 exists due to Claim 1, and hence, adimnJ2n=1.


## 3.2. Helm Graphs

Forn≥3, a helm graph, Hn, is obtained from a wheel graph W1,n=K1+Cn by attaching one leaf (a vertex of degree one) with each vertex of the cycle Cn. Let U=u1,u2,…,un be the set of leaves; then, the vertex set of a helm graph is VHn=VW1,n∪U, and its edge set is EHn=EW1,n∪vi∼ui;1≤i≤n, where the indices greater than n or less than 1 will be taken modulo n. One helm graph is shown in Figure 3.Figure 3
One helm graphH8.It is an easy task to verify the following observation.Observation 3.
Whenn∈3,5, adimkHn=1, for k=1,2,…,n. While(24)adimkH4=1,fork=1,4,5,fork=2,(25)adimkH6=1,fork=1,3,6,3,fork=2.Theorem 3.
Forn≥7, let Hn be a helm graph. Then,(26)adimkHn=1,fork=1,4,n,2,fork=3,3,fork=2.Proof.
It is significant to keep in hand the neighborhoodsNν=V and Nvi=ν,vi+1,vi−1,ui, for any vi∈V, and Nui=vi, for any leaf ui∈U. Now, we have to discuss the following eight claims.Claim 1: the setS=ν is an n−antimetric generator for Hn.Note thatcSx=1, for all x∈V, and cSy=2, for all y∈U. There are only two equivalence classes S1=V and S2=U, both of cardinality n, according to the relation ρS. Hence, mini=12Si=n, which implies that S is an n-antimetric generator, by Remark 1.Claim 2: every single leaf form a 1-antimetric generator forHn.LetS=ui be a set of one leaf ui∈U. Then, cSvi=1, where vi∈Nui, and no other vertex of Hn has the code similar to vi. It follows that there exists a singleton equivalence class due to the relation ρS. Accordingly, Remark 1 refers that S is an 1−antimetric generator.Claim 3: every singleton subset ofV is a 4-antimetric generator for Hn.LetS=vi⊂V, for any fixed 1≤i≤n; then, cSx=1, for all x∈Nvi, cSy=2, for all y∈ui−1,ui+1∪V−vi−1,vi,vi+1, and cSz=3, for all z∈U−ui−1,ui,ui+1. Thus, the relation ρS produces three equivalence classes S1=Nvi, S2=ui−1,ui+1∪V−vi−1,vi,vi+1, and S3=U−ui−1,ui,ui+1. Hence, mini=13Si=4, and S is a 4-antimetric generator for Hn, by Remark 1.Claim 4: the setS′=ui,w is a 3-antimetric generator for Hn whenever w∈Nui. Otherwise, S′ is a 1-antimetric generator.Wheneverw∈Nui, we have w=vi, and the metric codes with respect to S′ are(27)cS′x=2,1∀x∈Nvi−ui;cS′y=4,3∀y∈U−ui−1,ui,ui+1,(28)cS′z=3,2∀z∈ui−1,ui+1∪V−vi−1,vi,vi+1.The equivalence classes corresponds to the relationρS′ are S1=Nvi−ui, S2=U−ui−1,ui,ui+1, and S3=ui−1,ui+1∪V−vi−1,vi,vi+1. It follows, by Remark 1, that S′ is a 3-antimetric generator since mini=13Si=3.Whenw∈Nui, then the vertex vi∈Nui has the metric code which is not similar to the metric code of any other vertex of Hn. This creates at least one singleton equivalence class vi in accordance with the relation ρS′, which implies that S′ is a 1-antimetric generator for Hn, by Remark 1.Claim 5: every2−element subset of VHn, except the set S′ of Claim 4, is a 1-antimetric generator for Hn.LetS be a 2−element subset of VHn and S≠S′. Then, we discuss the following two cases:Case 1 (S does not contain ν): let S⊂U. When S=ui,ui+2, the vertex ui+1 has the unique metric code 3,3 with respect to S. When S=ui,ui−2, the vertex ui−1 has the unique metric code 3,3 with respect to S. Otherwise, the vertex ν has the unique metric code 2,2 with respect to S. Next, we let S⊂V. When S=vi,vi+2, the vertex vi−1 has the unique metric code 1,2 with respect to S. Otherwise, the vertex ν has the unique metric code 1,1 with respect to S.Case 2 (S contains ν): let S=vi,ν; then, the leaf ui∈Nvi has the unique metric code 1,2 with respect to S.Each possibility in both the cases yields at least one singleton equivalence class according to the relationρS, which implies that S is a 1-antimetric generator, by Remark 1.Claim 6: the setE=ui,vi,ν⊂VHn is a 2-antimetric generator for Hn.Note thatcEui−1=3,2,2=cSui+1, cEvi−1=2,1,1=cSvi+1,(29)cEx=3,2,1,∀x∈V−vi−1,vi,vi+1,cEy=4,3,2∀y∈U−ui−1,ui,ui+1.So, there are four equivalence classesS1=ui−1,ui+1, S2=vi−1,vi+1, S3=V−vi−1,vi,vi+1, and S4=U−ui−1,ui,ui+1 with respect to the relation ρE. That is, mini=14Si=2, and Remark 1 assists that E is a 2-antimetric generator.Claim 7: for even values ofn≥8, the set S=ν,vi,ui,vi+n/2,ui+n/2⊂VHn is a 2-antimetric generator for Hn.Note the metric coding of the vertices with respect toS is as follows:(30)cSvi−1=2,1,1,2,3=cSvi+1,cSui−1=3,2,2,3,4=cSui+1,(31)cSx=3,2,1,2,3∀x∈V−vi−1,vi,vi+1,vi+n/2−1,vi+n/2+1,(32)cSy=4,3,2,3,4∀y∈U−ui−1,ui,ui+1,ui+n/2−1,ui+n/2+1,(33)cSvi+n/2−1=3,2,1,1,2=cSvi+n/2+1,cSui+n/2−1=4,3,2,2,3=cSui+n/2+1.Hence, the classes according to the relationρS are S1=vi−1,vi+1, S2=ui−1,ui+1, S3=vi+n/2−1,vi+n//2+1, S4=ui+n/2−1,ui+n/2+1, S5=V−vi−1,vi,vi+1,vi+n/2−1,vi+n/2+1, and S6=U−ui−1,ui,ui+1,ui+n/2−1,ui+n/2+1. Here, mini=16Si=2, which implies that S is a 2-antimetric generator, by Remark 1.Claim 8: any subset ofVHn of cardinality t≥3 is a 1-antimetric generator for Hn, except the sets E and S considered in Claims 6 and 7, respectively.
LetW be a subset of VHn with |W|=t≥3 and W≠E,S. Then, note the following two possibilities:(1)
W contains ν: if W=3 and W=u,v,ν with u∈U, v∈V but v∈Nu (because this case is already discussed in Claim 6). Then, the vertex x∈Nu has the unique metric code from the set 1,1,1,1,1,2 with respect to W. If W≥4, then a neighbor of some w∈W−ν receives the unique metric code with respect to W.(2)
W does not contain ν: the vertex ν has the unique metric code with respect to W.
In both the possibilities, we get at least one singleton equivalence class according to the relationρW. Thus, miniSi=1, and Remark 1 provides that S is a 1-antimetric generator.
The proof will reach to its end by discussing the following points on the base of formerly discussed claims:(i)
Fork∈5,6,…,n−1, there does not exist a k-antimetric generator for Hn.(ii)
We find a 1-antimetric generator forHn of (1) cardinality 1 due to Claim 2, (2) cardinality 2 due to Claims 4 and 5, and (3) cardinality t≥3 due to Claim 8. Since a 1-antimetric generator for Hn of cardinality 1 is the smallest one, so adim1Hn=1.(iii)
Claim 6 assures the existence of a 2-antimetric generator forHn of cardinality 3 for all values of n, while Claim 7 assures the existence of a 2-antimetric generator for Hn of cardinality 5 just for even values of n. Moreover, no singleton set or 2-element set of vertices in Hn is a 2-antimetric generator for Hn due to Claims 1 to 5. It follows that adim2Hn=3.(iv)
We receive a3−antimetric generator of cardinality 2 from Claim 4, and no singleton set is a 3-antimetric generator for Hn due to Claims 1 to 3, which implies that adim3Hn=2.(v)
Claim 3 assists thatadim4Hn=1 because of the existence of a 4-antimetric generator for Hn of cardinality 1.(vi)
Finally,adimnHn=1 due to an n-antimetric generator for Hn of cardinality 1 exists by Claim 1.


## 3.3. Flower Graphs

Forn≥3, a flower graph, Fn, is obtained from a helm graph Hn by joining its each leaf ui to the vertex ν of K1. Accordingly, the vertex set of a flower graph is VFn=VHn, and its edge set is EFn=EHn∪ν∼ui;1≤i≤n, where the indices greater than n or less than 1 will be taken modulo n. Figure 4 provides graphical appearance of one flower graph.Figure 4
One flower graphF8.The following observation is easy to understand for the flower graphF3.Observation 4.
(34)adimkF3=1,fork=2,6,2,fork=1.Theorem 4.
For alln≥4, let Fn be a flower graph. Then,(35)adimkFn=1,fork=2,4,2n,2,fork=1,3.Proof.
The following listed neighborhoods of the vertices ofFn will be used in the proof: Nν=V∪U and Nvi=ν,vi+1,vi−1,ui, for any vi∈V, and Nui=ν,vi, for any ui∈U. We have to discuss the following nine claims to prove the required result.Claim 1: the setS=ν is a 2n-antimetric generator for Fn.Note thatcSx=1, for all x∈VFn. So, the only one equivalence class of cardinality 2n is produced by the relation ρS. Hence, S is a 2n-antimetric generator.Claim 2: every singleton subset ofU is a 2−antimetric generator for Fn.LetS=ui⊂U for any fixed 1≤i≤n; then, cSx=1, for all x∈Nui, and cSy=2, for all y∈VFn−Nui. The relation ρS creates two equivalence classes S1=Nui and S2=VFn−Nui. It follows that mini=12Si=2, and Remark 1 proposes that S is a 2-antimetric generator.Claim 3: every singleton subset ofV is a 4-antimetric generator for Fn.LetS=vi⊂V for any fixed 1≤i≤n; then, cSx=1, for all x∈Nvi, and cSy=2, for all y∈VFn−Nvi. Thus, we get two equivalence classes S1=Nvi and S2=VFn−Nvi by the relation ρS with mini=12Si=4. Hence, S is a 4-antimetric generator, by Remark 1.Claim 4: the setW=vi,ν⊂VFn is a 3-antimetric generator for Fn.Note the metric codes with respect toW is as follows: cWx=1,1, for all x∈Nvi−ν, and cWy=2,1, for all y∈VFn−Nvi. Here, the equivalence classes obtained through the relation ρW are S1=Nvi−ν and S2=VFn−Nvi. Hence, mini=12Si=3, and Remark 1 implies that W is a 3-antimetric generator.Claim 5: the setW′=vi,u⊂VFn is a 2-antimetric generator for Fn, where u∈ui−1,ui+1.The metric codes with respectW′ are cW′x=1,1, for all x∈Nu, cW′y=1,2, for all y∈Nvi−Nu, and cW′z=2,2, for all z∈VFn−Nvi∪Nu. Accordingly, three equivalence classes S1=Nu, S2=Nvi−Nu, and S3=VFn−Nvi∪Nu are generated by the relation ρW′ with mini=13Si=2. Therefore, Remark 1 provides that W′ is a 2−antimetric generator.Claim 6: any 2-element set,S⊆VFn, is a 1-antimetric generator for Fn, except the sets W and W′ discussed in Claims 4 and 5, respectively. We discuss the following two possibilities:(1)
EitherS⊂V or S⊂U or S=vi,uj with S≠W′. Then, cSν=1,1 is the unique metric code in Fn.(2)
IfS=ui,ν, then cSvi=1,1 is the unique metric code in Fn.In both the possibilities, we receive at least one singleton equivalence class, in accordance with the relationρS, which implies that miniSi=1. Hence, Remark 1 yields that S is a 1-antimetric generator.Claim 7: the setM=ui,vi,ν⊂VFn is a 2-antimetric generator for Fn.The metric coding with respect toM is(36)cMx=2,1,1∀x∈Nvi−ui,ν;cMy=2,2,1∀y∈VFn−vi−1,vi+1.It follows thatS1=Nvi−ui,ν and S2=VFn−Nvi are the equivalence classes produced by the relation ρM. Here, mini=12Si=2, which implies that M is a 2-antimetric generator, by Remark 1.Claim 8: the setM′=vi,ν,f⊂VFn is a 3-antimetric generator for Fn whenever f∈V−vi−2,vi−1,vi,vi+1,vi+2. Otherwise, M′ is a 1−antimetric generator for Fn.f∈V−vi−2,vi−1,vi,vi+1,vi+2, and we have the metric codes of the vertices with respect to M′ as follows:(37)cM′x=1,1,2∀x∈Nvi−ν;cM′y=2,1,1∀y∈Nf−ν,(38)cM′z=2,1,2∀z∈VFn−Nvi∪Nf.Thus, the relationρM′ partitioned VFn−M′ into three equivalence classes S1=Nvi−ν, S2=Nf−ν, and S3=VFn−Nvi∪Nf, with mini=13Si=3. It follows, by Remark 1, that M′ is a 3-antimetric generator.Wheneverf∈vi−2,vi−1,vi+1,vi+2, if f=vi+1 or vi−1, then a neighbor of f lying in U has the unique metric code 2,1,1 with respect to M′. If f=vi+2 or vi−2, then vi+1 or vi−1, respectively, has the unique metric code 1,1,1 with respect to M′. In either cases, we obtain at least one singleton equivalence class according to the relation ρM′, which implies that M′ is a 1-antimetric generator, by Remark 1.Claim 9: any setS⊆VFn of cardinality t≥3 is a 1−antimetric generator for Fn, except the sets M and M′ discussed in Claims 7 and 8, respectively.We discuss the following two cases:Case 1 (S does not contain ν): in this case, the vertex ν has the unique metric code with respect to SCase 2 (S contains ν): since S≠M,M′, there exists a vertex x∈Ns for at least one s∈S−ν such that x has the unique metric code with respect to S
In both the cases, we get at least one singleton equivalence class according to the relationρS, which implies that S is a 1−antimetric generator, by Remark 1.
We conclude the proof by discussing the following points using preceding claims:(i)
Fork∈5,6,…,2n−1, there does not exist a k-antimetric generator for Fn.(ii)
We get an1-antimetric generator for Fn of (1) cardinality 2 by Claim 6 and (2) cardinality t≥3 by Claims 8 and 9. Furthermore, no singleton set possesses the property of 1−antimetric generator in Fn, by Claims 1 to 3. It follows that adim1Fn=2.(iii)
ForFn, Claim 2 promises the existence of a 2-antimetric generator of cardinality 1, Claim 5 promises the existence of a 2-antimetric generator of cardinality 2, and Claim 7 promises the existence of a 2-antimetric generator of cardinality 3. All these promises conclude that adim2Fn=1.(iv)
There exists a 3-antimetric generator forFn of cardinality 2 due to Claim 4, and a 3-antimetric generator of cardinality 3 due to Claim 8. Thus, Claims 1 to 3 conclude that adim3Fn=2.(v)
Claim 3 declares the existence of a 4-antimetric generator forFn of cardinality 1, which implies that adim4Fn=1.(vi)
A2n-antimetric generator for Fn exists due to Claim 1, so adim2nFn=1.


## 3.4. Sunflower Graphs

Forn≥3, a sunflower graph, SFn, is obtained from a wheel graph W1,n=K1+Cn by attaching one vertex ui to every two consecutive vertices of the cycle Cn. Let U=u1,u2,…,un; then, the vertex set of a sun flower graph is VSFn=VW1,n∪U and its edge set is ESFn=EW1,n∪ui∼vi,ui∼vi+1;1≤i≤n, where the indices greater than n or less than 1 will be taken modulo n. A graphical preview of this graph is displayed in Figure 5.Figure 5
One sunflower graphSF8.The following observation is an easy exercise to understand.Observation 5.
Whenn∈3,5,6, adimkSFn=1, for k=1,2,…,n. While(39)adimkSF4=1,fork=1,3,4,3,fork=2,(40)adimkSF7=1,fork=2,3,7,2,fork=1,(41)adimkSF8=1,fork=2,4,8,2,fork=1.Theorem 5.
Forn≥9, let SFn be a sunflower graph. Then,(42)adimkSFn=1,fork=2,5,n,2,fork=1.Proof.
The neighborhoods,Nν=V and Nvi=ν,vi+1,vi−1,ui,ui−1 for any vi∈V, and Nui=vi,vi+1, for any ui∈U, of the vertices in SFn are useful to discuss the following nine claims.Claim 1: the setS=ν is an n-antimetric generator for SFn.Note thatcSx=1, for all x∈V, and cSy=2, for all y∈U. Thus, there are two equivalence classes V and U according to the relation ρS, and each class has n elements. Hence, Remark 1 yields that S is an n-antimetric generator.Claim 2: every singleton subsetS of V is a 5−antimetric generator for SFn.LetS=vi⊂V for any fixed 1≤i≤n. Then, cSx=1, for all x∈Nvi:(43)cSy=3∀y∈U−ui−2,ui−1,ui,ui+1;cSz=2∀z∈ui−2,ui+1∪V−vi−1,vi,vi+1.Therefore, the equivalence classes, corresponding to the relationρS, are S1=Nv, S2=ui−2,ui+1∪V−vi−1,vi,vi+1, and S3=U−ui−2,ui−1,ui,ui+1. It follows that mini=13Si=5, and S is a 5-antimetric generator, by Remark 1.Claim 3: every singleton subsetS of U is a 2−antimetric generator for SFn.LetS=ui⊂U, for any fixed 1≤i≤n. Then,(44)cSq=1∀q∈Nui;cSx=2∀x∈ν∪vi−1,ui−1,ui+1,vi+2,(45)cSy=3∀y∈ui−2,ui+2∪V−vi−1,vi,vi+1,vi+2,(46)cSz=4,∀z∈U−ui−2,ui−1,ui,ui+1,ui+2.We have four equivalence classesS1=Nui, S2=ν∪vi−1,ui−1,ui+1,vi+2, S3=ui−2,ui+2∪V−vi−1,vi,vi+1,vi+2, and S4=U−ui−2,ui−1,ui,ui+1,ui+2, in accordance with the relation ρS. Thus, mini=14Si=2, which implies that S is a 2-antimetric generator, by Remark 1.Claim 4: the setS=vi,ν⊂VSFn is a 2-antimetric generator for SFn.The metric coding with respect toS is listed as follows:(47)cSui−1=1,2=cSui;cSvi−1=1,1=cSvi+1;cSui−2=2,2=cSui+1,(48)cSx=2,1∀x∈V−vi−1,vi,vi+1;cSy=3,2∀y∈U−ui−2,ui−1,ui,ui+1.So, the relationρS supplies five equivalence classes S1=ui−1,ui, S2=vi−1,vi+1, S3=ui−2,ui+1, S4=V−vi−1,vi,vi+1, and S5=U−ui−2,ui−1,ui,ui+1. Hence, mini=15Si=2, and S is a 2-antimetric generator, by Remark 1.Claim 5: the setS=ui,ν⊂VSFn is a 2-antimetric generator for SFn.We have the following metric coding with respect toS: cSt=1,1, for all t∈Nui:(49)cSui−1=2,2=cSui+1;cSvi−1=2,1=cSvi+2;cSui−2=3,2=cSui+2,cSx=3,1, for all x∈V−Nui∪vi−1,vi+2, and cSy=4,2, for all y∈U−ui−2,ui−1,ui,ui+1,ui+2. So, the equivalence classes, in accordance with the relation ρS, are S1=Nui, S2=ui−1,ui+1, S3=vi−1,vi+2, s4=ui−2,ui+2, S5=V−Nui∪vi−1,vi+2, and S6=U−ui−2,ui−1,ui,ui+1,ui+2. Here, mini=16Si=2, which implies that S is a 2-antimetric generator, by Remark 1.Claim 6: each 2-element setS⊂VSFn−ν is a 1−antimetric generator for SFn.We discuss the following three possibilities:(1)
LetS=u,v for u∈U and v∈V. If either du,v=1 or du,v=2, then there is a vertex p in V such that p∈Nu∩Nv, and cSp=1,1≠cSp′, for any p′∈VSFn−p. If du,v=3, then there is a neighbor q of v from U such that cSq=4,1≠cSq′, for any q′∈VSFn−q. If du,v≥4, then the vertex ν has the unique metric code 2,1 with respect to S.(2)
LetS⊂V and S=v,v′. Then, either dv,v′=1 or dv,v′=2. In the former case, a vertex u∈U, for which du,v=2 and du,v′=3, has the unique metric code 2,3 with respect to S. In the later case, we have two discussions: If Nv∩Nv′=v′′⊂V, then a vertex u∈U, such that du,v′′=2, has the unique metric code from the set 1,3,3,1 with respect to S. If no vertex in V is a common neighbor of v and v′, then the vertex ν has the unique metric code 1,1 with respect to S.(3)
LetS⊂U; then, cSν=2,2 is the unique metric code in SFn. In all these possibilities, we get at least one singleton equivalence class according to the relation ρS, which implies that miniSi=1. Hence, S is a 1-antimetric generator, by Remark 1.Claim 7: the setE=vi,ν,x⊂VSFn is a 2-antimetric generator of SFn whenever x∈V−vi−3,vi−2,vi−1,vi,vi+1,vi+2,vi+3. Otherwise, E is a 1-antimetric generator.Wheneverx∈V−vi−3,vi−2,vi−1,vi,vi+1,vi+2,vi+3, note that cEui−2=2,2,3=cEui+1 and(50)cEui−1=1,2,3=cEui,whereui−1,ui∈Nvi−vi−1,ν,vi+1,(51)cEvi−1=1,1,2=cEvi+1,wherevi−1,vi+1∈Nvi−ν,ui−1,ui,(52)cEh=3,2,2=cEh′,whereh,h′∈Uwith dh,x=dh′,x=2,(53)cEg=2,1,1=cEg′,whereg,g′∈Vwith dg,x=dg′,x=1,(54)cEl=3,2,1=cEl′,wherel,l′∈Uwith dl,x=dl′,x=1,(55)cEy=2,1,2∀y∈V−vi−1,vi,vi+1,g,x,g′,(56)cEz=3,2,3∀z∈U−ui−2,ui−1,ui,ui+1,h,h′,l,l′.Hence, we have eight equivalence classesS1=ui−1,ui, S2=vi−1,vi+1, S3=ui−2,ui+1, S4=h,h′, S5=l,l′, S6=g,g′, s7=V−S2∪S6, and S8=U−S1∪S3∪S4∪S5 in accordance with the relation ρE. It can be seen that mini=18Si=2, which yields that E is a 2-antimetric generator, by Remark 1.Wheneverx∈vi−3,vi−2,vi−1,vi+1,vi+2,vi+3, we have a vertex u∈U such that cEu≠cEu′ for any u′∈VSFn−u. Hence, we receive at least one singleton equivalence class due to the relation ρE, which implies that E is a 1-antimetric generator, by Remark 1.Claim 8: the setE′=ui,ν,a⊂VSFn is a 2-antimetric generator for SFn whenever a∈U−ui−4,ui−3,ui−2,ui−1,ui,ui+1,ui+2,ui+3,ui+4. Otherwise, E′ is a 1-antimetric generator.Whenevera∈U−ui−4,ui−3,ui−2,ui−1,ui,ui+1,ui+2,ui+3,ui+4, we have the metric codes with respect to E′ as follows:(57)cE′t=1,1,3∀t∈Nui;cE′ui−2=3,2,4=cE′ui+2,(58)cE′ui−1=2,2,4=cE′ui+1;cE′vi−1=2,1,3=cE′vi+2,(59)cE′p=3,1,1=cE′p′,wherep,p′∈Na,(60)cE′q=4,2,2=cE′q′,whereq,q′∈Usuch that dq,a=dq′,a=2,(61)cE′r=3,1,2=cE′r′,wherer,r′∈Vsuch that dr,a=dr′,a=2,(62)cE′x=4,2,3=cE′x′,wherex,x′∈Usuch that dx,a=dx′,a=3,(63)cE′y=3,1,3∀y∈V−Nui∪Na∪vi−1,vi+2,r,r′,(64)cE′z=4,2,4∀z∈U−ui−2,ui−1,ui,ui+1,ui+2,x,q,l,q′,x′.Therefore, we get 10 equivalence classesS1=Nui, S2=ui−1,ui+1, S3=vi−1,vi+2, S4=ui−2,ui+2, S5=Na, S6=q,q′, S7=r,r′, S8=x,x′, S9=V−S1∪S3∪S5∪S7, and S10=U−S2∪S4∪S6∪S8 in accordance with the relation ρE′. It has been observed that mini=110Si=2, so E′ is a 2−antimetric generator, by Remark 1.Whenevera∈ui−4,ui−3,ui−2,ui−1,ui+1,ui+2,ui+3,ui+4, we have a vertex u∈U such that cE′u≠cE′u′, for any u′∈VSFn−u. Hence, we receive at least one singleton equivalence class by the relation ρE′, which implies that miniSi=1. Hence, E′ is a 1−antimetric generator, by Remark 1.Claim 9: except the setsE,E′⊂VSFn discussed in Claims 7 and 8, respectively, each set S⊆VSFn of cardinality k≥3 is a 1−antimetric generator for SFn.We have to discuss the following two cases:Case 1 (S contains ν): let S≥4 (because the case, when S=3, has been discussed in Claims 7 and 8). Then, there a vertex x∈V such that x is a neighbor of some s∈S whenever S∩V=∅, or there a vertex x∈U such that x is a neighbor of some s∈S whenever either S∩U=∅ or S∩V≠∅≠S∩U, and we get the unique metric code of x with respect to S.Case 2 (S does not contain ν): whenever S⊆V or S⊆U, the vertex ν has the unique metric code of x with respect to S. Whenever S∩U≠∅≠S∩V, there is a vertex x∈U (or x∈V) such that dx,s=1 for some element s∈S, and cSx≠cSx′, for any x′∈VSFn−x.
In both the cases, the relationρS supplies at least one singleton equivalence class, which yields that miniSi=1. Hence, S is a 1-antimetric generator, by Remark 1.
These claims complete the proof with the following deductions:(i)
There does not exist ak−antimetric generator for SFn when k∈3,4,6,7,…,n−1.(ii)
Claim 6 supplies a1−antimetric generator for SFn of cardinality 2, and Claims 7 to 9 supply a 1−antimetric generator for SFn of cardinality t≥3. Claims 1 to 3 provide the guaranty of nonexistence of singleton 1−antimetric generator for SFn. It follows that adim1SFn=2.(iii)
The existence of a2−antimetric generator for SFn of cardinalities 1, 2, and 3 is assured by Claim 3, by Claims 4 and 5, and by Claims 7 and 8, respectively. Accordingly, adim2SFn=1.(iv)
adim5SFn=1 because of the existence of a 5−antimetric generator for SFn of cardinality 1 in Claim 2.(v)
Claim 1 provides ann−antimetric generator for SFn of cardinality 1, which yields that adimnSFn=1.


## 4. Concluding Remarks

For a connected graphG, the number radG=mineccx=maxy∈VGdx,y;x∈VG is called the radius of G, where eccx is the eccentricity of x. The center of G is a subgraph GX induced by the set X=x∈VG:eccx=radG. It has been observed the following useful properties about a k−antimetric dimensional graph in [7].Remarks 2.
(see [7])(a)
If a connected graph isk−metric antidimensional, then 1≤k≤Δ(b)
If the center of a connected graph is trivial, then it isk−metric antidimensional for some k≥2It can be easily seen that each wheel-related social graph, considered in this paper, has the trivial center. Remark2 (a) insures that each of these graphs has k−metric antidimension, for some k≥1, and it must be k−metric antidimensional for some k≥2. So, naturally, it raises the following two questions:Q1. For how many and for which values ofk≥1 a wheel-related social graph admits k−metric antidimension?Q2. For which maximum value ofk, 2≤k≤Δ, a wheel-related social graph is k−metric antidimensional?The results of Čangalović et al., proved in [1] and listed in Observation 1 and Theorem 1, were the pioneers to address the answers of questions Q1 and Q2. These results revealed that (1) when n=3,5, a wheel graph W1,n admits k−metric antidimension for three values of k∈1,2,n and (2) when n=4 and for all n≥6, W1,n admits k−metric antidimension for four values of k∈1,2,3,n. It follows that W1,n is Δ−metric antidimensional.To extend the study ofk,l−anonymity based on the k−metric antidimension, we considered four graphs related to wheel graphs in this article. By investigating their k−metric antidimension, we addressed the answers of questions Q1 and Q2 as follows:(i)
For a Jahangir graphJ2n, Observation 2 and Theorem 2 revealed that (1) J4 admits k−metric antidimension for three values of k∈1,2,3, (2) when n=3,4, J2n admits k−metric antidimension for three values of k∈1,2,n, and (3) for all n≥5, J2n admits k−metric antidimension for four values of k∈1,2,3,n(ii)
For a helm graphHn, Observation 3 and Theorem 3 revealed that (1) when n=3,4,5, Hn admits k−metric antidimension for three values of k∈1,2,n, (2) H6 admits k−metric antidimension for four values of k∈1,2,3,6, and (3) for all n≥7, Hn admits k−metric antidimension for five values of k∈1,2,3,4,n(iii)
For a flower graphFn, Observation 4 and Theorem 4 revealed that (1) F3 admits k−metric antidimension for three values of k∈1,2,6 and (2) for all n≥4, Fn admits k−metric antidimension for five values of k∈1,2,3,4,2n.(iv)
For a sunflower graphSFn, Observation 5 and Theorem 5 revealed that (1) when n=3,5,6, SFn admits k−metric antidimension for three values of k∈1,2,n, (2) when n=4,7, SFn admits k−metric antidimension for four values of k∈1,2,3,n, (3) SF8 admits k−metric antidimension for four values of k∈1,2,4,8, and (4) for all n≥9, SFn admits k−metric antidimension for four values of k∈1,2,5,n.From all these results, it can be concluded that each considered wheel-related social graph isΔ−metric antidimensional.Furthermore, according to the computedk−metric antidimension of wheel-related social graphs, we investigated that each of them meets the k,l−anonymity in the following ways (skipping particular cases which can be observed straightforwardly).Wheel graph: forn≥6 and Δ=n and by Theorem 1, we have(65)k:123Δk−metric antidimension:2211k,l−anonymity:1,22,23,1Δ,1.Jahangir graph: forn≥5 and Δ=n and by Theorem 2, we have(66)k:123Δk−metric antidimension:2111k,l−anonymity:1,22,13,1Δ,1.Helm graph: forn≥7 and Δ=n and by Theorem 3, we have(67)k:1234Δk−metric antidimension:13211k,l−anonymity:1,12,33,24,1Δ,1.Flower graph: forn≥4 and Δ=2n and by Theorem 4, we have(68)k:1234Δk−metric antidimension:21211k,l−anonymity:1,22,13,24,1Δ,1.Sunflower graph: forn≥9 and Δ=n and by Theorem 5, we have(69)k:125Δk−metric antidimension:2111k,l−anonymity:1,22,13,1Δ,1.Thek,l−anonymity, measured on the base of k−metric antidimension for the maximum value of k=Δ, assures that a user can be reidentified with the probability less than or equal 1/Δ by a rival controlling only single attacker node ν in every considered wheel-related social graph. It is remarkably interesting to leave the following conjecture for the readers.Conjecture 1.
Each wheel-related social graph and generalizations of wheels areΔ−metric antidimensional and meet Δ,1−anonymity.



---

*Source: 8038253-2021-09-16.xml*