On ℓ-Distance-Balanced Product Graphs Jerebic, Janja; Klavžar, Sandi; Rus, Gregor
Graphs and combinatorics,
2021/1, Letnik:
37, Številka:
1
Journal Article
Recenzirano
Odprti dostop
A graph
G
is
ℓ
-distance-balanced if for each pair of vertices
x
and
y
at a distance
ℓ
in
G
, the number of vertices closer to
x
than to
y
is equal to the number of vertices closer to
y
than to
x
. A ...complete characterization of
ℓ
-distance-balanced corona products is given and characterization of lexicographic products for
ℓ
≥
3
, thus complementing known results for
ℓ
∈
{
1
,
2
}
and correcting an earlier related assertion. A sufficient condition on
H
which guarantees that
K
n
□
H
is
ℓ
-distance-balanced is given, and it is proved that if
K
n
□
H
is
ℓ
-distance-balanced, then
H
is an
ℓ
-distance-balanced graph. A known characterization of 1-distance-balanced graphs is extended to
ℓ
-distance-balanced graphs, again correcting an earlier claimed assertion.
Maximally distance-unbalanced trees Kramer, Marie; Rautenbach, Dieter
Journal of mathematical chemistry,
11/2021, Letnik:
59, Številka:
10
Journal Article
Recenzirano
Odprti dostop
For a graph
G
, and two distinct vertices
u
and
v
of
G
, let
n
G
(
u
,
v
)
be the number of vertices of
G
that are closer in
G
to
u
than to
v
. Miklavič and Šparl (
arXiv:2011.01635v1
) define the ...distance-unbalancedness
uB
(
G
)
of
G
as the sum of
|
n
G
(
u
,
v
)
-
n
G
(
v
,
u
)
|
over all unordered pairs of distinct vertices
u
and
v
of
G
. For positive integers
n
up to 15, they determine the trees
T
of fixed order
n
with the smallest and the largest values of
uB
(
T
)
, respectively. While the smallest value is achieved by the star
K
1
,
n
-
1
for these
n
, which we then proved for general
n
(Minimum distance-unbalancedness of trees, J Math Chem,
https://doi.org/10.1007/s10910-021-01228-4
), the structure of the trees maximizing the distance-unbalancedness remained unclear. For
n
up to 15 at least, all these trees were subdivided stars. Contributing to problems posed by Miklavič and Šparl, we show
max
{
uB
(
T
)
:
T
is
a
tree
of
order
n
}
=
n
3
2
+
o
(
n
3
)
and
max
{
uB
(
S
(
n
1
,
…
,
n
k
)
)
:
1
+
n
1
+
⋯
+
n
k
=
n
}
=
1
2
-
5
6
k
+
1
3
k
2
n
3
+
O
(
k
n
2
)
,
where
S
(
n
1
,
…
,
n
k
)
is the subdivided star such that removing its center vertex leaves paths of orders
n
1
,
…
,
n
k
.
In this article, we are using the regular graph of even number of vertices and computing the distance balanced graphs. First we take a graph for satisfying regular definition and then we compute the ...Mostar index of that particular graph. If the Mostar index of that particular graph is zero, then the graph is said to be a distance balanced graph. So we discuss first distance balanced graph. Suppose if we delete one edge in that particular graph, that is non-regular graph, we can verify the balanced graph is whether distance balanced graph or not. We discuss and compute the Mostar index of certain regular and non-regular graphs are balanced distance or not. Finally we see few theorems are related in this topic. So in this paper, we study some distance based topological indices for regular graphs and also cubic graphs.
Given a graph G and a set X⊆V(G), the relative Wiener index of X in G is defined as WX(G)=∑{u,v}∈X2dG(u,v). The graphs G (of even order) in which for every partition V(G)=V1+V2 of the vertex set V(G) ...such that |V1|=|V2| we have WV1(G)=WV2(G) are called equal opportunity graphs. In this note we prove that a graph G of even order is an equal opportunity graph if and only if it is a distance-balanced graph. The latter graphs are known by several characteristic properties, for instance, they are precisely the graphs G in which all vertices u∈V(G) have the same total distance DG(u)=∑v∈V(G)dG(u,v). Some related problems are posed along the way, and the so-called Wiener game is introduced.
•A new characterization of distance balanced graph of even order under the name “Equal Opportunity Graphs”.•Construction of a new infinite family of distance balanced partial cubes.•Introduction of a new game played on the vertices of a graphs named as “Wiener game”.
We prove that any harmonic partial cube is antipodal, which was conjectured by Fukuda and K. Handa,
, Discrete Math. 111 (1993) 245–256. Then we prove that a partial cube
is antipodal if and only if ...the subgraphs induced by
and
are isomorphic for every edge
of
. This gives a positive answer to a question of Klavžar and Kovše,
, Ars Combin. 93 (2009) 77–86. Finally we prove that the distance-balanced partial cube that are antipodal are those whose pre-hull number is at most 1.
PDF
