A proof of a conjecture on matching-path connected size Ramsey number

1.   Introduction

The Laplacian matrix of a graph $G$, denoted by $L(G)$, is given by $L(G) = D(G)-A(G)$, where $D(G)$ is the diagonal matrix of its vertex degrees and $A(G)$ is the adjacency matrix. The Laplacian characteristic polynomial of $G$, is equal to $\det(xI_n-L(G))$, denoted by $\phi(L(G))$. We denote $\lambda_i = \lambda_i(G)$ the $i$-th smallest eigenvalue of $L(G)$. In particular, $\lambda_2(G)$ and $\lambda_n(G)$ are called the algebraic connectivity ^[8] and the Laplacian spectral radius of $G$, respectively. The Laplacian spectral ratio of a connected graph $G$ with $n$ vertices is defined as $r_L(G) = \frac{\lambda_n}{\lambda_2}$. Barahona et al. ^[4] showed that a graph $G$ exhibits better synchronizability if the ratio $r_L(G)$ is small.

The topological indices have fundamental applications in chemical disciplines ^[5,7,31], computational linguistics ^[29], computational biology ^[28] and etc. Let $d(u, v)$ be the distance between vertices $u$ and $v$ of $G$. The Wiener index $W(G)$ of a connected graph $G$, introduced by Wiener ^[35] in 1947, is defined as $W(G) = \sum_{u, v\in V(G)}d(u, v)$, which is used to predict the boiling points of paraffins by their molecular structure. The Wiener index found numerous applications in pure mathematics and other sciences ^[13,21]. In 1972, Gutman and Trinajstić ^[18] proposed the first Zagreb index $M_1(G)$ of a graph $G$, and defined it as the sum of the squares of vertex degrees of $G$. There is a wealth of literature relating to the first Zagreb index, the readers are referred to ^[3,10,34] and the references therein. Recently, Furtula and Gutman ^[9] defined the forgotten topological index of a graph $G$ as the sum of the cubes of vertex degrees of $G$, denoted by $F(G)$. In particular, the forgotten topological index of several important chemical structures which have high frequency in drug structures is obtained ^[1,17]. The Kirchhoff index of a graph $G$ is defined as the sum of resistance distances ^[20] between all pairs of vertices of $G$, denoted by $Kf(G)$. Gutman and Mohar ^[15] gave an important calculation formula on Kirchhoff index, that is $Kf(G) = \sum_{i = 2}^{n}\frac{1}{\lambda_i}$. The Kirchhoff index is often used to measure how well connected a network is ^[12,20].

In 2010, Lipman, Rustamov and Funkhouser ^[25] proposed the biharmonic distance $d_B(u, v)$ between two vertices $u$ and $v$ in a graph $G$ as follows:

where $L_{uv}^{2+}$ is the $(u, v)$-entry of the matrix obtained from the square of Moore Penrose inverse of $L(G)$. They showed that the biharmonic distance has some advantages over resistance distance and geodesic distance in computer graphics, geometric processing, shape analysis and etc. Meanwhile, They used biharmonic distance to measure the distances between pairs of points on a 3D surface, which is a fundamental problem in computer graphics and geometric processing. Moreover, the biharmonic distance as a tool is used to analyze second-order consensus dynamics with external perturbations in ^[37,38]. Inspired by Wiener index, Yi et al. ^[37] and Wei et al. ^[36] proposed the concept of biharmonic index of a graph $G$ as follows:

Wei et al. ^[36] obtained a relationship between biharmonic index and Kirchhoff index and determined the unique graph having the minimum biharmonic index among the connected graphs with $n$ vertices.

In this paper, we study the biharmonic index of connected graphs from the perspective of Mathematics. Firstly, we establish the mathematical relationships between the biharmonic index and some classic topological indices: the first Zagreb index, the forgotten topological index and the Kirchhoff index. Secondly, we study the extremal value on the biharmonic index for all graphs with diameter two, trees and firefly graphs of fixed order, around Problem 6.3 in ^[36]. Finally, some graph operations on the biharmonic index are presented.

2.   Preliminaries

Let $K_{1, \, n-1}$, $P_n$ and $K_n$ denote the star, the path and the complete graph with $n$ vertices, respectively. Let $\tau(G)$ be the number of spanning trees of a connected graph. The double star $S(a, \, b)$ is the tree obtained from $K_2$ by attaching $a$ pendant edges to a vertex and $b$ pendant edges to the other. A firefly graph $F_{s, \, t, \, n-2s-2t-1}$ ($s\geq0, \, t\geq 0, \, n-2s-2t-1\geq 0$) is a graph of order $n$ that consists of $s$ triangles, $t$ pendent paths of length $2$ and $n-2s-2t-1$ pendent edges, sharing a common vertex. For $v\in V(G)$, let $L_v(G)$ be the principal submatrix of $L(G)$ formed by deleting the row and column corresponding to vertex $v$.

Lemma 2.1. (^[32]) Let $X = (a_1, \ldots, a_n)$ and $Y = (b_1, \ldots, b_n)$ be two positive $n$-tuples. Then

where $a = \min\{\frac{a_i}{b_i}\}$ and $A = \max\{\frac{a_i}{b_i}\}$ for $1\leq i \leq n$.

Lemma 2.2. (^[32]) Let $X = (a_1, \ldots, a_n)$ and $Y = (b_1, \ldots, b_n)$ be two positive $n$-tuples. Then

where $a = \min\{\frac{a_i}{b_i}\}$ and $A = \max\{\frac{a_i}{b_i}\}$ for $1\leq i \leq n$.

Lemma 2.3. (^[33]) If $a_i > 0$, $b_i > 0$, $p > 0$, $i = 1, 2, \ldots, n$, then the following inequality holds:

with equality if and only if $\frac{a_1}{b_1} = \frac{a_2}{b_2} = \cdots = \frac{a_n}{b_n}$.

Lemma 2.4. (^[30]) Let $n\geq 1$ be an integer and $a_1\geq a_2\geq \cdots \geq a_n$ be some non-negative real numbers. Then

Moreover, the equality holds if and only if for some $r\in \{1, 2, \ldots, n\}$, $a_1 = \cdots = a_r$ and $a_{r+1} = \cdots = a_n$.

Lemma 2.5. (^[22]) Let $a_1, \ldots, a_n\geq 0$. Then

where $\Phi = n\sum_{i = 1}^{n}a_i-\left(\sum_{i = 1}^{n}\sqrt{a_i}\right)^2$.

Lemma 2.6. (^[23]) Let $a_1, a_2, \ldots, a_n$ and $b_1, b_2, \ldots, b_n$ be real numbers such that $a\leq a_i\leq A$ and $b\leq b_i\leq B$ for $i = 1, 2, \ldots, n$. Then there holds

where $\lfloor x\rfloor$ denotes the integer part of $x$.

Lemma 2.7. (^[16]) If $T$ is a tree with diameter $d(T)$, then $\lambda_2(T)\leq 2\left(1-\cos\left(\frac{\pi}{d+1}\right)\right)$.

Lemma 2.8. (^[19]) The number of Laplacian eigenvalues less than the average degree $2-\frac{2}{n}$ of a tree with $n$ vertices is at least $\lceil \frac{n}{2}\rceil$.

Lemma 2.9. (^[6]) Let $G$ be a connected graph of diameter $2$. Then $\lambda_2(G)\geq 1$.

Lemma 2.10. (^[11]) Let $uv$ be a cut edge of a graph $G$. Let $G-uv = G_1+G_2$, where $G_1$ and $G_2$ are the components of $G-uv$, $G_1+G_2$ is the sum of $G_1$ and $G_2$, $u\in V(G_1)$ and $v\in V(G_2)$. Then

3.   The biharmonic index, the first Zagreb index and the forgotten topological index

In the following theorems, mathematical relations between the biharmonic index and other classic topological indices are established.

Theorem 3.1. Let $G$ be a connected graph with $n$ vertices and $m$ edges. Then

Proof. In this proof we use Lemma 2.1 with $a_i = \lambda_i$ and $b_i = \frac{1}{\lambda_i}$ for $2\leq i \leq n$. Then $a = \lambda_2^2$ and $A = \lambda_n^2$. Thus

Since $\sum_{i = 2}^{n}\lambda_i^2 = 2m+M_1(G)$, we have

that is,

This completes the proof.

Theorem 3.2. Let $G$ be a connected graph with $n$ vertices and $m$ edges. Then

Proof. In this proof we use Lemma 2.2 with $a_i = \lambda_i$ and $b_i = \frac{1}{\lambda_i}$ for $2\leq i \leq n$. Then $a = \lambda_2^2$ and $A = \lambda_n^2$. Thus

Since $\sum_{i = 2}^{n}\lambda_i^2 = 2m+M_1(G)$, we have

that is,

This completes the proof.

Theorem 3.3. Let $p$ be a positive real number and $G$ be a connected graph with $n$ vertices and $m$ edges. Then

with equality if and only if $G\cong K_n$.

Proof. In this proof we use Lemma 2.3 with $a_i = \lambda_i$ and $b_i = \frac{1}{\lambda_i^2}$ for $2\leq i \leq n$. Then we have

Since $\sum_{i = 2}^{n}\lambda_i = 2m$, we have

with equality if and only if $\lambda_2^3 = \cdots = \lambda_n^3$, that is $G\cong K_n$. This completes the proof.

Corollary 3.4. Let $G$ be a connected graph with $n$ vertices and $m$ edges. Then

with equality if and only if $G\cong K_n$.

Proof. Let $p = \frac{1}{3}$. Since $\sum_{i = 2}^{n}\lambda_i^{2} = 2m+M_1(G)$, by Theorem 3.3, we have

with equality if and only if $G\cong K_n$. This completes the proof.

Corollary 3.5. Let $G$ be a connected graph with $n$ vertices, $m$ edges and $t(G)$ triangles. Then

with equality if and only if $G\cong K_n$.

Proof. Let $p = \frac{2}{3}$. Since $\sum_{i = 2}^{n}\lambda_i^{3} = 3M_1(G)+F(G)+6t(G)$, by Theorem 3.3, we have

with equality if and only if $G\cong K_n$. This completes the proof.

4.   The biharmonic index and Kirchhoff index

In this section, we establish relationship between biharmonic index and Kirchhoff index based on the algebraic connectivity, the Laplacian spectral radius and the number of spanning trees.

Theorem 4.1. Let $G$ be a connected graph with $n$ vertices. Then

with equality if and only if for some $r\in \{2, \ldots, n\}$, $\lambda_2 = \cdots = \lambda_r$ and $\lambda_{r+1} = \cdots = \lambda_n$.

Proof. By Lemma 2.4, we have

that is,

that is,

that is,

with equality if and only if for some $r\in \{2, \ldots, n\}$, $\lambda_2 = \cdots = \lambda_r$ and $\lambda_{r+1} = \cdots = \lambda_n$. This completes the proof.

Theorem 4.2. Let $G$ be a connected graph with $n\geq 3$ vertices. Then

Proof. In this proof we use Lemma 2.5 with $a_i = \frac{1}{\lambda_i^2}$ for $2\leq i \leq n$. Then we have

where $\Phi = (n-1)\sum_{i = 2}^{n}\frac{1}{\lambda_i^2}-\left(\sum_{i = 2}^{n}\sqrt{\frac{1}{\lambda_i^2}}\right)^2 = \frac{n-1}{n}BH(G)-\frac{1}{n^2}Kf^2(G)$. Since $\prod_{i = 2}^{n}\lambda_i = n\tau(G)$, we have

where $\Phi = \frac{n-1}{n}BH(G)-\frac{1}{n^2}Kf^2(G)$. Thus we have

This completes the proof.

Theorem 4.3. Let $G$ be a connected graph with $n$ vertices. Then

Proof. In this proof we use Lemma 2.6 with $a_i = b_i = \frac{1}{\lambda_i}$ for $2\leq i \leq n$. Then we have

that is,

Note that $\left\lfloor\frac{n}{2}\right\rfloor\left(1-\frac{1}{n}\left\lfloor\frac{n}{2}\right\rfloor\right) = \frac{n}{4}\left(1-\frac{1+(-1)^{n+1}}{2n^2}\right)$. We have

This completes the proof.

5.   The biharmonic index of trees and firefly graphs

In this section, we study the extremal value on the biharmonic index for trees and firefly graphs of fixed order. Moreover, we show that the star is the unique graph with maximum biharmonic index among all graphs on diameter two.

Theorem 5.1. Let $S(a, b)$ be a double star tree on $n$ vertices and $a+b = n-2$. Then

the left (right) equality holds if and only if $S(1, n-3)$ $(S(\lceil\frac{n-2}{2}\rceil, \lfloor\frac{n-2}{2}\rfloor)$.

Proof. By direct calculation, we have

Let $x_1$, $x_2$ and $x_3$ be the roots of the following polynomial

By the Vieta Theorem, we have

Thus

Further, we have

Since $n-3\leq ab \leq \lceil\frac{n-2}{2}\rceil\lfloor\frac{n-2}{2}\rfloor$, we have

the left (right) equality holds if and only if $S(1, n-3)$ $(S(\lceil\frac{n-2}{2}\rceil, \lfloor\frac{n-2}{2}\rfloor)$. This completes the proof.

Theorem 5.2. Let $T_n$ be a tree on $n\geq 8$ vertices. If the diameter $d(T_n)\geq \pi \sqrt[4]{\frac{7n}{8}}-1$, then

Proof. Since $1-\cos x < \frac{x^2}{2}$, by Lemma 2.7, we have

By Lemma 2.8, we have

for $n\geq 8$. This completes the proof.

The following conjecture is concretization of Problem 6.3 in ^[36].

Conjecture 5.3. Let $T_n$ be a tree on $n\geq 5$ vertices. Then

the left (right) equality holds if and only if $T_n = K_{1, \, n-1}$ ($T_n = P_n$).

Theorem 5.4. Let $G$ be a connected graph with $n$ vertices and diameter $d(G) = 2$. Then

with equality if and only if $G = K_{1, \, n-1}$.

Proof. It is well known that $\lambda_n\geq \Delta+1$ and $\lambda_{n-1}\geq \Delta_2$ (see ^[14,24]), where $\Delta$ and $\Delta_2$ are the maximum degree and the second largest degree of $G$, respectively. If $2\leq\Delta_2\leq \Delta$, by Lemma 2.9, we have

Thus $\Delta_2 = 1$, that is, $G = K_{1, \, n-1}$, then $BH(G) = BH(K_{1, \, n-1})$.

Combining the above arguments, we have $BH(G)\leq BH(K_{1, \, n-1})$ with equality if and only if $G = K_{1, \, n-1}$. This completes the proof.

Theorem 5.5. Let $F_{s, \, t, \, n-2s-2t-1}$ ($s\geq0, \, t\geq 0, \, n-2s-2t-1\geq 0$) be a firefly graph with $n\geq 7$ vertices.

(1) If $s = t = 0$, then $BH(F_{0, \, 0, \, n-1}) = n^2-2n+\frac{1}{n}$.

(2) If $s = 0$ and $t = 1$, then $BH(F_{0, \, 1, \, n-3}) = n^2+3n-16+\frac{4}{n}$.

(3) If $s = 0$, $t\geq 2$ and $n$ is odd, then

the left (right) equality holds if and only if $F_{0, \, t, \, n-2t-1} = F_{0, \, 2, \, n-5}$ ($F_{0, \, t, \, n-2t-1} = F_{0, \, \frac{n-1}{2}, \, 0}$).

If $s = 0$, $t\geq 2$ and $n$ is even, then

the left (right) equality holds if and only if $F_{0, \, t, \, n-2t-1} = F_{0, \, 2, \, n-5}$ ($F_{0, \, t, \, n-2t-1} = F_{0, \, \frac{n-2}{2}, \, 1}$).

(4) If $s\geq 1$, $t = 0$ and $n$ is odd, then

the left (right) equality holds if and only if $F_{s, \, 0, \, n-2s-1} = F_{1, \, 0, \, n-3}$ ($F_{s, \, 0, \, n-2s-1} = F_{\frac{n-1}{2}, \, 0, \, 0}$).

If $s\geq 1$, $t = 0$ and $n$ is even, then

the left (right) equality holds if and only if $F_{s, \, 0, \, n-2s-1} = F_{1, \, 0, \, n-3}$ ($F_{s, \, 0, \, n-2s-1} = F_{\frac{n-2}{2}, \, 0, \, 1}$).

(5) If $s\geq 1$, $t\geq 1$ and $n$ is odd, then

the left (right) equality holds if and only if $F_{s, \, t, \, n-2s-2t-1} = F_{\frac{n-3}{2}, \, 1, \, 0}$ ($F_{s, \, t, \, n-2s-2t-1} = F_{1, \, \frac{n-3}{2}, \, 0}$).

If $s\geq 1$, $t\geq 1$ and $n$ is even, then

the left (right) equality holds if and only if $F_{s, \, t, \, n-2s-2t-1} = F_{\frac{n-4}{2}, \, 1, \, 1}$ ($F_{s, \, t, \, n-2s-2t-1} = F_{1, \, \frac{n-4}{2}, \, 1}$).

Proof. (1) If $s = t = 0$, then $F_{0, \, 0, \, n-1}\cong K_{1, \, n-1}$. Thus $BH(F_{0, \, 0, \, n-1}) = n^2-2n+\frac{1}{n}$.

(2) If $s = 0$ and $t = 1$, by Lemma 2.10, we have

By a similar reasoning as the proof of Theorem 5.1, we have

(3) If $s = 0$ and $t\geq 2$, then we have

By a similar reasoning as the proof of Theorem 5.1, we have

If $2\leq t\leq \frac{n-1}{2}$ for odd $n$, we have

the left (right) equality holds if and only if $F_{0, \, t, \, n-2t-1} = F_{0, \, 2, \, n-5}$ ($F_{0, \, t, \, n-2t-1} = F_{0, \, \frac{n-1}{2}, \, 0}$). If $2\leq t\leq \frac{n-2}{2}$ for even $n$, we have

the left (right) equality holds if and only if $F_{0, \, t, \, n-2t-1} = F_{0, \, 2, \, n-5}$ ($F_{0, \, t, \, n-2t-1} = F_{0, \, \frac{n-2}{2}, \, 1}$).

(4) If $s\geq 1$ and $t = 0$, by Lemma 2.10, we have

Thus

If $1\leq s\leq \frac{n-1}{2}$ for odd $n$, we have

the left (right) equality holds if and only if $F_{s, \, 0, \, n-2s-1} = F_{1, \, 0, \, n-3}$ ($F_{s, \, 0, \, n-2s-1} = F_{\frac{n-1}{2}, \, 0, \, 0}$). If $1\leq s\leq \frac{n-2}{2}$ for even $n$, we have

the left (right) equality holds if and only if $F_{s, \, 0, \, n-2s-1} = F_{1, \, 0, \, n-3}$ ($F_{s, \, 0, \, n-2s-1} = F_{\frac{n-2}{2}, \, 0, \, 1}$).

(5) If $s\geq 1$ and $t\geq 1$, by Lemma 2.10, we have

By a similar reasoning as the proof of Theorem 5.1, we have

If $s = 1$ and $t = \frac{n-3}{2}$ for odd $n$, we have

the equality holds if and only if $F_{s, \, t, \, n-2s-2t-1} = F_{1, \, \frac{n-3}{2}, \, 0}$.

If $s = 1$ and $t = \frac{n-4}{2}$ for even $n$, we have

the equality holds if and only if $F_{s, \, t, \, n-2s-2t-1} = F_{1, \, \frac{n-4}{2}, \, 1}$.

If $s = \frac{n-3}{2}$ and $t = 1$ for odd $n$, we have

the equality holds if and only if $F_{s, \, t, \, n-2s-2t-1} = F_{\frac{n-3}{2}, \, 1, \, 0}$.

If $s = \frac{n-4}{2}$ and $t = 1$ for even $n$, we have

the equality holds if and only if $F_{s, \, t, \, n-2s-2t-1} = F_{\frac{n-4}{2}, \, 1, \, 1}$.

Combining the above arguments, we have the proof.

6.   The biharmonic index and graph operations

Lemma 6.1. (^[26]) Let $G$ be a connected graph with $n$ vertices. Then $\lambda_i(\overline{G}) = n-\lambda_{n+2-i}(G)$ for $i = 2, \ldots, n$.

Theorem 6.2. Let $G$ be a connected graph with $n$ vertices. If $\overline{G}$ is a connected graph, then

Proof. By Lemma 6.1, we have the proof.

The union of two graphs $G_1$ and $G_2$ is the graph $G_1\cup G_2$ with vertex set $V_1(G)\cup V_2(G)$ and edge set $E(G_1)\cup E(G_2)$. The join $G_1\vee G_2$ is obtained from $G_1\cup G_2$ by adding to it all edges between vertices from $V(G_1)$ and $V(G_2)$.

Lemma 6.3. (^[27]) Let $G_1$ and $G_2$ be graphs on $n_1$ and $n_2$ vertices, respectively. Then the Laplacian eigenvalues of $G_1\vee G_2$ are $n_1+n_2$, $\lambda_i(G_1)+n_2$ ($2\leq i\leq n_1$) and $\lambda_j(G_2)+n_1$ ($2\leq j\leq n_1$).

Theorem 6.4. Let $G$ be a connected graph with $n$ vertices. Then

Proof. By Lemma 6.3, we have the proof.

The Cartesian product of $G_1$ and $G_2$ is the graph $G_1\Box G_2$, whose vertex set is $V = V_1\times V_2$ and where two vertices $(u_i, v_s)$ and $(u_j, v_t)$ are adjacent if and only if either $u_i = u_j$ and $v_sv_t\in E(G_2)$ or $v_s = v_t$ and $u_iu_j\in E(G_1)$.

Lemma 6.5. (^[8,26]) Let $G_1$ and $G_2$ be graphs on $n_1$ and $n_2$ vertices, respectively. Then the Laplacian eigenvalues of $G_1\Box G_2$ are all possible sums $\lambda_i(G_1)+\lambda_j(G_2)$, $1\leq i \leq n_1$ and $1\leq j \leq n_2$.

Theorem 6.6. Let $G_1$ and $G_2$ be two connected graphs. Then

Proof. By Lemma 6.5, we have the proof.

The lexicographic product $G_1[G_2]$, in which vertices $(u_i, v_s)$ and $(u_j, v_t)$ are adjacent if either $u_iu_j\in E(G_1)$ or $u_i = u_j$ and $v_sv_t\in E(G_2)$ (see ^[2]).

Lemma 6.7. (^[2]) Let $G_1$ and $G_2$ be graphs on $n_1$ and $n_2$ vertices, respectively. Then the Laplacian eigenvalues of $G_1[G_2]$ are $n_2\lambda_i(G_1)$ and $\lambda_j(G_2)+d(u_i)n_2$, where $d(u_i)$ is vertex degree of $G_1$, $1\leq i \leq n_1$ and $2\leq j \leq n_2$.

Theorem 6.8. Let $G_1$ and $G_2$ be connected graphs on $n_1$ and $n_2$ vertices, respectively.

Proof. By Lemma 6.7, we have the proof.

7.   Conclusions

We study the biharmonic index from three aspects: the mathematical relationships between the biharmonic index and some classic topological indices, the extremal value on the biharmonic index for some special graph classes, and some graph operations on the biharmonic index. On the basis of the biharmonic distance, the biharmonic eccentricity $\varepsilon_b(u)$ of vertex $u$ in a connected graph $G$ is defined as $\varepsilon_b(u) = \max\{d_{B}(u, v)\mid v\in V(G)\}$. Let $d(u)$ be the degree of the corresponding vertex $u$. The following four topological indices will be the problems that need further exploration.

(1) The Schultz biharmonic index:

(2) The Gutman biharmonic index:

(3) The eccentric biharmonic distance sum:

(4) The multiplicative eccentricity biharmonic distance:

Acknowledgments

The author is grateful to the anonymous referee for careful reading and valuable comments which result in an improvement of the original manuscript. This work was supported by the National Natural Science Foundation of China (No. 12071411) and Qinghai Provincial Natural Science Foundation (No. 2021-ZJ-703).

Conflict of interest

The authors declare no conflict of interest.