# The Ordering of the Unicyclic Graphs with respect to Largest Matching Root with Given Matching Number

Authors: Luozhong Gong; Weijun Liu
Journal: Journal of Mathematics
 (2022)

---

## Abstract

The matching roots of a simple connected graphG are the roots of the matching polynomial which is defined as MGx=∑k=0n/2−1kmG,kxn−2k, where mG,k is the number of the k matchings of G. Let λ1G denote the largest matching root of the graph G. In this paper, among the unicyclic graphs of order n, we present the ordering of the unicyclic graphs with matching number 2 according to the λ1G values for n≥11 and also determine the graphs with the first and second largest λ1G values with matching number 3.


---

## Body

## 1. Introduction

In this paper, all of the graphs considered are connected and finite. LetG=VG,EG be a graph of order n, where VG and EG denote the vertex set and edge set of G, respectively. Let Nu and dGu be the neighbor set and the degree of the vertex u∈VG in G, respectively. A k-edge matching of G is a set of k mutually independent edges, and the number of all the k-edge matchings of G is denoted by mG,k. Obviously, mG,k=0 if k>n/2. For convenience, we set mG,0=1.The original definition of the matching polynomial was introduced in [9] as ∑kmG,kxk, which is now defined in [14] as(1)MGx=∑k=0n/2−1kmG,kxn−2k.Each root of the matching polynomialMGx is called a matching root of G. The largest matching root of a graph G which is denoted by λ1G is the largest root of MGx. In particular, λ1G has been proved to be positive real numbers excepting for the edgeless graphs in [3, 4].The matching polynomial of a graph has been used in various branches of physics and chemistry. In analogy with the traditional graph energy, the matching energy of a graph has been conceived as the sum of the absolute values of the roots of the matching polynomial. This graph invariant has recently attracted much attention (see [2, 3, 5–11]). In [15], Gutman and Zhang have ordered the graphs by matching numbers. Zhang et al. [18] investigated the largest matching root λ1G for unicyclic graphs and characterized the extremal graph. Zhang and Chen [10] studied the largest matching roots of unicyclic graphs and trees with a given number of fixed matching numbers and characterized the extremal graph with respect to the largest matching roots. In [3], Liu et al. determined the graphs with the four largest and two smallest λ1G values.Motivated by the previous research, in this paper, we focus on the ordering of the unicyclic graph with the fixed matching number with respect to the largest matching rootλ1G. Among the unicyclic graphs of order n, we order the unicyclic graphs with matching number 2 according to the λ1G values for n≥11 and also determine the graphs with the first and second largest λ1G values with matching number 3.


## 2. Preliminaries

LetH be a subgraph of G. If VH=VG, then H is said to be a spanning subgraph of G. The following lemma about the largest matching root is well known.Lemma 1.
(see [8]). Let H be a spanning subgraph of G and λ1G the largest matching root of G. If κ≥λ1G, then MHκ≥MGκ; if H is a proper subgraph of G and κ>λ1G, then MHκ>MGκ.Definition 1.
Letu,v denote two vertices of G. The Kelmans transformation of G is defined as follows (cf. Figure 1): delete all edges which are with one end v and another end in Nv/Nu∪u and add all edges between u and Nv\Nu∪u.Figure 1
The Kelmans transformation.LetG′ denote the graph obtained from G by a series of Kelmans transformation without referring to the vertices u,v. Obviously, G′ and G have the same size.The relationship between the largest matching roots ofG′ and G is given as follows.Lemma 2.
(see [7]). Let G′ be the graph obtained from G by some Kelmans transformation. Then, λ1G′≥λ1G.In [3], Liu et al. characterized the unicyclic graphs with a triangle as given in Figure 2 and obtained the following lemma.Figure 2
Two graphsDk and Dk−1.Lemma 3.
(see [3]). The graphs of order nDk and Dk−1 are shown in Figure 2. If 2≤k≤n/2−1, then λ1Dk≤λ1Dk−1, with equality holding if and only if k=n/2−1.LetSn be the star graph of order n and Sn+ the unicyclic graph obtained by adding a new edge to Sn. Let Cn−1 be a cycle of length n−1 and Cn2 the graph obtained from Cn−1 by adding a new pendent edge. Let Dn2 be the graph obtained by identifying one end vertex of the path Pn−2 and one vertex of the triangle C3.Lemma 4.
(see [3]). Among all connected unicyclic graphs with nn≥8 vertices, the first four largest matching roots are λ1Sn+>λ1Sn2>λ1Sn3>λ1Sn4, and the last three largest matching roots are λ1Cn2 or λ1Dn2 and λ1Cn, where Sn2, Sn3, and Sn4 are shown in Figure 3.Figure 3
GraphsSn2, Sn3, and Sn4.Lemma 5.
(see [11]). Let G be a graph of order n. Then, λ12G≥4EG/n−1, where EG is the number of edges of G.Corollary 1.
LetG be a connected unicyclic graph with n vertices. Then, λ1G≥3.


## 3. Main Results

In this section, we first investigate the largest matching root of unicyclic graphs with matching number 2.Fork≥2, let Sk be a star graph with center u. Let v1,v2 be two vertices of Sn−k+1+ which are of degree 1 and 2, respectively. We write Dn,kCn,k denote the graph obtained by identifying u with v1v2. In fact, Cn,k is the graph Dk−1 in Figure 2. All the connected unicyclic graphs with matching number 2 are Sn+, Cn,k, Dn,n−3,Sn4, and Tnk as shown in Figure 4.Figure 4
GraphsSn+, Cn,k,Sn4, Dn,n−3, and Tnk.Theorem 1.
λ1Cn,k+1>λ1Tnk>λ1Cn,k+2>λ1Tnk+1, k<n−4/3.Proof.
We can easily getmTnk,2=n+kn−k2−2k−3,mTnk+1,2=2n+kn−k2−4k−6 and mCn,k+1,2=n+kn−k2−3k−3, mCn,k+2,2=2n+kn−k2−5k−7, then the matching polynomial of graphs Tnk and Tnk+1 is(2)MTnk+1x=xn−nxn−2+2n+kn−k2−4k−6xn−4,MTnkx=xn−nxn−2+n+kn−k2−2k−3xn−4,MCn,k+1x=xn−nxn−2+n+kn−k2−3k−3xn−4,MCn,k+2x=xn−nxn−2+2n+kn−k2−5k−7xn−4.
Therefore,(3)MTnk+1x−MTnkx=n−2k−3xn−4,MCn,k+1x−MTnkx=−kxn−4,MCn,k+2x−MTnkx=n−3k−4xn−4.
ThenMTnk+1λ1Tnk>0, MCn,k+1λ1Tnk<0, and MCn,k+2λ1Tnk>0, so λ1Cn,k+1>λ1Tnk>λ1Cn,k+2>λ1Tnk+1, since the MGx is strictly monotonically increasing for x>0.Theorem 2.
Among all connected unicyclic graphs of ordernn≥11 with matching number 2, λ1Sn+>λ1Cn,2>λ1Sn4>λ1Cn,3>λ1Dn,n−3=λ1Tn2>λ1Cn,4>⋯>λ1Cn,k+1>λ1Tnk>λ1Cn,k+2>λ1Tnk+1, with k<n−4/3.Proof.
It is obvious thatmG,1=n for any connected unicyclic graph G of order n. By simple calculations, we have(4)mCn,2,2=2n−7,mSn4,2=2n−6,mCn,3,2=3n−13,mDn,n−3,2=3n−11,mCn,4,2=4n−21,mTn2,2=3n−11.
Then,(5)MCn,2x=xn−nxn−2+2n−7xn−4,MSn4x=xn−nxn−2+2n−6xn−4,MCn,3x=xn−nxn−2+3n−13xn−4,MDn,n−3x=MTn2x=xn−nxn−2+3n−11xn−4,MCn,4x=xn−nxn−2+4n−21xn−4.
SinceMSn4x−MCn,2x=xn−4, then MSn4λ1Cn,2>0. Since the matching polynomial MGx is strictly monotonically increasing for x>0, λ1Cn,2>λ1Sn4. Similarly, since MCn,3x−MSn4x=n−7xn−4, then MCn,3λ1Sn4>0 by putting x=λ1Sn4, and so λ1Sn4>λ1Cn,3. Similarly, we have(6)MCn,3x−MDn,n−3x=−2xn−4,MDn,n−3x−MCn,4x=−n+10xn−4,MDn,n−3x−MTn2x=0.
Puttingx=λ1Cn,3 and x=λ1Dn,n−3 to the above two equations, respectively, we have(7)λ1Cn,3>λ1Dn,n−3=λ1Tn2>λ1Cn,4.
SinceSn+ can be obtained from Cn,k by Kelmans transformations, then λ1Sn+>λ1Cn,k by Lemma 3. By Lemma 3, we have λ1Cn,k−1>λ1Cn,k. Combining the discussions above and Theorem 1, the proof is completed.We now investigate the largest matching root of graphs with matching number 3.Theorem 3.
Let the graphsDn,k+1 and Dn,k be defined above. Then, λ1Dn,k+1<λ1Dn,k if 2≤k≤n−1/2 and λ1Dn,k+1>λ1Dn,k if k>n−1/2.Proof.
By simple calculations, it is obtained that(8)mDn,k+1,1=n,mDn,k+1,2=kn−k2−2k+n−3,mDn,k+1,3=kn−k2−4k,mDn,k,1=n,mDn,k,2=kn−k2−2,mDn,k,3=kn−k2−2k−n+3.
Then,(9)MDn,k+1x=xn−nxn−2+kn−k2−2k+n−3xn−4−kn−k2−4kxn−6,MDn,kx=xn−nxn−2+kn−k2−2xn−4−kn−k2−2k−n+3xn−6.
Ifk≠n−1/2, then(10)MDn,k+1x−MDn,kx=n−2k−1xn−6x2−n−2k−3n−2k−1.
Puttingx=λ1Dn,k+1. Since Dn,k+1 is a connected unicyclic graph, then λ12Dn,k+1≥3 by Lemma 5. Thus, if 2≤k<n−1/2, then MDn,kλ1Dn,k+1<0 and so λ1Dn,k+1<λ1Dn,k. If k>n−1/2, then MDn,kλ1Dn,k+1>0 and so λ1Dn,k+1>λ1Dn,k.
Ifk=n−1/2, then MDn,k+1x−MDn,kx=2xn−6 and so λ1Dn,k+1<λ1Dn,k.Theorem 4.
LetLk and Lk−1 be the graphs as shown in Figure 5. If 2≤k≤n−3/2, then λ1Lk≤λ1Lk−1, with equality holding if and only if k=n−3/2.Figure 5
Graph transformation in Theorem4.Proof.
By simple calculations, it is obtained that(11)mLk,1=n,mLk,2=kn−k2−4k+2n−6,mLk,3=kn−k2−4k,mLk−1,1=n,mLk−1,2=kn−k2−2k+n−3,mLk−1,3=kn−k2−2k−n+3.
Then,(12)MLkx=xn−nxn−2+kn−k2−4k+2n−6xn−4−kn−k2−4kxn−6,MLk−1x=xn−nxn−2+kn−k2−2k+n−3xn−4−kn−k2−2k−n+3xn−6.
It follows that(13)MLkx−MLk−1x=n−2k−3xn−6x2−1.
By Lemma5, λ12Lk≥3. Therefore, putting x=λ1Lk, if k≤n−3/2, then MLk−1λ1Lk≤0 and so λ1Lk≤λ1Lk−1, with equality holding if and only if k=n−3/2.Theorem 5.
The graphsGa,b,c and Ga,b−1,c+1 with n vertices are shown in Figure 6, where a+b+c=n−3. If a≥n/3−1 and b≥c, then λ1Ga,b,c<λ1Ga,b+1,c−1. If a=1 and b≥c, then λ1Ga,b,c<λ1Ga,b+1,c−1.Figure 6
Graph in Theorem5.Proof.
LetG1,G2 denote the graphs Ga,b,c and Ga,b+1,c−1, respectively. Without loss of generality, assume that a≥n/3−1 and b≥c. It is easy to get that(14)mG1,1=n,mG1,2=ab+ac+bc+a+b+c,mG1,3=abc,mG2,1=n,mG2,2=ab+ac+bc+a+2c−1,mG2,3=abc+ac−ab−a.
Then,(15)MG1x=xn−nxn−2+ab+ac+bc+a+b+cxn−4−abcxn−6,MG2x=xn−nxn−2+ab+ac+bc+a+2c−1xn−4−abc+ac−ab−axn−6.
Puttingx=a+1 to MG1x, then(16)MG1a+1=a+1n/2−3a+13−na+12+ab+ac+bc+a+b+ca+1−abc.
Sincea+b+c=n−3, then(17)MG1a+1=a+1n/2−3−a2−3a−2+bc.
Sincea≥n/3−1 and a+b+c=n−3, then(18)bc≤b+c22≤n−332<a2+3a+2.
Therefore,MG1a+1<0, and so λ1G1>a+1. Moreover, MG1x−MG2x=b−c+1xn−6x2−a. Since b≥c, then MG1x−MG2x<0 for any x>a+1. Thus, if a≥n/2−1 and b≥c, then(19)MG1λ1G1−MG2λ1G1>0,that is, MG2λ1G1<0. Therefore, λ1G1<λ1G2.
We now discuss the case fora=1. Without loss of generality, assume that b≥c. Obviously, we have(20)MG1x=xn−nxn−2+2b+2c+bc+1xn−4−bcxn−6,MG2x=xn−nxn−2+b+3c+bcxn−4−bc+c−b−1xn−6.
Then,(21)MG1x−MG2x=b−c+1xn−6x2−1.
By Corollary1, λ12G1≥3. Thus, if b≥c, then MG2λ1G1<0. Hence, λ1G1<λ1G2.Theorem 6.
The graphsHii=1,2,…,5 with n>8 vertices are shown in Figure 7. Then, λ1H1>λ1H2>λ1H3=λ1H4>λ1H5.Figure 7
Five graphs in Theorem6.Proof.
Obviously,mHi,1=n (for i=1,2,3,4,5) and(22)mH1,2=3n−12,mH1,3=n−5,mH2,2=3n−11,mH2,3=2n−12,mH3,2=3n−10,mH3,3=n−5,mH4,2=3n−10,mH4,3=n−5,mH5,2=4n−18,mH5,3=n−5.
Then,(23)MH1x=xn−nxn−2+3n−12xn−4−n−5xn−6,MH2x=xn−nxn−2+3n−11xn−4−2n−12xn−6,MH3x=xn−nxn−2+3n−10xn−4−n−5xn−6,MH4x=xn−nxn−2+3n−10xn−4−n−5xn−6,MH5x=xn−nxn−2+4n−18xn−4−n−5xn−6.
Puttingx=n−6 to matching polynomial of H2, we have(24)MH2n−6=n−6n/2−3n−63−nn−62+3n−11n−6−2n−6,=n−6n/2−3−3n2+41n−138.
Sincen>8, then MH2n−6<0 and so λ1H2>n−6. Since MH2x−MH1x=xn−6x2−n−7, then MH2x−MH1x>0 for any x>n−6. Therefore, MH1λ1H2<0, and thus, λ1H1>λ1H2.
SinceMH3x−MH2x=xn−6x2+n−7, then MH3λ1H3−MH2λ1H3>0, and thus, λ1H2>λ1H3. It is obvious that λ1H3=λ1H4. Since MH4x−MH5x=−n+8xn−4 and n>8, then MH4λ1H4−MH5λ1H4<0 and so λ1H4>λ1H5. Therefore, λ1H1>λ1H2>λ1H3=λ1H4>λ1H5.Theorem 7.
Among all unicyclic graphs of ordern>8 with matching number 3, the graphs with the first second largest matching root are Dn,2 and H1.Proof.
SinceDn,2≅Sn3, then the graph with the largest matching root among all unicyclic graphs with matching number 3 is Dn,2 by Lemma 4.
LetG be the unicyclic graph of order n≥8 with the second largest matching root among all graphs with matching number 3. Since G is a unicyclic graph of order n with matching number 3, then the girth g of G is possibly 3,4, or 5.


### 3.1. Case 1:g=3

Under the Kelmans transformation,G is Dn,k or Ga,b,c in Figure 6. By Theorem 3, λ1Dn,k+1<λ1Dn,k if 2≤k<n−1/2 and λ1Dn,k+1>λ1Dn,k if k>n−1/2. Therefore, among all the graphs of type Dn,k, G is Dn,3 or Dn,n−4. Since Dn,3≅H2 and Dn,n−4≅H5, then λ1Dn,3>λ1Dn,n−4 by Theorem 6.By Theorem5, G1,n−5,1 is the graph with the first largest matching root among the graphs of type Ga,b,c. Moreover, G1,n−5,1≅H1. Thus, by Theorem 6, the graph with the second largest matching root and girth 3 is H1. □


### 3.2. Case 2:g=4

In this case,G possibly is the graph Tii=1,2,3,4,5 in Figure 8. Obviously, T1 can be obtained by a series of Kelmans transformations from the graph Tii=2,3,4,5. Moreover, T1 is the graph Lk in Theorem 4. By Theorem 4, the graph with the largest matching roots among graphs of type Lk is L1 which is isomorphic to H3. Therefore, the graph with the largest matching root among the graphs with matching number 3 and girth 4 is H3.Figure 8
Five graphs in Case 2.


### 3.3. Case 3:g=5

In this case, the unicyclic graphs with matching number 3 isomorphism to the following four families graphs denoted byCn−5,0,0,0,0,Cn−5−k,k,0,0,0,Cn−5−k,0,k,0,0, and Cn−5−k1−k2,0,k1,0,k2, where Cm1,m2,m3,m4,m5 denote the unicyclic graphs with girth 5, such that there are mi pendent edges attached to the vertex vi of the cycle. Obviously, Cn−5,0,0,0,0 is isomorphic to H4 in Theorem 5, and the rest three families can arrive at graphs of Case 1 or 2 by a series of Kelmans transformations. Thus, G is H4 in this case.Therefore, by Theorem6, the graph with the second largest matching root is H1.


## 3.1. Case 1:g=3

Under the Kelmans transformation,G is Dn,k or Ga,b,c in Figure 6. By Theorem 3, λ1Dn,k+1<λ1Dn,k if 2≤k<n−1/2 and λ1Dn,k+1>λ1Dn,k if k>n−1/2. Therefore, among all the graphs of type Dn,k, G is Dn,3 or Dn,n−4. Since Dn,3≅H2 and Dn,n−4≅H5, then λ1Dn,3>λ1Dn,n−4 by Theorem 6.By Theorem5, G1,n−5,1 is the graph with the first largest matching root among the graphs of type Ga,b,c. Moreover, G1,n−5,1≅H1. Thus, by Theorem 6, the graph with the second largest matching root and girth 3 is H1. □


## 3.2. Case 2:g=4

In this case,G possibly is the graph Tii=1,2,3,4,5 in Figure 8. Obviously, T1 can be obtained by a series of Kelmans transformations from the graph Tii=2,3,4,5. Moreover, T1 is the graph Lk in Theorem 4. By Theorem 4, the graph with the largest matching roots among graphs of type Lk is L1 which is isomorphic to H3. Therefore, the graph with the largest matching root among the graphs with matching number 3 and girth 4 is H3.Figure 8
Five graphs in Case 2.


## 3.3. Case 3:g=5

In this case, the unicyclic graphs with matching number 3 isomorphism to the following four families graphs denoted byCn−5,0,0,0,0,Cn−5−k,k,0,0,0,Cn−5−k,0,k,0,0, and Cn−5−k1−k2,0,k1,0,k2, where Cm1,m2,m3,m4,m5 denote the unicyclic graphs with girth 5, such that there are mi pendent edges attached to the vertex vi of the cycle. Obviously, Cn−5,0,0,0,0 is isomorphic to H4 in Theorem 5, and the rest three families can arrive at graphs of Case 1 or 2 by a series of Kelmans transformations. Thus, G is H4 in this case.Therefore, by Theorem6, the graph with the second largest matching root is H1.


## 4. Further Remarks

In the introduction, we already talk about that the matching energies have been getting a lot of attention recently. The graphs with maximum and minimum values of matching roots are the graphs with minimum and maximum matching energy. Therefore, any result for the largest matching roots can reveal the structural dependence of the matching energy or at least provide guidance for its research. Recently, References [2,5,6] showed some new findings on the matching energy of unicyclic graphs. Therefore, the results of this paper have a direct application value [4, 16].



---

*Source: 3589448-2022-05-28.xml*