ARS MATHEMATICA CONTEMPORANEA
ISSN 1855-3966 (printed edn.), ISSN 1855-3974 (electronic edn.)
ARS MATHEMATICA CONTEMPORANEA 15 (2018) 81-95
https://doi.org/10.26493/1855-3974.1382.dee
(Also available at http://amc-journal.eu)
On 2-distance-balanced graphs*
Boštjan Frelih t, Stefko Miklavic *
University of Primorska, FAMNIT and IAM, Muzejski trg 2, 6000 Koper, Slovenia
Received 12 April 2017, accepted 11 September 2017, published online 26 January 2018
Let n denote a positive integer. A graph r of diameter at least n is said to be n-distance-balanced whenever for any pair of vertices u, v of r at distance n, the number of vertices closer to u than to v is equal to the number of vertices closer to v than to u. In this article we consider n =2 (e.g. we consider 2-distance-balanced graphs). We show that there exist 2-distance-balanced graphs that are not 1-distance-balanced (e.g. distance-balanced). We characterize all connected 2-distance-balanced graphs that are not 2-connected. We also characterize 2-distance-balanced graphs that can be obtained as cartesian product or lexicographic product of two graphs.
Keywords: n-distance-balanced graph, cartesian product, lexicographic product. Math. Subj. Class.: 05C12, 05C76
1 Introductory remarks
A graph r is distance-balanced if for each pair u, v of adjacent vertices of r the number of vertices closer to u than to v is equal to the number of vertices closer to v than to u. Although these graphs are interesting from the purely graph-theoretical point of view, they also have applications in other areas of research, such as mathematical chemistry and communication networks. It is for that reason that they have been studied from various different points of view in the literature.
Distance-balanced graphs were first studied by Handa [9] in 1999. The name distance-balanced, however, was introduced nine years later by Jerebic, Klavžar and Rall [12]. The
* We thank the two anonymous referees for many useful comments and suggestions that have greatly improved our initial manuscript, especially for pointing out the mistake in Theorem 5.4.
t This work is partially supported by Erasmus+ Programme of the European Union (project ECCUM - Establishment of Computing Centers and Curriculum Development in Mathematical Engineering Master Programme).
t The author acknowledges the financial support from the Slovenian Research Agency (research core funding No. P1-0285 and research projects N1-0032, N1-0038, J1-5433, J1-6720, J1-7051).
E-mail addresses: bostjan.frelih@upr.si (Boštjan Frelih), stefko.miklavic@upr.si (Stefko Miklavic)
Abstract
©® This work is licensed under https://creativecommons.org/licenses/by/3.0/
82
Ars Math. Contemp. 15 (2018) 147-160
family of distance-balanced graphs is very rich (for instance, every distance-regular graph as well as every vertex-transitive graph has this property [13]). In the literature these graphs were studied from various purely graph-theoretic aspects such as symmetry [13], connectivity [9, 16] or complexity aspects of algorithms related to such graphs [6], to name just a few. However, it turns out that these graphs have applications in other areas, such as mathematical chemistry (see for instance [3, 11, 12]) and communication networks (see for instance [3]).
Another interesting fact is that these graphs can be characterized by properties that do not seem to have much in common with the original definition from [12]. For example, the distance-balanced graphs coincide with self-median graphs, that is graphs for which the sum of the distances from a given vertex to all other vertices is independent of the chosen vertex (see [4]). In [1], distance-balanced graphs are called transmission regular. Finally, even order distance-balanced graphs possess yet another nice property, making them what are called equal opportunity graphs (see [3] for the definition).
In distance-balanced graphs one only considers pairs of adjacent vertices. However, it is very natural to extend the definition to the pairs of nonadjacent vertices. This generalized concept of n-distance-balanced graphs (see Section 2 for the definition) was first introduced by Bostjan Frelih in 2014 [8] (we point out that certain other generalizations of this concept, where one still focuses just on pairs of adjacent vertices, have also been considered in the recent years [10,14,15]). The n-distance-balanced graphs and their properties were extensively studied in [17]. They are also the main topic in the paper [7], but in this paper some of the stated results do not hold. We comment on one of these problems later (see Remark 5.1).
In this article we consider 2-distance-balanced graphs. We now summarize our results. After some preliminaries in Section 2, we show in Section 3 that there exist 2-distance-balanced graphs that are not 1-distance-balanced (e.g. distance-balanced). It was shown in [9] that every distance-balanced graph is 2-connected. It turns out that not all 2-distance-balanced graphs are 2-connected. However, we characterize all connected 2-distance-balanced graphs that are not 2-connected.
In [12] distance-balanced cartesian products and distance-balanced lexicographic products of two graphs were characterized. We characterize 2-distance-balanced cartesian products and 2-distance-balanced lexicographic products of two graphs in Section 4 and 5, respectively.
2 Preliminaries
In this section we review some basic definitions that we will need later. Throughout this paper, all graphs are assumed to be finite, undirected, without loops and multiple edges. Given a graph r let V(T) and E(T) denote its vertex set and edge set, respectively.
For v e V(r) we denote the set of vertices adjacent to v by Nr(v). If the number |Nr(v)| is independent of the choice of v e V(r), then we call this number the valency of r and we denote it by kr (or simply by k if the graph r is clear from the context). In this case we say that r is regular with valency k or k-regular.
For u,v e V(r) we denote the distance between u and v by dr (u, v) (or simply by d(u,v) if the graph r is clear from the context). The diameter max{dr(u,v) | u,v e V(r)} of r will be denoted by Dr (or simply by D if the graph r is clear from the context). For any pair of vertices u,v e V(r) we let WUv be the set of vertices of r that are closer
B. Frelih and S. Miklavic: On 2-distance-balanced graphs
83
to u than to v, that is
W„rv = {w e V(r) | dr(u,w) < dr(v,w)}.
Let n denote a positive integer. A graph r of diameter at least n is said to be n-distance-balanced, if \WrV | = |WVr„| for any u, v e V(r) at distance n. The distance-balanced graphs are n-distance-balanced graphs for n = 1.
For W C V(r) the subgraph of r induced by W is denoted by (W) (we abbreviate r - W = (V(r) \ W)). A vertex cut of a connected graph r is a set W C V(r) such that r - W is disconnected. A vertex cut of size k is called a k-cut. A graph is said to be k-connected if it has at least k + 1 vertices and the size of the smallest vertex cut is at least k. If a vertex cut consists of a single vertex v, then v is called the cut vertex.
We complete this section by defining the cartesian product and the lexicographic product of graphs G and H. In both cases, the vertex set of the product is V(G) x V(H). Pick (gi,hi), (g2,h2) e V(G) x V(H).
In the cartesian product of G and H, denoted by GDH, (gi, hi) and (g2, h2) are adjacent if and only if g1 = g2 and h1, h2 are adjacent in H, or h1 = h2 and g1, g2 are adjacent in G. Note that the cartesian product is commutative.
In the lexicographic product of G and H, denoted by G[H], (g1, h1) and (g2, h2) are adjacent if and only if g1 = g2 and h1, h2 are adjacent in H, or g1, g2 are adjacent in G.
3 On the connectivity of 2-distance-balanced graphs
In this section we characterize connected 2-distance-balanced graphs that are not 2-connect-ed (Corollary 3.4). As a consequence, using the well known fact that an arbitrary connected distance-balanced graph is at least 2-connected (see [9]), we construct an infinite family of 2-distance-balanced graphs that are not distance-balanced.
Let G be an arbitrary (not necessary connected) graph, and let c be a vertex that does not belong to the set of vertices of G. We construct a graph, denoted by r(G, c), with the set of vertices
V(r(G,c)) = V(G) U{c}
and the set of edges
E(r(G, c)) = E(G) U {cv | v e V(G)}.
This graph is obviously connected. Next theorem follows directly from the construction
of r(G, c).
Theorem 3.1. G is not connected if and only if r(G, c) is not 2-connected.	□
We show that regularity of G is a sufficient condition for r(G, c) to be 2-distance-balanced.
Theorem 3.2. If G is a regular graph that is not a complete graph, then r = r(G, c) is 2-distance-balanced.
Proof. Assume that G is a k-regular graph that is not a complete graph. Let Gi, G2,..., Gn be its connected components for some positive integer n. If G is connected, then n =1, otherwise G has at least two connected components. Since G is not a complete graph, it
84
Ars Math. Contemp. 15 (2018) 147-160
is clear that the diameter of r equals 2, which means that two arbitrary vertices of r are either adjacent or they are at distance 2.
There are two different types of vertices at distance 2 in r. The first type is when both vertices at distance 2 belong to the same connected component of G. The second type is when vertices at distance 2 belong to different connected components of G.
Let Gj be an arbitrary connected component of G. Let vi, v2 G V(Gj) be arbitrary vertices at distance 2 in r. We count vertices that are closer to vi than to v2 in r and vertices that are closer to v2 than to vi in r. We get
WU = {vi} u (NGi(vi) \ (NGi(vi) n NGi(V2))).
It follows that
WU I = 1 + |NGi(vi)| - |NGi(vi) n NGi(v2)|.
Changing the roles of vertices vi and v2 , we get
|wV2v11 = 1 + |NGi(v2)| - |NGi(v2) n NGi(vi)|.
Since G is regular, the number of vertices that are closer to vi than to v2 in r equals the number of vertices that are closer to v2 than to vi in r.
Let now Gj and Gj be arbitrary different connected components of a disconnected graph G. Pick arbitrary vi G V(Gj) and v2 G V(Gj). Obviously these two vertices are at distance 2 in r. Observe that
Wvriv2 = {vi} u NGi(vi) and W^ = {v2} U NGj (v2).
Since every connected component of a k-regular graph is also a k-regular (induced) subgraph, it follows that
|W„riJ=1 + k and |WV2 vi | = 1 + k,
where k is the valency of G. So the number of vertices that are closer to vi than to v2 in r equals the number of vertices that are closer to v2 than to vi in r. Since this is true for an arbitrary pair of vertices at distance 2 in r, this graph is 2-distance-balanced.	□
Next we prove that every connected 2-distance-balanced graph, that is not 2-connected, is isomorphic to r(G, c) for some regular graph G that is not connected.
Theorem 3.3. Let r be a connected 2-distance-balanced graph that is not 2-connected. Then r is isomorphic to r(G, c) for some disconnected regular graph G.
Proof. Since r is not 2-connected, there exists a cut vertex c G V(r). Let Gi, G2,..., Gn be connected components of G = r — {c}, n > 2. We want to prove that G is regular and that the cut vertex c is adjacent to every other vertex in r. To do this we will first prove some partial results.
First we claim that the cut vertex c is adjacent to every vertex in a connected component Ge of G for at least one integer 1 < I < n. Suppose that this is not true. Let Gj and Gj be two different connected components of G. Then there exist v2 G V(Gj) and u2 G V(Gj), both at distance 2 from c in r. This means that there exists vi G V(Gj) that is adjacent to c and v2 in r, and there exists ui G V(Gj) that is adjacent to c and u2 in r. If we compare
B. Frelih and S. Miklavic: On 2-distance-balanced graphs
85
the set of vertices that are closer to c than to v2 in r and the set of vertices that are closer to v2 than to c in r, we get
Wl D {c} u V(Gj) and W^ C V(G<) \ {vi}.
It follows that
1 + |V(Gj)| < W
r |
cv 2 I
and
|Wr.
< |V(Gi)|- 1.
Since r is 2-distance-balanced, we get
|V(Gj)| < |V(Gi)|- 2. Similarly as above (changing vertex v2 with u2) we get
|V(Gi)| + 2 < |V(Gj)|. However, inequalities (3.1) and (3.2) imply
(3.1)
(3.2)
|V(Gi)| + 2 < |V(Gj)| < |V(Gi)|- 2,
a contradiction. It follows that the cut vertex c G V(r) is adjacent to every vertex in V(G^) for at least one integer 1 < I < n. Without loss of generality we may assume that I =1.
Next we claim that the induced subgraph G1 of r is regular. Pick some u G V(G) \ V(G1) that is adjacent to the cut vertex c in r. Since c is adjacent to every vertex in V(G1), the distance between u and an arbitrary v G V(G1) equals 2 in r. Pick v G V(G1). Notice that
It follows that
|W1
WVu = {v}u (Nr(v) \{c}).
1 + |Nr(v)|- 1 = |NGl (v)| + 1.
Pick w g V(G1). Since r is 2-distance-balanced and c is adjacent to every vertex of V(G1), we get the following sequence of equalities
|NGi (v)| + 1 = |Nr (v)| = |Wvr
| W1
| W1
So
= |WWU| = |Nr(w)| = |Ngi (w)| + 1.
|NGi (v)| = |Ngi (w)
for arbitrary v, w G V(G1). From now on we may assume that the induced subgraph G1 of r is k-regular. This also means that every vertex in V(G1) has valency k + 1 in r.
Our next step is to show that the cut vertex c G V(r) is adjacent to every vertex in V(G) \ V(G1). Suppose that this is not true. Then there exists some vertex u2 in a connected component Ge of G, 2 < I < n, that is at distance 2 from c in r. Without loss of generality we can take I = 2. Consequently there exists some u1 g V(G2) that is adjacent to both c and u2 in r. Pick an arbitrary v G V(G1). We have already proved that the valency of an arbitrary vertex in V(G1) is k + 1 in r. Now we count vertices that are closer to v than to u1 in r. Since
W„r
{v}U (Nr(v) \{c}),
86
Ars Math. Contemp. 15 (2018) 147-160
we get
|Wr„ J = 1 + k + 1 - 1 = k + 1.
In addition, for vertices that are closer to c than to u2 in r, we have
Wcru2 D V(Gi) U{c}.
It follows that	| |
|Wcr„2|>|V(Gi)| + 1 > k + 2.	(3.3)
Consider the distance partition of r according to adjacent vertices c and u1 that is shown in Figure 1. The symbol Dj denotes the set of vertices that are at distance i from u1 and at distance j from c in r. Define a set
U 2
Figure 1: The distance partition of r according to adjacent vertices c and u1.
D
U = U = (Di-1 U Di),
i= i
where D denotes the diameter of r. First we show that Wr2C C U. Recall that for u, v e V(r), d(u, v) denotes the distance between vertices u and v. Pick an arbitrary w e Wr2C. Since u1, u2 are, by the assumption, adjacent vertices in r, the triangle inequality tells us that
d(ui, w) e {d(u2, w) — 1, d(u2, w), d(u2, w) + 1}. If we consider all three cases, we get
d(ui,w) = d(u2,w) — 1 < d(c,w), d(ui,w) = d(u2,w) < d(c,w), d(ui, w) = d(u2, w) + 1 < d(c, w).
Each considered case gives us that w e U and so c C U. Note also that U C V (G2). Now we show that U C WrlV (recall that v is an abitrary vertex in V(G1)). Let w be an arbitrary vertex in U, which means that w is also in V(G2). We get that
d(ui,w) < d(c,w) < d(v,w),
since vertices v and c are adjacent in r, and v is not in V(G2). It follows that w e W^v,
and so U C W^1V. From relations W^2C C U C W^1V, we get that W^2C C W^1V and so
(3.4)
B. Frelih and S. Miklavic: On 2-distance-balanced graphs
87
By taking into account inequalities (3.3) and (3.4), and since r is 2-distance-balanced, we
get
k + 2 <|Wcr„21 = |W„r2C|< k +1,
which is a contradiction. This shows that the cut vertex c g V(T) is adjacent to all vertices
in V(G).
It remains to prove that the induced subgraph Ge (2 < I < n) of r is k-regular. Without loss of generality assume I = 2. Since we already know that the cut vertex c is adjacent to every vertex in r, an arbitrary vertex u in V(G2) is at distance 2 from an arbitrary vertex v in V(Gi) in r. Observe that
WUV = {u} U (Nr(u) \ {c}) = {u} U NG2 (u)
and
= {v} U (Nr(v) \ {c}) = {v} U NGl (v).
This means that
|W„rv| = 1 + |NG2 (u)| and |W„ru|=1 + k.
Since r is 2-distance balanced, it follows that | = |WVU| and so |NG2 (u)| = k for an arbitrary vertex u g V (G2). Therefore, G2 is regular and has the same valency k as the induced subgraph G1. It follows that G is regular and this completes the proof.	□
The characterization of all connected 2-distance-balanced graphs that are not 2-co-nnected follows immediately from Theorems 3.1, 3.2 and 3.3.
Corollary 3.4. Let r be a connected graph. Then r is 2-distance-balanced and not 2-connected if and only if it is isomorphic to r(G, c) for some disconnected regular graph G.	□
4 2-distance-balanced cartesian product
Throughout this section let G and H be graphs and let r = GIUH be the cartesian product of G and H. We characterize connected 2-distance-balanced cartesian products of graphs G and H (see Theorem 4.4). It follows from the definition that the cartesian product r is connected if and only if G and H are both connected. In order to avoid trivialities we assume that |V(G)| > 2 and |V(H)| > 2. Recall that
dr((gi, hi), (g2, h2)) = dG(gi, g2) + ¿H (hi, M	(4.1)
for arbitrary (gi, hi), (g2,h2) g V(r). Since we are dealing with 2-distance-balanced cartesian products of graphs, we are interested in vertices at distance 2. It follows from equality (4.1), that there exist three different types of vertices at distance 2 in r. We now state these three types and we will refer to them later. Let (gi, hi), (g2, h2) g V(r) be vertices at distance 2 in r. We say that these two vertices are of type
•	G2, if hi = h2 and <9G(gi, 02) = 2,
•	H2, if gi = g2 and dH(hi, h2) = 2,
•	GH2, if 5g(3i,32) = dH(hi,h2) = 1.
88
Ars Math. Contemp. 15 (2018) 147-160
Note that vertices of type G2 (H2, respectively) do not exist if G (H, respectively) is a complete graph. Denote the set of vertices that are at equal distance from g1 and g2 in G by EG S2, and the set of vertices that are at equal distance from h1 and h2 in H by E®^.
We first prove three lemmas that we will need later in the proof of the main theorem of this section.
W(gi ,h)(S2,h)
|H| |wgifl21 and
W(g2,h)(gi,h)
tG | ' 3231 I
Lemma 4.1. Let (gi, h) and (g2, h) be arbitrary vertices of type G2 in r = GDH. Then
|H| |WSG
Proof. Let (a, x) be an arbitrary vertex of r. It follows from the equality (4.1) that
dr((gi,h), (a,x)) = dG(gi,a) + Oh(h,x)
and
dr((g2,h), (a, x)) = dG(g2,a) + Oh(h,x).
So (a, x) is closer to (g1, h) than to (g2, h) in r if and only if a is closer to g1 than to g2 in G. Since (a, x) G V(r) was an arbitrary vertex, this means that
W(3i,h)(32,h)
lH IIWG32I
Similarly we get that
W(r32,h)(gi,h)
= lHI IWG31 I .	□
Lemma 4.2. Let (g, h1) and (g, h2) be arbitrary vertices of type H2 in r = GDH. Then
W(3,hl )(3,h2)
= |G| |wHh21 and Proof. Similar to the proof of Lemma 4.1.
W(r,h2)(3,hi)
= |G| |wHhi | .
□
Lemma 4.3. Let (g1, h1) and (g2, h2) be arbitrary vertices of type GH 2 in r = GDH. Then
and
Wri,hi)(32,h2)
W(32,h2)(3i,hi)
|EHh2 ||W
, + |wH | |WG u eg |
3i32 I 1 I hi"2I I 3i32 U ^3i32 I
|E
H
| + |wHh
h , ,W0G„ U EG„ |
2"i II 323i 3i32 I
^hih-2 I I '' 323i I
Proof. Let (a, x) be an arbitrary vertex of r. It follows from the equality (4.1) that
dr((g1,h1), (a,x)) = dG(g1,a) + Oh(hux)
and
dr((g2,h2), (a, x)) = dG(g2,a) + Oh(h2,x).
(4.2)
(4.3)
There are three different cases according to the distance of h1 and h2 from x in H.
In the first case let dH(h1, x) = dH(h2, x). From equalities (4.2) and (4.3) we get that
dr((g1, h1), (a, x)) < dr((g2, h2), (a,x)) ^^ dG(g1,a) < 8g(g2, a).
B. Frelih and S. Miklavic: On 2-distance-balanced graphs
89
This is true for exactly those (a, x) G V(T), for which a G WgGg2. Similarly we get that
dr((g2, M, (a, x)) < 3r((gi, hi), (a, x)) ^^ dG(g2,a) < dG(gi,a).
And this is true for exactly those (a, x) G V(r), for which a G WsGSi.
In the second case let dH(h1, x) < dH(h2, x). Since h1 and h2 are adjacent in H, it is obvious that dH(h2, x) = dH(h1, x) + 1. From equalities (4.2) and (4.3) we get that
dr((gi, hi), (a, x)) < 3r((g2, ^-2), (a,x)) ^^ 5G(gi,a) < dG(g2, a) + 1.
This is true for exactly those (a, x) G V(r), for which a G WgGS2 U EG«2. Similarly we get that
dr((g2, h2), (a, x)) < dr((gi, hi), (a,x)) ^^ dG(g2,a) + 1 < $G(gi,a).
But such vertices do not exist, since dG(gi, a) < dG(g2, a) + 1 by the triangle inequality.
In the third case let dH(h2, x) < dH(hi, x). Similarly as above we get that (a, x) is closer to (g2, h2) that to (gi, hi) if and only if a G WGSl U EGS2, and that (a, x) is never closer to (gi, hi) that to (g2, h2).
It follows from the above comments that
Next theorem gives the characterization of connected 2-distance-balanced cartesian products of graphs G and H.
Theorem 4.4. The cartesian product r = GDH is a connected 2-distance-balanced graph if and only if each of G, H is either a connected 2-distance-balanced and 1-distance-balanced graph, or a complete graph.
Proof. We first prove that if each of G, H is either a connected 2-distance-balanced and 1-distance-balanced graph or a complete graph, then r is a connected 2-distance-balanced graph.
Let us assume that G and H are connected 2-distance-balanced and 1-distance-balanced graphs. The connectivity of r follows from the connectivity of G and H. In this case all three types of vertices at distance 2 are present in r.
Let (gi, h) and (g2, h) be arbitrary vertices of type G2 in r. Since G is, by the assumption, 2-distance-balanced and since vertices gi, g2 are at distance 2 in G, it follows from Lemma 4.1 that
wlhi)(S2,h2) = (EHh2 X WsgS2 ) U Mh2 X ««2 U EGlS2))
and
WLh2)(Si,M = (EHh2 X ) U (WHhi X « «1U EGi«2)).
The result follows.
□
So for arbitrary vertices (gi, h), (g2, h) G V(r) of type G2, the number of vertices that are closer to (gi, h) than to (g2, h) in r equals the number of vertices that are closer to (g2, h) than to (gi, h) in r.
90
Ars Math. Contemp. 15 (2018) 147-160
If (g, h1) and (g, h2) are arbitrary vertices of type H2 in r, then similarly as above (using Lemma 4.2 instead of Lemma 4.1) we find that the number of vertices that are closer to (g, h1) than to (g, h2) in r equals the number of vertices that are closer to (g, h2) than to (g, h1) in r.
Let (g1, h1), (g2, h2) G V(r) be arbitrary vertices of type GH2 in r. Since G and H are both, by the assumption, 1-distance-balanced, and since g1, g2 are adjacent in G and h1, h2 are adjacent in H, we have
\WG
\WG
and \W,
H
hih.2
\W
H
hohi
It follows from Lemma 4.3 that
W(g1,h1)(S2,h2)
W(g2,h2 )(gi,hi)
for arbitrary vertices of type GH2 in r. So we proved that if G and H are both connected 2-distance-balanced and 1-distance-balanced graphs, then the cartesian product r = GDH is a connected 2-distance-balanced graph. Note that since G and H are 1-distance-balanced graphs, it follows that the cartesian product r = GDH is also 1-distance-balanced (see [12, Proposition 4.1]).
If one (or both) of G, H is a complete graph, then the proof that r = GDH is a connected 2-distance balanced graph is similar to the proof above. The only diference is that we do not have to consider vertices of type G2 (H2, respectively).
Assume now that r = GDH is a connected 2-distance-balanced graph. The connectivity of G and H follows from the connectivity of r. If G and H are complete graphs, then we are done. Therefore we assume that at least one of G or H is not a complete graph. First we show that in this case G and H are 2-distance-balanced graphs provided they are not complete.
Assume that G is not a complete graph. For an arbitrary h G V (H) and arbitrary
gi, g2 G V (G) that are at distance 2 in G, consider (gi, h), (g2, h) G V (r). Note that dr((gi, h), (02, h)) = 2 by (4.1) and that
W(gi,h)(s2 ,h)
|HI \WG
and
W(s2,h)(si,h)
|H| \WG
by Lemma 4.1. Since r is 2-distance-balanced, it follows that | WgGg21 = | WgGgi |, so also G is a 2-distance-balanced graph. Due to commutativity of the cartesian product, if H is not a complete graph, we can similarly show that H is a 2-distance-balanced graph.
Finally we show that G and H are also 1-distance-balanced graphs. Pick arbitrary adjacent vertices g1,g2 of G and arbitrary adjacent vertices h1, h2 of H, and note that (g1, h1), (g2, h2) g V(r) are at distance 2. Since r is 2-distance-balanced, it follows that
W(ri,hi)(S2,h2)
W(g2,h2)(gi,hi)
From Lemma 4.3 we get that
\ rp H \ \Ehi h2 \
(\W
SiS2l I S2Si I
= \WhHhi \
\ws2si u eSGs2 \
-\WHh2\
\ wG u \
I Si S2 u ^SiS2 I
(4.4)
B. Frelih and S. Miklavic: On 2-distance-balanced graphs
91
Assume that G is not a 1-distance-balanced graph. Then we could choose gi, in such a
' I > |WG I
9192 I ^ I 9291 I
way that \ W„G„2\ > IWGL |. As a consequence we also have that
\WG U EG \ > \ WG U EG \ .
i 9i92 gig2 \ ^ i g2gi w 9i92 i
It follows from (4.4) that |WHh \ > \WH^ \. Consider now vertices (gi, h2), (g2, h1), which are also at distance 2 in r. Similar argument as above shows that jW^^ \ < \ WH^ \, which is a contradiction. So G is a 1-distance balanced graph. Since the cartesian product is commutative, the proof that H is a 1-distance balanced graph is analogous to the proof for G.	□
5 2-distance-balanced lexicographic product
Throughout this section let G and H be graphs and let r = G[H] be the lexicographic product of G and H. It follows from the definition that the lexicographic product r is connected if and only if G is connected. In order to avoid trivialities we assume that | V(G) | > 2 and |V(H)| > 2. We characterize connected 2-distance-balanced lexicographic products of G and H (see Theorem 5.4).
Remark 5.1. A more general result about the characterization of connected n-distance-balanced lexicographic products of G and H as in Theorem 5.4 is stated in [7, Theorem 3.4]. But the result is not correct for at least n = 2. As a counterexample, let both G and H be paths on 3 vertices, which are connected graphs. Observe that G is 2-distance-balanced, and that H is locally regular (in a sense that any non-adjacent vertices in H have the same number of neighbours). By [7, Theorem 3.4], G[H] is 2-distance-balanced. However, one can easily check that the G[H] is not 2-distance-balanced.
Notice that there exist two different types of vertices at distance 2 in r. We now state these two types and we will refer to them in the proof of the Theorem 5.4. Let (g1, h1), (g2, h2) € V(r) be vertices at distance 2 in r. We say that this two vertices are of type
•	G2, if dG(gi,g2) =2,
•	H2, if g1 = g2 and dH(h1, h2) > 2.
It follows from the definition that there exist vertices of type G2 in r if and only if G is connected non-complete graph. Similarly, there exist vertices of type H2 in r if and only if H is non-complete graph.
The following two lemmas will be used in the proof of the main theorem of this section.
Lemma 5.2. Let (g1, h1) and (g2, h2) be arbitrary vertices of type G2 in r = G[H]. Then
1 + |Nh(h1)| + (\WgGg2\- 1) |V(H)|
W(gi,hi)(g2,h2)
and
W(g2,h2)(gi,hi)
= 1 + |Nh(h2)| + (\WgGgi |- 1) \ V(H)|.
Proof. Let (g1, h1) and (g2, h2) be arbitrary vertices of type G2 in r. Clearly, (g1, h1) is closer to itself than to (g2, h2). Now consider vertices of r of type (g1, h), where h = h1. Note that dr((g1,h), (g2,h2)) = 2, and so (g1,h) G W(r9i,hi)(92jh2) if and only
92
Ars Math. Contemp. 15 (2018) 147-160
if h € NH(hi). Finally, consider vertices of r of type (g, h), where g = gi. Then
^((g^ hl), (g, h)) = dG(gi,g),andso (g, h) € W(r31,h1)(S2,h2) ifandonlyifg € \ {gi}. It follows that
Wto ,hi)(S2,h2) = {(gi, hi)} U ({gi} x Nh (hi)) u ((W^ \ {gi}) x V (H)). Similarly we get
W(rS2,h2)(gi,hi) = {(g2, h2)} u ({g2} x Nh(h2)) U ((WGGgi \ {g2}) x V(H)). The result follows.	□
Lemma 5.3. Let (g, hi) and (g, h2) be arbitrary vertices of type H2 in r = G[H]. Then
1 + |Nh(hi)|-|NH(hi) n Nh(h2)|
W(g,hi)(g,h2)
and
1 + |Nh(h2)|-|NH(hi) n Nh(ha)|.
W(g,h2)(g,hi)
Proof. Let (g, hi) and (g, h2) be arbitrary vertices of type H2 in r, and let (g', h') be an arbitrary vertex of r. Note that if g = g' then dr((g, hi), (g', h')) = dr((g, h2), (g', h')). Assume therefore that g' = g. But it is clear that in this case (g, h') € W^ hi )(g h2) if and only if dH(hi, h') < 1 < dH(h2, h'). It follows that	, ,
W(rg,hi)(g,h2) = {(g, hi)} U ({g} x (Nh (hi) \ (Nh (hi) n Nh (hi)))). Similarly we get
W(rg,h2)(g,hi) = {(g, h2)} U ({g} x (Nh(h2) \ (Nh(hi) n Nh(hO))).
The result follows.	□
Next theorem gives the characterization of connected 2-distance-balanced lexicographic products of graphs G and H.
Theorem 5.4. The lexicographic product r = G[H] is a connected 2-distance-balanced graph ifandonly if one of the following (i), (ii) holds:
(i)	G is a connected 2-distance-balanced graph and H is a regular graph.
(ii)	G is a complete graph, H is not a complete graph, and each connected component of the complement of H induces a regular subgraph of the complement of H.
Proof. We first prove that if one of (i), (ii) holds, then r is a connected 2-distance-balanced graph. The connectivity of r follows from the connectivity of G.
Assume that (i) holds. Take arbitrary (gi, hi), (g2, h2) € V(r) of type G2. Since G is a 2-distance-balanced graph and H is a regular graph, we have that | W^, | = | WgG 1 and |Nh(hi)| = |Nh(h2)|. It follows from Lemma 5.2 that
W(si,hi)(g2,h2)
W(rg2,h2 )(gi,hi)
B. Frelih and S. Miklavic: On 2-distance-balanced graphs
93
for arbitrary vertices of type G2 in r.
Take now arbitrary (g, hi), (g, h2) G V(T) of type H2. Since, by the assumption, H is a regular graph, we have that |NH(h1) | = |NH(h2) |. It follows from Lemma 5.3 that
W(g,hi)(S,h2)
W(s,h2)(s,hi)
for arbitrary vertices of type H2 in r. So, if (i) holds then r is a connected 2-distance-balanced graph.
Assume that (ii) holds. Then G is a complete graph and H is not a complete graph, so we only have vertices of type H2 in r. Let us denote the complement of H by H. Let (g, h1), (g, h2) G V(r) be arbitrary vertices of type H2. Note that this implies that h1, h2 are not adjacent in H, and so h1, h2 are adjacent in H. As a consequence, h1, h2 are contained in the same connected component of H. It follows that |Nh(h1)| = |N^(h2)|, and consequently also |NH(h1)| = |NH(h2)|. It follows from Lemma 5.3 that
W(S,hi)(S,h2)
W(r,h2)(s,hi)
So, if (ii) holds then r is a connected 2-distance-balanced graph.
Assume now that the lexicographic product r = G[H] is a connected 2-distance-balanced graph. The connectivity of G follows from the connectivity of r. In what follows we first treat the case where G is not a complete graph, and then the case when G is a complete graph.
Suppose that G is not a complete graph. Take arbitrary g1, g2 g V(G) at distance 2 in G. Then (g1, h), (g2, h) G V(r) are of type G2 in r for an arbitrary h G V(H). Since r is, by the assumption, a 2-distance-balanced graph, it follows from Lemma 5.2 that | WsGS2 | = | Wg | for arbitrary vertices at distance 2 in G. So, G is a connected 2-distance-balanced graph. For arbitrary h1, h2 G V(H) and arbitrary g1,g2 G V(G) at distance 2 in G, consider (g1, h1), (g2, h2) G V(r). These two vertices are of type G2 in r. Since r is, by the assumption, a 2-distance-balanced graph and we already know that G is also 2-distance-balanced graph, it follows from Lemma 5.2 that |NH(h1)| = |NH(h2)| for arbitrary two vertices in H. So, H is a regular graph and (i) holds.
From now on let G be a complete graph. Since r is not a complete graph, it follows that also H is not a complete graph. This means that all vertices at distance 2 in r are of type H2. We want to show that in this case each connected component of the complement of H induces a regular subgraph of the complement of H.
Let h1, h2 G V(H) be arbitrary vertices at distance greater or equal than 2 in H (that is, vertices h1, h2 are not adjacent in H). Observe that (g, h1), (g, h2) G V(r) are of type H2 for an arbitrary g G V(G). From Lemma 5.3 we get that |NH(h1)| = |NH(h2)|, and consequently also |N;H(h1)| = |N^(h2)|. This shows that any adjacent vertices of H have the same valency in H, and therefore each connected component of H induces a regular subgraph of H.	□
94
Ars Math. Contemp. 15 (2018) 147-160
We finish our paper with a suggestion for further research. A fullerene is a cubic planar graph having all faces 5- or 6-cycles. Examples include the dodecahedron and generalized Petersen graph GP(12,2). Dodecahedron is distance-regular, and so it is n-distance-balanced for every 1 < n < 5 (recall that the diameter of dodecahedron is 5). On the other hand, the diameter of GP(12, 2) is also 5, but GP(12, 2) is n-distance-balanced only for n = 5, see [17]. Therefore, it would be interesting to know, which fullerenes are n-distance-balanced at least for some values of n (for example, for n G {1, 2, D}, where D is the diameter of a fullerene in question). For more on fullerenes see [2, 5, 18].
References
[1]	A. Abiad, B. Brimkov, A. Erey, L. Leshock, X. Martinez-Rivera, S. O, S. Y. Song and J. Williford, On the Wiener index, distance cospectrality and transmission-regular graphs, Discrete Appl. Math. 230 (2017), 1-10, doi:10.1016/j.dam.2017.07.010.
[2]	V. Andova, F. Kardoš and R. Skrekovski, Mathematical aspects of fullerenes, Ars Math. Con-temp. 11 (2016), 353-379, doi:10.26493/1855-3974.834.b02.
[3]	K. Balakrishnan, B. Brešar, M. Changat, S. Klavzar, A. Vesel and P. Žigert Pleteršek, Equal opportunity networks, distance-balanced graphs, and Wiener game, Discrete Optim. 12 (2014), 150-154, doi:10.1016/j.disopt.2014.01.002.
[4]	K. Balakrishnan, M. Changat, I. Peterin, S. Spacapan, P. Sparl and A. R. Subhamathi, Strongly distance-balanced graphs and graph products, European J. Combin. 30 (2009), 1048-1053, doi:10.1016/j.ejc.2008.09.018.
[5]	A. Behmaram, T. Došlic and S. Friedland, Matchings in m-generalized fullerene graphs, Ars Math. Contemp. 11 (2016), 301-313, doi:10.26493/1855-3974.882.539.
[6]	S. Cabello and P. Luksšicš, The complexity of obtaining a distance-balanced graph, Electron. J. Combin. 18 (2011), #P49, http://www.combinatorics.org/ojs/index.php/ eljc/article/view/v18i1p4 9.
[7]	M. Faghani, E. Pourhadi and H. Kharazi, On the new extension of distance-balanced graphs, Trans. Comb. 5 (2016), 21-34, doi:10.22108/toc.2016.15048.
[8]	B. Frelih, Različni vidiki povezave regularnosti v grafih, Ph.D. thesis, University of Primorska, 2014, in Slovene.
[9]	K. Handa, Bipartite graphs with balanced (a, b)-partitions, Ars Combin. 51 (1999), 113-119, http://www.combinatorialmath.ca/arscombinatoria/vol51.html.
[10]	T. Hilado and K. Nomura, Distance degree regular graphs, J. Comb. Theory Ser. B 37 (1984), 96-100, doi:10.1016/0095-8956(84)90050-9.
[11]	A. Ilic, S. Klavzar and M. Milanovic, On distance-balanced graphs, European J. Combin. 31 (2010), 733-737, doi:10.1016/j.ejc.2009.10.006.
[12]	J. Jerebic, S. Klavzar and D. F. Rall, Distance-balanced graphs, Ann. Comb. 12 (2008), 71-79, doi:10.1007/s00026-008-0337-2.
[13]	K. Kutnar, A. Malnic, D. Marušic and S. Miklavic, Distance-balanced graphs: Symmetry conditions, Discrete Math. 306 (2006), 1881-1894, doi:10.1016/j.disc.2006.03.066.
[14]	K. Kutnar, A. Malnic, D. Marušic and S. Miklavic, Matchings in m-generalized fullerene graphs, Ars Math. Contemp. 2 (2009), 41-47, doi:10.26493/1855-3974.75.895.
[15]	K. Kutnar and S. Miklavic, Nicely distance-balanced graphs, European J. Combin. 39 (2014), 57-67, doi:10.1016/j.ejc.2013.12.002.
B. Frelih and S. Miklavic: On 2-distance-balanced graphs
95
[16]	S. Miklavic and P. Sparl, On the connectivity of bipartite distance-balanced graphs, European J. Combin. 33 (2012), 237-247, doi:10.1016/j.ejc.2011.10.002.
[17]	S. Miklavic and P. Sparl, ¿-distance-balanced graphs, 2017, arXiv:1702.05257 [math.CO] .
[18]	N. Tratnik and P. Zigert Pletersek, Resonance graphs of fullerenes, Ars Math. Contemp. 11 (2016), 425-435, doi:10.26493/1855-3974.1000.8db.