A graph G is said to be quasi-λ-distance-balanced if for every pair of adjacent vertices u and v, the number of vertices that are closer to u than to v is λ times bigger (or λ times smaller) than the ...number of vertices that are closer to v than to u, for some positive rational number λ>1. This paper introduces the concept of quasi-λ-distance-balanced graphs, and gives some interesting examples and constructions. It is proved that every quasi-λ-distance-balanced graph is triangle-free. It is also proved that the only quasi-λ-distance-balanced graphs of diameter two are complete bipartite graphs. In addition, quasi-λ-distance-balanced Cartesian and lexicographic products of graphs are characterized. Connections between symmetry properties of graphs and the metric property of being quasi-λ-distance-balanced are investigated. Several open problems are posed.
The status of a vertex u, denoted by σG(u), is the sum of the distances between u and all other vertices in a graph G. The first and second status connectivity indices of a graph G are defined as ...S1(G)=∑uv∈E(G)σG(u)+σG(v) and S2(G)=∑uv∈E(G)σG(u)σG(v) respectively, where E(G) denotes the edge set of G. In this paper we have defined the first and second status co-indices of a graph G as S1¯(G)=∑uv∉E(G)σG(u)+σG(v) and S2¯(G)=∑uv∉E(G)σG(u)σG(v) respectively. Relations between status connectivity indices and status co-indices are established. Also these indices are computed for intersection graph, hypercube, Kneser graph and achiral polyhex nanotorus.
Distance-Balanced Graphs Jerebic, Janja; Klavžar, Sandi; Rall, Douglas F.
Annals of combinatorics,
04/2008, Letnik:
12, Številka:
1
Journal Article
Recenzirano
.
Distance-balanced graphs are introduced as graphs in which every edge
uv
has the following property The number of vertices closer to
u
than to
v
is equal to the number of vertices closer to
v
than ...to
u
. Basic properties of these graphs are obtained. The new concept is connected with symmetry conditions in graphs and local operations on graphs are studied with respect to it. Distance-balanced Cartesian and lexicographic products of graphs are also characterized. Several open problems are posed along the way.
For a graph $ G $, let $ n_G(u, v) $ be the number of vertices of $ G $ that are strictly closer to $ u $ than to $ v $. The distance–unbalancedness index $ {\rm uB}(G) $ is defined as the sum of $ ...|n_G(u, v)-n_G(v, u)| $ over all unordered pairs of vertices $ u $ and $ v $ of $ G $. In this paper, we show that the minimum distance–unbalancedness of the merged graph $ C_3\cdot T $ is $ (n+2)(n-3) $, where $ C_3 \cdot T $ is obtained by attaching a tree $ T $ to the cycle $ C_3 $.
A connected graph
G
of diameter
diam
(
G
)
≥
ℓ
is
ℓ
-distance-balanced if
|
W
xy
|
=
|
W
yx
|
for every
x
,
y
∈
V
(
G
)
with
d
G
(
x
,
y
)
=
ℓ
, where
W
xy
is the set of vertices of
G
that are closer ...to
x
than to
y
. We prove that the generalized Petersen graph
GP
(
n
,
k
) is
diam
(
G
P
(
n
,
k
)
)
-distance-balanced provided that
n
is large enough relative to
k
. This partially solves a conjecture posed by Miklavič and Šparl (Discrete Appl Math 244:143–154, 2018). We also determine
diam
(
G
P
(
n
,
k
)
)
when
n
is large enough relative to
k
.
Distance-unbalancedness of graphs Miklavič, Štefko; Šparl, Primož
Applied mathematics and computation,
09/2021, Letnik:
405
Journal Article
Recenzirano
Odprti dostop
•In this manuscript we initiated the study of new structural invariant for graphs, based on a previously studied notion of being (ℓ)-distance-balanced.•We believe that this invariant will attract ...attention of numerous researchers working with various graph indices, such as the Wiener index, the Szeged index, etc.
In this paper we propose and study a new structural invariant for graphs, called distance-unbalancedness, as a measure of how much a graph is (un)balanced in terms of distances. Explicit formulas are presented for several classes of well-known graphs. Distance-unbalancedness of trees is also studied. A few conjectures are stated and some open problems are proposed.
The Mostar index is a recently‐introduced molecular structure descriptor used for measuring the peripherality and distance‐non‐balancedness extent in molecular graphs. In this paper, we present exact ...formulae or sharp upper bounds on the Mostar index of some families of graph operations. Using the obtained results, the peripherality extent of some chemical graphs and nanostructures are measured and a number of results related to the Mostar index of graph operations reported in (Int. J. Quantum. Chem. 2021, 121(15), e26674) and (TWMS J. App. and Eng. Math. 2021, 11(2), 587) are improved or generalized.
Studying topological indices of molecular graphs related to chemical compounds is difficult and time consuming work in general. One of the efficient ways for such studies is to produce molecular graphs with complicated structures from simpler graphs by using operations on graphs. This paper is concerned with studying a recently‐introduced molecular structure descriptor called Mostar index for various families of graph operations and some chemical graphs and nanostructures constructed from them.
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 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
. Confirming one of their conjectures, we show that the stars minimize the distance-unbalancedness among all trees of a fixed order.
PDF
