# On Self-Centeredness of Product of Graphs

Authors: Priyanka Singh; Pratima Panigrahi
Journal: International Journal of Combinatorics
 (2016)

---

## Abstract

A graphG is said to be a self-centered graph if the eccentricity of every vertex of the graph is the same. In other words, a graph is a self-centered graph if radius and diameter of the graph are equal. In this paper, self-centeredness of strong product, co-normal product, and lexicographic product of graphs is studied in detail. The necessary and sufficient conditions for these products of graphs to be a self-centered graph are also discussed. The distance between any two vertices in the co-normal product of a finite number of graphs is also computed analytically.


---

## Body

## 1. Introduction

The concept of self-centered graphs is widely used in applications, for example, the facility location problem. The facility location problem is to locate facilities in a locality (network) so that these facilities can be used efficiently. All graphs in this paper are simple and connected graphs. Thedistance between two vertices u and v in a graph G, denoted by dG(u,v) (or simply d(u,v)), is the minimum length of u-v path in the graph. Theeccentricity of a vertex v in G, denoted by eccG(v), is defined as the distance between v and a vertex farthest from v; that is, eccG(v)=max⁡{dG(v,u):u∈V(G)}. The radius rad⁡(G) and diameter diam⁡(G) of the graph G are, respectively, the minimum and maximum eccentricity of the vertices of graph G; that is, rad⁡(G)=min{ecc(v):v∈V(G)} and diam⁡(G)=max⁡{ecc(v):v∈V(G)}. The center C(G) of graph G is the induced subgraph of G on the set of all vertices with minimum eccentricity. A graph G is said to be aself-centered graph if the eccentricity of every vertex is the same; that is, C(G)=G or rad⁡(G)=diam⁡(G). If the eccentricity of every vertex is equal to d, then G is called d-self-centered graph.For any kind of graph productG of the graphs G1,G2,…,Gn, the vertex set is taken as V(G)={(x1,x2,…,xn):xi∈V(Gi)}. Because of their adjacency rules, product names are different. Let x=(x1,…,xn) and y=(y1,…,yn) be two vertices in V(G). Then the product is called(i)
Cartesian  product, denoted by G=G1□G2□⋯□Gn, where x~y if and only if xiyi∈E(Gi) for exactly one index i, 1≤i≤n, and xj=yj for each index j≠i,(ii)
strong  product, denoted by G=G1⊠⋯⊠Gn, where x~y if and only if xiyi∈E(Gi) or xi=yi, for every i, 1≤i≤n,(iii)
lexicographic  product, denoted by G=G1∘⋯∘Gn, where x~y if and only if, for some j∈{1,2,…,n},xjyj∈E(Gj) and xi=yi for each 1≤i<j,(iv)
co-normal  product, denoted by G=G1∗G2∗⋯∗Gn, where x~y if and only if xi~yi for some i∈{1,2,…,n}. Self-centered graphs have been broadly studied and surveyed in [1–3]. In [4], the authors described several algorithms to construct self-centered graphs. Stanic [5] proved that the Cartesian product of two self-centered graphs is a self-centered graph. Inductively, one can prove that Cartesian product of n-self-centered graphs is also a self-centered graph.In this paper, we find conditions for self-centeredness of strong product, co-normal product, and lexicographic product of graphs.


## 2. Main Results

In this section, we will discuss the self-centeredness of different types of product graphs. As mentioned before, all graphs considered here are simple and connected. The following result is given by Stanic [5].Theorem 1.
IfG1 and G2 are m- and n-self-centered graphs, respectively, then G1□G2 is (m+n)-self-centered graph. Reciprocally, if G1□G2 is self-centered, then both graphs G1 and G2 are self-centered.By method of induction, one can extend the above theorem and get the result given below.Theorem 2.
LetG=G1□G2□⋯□Gn be the Cartesian product of graphs G1,G2,…,Gn. If every Gi is di-self-centered graph, then G is m-self-centered graph, where m=∑i=1ndi, 1≤i≤n. Conversely, if G is a self-centered graph, then every Gi is a self-centered graph.Next we will discuss self-centeredness of strong product of graphs.Theorem 3.
LetG=G1⊠⋯⊠Gn be the strong product of graphs G1,G2,…,Gn. Then G is d-self-centered graph if and only if, for some k∈{1,…,n}, Gk is d-self-centered graph and diam⁡(Gi)≤d for every i, 1≤i≤n.Proof.
For any two verticesx=(x1,…,xn) and y=(y1,…,yn), the distance between them is given in [6]: (1)dx,y=max1≤i≤n⁡dGixi,yi. Now, the eccentricity of any vertex x of G is given by (2)eccx=max⁡dx,y:y∈VG=max⁡max1≤i≤ndGixi,yi:y∈VG,where x=(x1,…,xn) and y=(y1,…,yn).
First, letGk be d-self-centered graph for some k∈{1,2,…,n} and diam⁡(Gi)≤d for all i, 1≤i≤n. Since Gk is d-self-centered, ecc(xk)=d and there exists some yk in Gk such that d(xk,yk)=d. As diam⁡(Gi)≤d for all i, 1≤i≤n, the distance between any two vertices in any Gi cannot exceed d. Hence, ecc(x)=d for all x∈V(G) and thus G is d-self-centered graph.
Conversely, letG be a d-self-centered graph. If, for some l∈{1,…,n}, diam⁡(Gl)=dl>d, then there exist vertices xl and yl in Gl such that d(xl,yl)=dl. Now for x=(x1,…,xl,…,xn) and y=(y1,…,yl,…,yn) in V(G), d(x,y)≥d(xl,yl)=dl>d and so ecc(x)≥dl>d. This contradicts the fact that G is d-self-centered graph and thus it is proven that diam⁡(Gi)≤d for all i. Now, our claim is that there exists k∈{1,…,n} such that Gk is d-self-centered graph. On the contrary, suppose that none of Gi is d-self-centered graph. Then there exist vertices xi∈V(Gi) for all i such that ecc(xi)=di<d. Let x=(x1,…,xn). Then ecc(x)=max1≤i≤n⁡{di}<d, which contradicts the fact that G is d-self-centered graph.In the following lemma, we determine the formula for the distance between two vertices in the co-normal product of a finite number of graphs.Lemma 4.
LetG=G1∗G2∗⋯∗Gn be the co-normal product of graphs G1,G2,…,Gn. The distance between x=(x1,…,xn) and y=(y1,…,yn) in G is(3)dx,y=1ifxi~yiforsomei∈1,2,…,ndxi,yiifGj=K1,∀j≠i2ifx≁y,xl≠ylforexactlyoneindexlandGj≠K1forsomej≠l2ifx≁yand∃atleasttwoindicesk,ls.t.xk≠ykandxl≠yl.Proof.
Consider two verticesx=(x1,…,xn) and y=(y1,…,yn) of G. If, for some i∈{1,2,…,n}, xi~yi, then by the definition of co-normal product x~y and thus d(x,y)=1.
Next, letGj=K1 for all j≠i. In this case, for any path P between x and y, every adjacent pair of vertices in P differ only in the ith coordinate. So d(x,y)=d(xi,yi). For the third option of the distance formula, we have vertices x and y as x=(x1,x2,…,xl,…,xj,…,xn) and y=(x1,x2,…,yl,…,xj,…,xn) such that xl≠yl and Gj≠K1 for some j≠l. Since Gj is connected graph, there exists a vertex zj∈V(Gj) such that xj~zj and thus we get a vertex z=(x1,x2,…,xl,…,zj,…,xn)∈G such that x~z and z~y (because xj=yj) and xzy is a path of length two and hence d(x,y)=2.
Finally, consider the case, where, for at least two indicesk and l, xk≠yk and xl≠yl; that is, for at least two indices k and l, Gk≠K1 and Gl≠K1. Since x≁y, xk≁yk, and xl≁yl, then from the connectivity of graphs Gk and Gl there exist vertices zk∈V(Gk) and zl∈V(Gl) such that zk~xk in Gk and zl~yl in Gl. Then we have a vertex z=(x1,…,zk,…,zl,…,xn)∈V(G) such that x~z and z~y. Thus xzy will be an x-y path of length two and this proves that d(x,y)=2.The following theorem gives necessary and sufficient conditions for a co-normal product of graphs to be a self-centered graph.Theorem 5.
LetG=G1∗G2∗⋯∗Gn be the co-normal product of graphs G1,G2,…,Gn with VGi=ni. Then the following hold:(i)
LetGi≠K1 and Gj=K1 for all j≠i. Then G is d-self-centered graph if and only if Gi is d-self-centered graph.(ii)
Let there be at least two values ofi such that Gi≠K1. Then G is 2-self-centered graph if and only if there exists an index l such that Δ(Gl)≠nl-1, where Δ(G) is the maximum degree of a vertex in G.Proof.
(i) The result is true becauseG is isomorphic to Gi in this case through the isomorphism (4)f:VG⟶VGi with f(x1,…,xi,…,xn)=xi.
(ii) LetG be a 2-self-centered graph. If, for all the indices i, Δ(Gi)=ni-1, then there are vertices xi∈V(Gi), 1≤i≤n, such that deg⁡(xi)=ni-1. Now, the vertex x=(x1,x2,…,xn), ecc(x)=1, which contradicts the fact that G is 2-self-centered graph. Hence there exists an index l such that Δ(Gl)≠nl-1.
Conversely, let there be an indexl such that Δ(Gl)≠nl-1. Then for any vertex x=(x1,x2,…,xl,xl+1,…,xn) in G there exists another vertex y=(x1,x2,…,yl,xl+1,…,xn), where yl∈V(Gl) and xl≁yl. Since x≁y, from the third option of the distance formula given in Lemma 4, ecc(x)=2. Since x is an arbitrary vertex, G is 2-self-centered graph.In the following two theorems, we discuss self-centeredness of lexicographic product of graphs.Theorem 6.
LetG=G1∘G2∘⋯∘Gn be the lexicographic product of graphs G1,G2,…,Gn and let k≥1 be the smallest index for which Gk≠K1. If Gk is d-self-centered graph, where d≥2, then G is d-self-centered graph. The converse is true for d≥3.Proof.
For verticesx=(x1,…,xn) and y=(y1,…,yn) of G, the following distance formula is due to Hammack et al. [6]:(5)dx,y=dG1x1,y1ifx1≠y1dGixi,yiifdGlxl=0∀1≤l<imin⁡dGixi,yi,2ifdGlxl≠0for  some1≤l<i,where i is the smallest index for which xi≠yi.
LetVGi=1 for i=1,2,…,k-1 and let Gk be d-self-centered graph, where d≥2. First let k=1. Since VG1>1,  G1 is connected and degree of no vertex in G1 is zero; then the second option in the distance formula will not arise. Then the above formula to calculate the distance reduces to(6)dx,y=dG1x1,y1ifi=1min⁡dGixi,yi,2ifi≥2,where i is the smallest index for which xi≠yi. For i≥2, let r=min{dGi(xi,yi),2}. Then r≤2. Since d≥2, we get r≤d. Now, for x∈V(G),(7)eccx=max⁡dx,y:y∈VG=max⁡dG1x1,y1,r:y1∈VG1=d,because ecc(x1)=d and there exists y1∈G1 such that d(x1,y1)=d. This proves that ecc(x)=d for all x∈V(G) and hence G is a d-self-centered graph.
Next, letk>1. Since VG1=1, there is no y1∈G1 such that x1≠y1. So, first option in the distance formula will not arise. Since the degree of the vertex in Gj for j=1,2,…,k-1 is zero, if i=k in the above distance formula then d(x,y)=dGk(xk,yk). Since Gk≠K1 and is connected deg⁡(xk)≠0. So if i≥k+1 in the above formula, d(x,y)=min⁡{dGi(xi,yi),2} and thus the above formula to calculate the distance reduces to(8)dx,y=dGkxk,ykifi=kmin⁡dGixi,yi,2ifi≥k+1,where i is the smallest index for which xi≠yi. For i≥k+1 let r1=min⁡{dGi(xi,yi),2}. Then r1≤2. Since d≥2, we get r1≤d. Thus, for any vertex x∈V(G), we have(9)eccx=max⁡dx,y:y∈VG=max⁡dGkxk,yk,r1:yk∈VGk=d.This proves that ecc(x)=d for all x∈V(G) and hence G is a d-self-centered graph.
Conversely, letG be a d-self-centered graph, where d≥3. Then ecc(x)=d for all x∈V(G). Notice that, for any vertex x=(x1,x2,…,xn) in G,(10)eccx=max⁡dx,y:y∈VG=max⁡eccx1,r:x1∈VG1ifk=1max⁡eccxk,r1:xk∈VGkifk>1,where r and r1 are as defined above. Since ecc(x) (which is the maximum of ecc(xk) and r or r1) is equal to d, d≥3 and r,r1≤2, we get ecc(xk)=d for all xk∈V(Gk). So Gk is d-self-centered graph.If we taked=2, then ecc(x)=2 may not imply that ecc(xk)=2 (there may be ecc(xk)<2 and r or r1 is equal to 2; see example below).Example 7.
Here we consider the lexicographic product of three graphs,G1, G2, and G3, where G1=K2, G2=P4, and G3=K2. Let V(G1)={x,y}, V(G2)={a,b,c,d}, and V(G3)={1,2}. The lexicographic product G=K2∘P4∘K2 of graphs K2, P4, and K2 is shown in Figure 1. One can check that the eccentricity of every vertex of G is two and hence G is a 2-self-centered graph. However, G1 is not a 2-self-centered graph.Figure 1In the theorem below, we present the general version of the 2-self-centered product graphs included in the previous example.Theorem 8.
LetG=G1∘G2∘⋯∘Gn be the lexicographic product of graphs G1,G2,…,Gn with VGi=ni, let Gk be 1-self-centered graph for some k∈{1,…,n-1}, and let Gi (if it exists) be K1 for all i<k. Then G is a 2-self-centered graph if and only if Δ(Gj)≠nj-1 for some j≥k+1.Proof.
First letG be a 2-self-centered graph. It is given that, for some k∈{1,…,n-1}, Gk is 1-self-centered graph and let Gi be K1 for all i<k. Our claim is that Δ(Gj)≠nj-1 for some j≥k+1. On the contrary, let Δ(Gj)=nj-1 for all j≥k+1. Then there are vertices gi∈Gi such that ecc(gi)=1 for every i, k≤i≤n. Now, by using above distance formula, for every x=(x1,…,xk-1,gk,…,gn) in G, one gets ecc(x)=1. This contradicts the fact that G is a 2-self-centered graph.
Conversely, letΔ(Gl)≠nl-1 for some l≥k+1. Then for any vertex xl∈Gl there exists yl∈Gl such that xl≁yl. For any vertex x=(x1,…,xk,…,xl,…,xn) there exists a vertex y=(x1,…,xk,…,yl,…,xn) such that x≁y. So, ecc(x)≥2. Since Gi=K1 for all i<k (if any), the distance formula will be(11)dx,y=dGixi,yiifi=kmin⁡dGixi,yi,2ifi≥k+1,where i is the smallest index for which xi≠yi. Since Gk is a 1-self-centered graph, dGi(xi,yi)=1 if i=k. Also, for i≥k+1, min{dGi(xi,yi),2}≤2. Thus eccentricity of no vertex is more than two and we get ecc(x)=2 for every x∈G. Hence G is a 2-self-centered graph.



---

*Source: 2508156-2016-08-07.xml*