Electronic Journal of Graph Theory and Applications 12 .
, 157Ae167 Determination of all graphs whose eccentric graphs are clusters Jin Akiyamaa .
Takako Kodateb .
Kiyoko Matsunagaa Tokyo University of Science,Tokyo.
Japan b Tokyo WomanAos Christian University.
Tokyo.
Japan ja@jin-akiyama.
com, kodate@lab.
jp, matsunaga@mathlab-jp.
Abstract A disconnected graph G is called a cluster if G is not union of K2s .
-facto.
but union of complete graphs of order at least two.
Akiyama.
Ando and D.
Avis showed in Lemma 2.
1 of .
that G is equi-eccentric if the eccentric graph Ge is a cluster or pK2 .
And they also characterized all graphs whose eccentric graphs are complete graphs and pK2 in .
In this paper, we determined in Theorem 2 all graphs whose eccentric graphs are clusters, which is an extension of Lemma 2.
Keywords: eccentricity, eccentric graph, cluster, distance, radius Mathematics Subject Classification : 05C12 DOI: 10.
5614/ejgta.
Introduction Let G = (V (G).
E(G)) be a simple S undirected graph.
A disconnected graph G is called a cluster if it is a union of complete graphs ni=1 Kpi .
O 2, pi O 2.
Figure .
The eccentricity e.
of a vertex v in V (G) is defined by e.
= maxuOOV (G) d.
, .
, where d.
, .
stands for the length of a shortest path in G between u and v.
We denote by Ge = (V (Ge ).
E(Ge )) the eccentric graph based on G (Figure .
, where the vertex set V (Ge ) is identical to V (G) and uv OO E(Ge ) Ni d.
, .
= min.
, e.
A similar graph, called the Aufurthest neighbor graphAy, was introduced by Shamos .
Its vertex set is a set of points in the plane, and the distance between two vertices is their Euclidean distance.
Received: 24 October 2023.
Revised: 22 April 2024.
Accepted: 10 May 2024.
Determination of all graphs whose eccentric graphs are clusters Jin Akiyama et al.
Figure 1: Example of a cluster G = 3K2 O K3 O 2K4 O K5 Two vertices are joined if either one is the Aufurthest neighborAy of the other.
Extremal properties of this graph are studied in .
A central vertex of a graph G is a vertex v with the property that the maximum distance between v and any other vertex is as small as possible, this distance being called the radius, denoted by r(G).
That is, r(G) = minvOOV (G) e.
The diameter of G denoted diam(G) is defined by diam(G) = maxvOOV (G) e.
A graph is a self-center .
or r-equi-eccentric .
r briefly r-equ.
if e.
= r(G) = diam(G) for all vertices v OO V (G) .
ee Figure .
If S OC V (G), then we say that e(S) = i if e.
= i for all v OO S, and we denote by S the subgraph induced by S.
denote by N .
the neighborhood of a vertex v of G consisting of the vertices in G adjacent to v.
The closed neighborhood N .
of v is defined by N .
= N .
O .
All other definitions and notations used in this paper might be found in .
Ge :
=Ne .
r(G) = 2, diam(G) = 3 .
Ge Figure 2: Example of a graph and its eccentric graph .
C6 , 3-equi .
4-equi Figure 3: Examples of a 3-equi and a 4-equi-eccentric graph Lemma A (.
Lemma 2.
If Ge = n O 2, then G is equi-eccentric.
i=1 Kpi , where i=1 pi = p, pi O 2.
= 1, 2, .
, .
and Determination of all graphs whose eccentric graphs are clusters Jin Akiyama et al.
Theorem A (.
Theorem 2.
If G is a graph of order 2p then Ge = pK2 if and only if G is radius critical, that is, r(G Oe .
= r(G) Oe 1 for all v OO V (G).
Theorem B (.
Theorem 2.
For any connected graph G of order p.
Ge = Kp if and only if for all v OO V (G) either e.
= 1 or e(N .
) = 1.
Theorem B can be restated as follows and we give a different proof of it from one in .
Theorem BA .
A graph G of order p whose eccentric graph is a complete graph Kp if and only if G is a join of a complete graph Km and n isolated vertices Kn i.
G = Km Kn , m n = p, m = 0.
Ge = K7
G = K3 K 4
Figure 4: Example of Theorem BA Proof.
We divide our proof into two cases depending on r(G) = 1 or not.
Case 1.
Suppose that r(G)=1.
Let S.
be a set of all vertices v of G with e.
= i.
Since S.
= OI for every i(O .
, we have that V (G) = S.
O S.
and S.
O S.
= OI.
Let |S.
|, |S.
| be m, n.
The induced subgraph S.
of G is a complete subgraph Km of G.
If there exists at least one edge vv A OO E(G) where both v, v A OO S.
, then we have that vv A OO / E(Ge ), which implies that Ge is not a complete graph (Figure .
Therefore.
must be a totally disconnected graph Kn .
That is.
G must be a Km Kn .
Conversely, if G = Km Kn , then Ge is a complete graph Km n .
=Ne vA Figure 5: Example of Case 1.
with the value of eccentricity of vertices in G Case 2.
Suppose that r(G) O 2.
For any vertex v of G, there is a vertex v A which is adjacent to v, implying that d.
, v A ) = Since e.
= 1 and e.
A ) = 1, we have that vv A is not an edge of Ge .
Therefore.
Ge cannot be a complete graph.
Determination of all graphs whose eccentric graphs are clusters Jin Akiyama et al.
Main results Theorem 1.
If r(G) O 2, then (G Kn )e = (G Kn ) = G O Kn , n O 2.
Proof.
Since r(G) O 2, there is no vertex v such that e.
= 1 in G.
Therefore.
G Kn is 2-equi (Figure .
Hence uv OO E(G Kn ) if and only if uv OO / E((G Kn )e ), which implies that (G Kn )e is isomorphic to the complement of (G Kn ).
G Kn .
Moreover, the complement G Kn is G O Kn .
=Ne G.
K3 (G K3 )e = G K3 = G O K3 Figure 6: Example of Theorem 1 Putting G = K.
1 , m2 , .
, mn ), we obtain the Corollary 1.
Corollary 1.
For mi O 2 for i.
O i O .
and Ee O 2, (K.
1 , m2 , .
, mn ) KEe )e = Km1 O Km2 O A A A O Kmn O KEe .
Proposition 1.
(C2p )e = pK2 .
ee Figure 7.
(C2p 1 )e = C2p 1 .
ee Figure 7.
=Ne =Ne .
C6 and (C6 )e = 3K2 .
C5 and (C5 )e = C5 Figure 7: C6 and C5 , and its eccentric graphs Theorem 2.
A graph whose eccentric graph is a cluster, i.
Ge = ni=1 Kpi .
O 2, pi O 2 for any i.
O i O .
, and at least one pi is not 2, ni=1 pi = .
, if and only if G is a complete n-partite graph K.
1 , p2 , .
, pn ).
Proof.
Since n O 2.
Ge = ni=1 Kpi is not connected.
Then, there exists no vertex v OO V (G) such that e.
= 1 .
f not.
Ge would be connecte.
Let k = diam(G) and let x and y be any pair of vertices in G such that d.
, .
= k.
Note that xy is an edge of Ge .
Let zk be a vertex in N .
such that d.
k , .
= k Oe1 (Figure 8.
For any vertex z in N .
, if every path between z and y passes through x, then d.
, .
> k, which is a contradiction.
Therefore, there exists at least one path between z and y not passing through x for any z OO N .
(Figure 8.
Determination of all graphs whose eccentric graphs are clusters Jin Akiyama et al.
to such a path between z and y:
if d.
, .
< k Oe 1 for some z OO N .
, d.
, .
= d.
, .
, .
< k, which is a contradiction.
If d.
, .
> k Oe 1 for some z OO N .
, that is d.
, .
= k(= diam(G)), e.
= k.
AndSthen, xy OO Ge , yz OO Ge , but xz OO / Ge , since d.
, .
= 1 = e.
or e.
It means that Ge is not Kpi .
, vertices x, y and z do not form a part of a complete grap.
, which is a contradiction.
Then, for any vertex z in N .
, there exists at least one path between z and y such that d.
, .
= k Oe 1, if Ge is a cluster.
Vertices in N .
and N .
Paths between z and y Figure 8 Due to the above results.
G includes a k-equi-eccentric graph GA which is composed of all paths xzi O zi y where zi OO N .
Note that the number of N .
is more than 1.
Otherwise, for a unique point w OO N .
, e.
= d.
, .
and d.
, .
= 1.
Then, xy OO Ge , xw OO Ge but yw OO / Ge , which means that vertices x, y and w do not form a part of complete graph, that is.
Ge cannot be a cluster.
Any GA can be constructed by applying one of or combination of following operations to GL , which is a union of n disjoint paths Pi = xzi O zi y .
= 1, 2, .
, .
where n = |N .
|, |V (GL )| = |V (GA )| and the length of Pi is k (Figure .
Operation 1.
Add an edge between points pi and pj where d.
i , .
1 = d.
j , .
Operation 2.
A point pi and some points pj s coincide, where 1 < d.
i , .
= d.
j , .
= Ee < kOe1, but at least two of them for each Ee must be distinct.
And add m points pk s, edges pk pq s and pk pr s so that m is just the reduced number above, and d.
k , .
= Ee, d.
k , .
Oe 1 = d.
q , .
and d.
k , .
1 = d.
r , .
For any z OO N .
, there must exist at least one point w OO N .
such that e.
= d.
, .
= k, if Ge is a cluster.
We can classify the situation into the following two cases by the maximum number of w for all z OO N .
where d.
, .
= k.
Case 1.
The maximum number of w is more than 1 for all z OO N .
where d.
, .
= k.
In this case, |N .
| O 3 and |N .
| O 3.
For zi in N .
, there exist at least two vertices wj and wEe in N .
such that d.
i , wj ) = k, d.
i , wEe ) = k.
That is, any paths zi y with d.
i , .
= k Oe 1 never pass through wj or wEe (Figure 10.
Then, both zi wj and zi wEe are edges of Ge , thus wj wEe must also be an edge of Ge = Determination of all graphs whose eccentric graphs are clusters Jin Akiyama et al.
N .
N .
GA .
GL .
GA Figure 9: Examples of GL and GA in the case of k = 4 zEe PEe wEe N .
z1 z2 z3 .
N .
=Ne N .
= N .
i , wj ) = d.
i , wEe ) = k .
G: 2-equi-eccentric graph Figure 10 i=1 Kpi .
Since d.
j , wEe ) = 2 and e.
j ) = e.
Ee ) = k, k must be 2, which implies that N .
= N .
and G is 2-equi-eccentric (Figure 10.
Case 1-1.
GA includes all vertices of G.
There are two cases .
depending on whether some pairs of N .
are joined by edges of G or not.
If no pair of N .
is joined by an edge of G.
G must be a complete bipartite graph K.
, .
(Figure 11.
and Ge is K2 O Km (Figure 11.
G = K.
, .
z1 z2 z3 .
NaNe N .
= N .
N .
= N .
z2 z3 zmOe1 m |N .
| = m zmOe1 .
Ge = K2 O Km .
G is isomorphic to K.
, .
Figure 11: Example of G and Ge of Case 1-1 .
If some pairs of N .
are joined by edges of G.
Ge is a cluster if and only if N .
induces a complete n-partite graph K.
1 , m2 , .
, mn ), mi O 2 for 1 O i O n by Corollary 1.
That is.
G is K.
1 , m2 , .
, mn ) K2 = K.
, m1 , m2 , .
, mn ) and Ge is Km1 O Km2 O A A A O Kmn O K2 .
Figure 12 shows that N .
induces a complete bipartite graph K.
, .
and G = K.
, .
K2 = K.
, 2, .
, respectively.
Determination of all graphs whose eccentric graphs are clusters G = K.
, 2, .
NaNe G = K.
, .
= K.
, 2, .
Jin Akiyama et al.
Ge = K2 O K2 O K3 :
N .
= K.
, .
=Ne Figure 12: N .
induces a complete bipartite graph K.
, .
Case 1-2.
GA does not include all vertices of G.
Let v1 , v2 , .
, vn be vertices which are included in none of GA .
Since .
G is connected, .
diam(G) = 2, and .
vi belongs to neither N .
or N .
, vi zj must be an edge of G for at least one vertex of N .
ay zj ) (Figure 13.
If no pair of N .
has an edge of G, vi .
= 1, 2, .
is joined by an edge with every vertex in N .
(Figure 13.
, since otherwise e.
i ) = 3 > diam(G)(= .
, which is a contradiction (Figure 13.
Therefore.
G must be K.
Ee .
(Figure 13.
, and Ge is Km O KEe 2 .
vEe vEe Ni G: x N .
(= N .
) vEe .
G = K.
Ee .
Example of Case 1-2.
Figure 13: Example of G of Case 1-2.
If some pairs of N .
are joined by edges of G.
N .
must form K.
1 , m2 , .
, mn ) to make Ge be a cluster by Corollary 1 (Figure .
Especially.
, 2, .
, .
is the power (C2n )nOe1 of C2n .
If N .
is (C2n )nOe1 .
G is also a power (C2.
)n of C2.
and Ge is .
K2 , which is not a cluster (Figure 15 is the case of n = .
Determination of all graphs whose eccentric graphs are clusters Jin Akiyama et al.
Let v1 , v2 , .
, vEe be vertices not in N .
O .
, .
For vi .
= 1, 2, .
, since .
vi does not belong to N .
, .
diam(G) = 2, and .
if there exists z OO N .
such that vi z OO / G, vi z OO Ge , vi x OO Ge but xz OO / Ge , then vi z must be an edge of G for all z in N .
(Figure 16.
Therefore.
G is K.
1 , m2 , .
, mn ) K2 Ee , i.
1 , m2 , .
, mn , 2 E.
(Figure 16.
, and Ge is Km1 OKm2 OA A AOKmn OK2 Ee (Figure 16.
N .
= K.
, 2, .
N .
(= N .
) Figure 14: Example of G: N .
K2 (|N .
| = .
Figure 15: Example of Case 1-2.
for N .
= C2n with n = 4 G = N .
K2 Ee :
N .
v1 v2 vEe .
V (G) = N .
O .
, .
O .
1 , .
, vEe }, where N .
= K.
, 2, .
Example with Ee = 3.
G = K.
, 2, .
K2 3 = K.
, 2, 3, .
Ge = K2 O K3 O K2 O K5 Figure 16: zi is simply stated by i.
Case 2.
The number of w for each z OO N .
where d.
, .
= k is 1.
This case can be also classified into the following four cases:
Determination of all graphs whose eccentric graphs are clusters Jin Akiyama et al.
Case 2-1.
|N .
| = |N .
| = 2 and GA includes all vertices of G.
In this case, if G is a C2k .
here 2k = .
G is k-equi-eccentric and Ge is a kK2 by Proposition 1 (Figure .
, which is not a cluster.
There exists no G such that Ge is a x : e.
= k N .
: e.
= k vA v : e.
= k N .
: e.
= k y : e.
= k .
G = C2k .
Ge = kK2 Figure 17: Example of G and Ge of Case 2-1.
Case 2-2.
|N .
| = |N .
| = 2 and GA does not include all vertices of G.
Let vi be a vertex which is not included in GA .
Since G is connected, vi is connected to some vertex of GA .
Let xA be a vertex on GA such that d.
i , xA ) is the shortest among d.
i , vc ) for any vertex vc on GA (Figure 18.
Let y A be a vertex on GA such that d.
A , y A ) = k.
For xA and y A , we repeat the analogous argument as one for x and y.
Then we see that there are at least three paths of length k from xA to y A .
If k = 2.
Ge cannot be a cluster as seen in Case 1.
If k = 2 and there is only one vertex v other than x and y in N .
A ) (Figure 18b where p = .
G is K.
, .
which is a 2-equi-eccentric graph, and thus Ge is K3 O K2 (Figure 18.
C2k |N .
A )| = 3
yA xA K2 :
xA .
G NaNe K3 :
yA .
G = K.
, .
xA yA .
Ge = K2 O K3 Figure 18: Example of Case 2-2.
where |N .
A )| = 3 If k = 2 and there are mA (O .
vertices v1 , v2 , .
, vmA other than xA , y A , x and y in N .
A ) .
here mA = p Oe .
(Figure 19.
G is K.
A 2, .
(Figure 19.
and G is a 2-equi-eccentric graph.
Thus Ge is K2 O KmA 2 .
Case 2-3.
|N .
| = 2 and |N .
| > 2.
If the number of w for each zi OO N .
where d.
i , .
= k is 1, there must exist just one wzi OO N .
such that no path zi y with distance k Oe1 passes through wzi and every path zi y passes through all wj OO N .
other than wzi (Figure .
But such a graph GA cannot be a k-equi-eccentric, so Ge is not a cluster.
We do not need to consider this Determination of all graphs whose eccentric graphs are clusters Jin Akiyama et al.
vmA yA xA v1 v2 v3 vmA NaNe |N .
A )| = mA 2 .
G xA yA .
G = K.
A 2, .
Figure 19: Example of Case 2-2.
where |N .
A )| > 3 Figure 20: Example of Case 2-3.
Case 2-4.
|N .
| > 2.
If the number of w for each zi OO N .
where d.
i , .
= k is 1, there must exist just one wzi OO N .
such that no path zi y with distance k Oe 1 passes through wzi and every path zi y passesSthrough all wj OO N .
other than wzi .
If G satisfies both this condition and Ge = ni=1 Kpi .
G is radius critical (Figure .
Therefore.
Ge is p2 K2 by Theorem A, which is not a cluster.
G = 3Cube .
-equ.
G = C4 y C4 (= K2,2 y K2,2 ).
5-equi .
G = 4Cube .
-equ.
Figure 21: Examples of Case 2-4.
Further research In this article, we determined that all graphs whose eccentric graphs are clusters if and only if the graph is a complete n-partite graph K.
1 , p2 , .
, pn ), p O 2.
For further research, one can try to determine all graphs that have the same eccentric graph.
One can also try to find more graph operations which preserve eccentricity like MycielskiAos operation, or to find practical applications of eccentric graphs.
Acknowledgement The authors would like to thank Kiyoshi Ando for his valuable comments.
References