Electronic Journal of Graph Theory and Applications 13 .
, 217Ae230 Doubly resolving number of the corona product Mohsen Jannesari Department of Science.
Shahreza Campus.
University of Isfahan.
Iran jannesari@shr.
Abstract Two vertices u, v in a connected graph G are doubly resolved by vertices x, y of G if d.
, .
Oe d.
, .
= d.
, .
Oe d.
, .
A set W of vertices of the graph G is a doubly resolving set for G if every two distinct vertices of G are doubly resolved by some two vertices of W .
Doubly resolving number of a graph G, denoted by O(G), is the minimum cardinality of a doubly resolving set for G.
In this paper, using adjacency resolving sets and dominating sets of graphs, we study doubly resolving sets in the corona product of graphs G and H.
G Oo H.
First, we obtain the upper and lower bounds for the doubly resolving number of the corona product G Oo H in terms of the order of G and the adjacency dimension of H, then we present several conditions that make each of these bounds feasible for the doubly resolving number of G Oo H.
Also, for some important families of graphs, we obtain the exact value of the doubly resolving number of the corona product.
Keywords: doubly resolving sets, resolving sets, adjacency resolving sets, corona product, dominating sets Mathematics Subject Classification : 05C12.
05C69
DOI: 10.
5614/ejgta.
Introduction Throughout this paper all graphs are simple, finite and undirected.
The vertex set of a graph G is denoted by V (G).
We use G for the complement of the graph G.
In a connected graph G.
Received: 8 April 2023.
Revised: 24 October 2023.
Accepted: 23 July 2024.
Doubly resolving number of the corona product graphs Mohsen Jannesari the distance between two vertices u and v, denoted by dG .
, .
, is the length of a shortest path between u and v in G.
We write it simply d.
, .
, when no confusion can arise.
The diameter of G, denoted by diam(G) is max.
, .
: u, v OO V }.
If G has a cycle, then the length of a shortest cycle in G is called the girth of G and denoted by girth(G).
The degree of a vertex v, deg.
is the number of its neighbours.
A leaf in a graph is a vertex of degree 1.
A dominating set for a graph G is a subset D of V (G) such that every vertex in V (G) \ D is adjacent to at least one vertex in We use the notations Pn and Cn for a path of order n and a cycle of order n, respectively.
The join of graphs G and H, denoted by G H, is the graph with vertex set V (G) O V (H) and edge set E(G) O E(H) O .
v | u OO V (G), v OO V (H)}.
The wheel graph is Wn = K1 Cn and the fan graph is Fn = K1 Pn .
For an ordered subset W = .
1 , .
, wk } of V (G) and a vertex v of a connected graph G, the metric representation of v with respect to W is r.
W ) = .
, w1 ), .
, d.
, wk )).
The set W is a resolving set for G if the distinct vertices of G have different metric representations, with respect to W .
A resolving set W for G with minimum cardinality is a metric basis of G, and its cardinality is the metric dimension of G, denoted by dim(G).
During the study of the metric dimension of the cartesian product of graphs CaAceres et al.
defined the concept of doubly resolving sets in graphs.
Two vertices u, v in a connected graph G are doubly resolved by x, y OO V (G) if d.
, .
Oe d.
, .
= d.
, .
Oe d.
, .
A set W of vertices of the graph G is a doubly resolving set for G if every two distinct vertices of G are doubly resolved by some two vertices of W .
Every graph with at least two vertices has a doubly resolving set.
A doubly resolving set for G with minimum cardinality is called a doubly basis of G and its cardinality is called the doubly resolving number of G and denoted by O(G).
Note that if x, y doubly resolves u, v then d.
, .
Oe d.
, .
= 0 or d.
, .
Oe d.
, .
= 0, and at least one of x and y resolves u, v.
Hence a doubly resolving set is also a resolving set and dim(G) O O(G).
CaAceres et al.
obtained doubly resolving number of trees, cycles and complete graphs.
In .
it was proved that the problem of finding doubly bases is NP-hard.
Doubly resolving number of Prism graphs and Hamming graphs are computed in .
, respectively.
For more results about doubly resolving sets in graphs see.
, 8, 11, .
Doubly resolving sets play an essential role in obtaining the metric dimension of the Cartesian product of graphs.
This concept was introduced by CaAceres and his colleagues during the study of the metric dimension of the Cartesian product of graphs.
They proved that the metric dimension of the Cartesian product of two graphs is at most one unit less than the sum of the metric dimension of one of them and the doubly resolving number of the other.
After that, these concepts were noticed by many people.
One of the fields of work regarding each parameter in graph theory is to obtain that parameter for different products of graphs.
One of the products that has been studied a lot recently is the corona product of two graphs.
The corona product.
G Oo H of graphs G and H is obtained by taking one copy of G and n(G) copy of H, and by joining each vertex of the i-th copy of H to the i-th vertex of G, 1 O i O n(G).
It is clear that if G is a connected graph then G Oo H is also connected.
Many results about this product have been investigated for parameters related to resolving Doubly resolving number of the corona product graphs Mohsen Jannesari sets, including metric dimension .
, adjacency dimension .
, edge metric dimension .
, local metric dimension and local adjacency dimension of graphs .
Our goal in this paper is to study doubly resolving sets for the corona product of graphs.
achieve this goal, we use the concept of dominating sets in graphs.
First, we prove that for a connected graph G of order n and a non-trivial graph H n dim2 (H) O O(G Oo H) O n.
dim2 (H)).
then we find some properties for the graph H that leads us to satisfying each side of this inequality.
Also, this inequality implies that n O O(G Oo H) O nm, where m is the order of H.
All graphs H with O(G Oo H) = n.
O(G Oo H) = n.
Oe .
and O(G Oo H) = nm are determined in this paper.
Also, the exact value of O(G Oo H) for some families of graphs is computed.
One of our important tools in this paper is the concept of adjacency resolving set, which is defined by Jannesari and Omoomi .
In the end of this section, we present the definition of this Let G be a graph and W = .
1 , .
, wk } OI V (G).
For each vertex v OO V (G), the adjacency representation of v with respect to W is the k-vector r2 .
W ) = .
G .
, w1 ), .
, aG .
, wk )), where aG .
, wi ) = min.
, dG .
, wi )}.
1 O i O k.
The set W is an adjacency resolving set for G if the vectors r2 .
W ) for v OO V (G) are distinct.
The minimum cardinality of an adjacency resolving set is the adjacency dimension of G, denoted by dim2 (G).
An adjacency resolving set of cardinality dim2 (G) is an adjacency basis of G.
Preliminaries In this section we present some known or primary results that are necessary for our us to get the main results.
Observation 2.
To determine whether a given set W is a .
n adjacenc.
resolving set for G, it is sufficient to look at the .
metric representations of vertices in V (G)\W , because w OO W is the unique vertex of G for which dG .
, .
= 0.
G .
, .
= .
Proposition 2.
For every graph G, dim2 (G) = dim2 (G).
Let G be a graph of order n.
It is easy to see that, 1 O dim2 (G) O n Oe 1.
In the following proposition, all graphs G with dim2 (G) = 1 and all graphs of order n and adjacency dimension n Oe 1 are characterized.
Proposition 2.
If G is a graph of order n, then .
dim2 (G) = 1 if and only if G OO {P1 .
P2 .
P3 .
P 2 .
P 3 }.
dim2 (G) = n Oe 1 if and only if G = Kn or G = K n .
All graphs of order n and adjacency dimension nOe2 are characterized in the following theorem.
Theorem 2.
Let G be a graph of order n.
Then dim2 (G) = n Oe 2 if and only if G or G is one of the graphs P4 .
Ks,t .
, t Ou .
Ks K t .
Ou 1, t Ou .
, or Ks (Kt O K1 ) .
, t Ou .
Doubly resolving number of the corona product graphs Mohsen Jannesari Metric dimension of G Oo H has a closed relation with order of G and adjacency dimension of Theorem 2.
For any connected graph G of order n and any non-trivial graph H, dim(G Oo H) = n dim2 (H).
Lemma 2.
Let v be a leaf in a connected graph G.
Then v belongs to all doubly bases of G, and O(G) is bigger than or equal to the number of leaves in G.
By the following proposition and theorem.
If G is a path or a cycle then dim2 (G) = dim G K1 .
Proposition 2.
If n Ou 4, then dim2 (Cn ) = dim2 (Pn ) = UO 2n 2 UU.
Theorem 2.
, .
UU,
If n OO / .
, .
, then dim(Cn K1 ) = UO 2n 2 .
If n OO / .
, 2, 3, .
, then dim(Pn K1 ) = UO 2n 2 UU.
Clearly, every doubly resolving set is also a resolving set.
In the next proposition we consider resolving sets in G Oo H that are not doubly resolving set.
Proposition 2.
Let W be a resolving set for G Oo H.
If x, y OO V (G Oo H) are not doubly resolved by any pair of vertices in W , then exactly one of them belongs to V (G) and they are adjacent.
Proof.
We consider the following five cases for x and y.
Case 1: x, y OO V (G).
Let x = vi , y = vj for some i, j.
1 O i, j O n.
By Lemma 3.
2, there exist vertices ui OO W O Hi and uj OO W O Hj .
Thus d.
, ui )Oed.
, ui ) = 1Oe.
, .
) = Oed.
, .
= d.
, .
= 1 d.
, .
Oe1 = d.
, uj )Oed.
, uj ).
Therefore x, y are doubly resolved by ui and uj , which is impossible.
Case 2: x = vi OO V (G) and y OO V (Hj ) for some j = i.
By Lemma 3.
2, there exist vertices ui OO W O Hi and uj OO W O Hj .
Hence d.
, ui ) Oe d.
, ui ) = 1 Oe .
j , ui )) = 1 Oe .
j , vi )) = Oe.
j , vi )) O Oe2 d.
, uj ) Oe d.
, uj ) = 1 d.
, vj ) Oe d.
, uj ) Ou 2 Oe d.
, uj ) Ou 0.
Therefore x, y are doubly resolved by ui and uj , a contradiction.
Doubly resolving number of the corona product graphs Mohsen Jannesari Case 3: x OO V (Hi ), y OO V (Hj ) for some i = j.
By Lemma 3.
2, there exist vertices ui OO W O Hi and uj OO W O Hj .
Thus d.
, ui ) Oe d.
, ui ) = d.
, ui ) Oe .
j , ui )) = d.
, ui ) Oe .
j , vi )) O Oe1, because d.
, ui ) = aH .
, ui ) O 2 and i = j.
On the other hand d.
, uj ) Oe d.
, uj ) = 1 d.
i , uj ) Oe d.
, uj ) Ou 2 d.
i , vj ) Oe d.
, uj ) Ou 1.
because d.
, uj ) = aH .
, uj ) O 2 and i = j.
Therefore x, y are doubly resolved by ui and uj .
That is impossible.
Case 4: x, y OO V (Hi ), for some i.
Let j = i, by Lemma 3.
2, there exist vertices uj OO W O Hj and ui OO W O Hi such that aH .
, ui ) = aH .
, ui ).
Hence d.
, ui )Oed.
, ui ) = aH .
, ui )OeaH .
, ui ) = 0 = d.
, vj ) 1Oe.
, vj ) .
= d.
, uj )Oed.
, uj ).
Therefore x, y are doubly resolved by ui and uj , which is impossible.
These contradictions imply that the following case is the only case that can happen.
Case 5: x = vi and y OO V (Hi ), for some i.
Clearly x OO V (G) and y OO / V (G) and x, y are Doubly resolving sets in G Oo H Throughout this section G is a connected graph of order n and H is an arbitrary graph of order For convenience let V (G) = .
1 , v2 , .
, vn } and Hi be the i-th copy of H in G Oo H, i.
vertices of Hi are joined to vi in the graph G Oo H.
When H is the trivial graph K1 , the doubly resolving number of G Oo H is equal to the order of G.
Theorem 3.
For every connected graph G of order n Ou 2.
O(G Oo K1 ) = n.
Proof.
Let V (G) = .
1 , v2 , .
, vn } and .
i } be the vertex of the i-th copy of K1 in G Oo K1 .
Clearly every ui .
1 O i O n, is a leaf in G Oo K1 and by Lemma 2.
6, each ui belongs to every doubly basis of G Oo K1 .
That means O(G Oo K1 ) Ou n.
Now let W = .
1 , u2 , .
, un }.
We prove that W is a doubly resolving set for G Oo K1 .
For every i, j.
1 O i = j O n we have d.
i , ui ) Oe d.
j , ui ) = Oed.
j , ui ) = d.
i , uj ) Oe d.
j , uj ), d.
i , ui ) Oe d.
j , ui ) = Oed.
j , vi ) = d.
j , vi ) = d.
i , uj ) Oe d.
j , uj ).
Also, for every i, j.
1 O i, j O n, d.
i , ui ) Oe d.
j , ui ) = 1 Oe d.
j , ui ) = Oed.
i , uj ) = d.
i , uj ) = d.
i , uj ) Oe d.
j , uj ).
Therefore W is a doubly resolving set for G Oo K1 and O(G Oo K1 ) = n.
Doubly resolving number of the corona product graphs Mohsen Jannesari Now we consider O(G Oo H) for graphs G and H of order at least 2.
Lemma 3.
If W is a resolving set for GOoH, then W OV (Hi ).
1 O i O n, contains an adjacency resolving set for Hi .
Proof.
Let x, y OO V (Hi ).
Clearly for every vertex v OO V (G Oo H) \ V (Hi ) we have d.
, .
= d.
, .
Therefore W must contain a vertex of Hi to resolve x, y.
But dGOoH .
, .
= aHi .
, .
Hence W contains an adjacency resolving set for Hi .
Through the following two theorems we will prove that O(G Oo H) is n dim2 (H) or n.
dim2 (H)), where n is the order of G.
Theorem 3.
Let H have an adjacency basis which is also a dominating set.
Then for every connected graph G of order n O(G Oo H) = n dim2 (H).
Proof.
Since every doubly resolving set is a resolving set, by Theorem 2.
5, we have O(G Oo H) Ou n dim2 (H).
ForSevery i.
1 O i O n, let Bi be an adjacency basis of Hi which is also a dominating set.
Let W = ni=1 Bi .
By Theorem 2.
5 and Lemma 3.
W is a basis of G Oo H.
If there exist vertices x, y OO V (G Oo H) that are not doubly resolved by W , then by Proposition 2.
9, exactly one of them belongs to V (G) and they are adjacent.
Therefor by symmetry, there exists i.
1 O i O n, such that x = vi and y OO V (Hi ).
Since Bi is a dominating set for Hi , there exits a vertex ui OO Bi = W O Hi such that d.
, ui ) O 1.
Clearly ui is adjacent to x = vi .
Let j = i and uj OO W O Hj .
Hence d.
, ui ) Oe d.
, ui ) = 1 Oe d.
, ui ) Ou 0 > Oe1 = d.
, uj ) Oe .
, uj )) = d.
, uj ) Oe d.
, uj ).
Therefore W is a doubly resolving set for G Oo H with cardinality n dim2 (H).
Theorem 3.
If no adjacency basis of H is a dominating set, then for every connected graph G of order n O(G Oo H) = n.
dim2 (H)).
Proof.
Since every doubly resolving set is a resolving set.
Lemma 3.
2 implies that every doubly resolving set for G Oo H contains an adjacency resolving set of each Hi .
1 O i O n.
But by the assumption every adjacency basis Bi of Hi is not a dominating set and so there is a vertex ti OO V (Hi ) \ Bi that is not adjacent to any vertex of Bi .
Hence for each ui OO Bi we have d.
i , ui ) Oe d.
i , ui ) = 1.
Moreover, for all vertices v OO V (G Oo H) \ V (Hi ), we have d.
i , .
Oe d.
i , .
= 1.
Therefore every doubly resolving set for G Oo H contains at least dim2 (H) 1 vertices from each Hi .
This means O(G Oo H) Ou n.
dim2 (H)).
Now we obtain a doubly resolving set for G Oo H with cardinality n.
dim2 (H)).
For each i, let Bi be an adjacency basis of Hi and ti OO V (Hi ) \ Bi be the vertex that does not have any adjacent in BiS Since Bi is an adjacency basis, ti is unique.
Thus Bi O .
i } is a dominating set for Hi .
Set W = ni=1 (Bi O .
i }).
By Theorem 2.
5 and Lemma 3.
W is a resolving set for G Oo H.
there exist vertices x, y OO V (G Oo H) that are not doubly resolved by W , then by Proposition 2.
exactly one of them belongs to V (G) and they are adjacent.
Therefore by symmetry, there exists Doubly resolving number of the corona product graphs Mohsen Jannesari i, such that x = vi and y OO V (Hi ).
Since Bi O .
i } is a dominating set for Hi , there exits a vertex ui OO Bi O .
i } = W O Hi such that d.
, ui ) O 1.
Clearly ui is adjacent to x = vi .
Let j = i and uj OO W O Hj .
Hence d.
, ui ) Oe d.
, ui ) = 1 Oe d.
, ui ) Ou 0 > Oe1 = d.
, uj ) Oe .
, uj )) = d.
, uj ) Oe d.
, uj ).
Therefore W is a doubly resolving set for G Oo H with cardinality n.
dim2 (H)).
Theorems 3.
3 and 3.
4 imply the following corollary.
Corollary 3.
Let G be a connected graph of order n Ou 2 and H be a non-trivial graph.
Then n dim2 (H) O O(G Oo H) O n.
dim2 (H)).
To find that O(G Oo H) is which one of n dim2 (H) or n.
dim2 (H), we need to know that is there an adjacency basis for H that is also a dominating set.
In the following, we investigate the conditions that provide this property.
Definition 3.
Let W be a subset of V (G), a vertex v OO V (G) \ W is called a dominant vertex for W if v is adjacent to all vertices of W .
Clearly an adjacency basis B for H is a dominating set for H if and only if there is no dominant vertex for B in H.
Therefore we have the following corollary.
Corollary 3.
Let G be a connected graph of order n Ou 2 and H be a non-trivial graph.
If H has an adjacency basis B such that there is not any dominant vertex for B in V (H) \ B, then O(G Oo H) = n dim2 (H).
If for every adjacency basis of H there exists a dominant vertex in V (H), then O(G Oo H) = n.
im2 (H) .
Clearly every adjacency basis of Kr,s .
r, s Ou 2, is a dominating set and there is no dominant vertex for any adjacency basis of Kr,s .
Also note that every adjacency basis of Km .
m Ou 2, is a dominating set and there is a dominant vertex for every adjacency basis of Km .
Thus we have the following observation.
Observation 3.
Let G be a connected graph of order n Ou 2.
For every r, s Ou 2 we have O(G Oo Kr,s ) = O(G Oo Kr,s ) = n.
s Oe .
For every m Ou 2 we have O(G Oo Km ) = n.
Oe .
and O(G Oo Km ) = nm.
The next two propositions specify the conditions under which the path.
Pm , and cycle.
Cm , have an adjacency basis that is also a dominating set.
Proposition 3.
Let m = 5k r, k Ou 1 and 0 O r O 4.
Then Pm has an adjacency basis that is a dominating set, if and only if r is even.
Doubly resolving number of the corona product graphs Mohsen Jannesari Proof.
We use induction on k.
Basis step: If k = 1, then 5 O n O 9 and by checking each case, the claim is true.
Induction step: k > 1.
Assume the claim for k Oe 1.
Let V (Pm ) = .
1 , v2 , .
, vm }, where vi is adjacent to vi 1 for all i.
1 O i O m Oe 1, and H be the induced subgraph v6 , v7 , .
, vm of Pm .
If r is even, then by the induction hypothesis, there exists an adjacency basis B for H which is a dominating set for H.
By Proposition 2.
7, dim2 (H) = dim2 (Pm ) Oe 2.
Now let W = B O .
2 , v4 }.
Clearly W is a dominating set for Pm and |W | = dim2 (Pm ).
Note that r2 .
1 |.
2 , v4 }) = .
, .
, r2 .
3 |.
2 , v4 }) = .
, .
, r2 .
5 |.
2 , v4 }) = .
, .
and for every vertex v of H we have r2 .
2 , v4 }) = .
, .
Therefore W is an adjacency basis of G that is also a dominating set.
If r is odd, suppose on the contrary that Pm has an adjacency basis B that is also a dominating Clearly |B O .
1 , v2 , .
, v5 }| Ou 2, otherwise the adjacency representations of some vertices in .
1 , v2 , .
, v5 } with respect to B are the same.
Since B is a dominating set.
B A = B O V (H) is an adjacency resolving set for H.
By Proposition 2.
7, dim2 (H) = dim2 (Pm ) Oe 2, hence B A is an adjacency basis for H and |B O .
1 , v2 , .
, v5 }| = 2.
By induction hypothesis B A is not a dominating set for H.
Since B is a dominating set and B A is not a dominating set, v6 has no neighbour in B A .
That means v6 , v7 OO / B and v5 OO B.
Thus |B O .
1 , v2 , .
, v4 }| = 1.
Since B is a dominating set we have v2 OO B.
Therefore r2 .
4 |B) = r2 .
6 |B).
This contradiction implies that B is not a dominating set for Pm .
Proposition 3.
Let m = 5k r, k Ou 1 and 0 O r O 4.
Then Cm has an adjacency basis that is a dominating set, if and only if r is even.
Proof.
Let V (Cm ) = .
1 , v2 , .
, vm }, where vi is adjacent to vi 1 for all i.
1 O i O m Oe 1, and v1 is adjacent to vm .
First, let r be an even number.
Suppose that H is the resulting graph from Cm by removing the edge between v1 and vm .
Clearly H is a path on m vertices.
Proposition 3.
9 implies that H has an adjacency basis B that is also a dominating set for H.
If |B O .
1 , vn }| OO .
, .
, then for every v OO .
1 , v2 , .
, vm } \ B the adjacency representations of v with respect to B in graphs Cm and H are the same.
Hence B is an adjacency basis for Cm that is also a dominating If |B O .
1 , vn }| = 1, say vn OO B.
If r2 .
B) = r2 .
B) for some u, v OO V (Cm ) \ B, then .
, .
= .
1 , vnOe1 }.
Since B is a dominating set for H, v2 must be in B.
Since m Ou 5, we have aCm .
1 , v2 ) = aCm .
nOe1 , v2 ).
Hence r2 .
1 |B) = r2 .
nOe1 |B).
Therefore B is an adjacency basis for Cm that is also a dominating set.
If r is odd, suppose on the contrary that Cm has an adjacency basis B that is also a dominating By Proposition 2.
7, there exist two adjacent vertices vi , vi 1 OO V (Cm )\B, otherwise UO 2m 2
UU=
|B| Ou UO 2 UU > UO 5 UU.
By removing the edge vi vi 1 we get a graph H that is a path on m Clearly B is an adjacency basis for H that is also a dominating set.
This contradicts Proposition 3.
Now we can obtain O(G Oo H) when H or H is a path or a cycle.
Proposition 3.
Let G be a connected graph of order n Ou 2 and H OO {Pm .
Cm }, m = 5k r, where k Ou 1 and 0 O r O 4.
UU.
If r is even, then O(G Oo H) = O(G Oo H) = nUO 2m 2 Doubly resolving number of the corona product graphs Mohsen Jannesari .
If m = 6, then O(G Oo H) = O(G Oo H) = n(UO 2m 2 UU .
If r is odd and m = 6, then O(G Oo H) = n(UO 2m 2 UU .
and O(G Oo H) = nUO 2m 2 UU.
Proof.
If r is even, then Propositions 3.
9 and 3.
10 imply that H has an adjacency basis that is also a dominating set.
Hence, by Theorem 3.
3 and Proposition 2.
O(G Oo H) = UU.
If m > 5, then Proposition 2.
7 yields dim2 (H) Ou 3.
Let B n dim2 (H) = nUO 2m 2 be an adjacency basis for H.
Since the degree of each vertex of H is at most 2 there is no dominant vertex for B in H.
Thus by Corollary 3.
7 and Proposition 2.
7 we have UU.
for m = 5 it is easy to see that there exists an adO(G Oo H) = n dim2 (H) = nUO 2m 2 jacency basis for H such that there is no dominant vertex for it in H.
Therefore by a same argument as in the case m > 5, we have O(G Oo H) = n dim2 (H) = nUO 2m 2 UU.
if m = 6, it is easy to see that every adjacency basis B of H is not a dominating set and there is a dominant vertex for B in H.
Therefore Theorem 3.
4 and Corollary 3.
7 imply that UU .
O(G Oo H) = O(G Oo H) = n.
im2 (H) .
= n(UO 2m 2 .
If r is odd and m = 6, then Propositions 3.
9 and 3.
10 imply that no adjacency basis of H is a dominating set, and by Theorem 3.
4 and Proposition 2.
O(G Oo H) = n.
im2 (H) .
= n(UO 2m 2 UU .
On the other hand, by Proposition 2.
7 we have dim2 (H) Ou 3 and so there is no dominant vertex for B in H, because the degree of each vertex of H is at most 2.
Thus UU.
Corollary 3.
7 and Proposition 2.
7 imply O(G Oo H) = n dim2 (H) = nUO 2m 2 In the following, we investigate the relations between O(G Oo H) and some parameters of the graph H or H such as maximum degree, minimum degree, diameter and girth.
The first result is about maximum and minimum degree.
Lemma 3.
Let H be a non-trivial graph of order m, maximum degree OI(H) and minimum degree (H).
If dim2 (H) > OI(H), then there is no dominant vertex for any adjacency basis of H.
If (H) Ou m Oe dim2 (H), then every adjacency basis of H is a dominating set.
Proof.
Let dim2 (H) > OI(H) and B be an adjacency basis of H.
If there is a dominant vertex x for B, then x is adjacent to all vertices in B.
Therefore deg.
Ou dim2 (H) > OI(H), which is a contradiction.
Let (H) > m Oe dim2 (H) and B be an adjacency basis of H.
If B is not a dominating set for H, then there exists a vertex x OO V (H) \ B such that x is not adjacent to any member of B.
Therefore deg.
O m Oe 1 Oe dim2 (H) < (H), which is impossible.
Corollary 3.
Let G be a connected graph of order m Ou 2 and H be a non-trivial graph of order m, maximum degree OI(H) and minimum degree (H).
Doubly resolving number of the corona product graphs Mohsen Jannesari .
If dim2 (H) > OI(H), then O(G Oo H) = n dim2 (H).
If (H) Ou m Oe dim2 (H), then O(G Oo H) = n dim2 (H).
The next proposition express some conditions on diameter of H those are enough for existence of an adjacency basis with no dominant vertex for it.
Proposition 3.
Let H be a graph such that for each adjacency basis of H there exists a dominant vertex.
If there exists an adjacency basis for H that is also a dominating set, then diam(H) O 4.
If any adjacency basis of H is not a dominating set, then diam(H) O 5.
Proof.
Suppose that B is an adjacency basis for H that is also a dominating set.
Let b be a dominant vertex for B.
Hence every two vertices of B are at distance at most 2.
Since B is a dominating set, every vertex of V (H) \ B has a neighbour in B.
Therefor the distance between two of them is at most 4.
Hence diam(H) O 4.
Let B be an adjacency basis of H and b be a dominant vertex for B.
Since B is not a dominating set, there exists a vertex v OO V (H) \ B such that v is not adjacent to any vertex in B.
But each neighbour of v has a neighbour in B, because B is an adjacency basis.
Therefore diam(H) O 5.
The following proposition specify some conditions on girth of H those are enough for existence of an adjacency basis with no dominant vertex for it.
Proposition 3.
Let H be a graph such that has a cycle and for each adjacency basis of H there exists a dominant vertex.
If there exists an adjacency basis for H that is also a dominating set, then girth(H) O 5.
If any adjacency basis of H is not a dominating set, then girth(H) O 6.
Proof.
Suppose that B is an adjacency basis for H that is also a dominating set.
Let b be a dominant vertex for B.
Hence every two vertices of B are at distance at most 2.
If there exists an edge between two vertices in B, then the ends of this edge along with b makes a Now let there is no edge between any two vertices in B.
Let C be a cycle in H with girth(H) vertices.
Therefore C has a vertex u in V (H) \ (B O .
Since B is a dominating set, every vertex of V (H) \ B has a neighbour in B.
If u is adjacent to at least two vertices of B O .
then girth(H) O 4.
Otherwise u has a neighbour uA out of B O .
Since uA has a neighbour in B we have girth(H) O 5.
Let B be an adjacency basis of H and b be a dominant vertex for B.
Since B is not a dominating set, there exists a vertex v OO V (H) \ B such that v is not adjacent to any vertex in B.
If there exists an edge between two vertices in B, then the ends of this edge and b Doubly resolving number of the corona product graphs Mohsen Jannesari makes a cycle.
Now let there is no edge between any two vertices in B.
Let C be a cycle in H with girth(H) vertices.
If v OO / V (C) then similar to previous case we have girth(H) O 5.
Now let v OO V (C) and u, uA be neighbours of v on C.
Clearly u, uA are not in B.
Since B is an adjacency basis, every vertex of V (H) \ B has a neighbour in B.
Therefore u, uA has neighbours in B and so girth(H) O 6.
Propositions 3.
14 and 3.
15 conclude the following corollary.
Corollary 3.
If H is a graph such that diam(H) > 5 or girth(H) > 6, then for every connected graph G of order n, we have O(G Oo H) = n dim2 (H).
The join of the graph K1 with another graph is an interesting graph.
In the following we investigate adjacency bases of K1 H.
Proposition 3.
Let H be a graph.
Then for every adjacency basis of K1 H there exists a dominant vertex.
Proof.
Suppose on the contrary that there exists an adjacency basis B of K1 H with no dominant Let v be the vertex of K1 in K1 H.
Clearly v OO B, otherwise v is a dominant vertex for B.
Hence B A = B \ .
is not an adjacency resolving set for K1 H.
Note that for every vertices x, y OO V (K1 H) \ .
we have, r2 .
B) = r2 .
B) if and only if r2 .
B A ) = r2 .
B A ).
Therefore, there exists a vertex u OO V (K1 H) \ B such that r2 .
B A ) = r2 .
B A ) = .
, 1, .
, .
Hence r2 .
B) = .
, 1, .
, .
and so u is a dominant vertex for B, which is a contradiction.
Corollary 3.
For every connected graph G of order n and arbitrary graph H.
O(G Oo K1 H) = n.
im2 (K1 H) .
In the following Proposition we compute O(G Oo H) and O(G Oo H), where H is a wheel or a fan graph of order at least 7.
Proposition 3.
Let G be a connected graph of order n Ou 2 and H OO {Wm .
Fm }, m = 5k r, where m Ou 7 and 0 O r O 4.
If r is even, then O(G Oo H) = nUO 2m 2 UU.
If r is odd, then O(G Oo H) = n(UO 2m 2 UU .
O(G Oo H) = n(UO 2m 2 UU .
Proof.
By Theorem 2.
8, dim(H) = UO 2m 2 UU.
Since the diameter of H is two we have dim(H) = dim2 (H).
Proposition 2.
7 implies that dim2 (H) = dim2 (Pm ) = dim2 (Cm ) = UO 2m 2 UU.
Doubly resolving number of the corona product graphs Mohsen Jannesari .
Since r is even.
Proposition 3.
9 implies that there exists an adjacency basis B for Pm that is also a dominating set.
By Proposition 2.
7, |B| Ou 3.
Hence, there is no dominant vertex for B in Pm , because the degree of every vertex of Pm is at most 2.
Now consider B as a subset of V (Fm ), thus for every x, y OO V (Pm ) we have aPm .
, .
= aFm .
, .
Therefore for a vertex v OO V (Pm ), the adjacency representation of v, as a vertex of Pm , with respect to B is the same as its adjacency representation of v, as a vertex of Fm , with respect to B.
Also, the adjacency representation of u OO V (Fm ) \ V (Pm ) is .
, 1, .
, .
Since there is no dominant vertex for B in Pm , the adjacency representation of u is different from all other vertices of Fm .
Hence.
B is an adjacency resolving set for Fm .
Since dim2 (Fm ) = dim2 (Pm ).
B is an adjacency basis for Fm .
Note that B is also a dominating set for Fm .
Therefore, by UU.
For H = Wm , the proof is Theorem 3.
3 we have O(G Oo Fm ) = n dim2 (Fm ) = nUO 2m 2 the same.
Let B be an adjacency basis of Fm .
Note that for every x, y OO V (Pm ) we have aPm .
, .
= aFm .
, .
Therefore B is an adjacency resolving set for Pm .
dim2 (Fm ) = dim2 (Pm ) concludes that B is an adjacency basis for Pm .
Proposition 3.
9 implies that B is not a dominating set for Pm , because r is odd.
Since for every x, y OO V (Pm ) we have aPm .
, .
= aFm .
, .
B is not a dominating set for Fm .
Therefor, by Theorem 3.
4 we have O(GOoFm ) = UU .
If H = Wm , the proof is the same.
im2 Fm .
= n(UO 2m 2 .
It immediately comes from Corollary 3.
Let G be a connected graph of order n Ou 2 and H be a non-trivial graph of order m.
Corollary 3.
5 concludes n dim2 (H) O O(G Oo H) O n.
im2 (H) .
Since 1 O dim2 (H) O m Oe 1, we have 1 O O(G Oo H) O nm.
The following theorem determines all graph H that O(G Oo H) gets one of the numbers n, n.
Oe .
or nm.
Theorem 3.
Let G be a connected graph of order n and H be an arbitrary graph of order m.
Then .
O(G Oo H) = n if and only if H is P1 or P2 .
O(G Oo H) = nm if and only if H = Km .
O(G Oo H) = n.
Oe .
if and only if H is one of the following graphs Km .
Ou .
K1,t .
Ou .
K1,t .
Ou .
Ks Kt .
, t Ou .
Ks (Kt O K1 ) .
, t Ou .
Proof.
By Corollary 3.
5 we have n dim2 (H) O O(G Oo H) O n.
im2 (H) .
If O(G Oo H) = n, then Inequality 1 implies that dim2 (H) = 1.
Hence.
Theorem 2.
3 concludes that H OO {P1 .
P2 .
P3 .
P 2 .
P 3 }.
If H OO {P3 .
P 2 .
P 3 }, then there is no adjacency basis for H that is also a dominating set and by Theorem 3.
O(G Oo H) = 2n.
On the other hand by Theorem 3.
O(G Oo P2 ) = n and by Theorem 3.
O(G Oo P1 ) = n.
Doubly resolving number of the corona product graphs Mohsen Jannesari .
If O(G Oo H) = nm, then Inequality 1 implies that dim2 (H) = m Oe 1, because dim2 (H) O m Oe 1.
Hence.
Theorem 2.
3 concludes that H OO {Km .
Km }.
Since every adjacency basis of Km is a dominating set.
Theorem 3.
3 yields O(G Oo Km ) = n.
Oe .
On the other hand for every adjacency basis of Km there exists a dominant vertex, thus by Corollary 3.
7 we have O(G Oo Km ) = nm.
Let O(G Oo H) = n.
Oe .
Since dim2 (H) O m Oe 1.
Inequality 1 implies that dim2 (H) OO .
Oe 2, m Oe .
If dim2 (H) = m Oe 1, then part .
of this proposition yields H = Km .
On the other hand O(G Oo Km ) = n.
Oe .
, because every adjacency basis of Km is a dominating set.
If dim2 (H) = m Oe 2, then Theorem 2.
3 implies that H or H is one of the graphs P4 .
Ks,t .
, t Ou .
Ks K t .
Ou 1, t Ou .
, or Ks (Kt O K1 ) .
, t Ou .
It is easy to see that if H is one of the graphs P4 .
Ks,t .
, t Ou .
Ks K t .
, t Ou .
Ks (Kt O K1 ) .
, t Ou .
, then there exists an adjacency basis for H that is a dominating set.
Therefore.
Theorem 3.
concludes that O(G Oo H) = n.
Oe .
Also if H is one of the graphs P4 or Ks,t .
, t Ou .
, then there is an adjacency basis for H that there is no dominant vertex for it.
Hence.
Corollary 3.
7 implies that O(G Oo H) = n.
Oe .
If H is one of the graphs Km .
Ou .
K1,t .
Ou .
K1,t .
Ou .
Ks Kt .
, t Ou .
Ks (Kt O K1 ) .
, t Ou .
, then no adjacency basis of H is a dominating set and by Theorem 3.
3 we have O(G Oo H) = n.
Oe .
Data Availability All data generated or analysed during this study are included in this article.
Conflicts of Interest The author declare no conflict of interest.
References