Minimum distance–unbalancedness of the merged graph of $C_3$ and a tree

1.   Introduction

Throughout this paper, all graphs are simple, undirected, finite, and connected. Let $G$ be a graph on $n$ vertices with vertex set $V(G)$ and edge set $E(G)$. For two vertices $u$ and $v$ of $G$, let dist$_G(u, v)$ denote the distance in $G$ between $u$ and $v$, and let $n_G(u, v)$ be the number of vertices $w$ of $G$ that are strictly closer to $u$ than to $v$, that is, that satisfy dist$_G(u, w) \; <$ dist$_G(v, w)$. We say that this pair of vertices is balanced if $n_G(u, v) = n_G(v, u)$. Thus, a connected graph is distance-balanced if and only if every pair of adjacent vertices is balanced.

For a positive integer $n$, the complete bipartite graph $K_{1, n-1}$ will be called the star of order $n$ and will be denoted by $S_{n-1}$. The cycle of order $n\geq 3$ will be denoted by $C_n$, and the path of order $n$ (and thus length $n-1$) will be denoted by $P_n$.

Topological indices play an important role in mathematical chemistry as well as in graph theory, which has been studied for several decades. Various indices are defined as sums of certain quantities over all vertices (such as the first Zagreb index ^[1]), over all pairs of adjacent vertices (such as the Szeged index ^[2]), or over all pairs of vertices of graphs (such as the Wiener index ^[3]).

To measure the peripherality in a graph $G$ (i.e., how far a graph is from being distance–balanced ^[4]), Došlić et al. ^[5] introduced the Mostar index of $G$, which is defined as

This index is closely related to the concept of distance-balancedness of graphs, which was first studied in ^[6]. In terms of the Mostar index, a graph is distance-balanced if and only if its Mostar index is equal to $0$. For more research on the Mostar index, see ^[7,8,9].

In 2021, Miklavič and Šparl ^[10] introduced the distance–unbalancedness (index) of a graph $G$ which is defined as

where $\left(_{\; 2}^{V(G)}\right)$ denotes the set of all 2-element subsets of the vertex set $V(G)$ of $G$.

As the definition of distance–unbalancedness involves a summation over all unordered pairs of distinct vertices, this parameter is much harder to approach than many other comparable parameters. Therefore, there have been very few results in this field up to now.

Miklavič and Šparl ^[10] computed the distance–unbalancedness index ${\rm uB}(G)$ for members of some well-known families of graphs, such as the complete multipartite graphs, the wheel graphs, and the Cartesian products of paths by cycles. Specifically, the distance–unbalancedness index of paths with $n$ vertices was obtained

A few conjectures about the minimum or maximum distance–unbalancedness indices of trees, spider graphs, and kite graphs are proposed.

Later, Kramer and Rautenbach ^[11] confirmed one of the above conjecture, and showed that the stars minimize the distance–unbalancedness among all trees of a fixed order, i.e.,

Meanwhile, they ^[12] contributed to problems posed by Miklavič and Šparl, and obtained the maximum distance–unbalancedness of the tree and the subdivided star, where the subdivided star $S(n_1, \cdots, n_k)$ arises from the star $K_{1, k}$ with the $k$ edges $e_1, \cdots, e_k$ by subdividing the edge $e_i$ exactly $n_i-1$ times for every $i\in \{1, \cdots, k\}$.

A merged graph of $C_3$ and a tree $T$, denoted by $C_3 \cdot T$, is obtained by attaching one vertex of the cycle $C_3$ with a vertex of a tree $T$, where $|V(T)| = n-2$. $S_{3, n}$ and $P_{3, n}$ are the merged graphs obtained by attaching a pendent-vertex of the star $S_{n-3}$ and an end-vertex of the path $P_{n-2}$ to $C_3$, respectively. Especially, let $\overline{S}_{3, n}$ be the merged graph obtained by attaching the center of the star $S_{n-3}$ to $C_3$. Clearly, $|V(C_3 \cdot T)| = |V(P_{3, n})| = |V(S_{3, n})| = |V(\overline{S}_{3, n})| = n$.

Although the conjecture of minimum distance–unbalancedness of trees has been solved, there are still some open problems worth studying in ^[10], such as the following:

Problem 1.1 (Miklavič and Šparl ^[10]) For each integer $n\geq 3$, determine the smallest possible nonzero value of the distance–unbalancedness index among all connected graphs of order $n$ and classify all graphs attaining this value.

Very recently, Ghorbani and Vaziri ^[13] classified all distance–balanced graphs with Sz-complexity one, where the Sz-complexity (W-complexity) is the number of different contributions to the Szeged index (Wiener index) in its summation formula. Moreover, the Sz-complexity and W-complexity of some merged graphs, such as the windmill graph and the Duch windmill graph, are determined. Inspired by this, we mainly study the minimum distance-unbalancedness of a merged graph $C_3\cdot T$. The minimum value and extremal graph with the minimum distance–unbalancedness of a merged graph $C_3 \cdot T$ are characterized, which has certain significance for investigating Problem 1.1. The detailed results are summarized as follows:

Theorem 1.2 Let $H = C_{3}\cdot T$ be a merged graph of $C_3$ and a tree $T$, where $|V(T)| = n-2$ and $|V(C_3 \cdot T)| = n$. Then

Moreover, ${\rm uB}(H) = 12$ if and only if $H = P_{3, 5}$ for $n = 5$, and ${\rm uB}(H) = 20$ if and only if $H = S_{3, 6}$ for $n = 6$, and ${\rm uB}(H) = (n+2)(n-3)$ if and only if $H = \overline{S}_{3, n}$ for $n\geq 7$.

The rest of this paper is devoted to the proof of Theorem 1.2.

2.   Proof of Theorem 1.2

For a graph $G$, the $k$-th power graph $G^k$ of $G$ has the same vertex set as $G$, and two distinct vertices of $G$ are adjacent in $G^k$ if their distance in $G$ is at most $k$. In order to prove Theorem 1.2, we consider the following auxiliary parameter:

and we establish the following lemma.

Lemma 2.1 Let $H = C_{3}\cdot T$ and $n\geq 8$, then ${\rm uB_3}(H)\geq (n+2)(n-3)$.

Before proving the lemma, we show that Theorem 1.2 is an immediate consequence.

Proof of Theorem 1.2. For $n\geq 8$, we have ${\rm uB}(H)\geq {\rm uB_3}(H)\geq (n+2)(n-3)$ by Lemma 2.1. It is an easy calculation that $H = S_{3, n}$ satisfies ${\rm uB}(H) = (n+2)(n-3)$. Now, in order to complete the proof, we only need to prove that ${\rm uB}(H) > (n+2)(n-3)$ if $H\not = S_{3, n}$. Since ${\rm uB}(H) = (n+2)(n-3)$ implies ${\rm uB}(H) = {\rm uB_3}(H)$, we have $n_H(u, v) = n_H(v, u)$ for every two vertices $u$ and $v$ at distance four in $H$.

Let $u$ and $v$ be two vertices at distance four in $H$. Suppose $u$ has a neighbor $u'$ that does not lie on the path $P$ between $u$ and $v$, and $v'$ is the neighbor of $v$ on $P$. If $u'$ and $v'$ have a distance of four, we obtain that $n_H(u', v') < n_H(u, v) = n_H(v, u) < n_H(v', u')$, which is a contradiction. Therefore, if there are vertices at distance four in $H$, $n_H(u, v) = n_H(v, u)$ implies that the induced subgraph of $H$ is isomorphic to the solid line in Figure 1(a). Furthermore, by the distinct connections with the center vertex $w$, we can conclude that $H$ can only be isomorphic to the graph in Figure 1(a) or 1(b). In Figure 1(a), we have

In Figure 1(b), $H$ is obtained by attaching $\frac{(n-4)}{3}$ stars $S_{3}$ and one subgraph $S_{3}+e$ to the center vertex $w$. So, we have

If the maximum distance between every two vertices $u$ and $v$ of $H$ is three, then $H$ is isomorphic to the graph in Figure 2. If there are $x$ pendant vertices far from the cycle $C_3$, then the number of pendant vertices adjacent to $C_3$ is $(n-4-x)$. So, we have

For $n = 5, 6$, and $7$, using enumeration to calculate the minimum value of ${\rm uB}(H)$. For convenience, we use the degree sequence of graphs to represent graph $H$. For instance, the degree sequence of graph $P_{3, 5}$ is denoted by $(2, 2, 3, 2, 1)$, the degree sequence of $S_{3, 6}$ is denoted by $(2, 2, 3, 3, 1, 1)$, and the degree sequence of $\overline{S}_{3, 7}$ is denoted by $(2, 2, 6, 1, 1, 1, 1)$.

If $n = 5$, since $H = C_{3}\cdot T$, then $T = P_3$, and by the distinct attaching of $C_{3}$ with $P_3$, $H_1 = (2, 2, 3, 2, 1)$, or $H_2 = (2, 2, 4, 2, 1)$. It is easy to obtain by calculation that ${\rm uB}(H_1) = 12$ and ${\rm uB}(H_2) = 14$, and hence, ${\rm uB}(H)\geq {\rm uB}(H_1) = 12$, where $H_1 = (2, 2, 3, 2, 1) = P_{3, 5}$.

If $n = 6$, then $T = P_4$ or $T = S_3$. Analogously, by the distinct attachment of $C_{3}$ to $P_4$ or $S_3$, there exist four degree sequences: $H_1 = (2, 2, 3, 2, 2, 1)$, $H_2 = (2, 2, 4, 1, 2, 1)$, $H_3 = (2, 2, 3, 3, 1, 1)$, and $H_4 = (2, 2, 5, 1, 1, 1)$. It is not difficult to obtain that ${\rm uB}(H_1) = 22$, ${\rm uB}(H_2) = 28$, ${\rm uB}(H_3) = 20$, and ${\rm uB}(H_4) = 24$. Therefore, ${\rm uB}(H)\geq {\rm uB}(H_3) = 20$, where $H_3 = (2, 2, 3, 3, 1, 1) = S_{3, 6}$.

For $n = 7$, then $T = P_5$, or $T = S_4$, or $T$ is a merged graphs obtained by attaching a pendent vertex of $S_{3}$ to $P_2$. Analogously, by the distinct attachment of $C_{3}$ to $T$, there exists nine degree sequences: $H_1 = (2, 2, 3, 2, 2, 2, 1)$, $H_2 = (2, 2, 4, 1, 2, 2, 1)$, $H_3 = (2, 2, 4, 2, 2, 1, 1)$, $H_4 = (2, 2, 3, 3, 1, 2, 1)$, $H_5 = (2, 2, 5, 1, 1, 2, 1)$, $H_6 = (2, 2, 4, 1, 3, 1, 1)$, $H_7 = (2, 2, 3, 2, 3, 1, 1)$, $H_8 = (2, 2, 3, 4, 1, 1, 1)$, and $H_9 = (2, 2, 6, 1, 1, 1, 1)$. After some tedious calculations, it can be concluded that ${\rm uB}(H)\geq 36$, with equality holds if and only if $H = H_9 = \overline{S}_{3, 7}$.

This completes the proof. □

3.   Proof of Lemma 2.1

In this section, we proceed to the proof of the lemma.

Proof of Lemma 2.1. Choose the graph $H = C_{3}\cdot T$ of order $n$ such that ${\rm uB_3}(H)$ is as small as possible. Hence, $H$ has at least one vertex of degree $\geq 3$. We will consider two different cases.

Case 1. $H$ has exactly one vertex $c$ of degree $k+2$, where $k\geq 1$.

In this case, there are $k+1$ components of $H-c$, one of which is $P_2$, and the other $k$ components are paths of orders $n_1, \cdots, n_k$, such that $n_1\geq n_2\geq \cdots\geq n_k\geq 1$. Thus, $n_1+n_2+ \cdots+n_k = n-3$.

Case 1.1. $n_1\leq \frac{n}{2}$.

Note that $\sum_{i = 1}^k \big[(n-4)+(n-6)+\cdots+n-2(n_i-1)\big]+2(n-2n_1)+\sum_{i = 1}^{k-1}\sum_{j = i+1}^k (n-2n_i)\geq 2n-10$ for $n\geq 8$, and thus have

where $f_1(n, k) = 2n^2-(k+3)n+k-13$.

We consider the following optimization problem:

Let $(n_1, n_2, \cdots, n_k)$ be a lexicographically maximal optimal solution of (3.1).

If $n_1 < \frac{n}{2}$, $n_i > 1$ for some $i\in\{2, \cdots, k\}$, and $i$ is chosen largest with this property, then

Therefore, if $n_i > 2$ or $n_1 > n_i = 2$, $(n_1+1, \cdots, n_i-1, \cdots, n_k)$ is a better solution of (3.1), which is a contradiction. This implies that there are only two cases:

$(a)\; n_1 = \cdots = n_i = 2, n_{i+1} = \cdots = n_k = 1$.

$(b)\; n_1 = n-k-2, n_2 = \cdots = n_k = 1$.

In the first case, since $2(n-2n_1)+\sum_{i = 1}^{k-1}\sum_{j = i+1}^k (n-2n_i)\geq 3(n-4)$, we have

In the second case, since $f(n_1) = -2n_1^2+(n+2)n_1+n-14$ is a quadratic function that is concave down and $f(2) = f(\frac{n}{2}-1) = 3n-18 > 0$ for $n\geq 8$, we get $f(n_1) > 0$. Therefore,

Finally, if $n_1 = \frac{n}{2}$ and $n_2 < \frac{n}{2}-k-1$, then $n_i > 1$ for some $i\in\{3, \cdots, k\}$. If $i$ is largest with this property, then

This implies that $(n_1, n_2+1, \cdots, n_i-1, \cdots, n_k)$ is a better solution of (3.1), which is a contradiction. So, there is only the following case:

$(c)\; n_1 = \frac{n}{2}$, $n_2 = \frac{n}{2}-k-1$, $n_3 = \cdots = n_k = 1$. Therefore, we have

Case 1.2. $n_1 > \frac{n}{2}$.

Note that for $n\geq 8$, $\sum_{i = 1}^k \big[(n-4)+(n-6)+\cdots+|n-2(n_i-1)|\big]+2(2n_1-n)\geq 2n-10+4 = 2n-6$, we have

where $f_2(n, k) = 2n^2-(k-1)n+k-12$.

We consider the following optimization problem:

Let $(n_1, n_2, \cdots, n_k)$ be a lexicographically maximal optimal solution of (3.2).

Note that $n_1+n_i\leq n_1+n_2\leq n-3-(k-2) = n-k-1$, $4(n_1+n_i)-4n+k+6\leq 4(n-k-1)-4n+k+6 = -3k+2 < 0$.

If $n_i > 1$ for some $i\in\{2, \cdots, k\}$, and $i$ is largest with this property, then

This observation implies that

$(d)\; n_1 = n-k-2$, $n_2 = \cdots = n_k = 1$. Therefore, we obtain

Case 2. $H$ has at least two vertices of degree at least three.

Considering the vertex of degree at least three that is farthest to $C_3$, denoted as $c$, which has a degree of $k+1$, where $k\geq 2$. It follows that $H-c$ has $k+1$ components, where $k$ components are paths of orders $n_1, \cdots, n_k$ with $n_1\geq n_2\geq \cdots\geq n_k\geq 1$. Let $n' = 1+n_1+n_2+ \cdots+n_k$, the other component $K$ of order $n-n'$.

Let $d\in V(K)$ be the neighbor of $c$. Let the new graph $H'$ arise from the disjoint union of $K$ and a path $P$ of order $n'$ by adding one edge between $d$ and an endvertex of $P$. Our goal is to show that ${\rm uB_3}(H) > {\rm uB_3}(H')$, which would contradict the choice of $H$, and complete the proof.

Case 2.1. $n' = 1+n_1+n_2+ \cdots+n_k\leq \frac{n}{2}$.

where $f_3(n, n', k)$ is a suitable function of $n, n'$ and $k$.

By the convexity of the function $g(x) = x^2$,

implies that

$(e)\; n_1 = n'-k$, $n_2 = \cdots = n_k = 1$.

Note that $3n' = 2n'+n'\geq 2(k+1)+3\geq 2k+5$, and hence,

Case 2.2. $n' = 1+n_1+n_2+ \cdots+n_k > \frac{n}{2}$.

Case 2.2.1. $n_1\leq \frac{n}{2}$.

Similar to the above case, it can be concluded that

where $f_4(n, n', k)$ is a suitable function of $n, n'$ and $k$.

By the convexity of the function $g(x) = x^2$,

implies that

$(f)\; n_1 = n'-k$, $n_2 = \cdots = n_k = 1$.

Note that $f(n') = -6n'^2+(6n+5k+1)n'-\frac{3}{2}n^2-(k+2)n-2k^2+1$ is a quadratic function that is concave, where $\frac{n}{2}+1\leq n'\leq n-3$. By some tedious calculations, it can be concluded that $f(\frac{n}{2}+1) > 0$ and $f(n-3) > 0$. Therefore, we have

Case 2.2.2. $n_1 > \frac{n}{2}$.

We have

where $f_5(n, n', k)$ is a suitable function of $n, n'$ and $k$.

We consider the following optimization problem:

Note that

and hence,

$(g)\; n_1 = n'-k$, $n_2 = \cdots = n_k = 1$. Then

which is the desired contradiction, completing the proof. □

4.   Conclusions

From ^[11], Kramer and Rautenbach showed that the star is the unique tree of order $n$ having the minimum possible distance–unbalancedness index among all trees of order $n$. This result leads to a natural questions what is the minimum distance–unbalancedness index and the extremal graph among all unicylic graphs of order $n$? After trying, we found that it is extremely difficult, and we cannot even determine the minimum value of a unicylic graph with girth three.

In the paper, the minimum value and extremal graph with the minimum distance–unbalancedness of a merged graph $C_3 \cdot T$ are characterized. As a type of connected graphs, our work is of interest, which has certain significance for investigating Problem 1.1. However, Problem 1.1 has been completely confirmed, and there will still be numerous tasks to be done.

Finally, we propose the following conjecture based on previous results:

Conjecture 4.1. Let $G$ be a unicylic graph on $n$ vertices with girth three. Then

Author contributions

Zhenhua Su: Writing-original draft preparation, Writing-review and editing; Zikai Tang: Formal analysis, Methodology. All authors have read and agreed to the published version of the manuscript.

Use of AI tools declaration

The authors declare they have not used Artificial Intelligence (AI) tools in the creation of this article.

Acknowledgments

This work is supported by the Department of Education of Hunan Province (22B0763).

Conflict of interest

The authors declare that they have no conflicts of interest.