On Matching Characterization of $P_m\cup T\left(1,3,n\right)$

Shichang Shen

School of Mathematics and Statistics, Qinghai Minzu University, Xining, China.

DOI: 10.4236/ojapps.2025.154068                

Abstract

We consider the problem of graphs characterization by its matching polynomial. In the paper, we show that $P_m\cup T\left(1,3,n\right)$ are determined by its matching polynomial iff $m$ is even or 3 and $n\ne 3,6,11$ .

Keywords

T-Shape Tree, Matching Polynomial, Matching Characterization

1. Introduction

All graphs in the paper are finite and have no loops or multiple edges. Let $G$ be a graph with $n$ vertices. An r-matching in a graph $G$ is a set of $r$ edges, no two of which have a vertex in common. The number of r-matching in $G$ will be denoted by $p\left(G,r\right)$ . We set $p\left(G,0\right)=1$ and define the matching polynomial of $G$ by

$\mu \left(G,x\right)={\displaystyle \sum _{r\ge 0}{\left(-1\right)}^{r}p\left(G,r\right)x^{n-2r}}$ (1)

The matching polynomial has very important applications in mathematics, statistical physics, and chemistry. In statistical physics, it serves as a mathematical model for describing a certain physical system. Physicists Heilmann and Lieb first introduced the matching polynomial of a graph in reference [1] to study this physical system. In theoretical chemistry, the sum of the absolute values of the roots of the matching polynomial is called the matching energy level of the graph, which is related to the activity of the aromatic hydrocarbon represented by this graph (see [2]). The sum of the absolute values of all its coefficients (that is, the total number of all matchings) is the Hosoya index of the hydrocarbon represented by this graph (see [3]).

For any graph $G$ , the roots of $\mu \left(G,x\right)$ are all real numbers. Assume that ${\gamma }_1\left(G\right)\ge {\gamma }_2\left(G\right)\ge \cdots \ge {\gamma }_n\left(G\right)$ , the largest root ${\gamma }_1\left(G\right)$ is referred to as the largest matching root of $G$ .

Throughout the paper, we denote by $P_n$ and $C_n$ the path and the cycle on $n$ vertices, respectively. $T\left(a,b,c\right)\left(a\le b\le c\right)$ denotes the tree with a vertex $v$ of degree 3 such that $T\left(a,b,c\right)-v=P_a\cup P_b\cup P_c$ , and $H\left(a,b,c\right)$ denotes the tree obtained from the path with versices $1,2,\cdots ,a+b+c-1$ (in order) by attching a pendant edge at each of the verices $a$ and $a+b$ . $Q\left(s_1,s_2\right)$ is obtained by appending a cycle $C_{s_1+1}$ to a pendant vertex of a path $P_{s_2}$ . Two graphs are matching equivalency if they share the same matching polynomial. A graph $G$ is said to be determined by its matching polynomial if for any graph $H$ , $\mu \left(G,x\right)=\mu \left(H,x\right)$ implies that $H$ is isomorphic to $G$ . For the notations and terms not explained in this article, please refer to [4]. Since Farrell E. J. studied the problem of graphs characterization by its matching polynomial, many matching characterization graphs have been found (see [5]-[8]). However, as most of the methods used are to compare the coefficients of the matching polynomials of two graphs, this work is quite difficult and progresses slowly. There are still a large number of problems that have not been solved. the paper makes full use of the information about the roots of the matching polynomial $\mu \left(G,x\right)$ , we prove $P_m\cup T\left(1,3,n\right)$ are determined by its matching polynomial iff $m$ is even or 3 and $n\ne 3,6,11$ .

2. Basic Results

Lemma 2.1 [4]. The matching polynomial $\mu \left(G,x\right)$ satisfies the following identities:

a) $\mu \left(G\cup H,x\right)=\mu \left(G,x\right)\mu \left(H,x\right)$ .

b) $\mu \left(G,x\right)=\mu \left(G\backslash e,x\right)-\mu \left(G\backslash u,v,x\right)$ if $e=\left\{u,v\right\}$ is an edge of $G$ .

Lemma 2.2 [4]. Let $G$ be a connected graph, and let $H$ be a proper subgraph $G$ . Then ${\gamma }_1\left(G\right)>{\gamma }_1\left(H\right)$ .

Lemma 2.3 [4]. Let $u$ be a vertex in the graph$G$ . Then the roots of $\mu \left(G\backslash u,x\right)$ interlace those of $\mu \left(G,x\right)$ . If $G$ is connected then the largest root of $\mu \left(G,x\right)$ is simple ,and is strictly greater than the largest root of $\mu \left(G\backslash u,x\right)$ .

Lemma 2.4 [5] [6]. Let $G$ be a connected graph, then

a) ${\gamma }_1\left(G\right)<2$ iff $G\in \left\{P_n,T\left(1,1,n\right),T\left(1,2,2\right),T\left(1,2,3\right),T\left(1,2,4\right),C_m,Q\left(2,1\right)\right\}$ .

b) ${\gamma }_1\left(G\right)=2$ iff $G\in \left\{K_{1,4},T\left(2,2,2\right),T\left(1,3,3\right),T\left(1,2,5\right),I_m,Q\left(2,2\right),Q\left(3,1\right)\right\}$ .

Lemma 2.5 [5] [6]. The connected graphs $G$ with the largest matching root

in the interval $\left(2,\sqrt{2+\sqrt{5}}\right)$ iff it is precisely the graphs of the following types:

a) $T\left(1,2,c\right)\left(c\ge 6\right)$ , $T\left(1,b,c\right)\left(c>b>2\right)$ , $T\left(2,2,c\right)\left(c>2\right)$ , $T\left(2,3,3\right)$ .

b) $Q\left(2,n\right)\left(n\ge 3\right)$ , $Q\left(m,1\right)\left(m\ge 4\right)$ , $Q\left(3,2\right)$ .

c) $H\left(a,b,c\right)$ , for $\left(a,b,c,\right)\in \left\{\left(2,1,3\right),\left(3,4,3\right),\left(3,5,4\right),\left(4,7,4\right),\left(4,8,5\right)\right\}$ or $a>1$

$b\ge b^{*}\left(a,c\right),c>1$ where $\left(a,c\right)\ne \left(2,2\right)$ and

$b^{*}\left(a,c\right)=\{\begin{array}{l}a+c,a>3,\\ 2+c,a=3,\\ -1+c,a=2,\end{array}$ (2)

Lemma 2.6 [5]. Let $G$ be a tree and let $G_{u,v}$ be obtained from $G$ by subdividing the edge $uv$ of $G$ , then

a) ${\gamma }_1\left(G_{u,v}\right)>{\gamma }_1\left(G\right)$ if $uv$ not lies on an internal path of $G$ .

b) ${\gamma }_1\left(G_{u,v}\right)<{\gamma }_1\left(G\right)$ if $uv$ lies on an internal path of $G$ , and if $G$ is not isomorphic to $H\left(2,m,2\right)$ .

Lemma 2.7 [7] [8]. ${\gamma }_1\left(T\left(1,2,n\right)\right)<{\gamma }_1\left(T\left(1,3,5\right)\right)$ , ${\gamma }_1\left(T\left(1,3,n\right)\right)<{\gamma }_1\left(T\left(1,4,6\right)\right)$ .

Lemma 2.8. ${\gamma }_1\left(T\left(1,m,n\right)\right)<{\gamma }_1\left(H\left(a,b,c\right)\right)\left(a\ge 2,c\ge m+1\right)$ .

Proof. If $b\ge n-1$ , clearly $T\left(1,m,n\right)$ is a proper subgraph of $H\left(2,b,m+1\right)$ , By Lemma 2.2, ${\gamma }_1\left(T\left(1,m,n\right)\right)<{\gamma }_1\left(H\left(2,b,m+1\right)\right)$ . If $b<n-1$ , $T\left(1,m,n\right)$ is a proper subgraph of $H\left(2,n-1,m+1\right)$ , then ${\gamma }_1\left(T\left(1,m,n\right)\right)<{\gamma }_1\left(H\left(2,n-1,m+1\right)\right)$ .

By Lemma 2.6, ${\gamma }_1\left(H\left(2,n-1,m+1\right)\right)<{\gamma }_1\left(H\left(2,b,m+1\right)\right)$ . So

${\gamma }_1\left(T\left(1,m,n\right)\right)<{\gamma }_1\left(H\left(2,b,m+1\right)\right)$ and $H\left(2,b,m+1\right)$ is a proper subgraph of $H\left(a,b,c\right)$ $\left(a\ge 2,c\ge m+1\right)$ , by Lemma 2.2, thus the lemma holds.

Lemma 2.9. If ${\gamma }_1\left(T\left(1,3,n\right)\right)={\gamma }_1\left(H\left(2,m,3\right)\right)={\gamma }_1\left(H\left(3,b,3\right)\right)$ , then $b=2m+2$ and $n$ may only be 5, 6, 7, 11.

Proof. By Lemma 2.1, $x\mu \left(H\left(3,2m+2,3\right),x\right)=\mu \left(H\left(2,m,3\right),x\right)\cdot \mu \left(T\left(1,2,m\right),x\right)$ .

So, we have ${\gamma }_1\left(H\left(2,m,3\right)\right)={\gamma }_1\left(H\left(3,2m+2,3\right)\right)$ . Direct calculate the largest matching root of $T\left(1,3,n\right)\left(n=4,5,6,7,11\right)$ and $H\left(2,b,3\right)\left(b=2,3,4,5,8\right)$ (using Matlab 8.0), we immediately have the following:

${\gamma }_1\left(T\left(1,3,5\right)\right)={\gamma }_1\left(H\left(2,8,3\right)\right)={\gamma }_1\left(H\left(3,18,3\right)\right)$ (3)

${\gamma }_1\left(T\left(1,3,6\right)\right)={\gamma }_1\left(H\left(2,5,3\right)\right)={\gamma }_1\left(H\left(3,12,3\right)\right)$ (4)

${\gamma }_1\left(T\left(1,3,7\right)\right)={\gamma }_1\left(H\left(2,4,3\right)\right)={\gamma }_1\left(H\left(3,10,3\right)\right)$ (5)

${\gamma }_1\left(T\left(1,3,11\right)\right)={\gamma }_1\left(H\left(2,3,3\right)\right)={\gamma }_1\left(H\left(3,8,3\right)\right)$ (6)

By Lemma 2.8, If $n=4$ , ${\gamma }_1\left(T\left(1,3,4\right)\right)={\gamma }_1\left(T\left(1,2,9\right)\right)<{\gamma }_1\left(H\left(2,b,3\right)\right)$ . If $n\ge 12$ , ${\gamma }_1\left(H\left(2,3,3\right)\right)={\gamma }_1\left(T\left(1,3,11\right)\right)<{\gamma }_1\left(T\left(1,3,n\right)\right)<{\gamma }_1\left(T\left(1,4,6\right)\right)<{\gamma }_1\left(H\left(2,2,3\right)\right)=2.0421$ This completes the proof.

3. Main Results

Theorem 3.1. Let $G=P_m\cup T\left(1,3,n\right)$ . Then $G$ is uniquely determined by its matching polynomial iff $m$ is even or 3 and $n\ne 3,6,11$ .

Proof. The necessary condition follows immediately from Lemma 2.1.

We have

$\begin{array}{c}\mu \left(P_{2k+1}\cup T\left(1,3,n\right),x\right)\left(k\ge 2\right)=\mu \left(P_k,x\right)\mu \left(C_{k+1},x\right)\mu \left(T\left(1,3,n\right),x\right)\\ =\mu \left(P_k\cup C_{k+1}\cup T\left(1,3,n\right),x\right)\end{array}$ (7)

$\begin{array}{c}\mu \left(P_m\cup T\left(1,3,3\right),x\right)=\mu \left(P_m,x\right)\mu \left(P_3,x\right)\mu \left(Q\left(3,1\right),x\right)\\ =\mu \left(P_m\cup P_3\cup Q\left(3,1\right),x\right)\end{array}$ (8)

$\begin{array}{c}\mu \left(P_m\cup T\left(1,3,6\right),x\right)=\mu \left(P_m,x\right)\mu \left(P_5,x\right)\mu \left(Q\left(2,3\right),x\right)\\ =\mu \left(P_m\cup P_5\cup Q\left(2,3\right),x\right)\end{array}$ (9)

$\begin{array}{c}\mu \left(P_m\cup T\left(1,3,11\right),x\right)=\mu \left(P_m,x\right)\mu \left(C_5,x\right)\mu \left(T\left(1,4,5\right),x\right)\\ =\mu \left(P_m\cup C_5\cup T\left(1,4,5\right),x\right)\end{array}$ (10)

Now suppose that $m$ is even or 3 and$n\ne 3,6,11$ , $H$ is a graph being matching equivalency with $G$ , hance ${\gamma }_1\left(H\right)={\gamma }_1\left(G\right)={\gamma }_1\left(T\left(1,3,n\right)\right)$ . We proceed to prove that $H$ must be isomorphic to $G$ . By Lemma 2.5, 2.7,

${\gamma }_1\left(H\right)\in \left(2,{\gamma }_1\left(T\left(1,4,6\right)\right)\right)\subset \left(2,\sqrt{2+\sqrt{5}}\right)$ . Set

${\varpi }_1=\left\{T\left(1,2,c\right)\left(c\ge 6\right),T\left(2,2,c\right),T\left(1,b,c\right)\left(b\ge 3\right),T\left(2,3,3\right)\right\}$ ,

${\varpi }_2=\left\{H\left(2,4,3\right),H\left(2,8,3\right),H\left(3,10,3\right),H\left(3,18,3\right)\right\}$ ,

${\varpi }_3=\left\{T\left(1,1,c\right),T\left(1,2,2\right),T\left(1,2,3\right),T\left(1,2,4\right)\right\}$ , then by Lemma 2.8, 2.9, we get

$H=t_1\ast {\varpi }_1\cup t_2\ast {\varpi }_2\cup t_3\ast {\varpi }_3\cup t_4\cdot K_1\cup t_5\cdot Q\left(2,1\right)\cup \left({\displaystyle \underset{i=0}{\overset{s}{\cup }}{P}_{n_i}}\right)\cup \left({\displaystyle \underset{i=0}{\overset{l}{\cup }}{C}_{p_i}}\right)$ (where $t_i\ast {\varpi }_i$ $\left(i=1,2,3\right)$ denotes $t_i$ re-elements form ${\varpi }_i$ , $n_i\ge 2$ ). By Lemma 2.3, $t_1+t_2=1$ . We distinguish the following cases:

Case 1. If $t_1=1$ . We further consider several cases:

Subcase 1. $H=T\left(1,2,c\right)\left(c\ge 6\right)\cup t_3\ast {\varpi }_3\cup t_4\cdot K_1\cup t_5\cdot Q\left(2,1\right)\cup \left({\displaystyle \underset{i=0}{\overset{s}{\cup }}{P}_{n_i}}\right)\cup \left({\displaystyle \underset{i=0}{\overset{l}{\cup }}{C}_{p_i}}\right)$

Then ${\gamma }_1\left(G\right)={\gamma }_1\left(T\left(1,3,n\right)\right)={\gamma }_1\left(H\right)={\gamma }_1\left(T\left(1,2,c\right)\right)\left(c\ge 6\right)$ . By Lemma 2.7, $n=4$ .

Direct computation shows $\mu \left(T\left(1,2,9\right),x\right)=\mu \left(T\left(1,3,4\right)\cup C_4,x\right)$ , hence we have $P_m$ matching equivalency with $C_4\cup t_3\ast {\varpi }_3\cup t_4\cdot K_1\cup t_5\cdot Q\left(2,1\right)\cup \left({\displaystyle \underset{i=0}{\overset{s}{\cup }}{P}_{n_i}}\right)\cup \left({\displaystyle \underset{i=0}{\overset{l}{\cup }}{C}_{p_i}}\right)$ .

Which is a contradiction.

Subcase 2. $H=T\left(2,2,c\right)\left(c\ge 3\right)\cup t_3\ast {\varpi }_3\cup t_4\cdot K_1\cup t_5\cdot Q\left(2,1\right)\cup \left({\displaystyle \underset{i=0}{\overset{s}{\cup }}{P}_{n_i}}\right)\cup \left({\displaystyle \underset{i=0}{\overset{l}{\cup }}{C}_{p_i}}\right)$

Then ${\gamma }_1\left(G\right)={\gamma }_1\left(T\left(1,3,n\right)\right)={\gamma }_1\left(H\right)={\gamma }_1\left(T\left(2,2,c\right)\right)\left(c\ge 3\right)$ . By Lemma 2.1, we get $\mu \left(T\left(2,2,c\right),x\right)=\mu \left(Q\left(2,c\right)\cup P_3,x\right)=\mu \left(\left(c+1,1\right),x\right)$ , which is a contradiction.

Subcase 3. $H=T\left(2,3,3\right)\cup t_3\ast {\varpi }_3\cup t_4\cdot K_1\cup t_5\cdot Q\left(2,1\right)\cup \left({\displaystyle \underset{i=0}{\overset{s}{\cup }}{P}_{n_i}}\right)\cup \left({\displaystyle \underset{i=0}{\overset{l}{\cup }}{C}_{p_i}}\right)$ . The same argument as subcase 2 can be used to get a contradiction.

Subcase 4. $H=T\left(1,b,c\right)\left(b\ge 3\right)\cup t_3\ast {\varpi }_3\cup t_4\cdot K_1\cup t_5\cdot Q\left(2,1\right)\cup \left({\displaystyle \underset{i=0}{\overset{s}{\cup }}{P}_{n_i}}\right)\cup \left({\displaystyle \underset{i=0}{\overset{l}{\cup }}{C}_{p_i}}\right)$ .

Then ${\gamma }_1\left(G\right)={\gamma }_1\left(T\left(1,3,n\right)\right)={\gamma }_1\left(H\right)={\gamma }_1\left(T\left(1,b,c\right)\right)\left(b\ge 3\right)$ . By Lemma 2.7, and $n\ne 11$ , we have $b=3,c=n,t_3=t_4=t_5=p_i=0,s=0,n_0=m$ , thus $H$ be isomorphic to $G$ .

Case 2. If $t_2=1$ . By lemma 2.9, we get $n=5$ or 7. First suppose that $n=5$ . Note that $\mu \left(K_1\cup H\left(3,`18,3\right),x\right)=\mu \left(T\left(1,3,5\right)\cup Q\left(2,1\right)\cup T\left(1,2,8\right),x\right)$ and $\mu \left(H\left(2,8,3\right),x\right)=\mu \left(T\left(1,3,5\right)\cup Q\left(2,1\right),x\right)$ . Thus we have $\mu \left(K_1\cup P_m,x\right)=$ $\mu \left(T\left(1,2,8\right)\cup t_3\ast {\varpi }_3\cup t_4\cdot K_1\cup t_5\cdot Q\left(2,1\right)\cup \left({\displaystyle \underset{i=0}{\overset{s}{\cup }}{P}_{n_i}}\right)\cup \left({\displaystyle \underset{i=0}{\overset{l}{\cup }}{C}_{p_i}}\right),x\right)\left(t_5\ge 1\right)$ or $\mu \left(P_m,x\right)=\mu \left(t_3\ast {\varpi }_3\cup t_4\cdot K_1\cup t_5\cdot Q\left(2,1\right)\cup \left({\displaystyle \underset{i=0}{\overset{s}{\cup }}{P}_{n_i}}\right)\cup \left({\displaystyle \underset{i=0}{\overset{l}{\cup }}{C}_{p_i}}\right),x\right)\left(t_5\ge 1\right)$ . Which contradicts to Lemma 2.9. Secondly assume $n=7$ . By Lemma 2.1, direct Direct computation shows $\mu \left(P_3\cup H\left(3,`10,3\right),x\right)=\mu \left(T\left(1,3,7\right)\cup T\left(1,2,4\right),x\right)$ and $\mu \left(P_3\cup H\left(2,4,3\right),x\right)=\mu \left(K_1\cup T\left(1,3,7\right),x\right)$ , hence we get

$\mu \left(P_3\cup P_m,x\right)=\mu \left(T\left(1,2,4\right)\cup t_3\ast {\varpi }_3\cup t_4\cdot K_1\cup t_5\cdot Q\left(2,1\right)\cup \left({\displaystyle \underset{i=0}{\overset{s}{\cup }}{P}_{n_i}}\right)\cup \left({\displaystyle \underset{i=0}{\overset{l}{\cup }}{C}_{p_i}}\right),x\right)$

or

$\mu \left(P_3\cup P_m,x\right)=\mu \left(t_3\ast {\varpi }_3\cup t_4\cdot K_1\cup t_5\cdot Q\left(2,1\right)\cup \left({\displaystyle \underset{i=0}{\overset{s}{\cup }}{P}_{n_i}}\right)\cup \left({\displaystyle \underset{i=0}{\overset{l}{\cup }}{C}_{p_i}}\right),x\right)\left(t_4\ge 1\right)$ .

which is a contradiction.

Combing cases1, 2, $H$ is isomorphic to $G$ . The proof is complete.

For a graph, its matching polynomial determine the matching polynomial of its complement (see [9]), so the complement of $G=P_m\cup T\left(1,3,n\right)$ is determined by its matching polynomial iff $m$ is even or 3 and $n\ne 3,6,11$ .

Conflicts of Interest

The author declares no conflicts of interest regarding the publication of this paper.

References

[1]	Heilmann, O.J. and Lieb, E.H. (1972) Theory of Monomer-Dimer Systems. Communications in Mathematical Physics, 25, 190-232. https://doi.org/10.1007/bf01877590
[2]	Gutman, I. and Wagner, S. (2012) The Matching Energy of a Graph. Discrete Applied Mathematics, 160, 2177-2187. https://doi.org/10.1016/j.dam.2012.06.001
[3]	Hosoya, H. (1971) Topological Index. a Newly Proposed Quantity Characterizing the Topological Nature of Structural Isomers of Saturated Hydrocarbons. Bulletin of the Chemical Society of Japan, 44, 2332-2339. https://doi.org/10.1246/bcsj.44.2332
[4]	Godsil, C.D. (1993) Algebraic Combinatorics. Chapman and Hall.
[5]	Ghareghani, N., Omidi, G.R. and Tayfeh-Rezaie, B. (2007) Spectral Characterization of Graphs with Index at Most . Linear Algebra and Its Applications, 420, 483-489. https://doi.org/10.1016/j.laa.2006.08.009
[6]	Cvetkovic, D.M., Doob, M. and Sachs, H. (1980) Spectra of Graphs. Academic Press.
[7]	Shen, S. (2016) A Note on Matching Uniqueness of and Its Complement. Journal of Qinghai Normal University, No. 2, 4-6.
[8]	Shen, S. (2020) The Matching Uniqueness T-Shape Tree with Nearly Equal Length. Pure and Applied Mathematics, 2, 297-301.
[9]	Beezer, R.A. and Farrell, E.J. (1995) The Matching Polynomial of a Regular Graph. Discrete Mathematics, 137, 7-18. https://doi.org/10.1016/0012-365x(93)e0125-n