# Extremal Matching Energy and the Largest Matching Root of Complete Multipartite Graphs

Authors: Xiaolin Chen; Huishu Lian
Journal: Complexity
 (2019)

---

## Abstract

The matching energyME(G) of a graph G was introduced by Gutman and Wagner, which is defined as the sum of the absolute values of the roots of the matching polynomial m(G,x). The largest matching root λ1(G) is the largest root of the matching polynomial m(G,x). Let Kn1,n2,…,nr denote the complete r-partite graph with order n=n1+n2+…+nr, where r>1. In this paper, we prove that, for the given values n and r, both the matching energy ME(G) and the largest matching root λ1(G) of complete r-partite graphs are minimal for complete split graph CS(n,r-1) and are maximal for Turán graph T(n,r).


---

## Body

## 1. Introduction

LetG be a finite simple graph of order n with vertex set V(G) and edge set E(G). A matching of G is a set of independent edges in G, and a k-matching of G is a matching of G that has exactly k edges. By mk(G) we denote the number of k-matchings in G. It is easy to verify that, for k<0 and k>⌈n/2⌉, mk(G)=0. And when k=1, m1(G) is the size of G. For convenience, we define m0(G)=1. The matching polynomial m(G,x) [1–3] of a graph G is defined as (1)mG,x=∑k=0n/2-1kmkGxn-2k.The matching polynomial has been widely studied and has many important applications in statistical physics and chemistry; see [1–4]. The largest root of the matching polynomial m(G,x), denoted by λ1(G), is called the largest matching root of G. The matching root has been much studied in algebraic combinatorics (see the book [5]). In [6], Fisher and Ryan deduced some bounds for λ1(G). Afterwards, many results about the largest matching root have been obtained; see [7–12].In [13], Gutman and Wagner introduced the matching energy (ME) of a graph G, which is defined as the sum of the absolute values of the roots of the matching polynomial of G. Note that the concept of the energy E(G) of a simple undirected graph G was introduced by Gutman in [14]. Afterwards, there have been lots of research papers on this topic. A systematic study of this topic can be found in the book [15]. In [13], Gutman and Wagner pointed out that the matching energy is a quantity of relevance for chemical applications. Moreover, they arrived at the simple relation(2)TREG=EG-MEG,where TRE(G) is the so-called “topological resonance energy” of the graph G. For more information about the applications of the matching energy, we refer the readers to [16, 17]. Recently, there have been some results on the matching energy of graphs; see [18–31]. In spite of this, few results are known for the matching energy of complete multipartite graphs. Note that Stevanović et al. [32] studied the energy of complete multipartite graphs, which inspires us to study the matching energy of complete multipartite graphs.For a fixed valuer>1, let Kn1,n2,…,nr denote the complete r-partite graph with order n=n1+n2+…+nr. There are two important complete r-partite graphs which have many implications in graph theory. One is complete split graph, denoted by CS(n,r-1), which is defined as CS(n,r-1)≅Kn-r+1,1,…,1. The other is Turán graph T(n,r), which is defined as the complete r-partite graph Kn1,n2,…,nr satisfying |ni-nj|≤1 for any two distinct numbers 1≤i,j≤r.In this paper, we show that, among all the completer-partite graphs with given order n, the graph with minimal matching energy is the complete split graph CS(n,r-1) and the graph with maximal matching energy is Turán graph T(n,r). Moreover, we prove that, among all the complete r-partite graphs with given order n, the graph with minimal λ1(G) is the complete split graph CS(n,r-1) and the graph with maximal λ1(G) is Turán graph T(n,r). In fact, we deduce the following theorems.Theorem 1.
For the fixed valuesn and r, ME(Kn1,n2,…,nr)≥ME(CS(n,r-1)) and equality holds if and only if Kn1,n2,…,nr≅CS(n,r-1).Theorem 2.
For the fixed valuesn and r, ME(Kn1,n2,…,nr)≤ME(T(n,r)) and equality holds if and only if Kn1,n2,…,nr≅T(n,r).Theorem 3.
For the fixed valuesn and r, λ1(Kn1,n2,…,nr)≥λ1(CS(n,r-1)) and equality holds if and only if Kn1,n2,…,nr≅CS(n,r-1).Theorem 4.
For the fixed valuesn and r, λ1(Kn1,n2,…,nr)≤λ1(T(n,r)) and equality holds if and only if Kn1,n2,…,nr≅T(n,r).In Section2, we prove Theorems 1 and 2. In Section 3, we give the proofs of Theorems 3 and 4.


## 2. Proofs of Theorems1 and 2

In this section, we first recall an integral formula for computing the value of matching energy which is also given by Gutman and Wagner [13].Definition 5 (see [13]).
LetG be a simple graph. The matching energy of G is(3)MEG=2π∫0∞1x2ln⁡∑k≥0mkGx2kdxBy this definition, we can deduce that ifmk(G)≥mk(H) for every k≥1, then ME(G)≥ME(H). Owing to the above observation, we derive the following lemma which is critical to the proofs of Theorems 1 and 2.Lemma 6.
For a completer-partite graph Kn1,…,ni,…,nj,…,nr with nj-2≥ni, we have m1(Kn1,…,ni,…,nj,…,nr)<m1(Kn1,…,ni+1,…,nj-1,…,nr), and mk(Kn1,…,ni,…,nj,…,nr)≤mk(Kn1,…,ni+1,…,nj-1,…,nr), for 2≤k≤n/2.Proof.
LetG denote the graph Kn1,n2,…,nr. Let V1,V2,…,Vr be the r partition classes with |Vi|=ni for 1≤i≤r and Vi=v1i,v2i,…,vnii. Without loss of generality, we just prove the case n2-2≥n1.
Fork=1, m1(Kn1+1,n2-1,…,nr)-m1(Kn1,n2,…,nr)=(n1+1)(n2-1)-n1n2=n2-n1-1>0. For 2≤k≤n/2, we will prove this lemma by induction on the number n1. For the case n1=1, we first delete the vertex v12 and the edges incident to it from K1,n2,…,nr, and then we get a new graph G′ which is isomorphic to K1,n2-1,…,nr. Next, we add a new vertex u into the graph G′ and add some edges such that we get a graph G′′ which is isomorphic to K2,n2-1,…,nr. In other words, these operations can be thought as the vertex v12 being moved from the second partition class to the first partition class. Thus, for convenience, we denote the new vertex u by v12. Now, we compare the number of k-matchings between G and G′′. Choosing a k-matching M in G, if the edge (v11,v12) lies in the matching M, M is not a k-matching of G′′. Otherwise, the matching M is a k-matching of G′′. For a k-matching M′ in G′′, when there exists an edge between v12 and {v22,…,vn22}, M′ is not in G. Otherwise, M′ is a k-matching of G. It follows that mk(G′′)-mk(G)=(n2-1)mk-1(K1,n2-2,n3,…,nr)-mk-1(Kn2-1,n3,…,nr). Since mk-1(K1,n2-2,n3,…,nr)≥mk-1(Kn2-1,n3,…,nr) and n2-1≥1, we get mk(G)≤mkG′.
Givent≥2, suppose that the lemma is right for n1=t-1, that is, mk(Kt-1,n2,…,nr)≤mk(Kt,n2-1,…,nr) for 2≤k≤n/2. For n1=t, just like the above operations, we move the vertex v12 from V2 into V1, then we get a new graph G′ which is isomorphic to Kt+1,n2-1,…,nr. For a k-matching M in G, when there exists an edge between {v11,…,vt1} and v12 in the matching M, M is not in G′. Otherwise, the matching M is a k-matching of G′. For a k-matching M′ in G′, when there exists an edge between v12 and {v22,…,vn22}, M′ is not in G. Otherwise, M′ is a k-matching of G. Then mkG′-mk(G)=(n2-1)mk-1(Kt,n2-2,…,nr)-tmk-1(Kt-1,n2-1,…,nr). Since n2-1>t, mk-1(Kt-1,n2-1,…,nr)≤mk-1(Kt,n2-2,…,nr), then mkG′-mk(G)≥0. Thus, we complete the proof.From this lemma, we give the proofs of Theorems1 and 2.Proof of Theorem1.
Suppose thatKn1,n2,…,nr is the complete multipartite graph with the smallest matching energy. If there are two parameters ni and nj satisfying nj≥ni>1, then (nj+1)-(ni-1)≥2. From Lemma 6, we get m1(Kn1,…,ni,…,nj,…,nr)>m1(Kn1,…,ni-1,…,nj+1,…,nr), and mk(Kn1,…,ni,…,nj,…,nr)≥mk(Kn1,…,ni-1,…,nj+1,…,nr) for 2≤k≤n/2. It implies that ME(Kn1,…,ni,…,nj,…,nr)>ME(Kn1,…,ni-1,…,nj+1,…,nr). It is a contradiction. Hence, Kn1,n2,…,nr satisfies that all parameters equal 1 except one parameter equal to n-r+1. Thus, Kn1,n2,…,nr≅CS(n,r-1).Proof of Theorem2.
Suppose thatKn1,n2,…,nr is the complete multipartite graph with the largest matching energy. If there are two parameters ni and nj satisfying nj≥ni+2, from Lemma 6, we get m1(Kn1,…,ni,…,nj,…,nr)<m1(Kn1,…,ni+1,…,nj-1,…,nr), and mk(Kn1,…,ni,…,nj,…,nr)≤mk(Kn1,…,ni+1,…,nj-1,…,nr) for 2≤k≤n/2. Owing to Definition 5, we can deduce that ME(Kn1,…,ni,…,nj,…,nr)<ME(Kn1,…,ni+1,…,nj-1,…,nr). It is a contradiction. Hence, for any i≠j, we have |ni-nj|≤1. It means that each parameter ni equals either ⌊n/r⌋ or ⌊n/r⌋+1, i.e., Kn1,n2,…,nr is isomorphic to T(n,r).


## 3. Proofs of Theorems3 and 4

We first review some useful results of the matching polynomial as the following lemmas.Lemma 7 (see [5]).
Letu be a vertex of G. Then(4)mG,x=xmG-u,x-∑u~vmG-u-v,xIn [33], Gutman showed some parallel results for the roots of the matching polynomial and the spectra of the characteristic polynomial.Lemma 8 (see [33]).
IfH is a subgraph of G, then λ1(G)≥λ1(H). If G is connected and H is a proper subgraph of G, then λ1(G)>λ1(H).Next, we recall a definition which is introduced in [34].Definition 9 (see [34]).
DefineG1≻G2 if for all x≥λ1(G1) we have m(G2,x)>m(G1,x).We then list some useful propositions about≻ which are proved in [34].Proposition 10 (see [34]).
The relation≻ is transitive. And if G1≻G2, then λ1(G1)>λ1(G2).Proposition 11 (see [34]).
IfG is connected and H is a proper spanning subgraph of G, then G≻H.Now, we are ready to give the following lemma which is the key to the proofs of Theorems3 and 4.Lemma 12.
For a completer-partite graph Kn1,…,ni,…,nj,…,nr with ni-2≥nj, we have Kn1,…,ni-1,…,nj+1,…,nr≻Kn1,…,ni,…,nj,…,nr.Without loss of the generality, we just need to prove the following lemma.Lemma 13.
For a completer-partite graph Kn1+1,n2,…,nr with n1-1≥n2, we have Kn1,n2+1,…,nr≻Kn1+1,n2,…,nr.Proof.
Using Lemma7, we get the following two equations:(5)mKn1+1,n2,…,nr,x=xmKn1,n2,…,nr,x-n2mKn1,n2-1,…,nr,x-⋯-nrmKn1,n2,…,nr-1,x.mKn1,n2+1,…,nr,x=xmKn1,n2,…,nr,x-n1mKn1-1,n2,…,nr,x-⋯-nrmKn1,n2,…,nr-1,x.By subtraction, we deduce that(6)mKn1+1,n2,…,nr,x-mKn1,n2+1,…,nr,x=n1mKn1-1,n2,…,nr,x-n2mKn1,n2-1,…,nr,x.By Definition 9, it suffices to show that, for every x≥λ1(Kn1,n2+1,…,nr), m(Kn1+1,n2,…,nr,x)-m(Kn1,n2+1,…,nr,x)>0. In the sequence, we will study the structure of the polynomial (6) and deduce an important recurrent formula.
By Lemma7, we first give two different expansions of m(Kn1,n2,…,nr,x).(7)mKn1,n2,…,nr,x=xmKn1-1,n2,…,nr,x-n2mKn1-1,n2-1,…,nr,x-⋯-nrmKn1-1,n2,…,nr-1,x.(8)mKn1,n2,…,nr,x=xmKn1,n2-1,…,nr,x-n1mKn1-1,n2-1,…,nr,x-⋯-nrmKn1,n2-1,…,nr-1,x.Then, combining with (7) and (8), we derive that (9)xn1mKn1-1,n2,…,nr,x-n2mKn1,n2-1,…,nr,x=n1-n2mKn1,n2,…,nr,x+n3n1mKn1-1,n2,n3-1,…,nr,x-n2mKn1,n2-1,n3-1,…,nr,x+⋯+nrn1mKn1-1,n2,…,nr-1,x-n2mKn1,n2-1,…,nr-1,x.Suppose x≠0, we get the following recurrent formula of the right side of (6):(10)n1mKn1-1,n2,…,nr,x-n2mKn1,n2-1,…,nr,x=n1-n2xmKn1,n2,…,nr,x+n3xn1mKn1-1,n2,n3-1,…,nr,x-n2mKn1,n2-1,n3-1,…,nr,x+⋯+nrxn1mKn1-1,n2,…,nr-1,x-n2mKn1,n2-1,…,nr-1,x.
Next, we will repeatedly use the above recurrent formula (10). For convenience, we introduce a new notation Δ(n3,…,nr)=n1m(Kn1-1,n2,…,nr,x)-n2m(Kn1,n2-1,…,nr,x). Then, (10) can be rewritten as(11)Δn3,…,nr=n1-n2xmKn1,n2,…,nr,x+n3xΔn3-1,…,nr+⋯+nrxΔn3,…,nr-1.Let T=n3+…+nr. For any 2≤h≤T, we claim that(12)Δn3,…,nr=n1-n2x∑k=0h-1∑i3+…+ir=ki3∈0,1,…,n3⋯ir∈0,1,…,nrn3i3⋯nrirxkki3,i4,…,irmKn1,n2,n3-i3,…,nr-ir,x+∑i3+…+ir=hi3∈0,1,…,n3⋯ir∈0,1,…,nrn3i3⋯nrirxhhi3,i4,…,irΔn3-i3,…,nr-ir.In the above formula, the symbol (t)s, where s,t are two nonnegative integers, is called the falling factorial which is defined as (t)s=t(t-1)(t-2)⋯(t-s+1), and it means the number of s-permutations of t in combinatorics. The symbol t! is defined as t!=t(t-1)⋯1. Note that (t)0=1, 0!=1, (t)s=0 if s>t. The numbers mi3,i4,…,ir in the above formula are the multinomial coefficients and mi3,i4,…,ir=m!/i3!i4!⋯ir!. In the reminder of paper, for the brevity of deduction, we give the following notes. If s is a negative integer, then (t)s=0. If there exists a number ij<0 for 3≤j≤r, then mi3,i4,…,ir=0.
Now, we prove Equation (12) by induction.
Whenh=1, it is (11). Suppose the above equation is true for 1≤h=l<T. We now consider the case h=l+1.
ForΔ(n3-i3,…,nr-ir), by (11), we can get its expanded formula. (13)Δn3-i3,…,nr-ir=n1-n2xmKn1,n2,n3-i3,…,nr-ir,x+n3-i3xΔn3-i3-1,…,nr-ir+⋯+nr-irxΔn3-i3,…,nr-ir-1.Then we can obtain that (14)∑i3+…+ir=li3∈0,1,…,n3⋯ir∈0,1,…,nrn3i3⋯nrirxlli3,…,irΔn3-i3,…,nr-ir=∑i3+…+ir=li3∈0,1,…,n3⋯ir∈0,1,…,nrn3i3⋯nrirxlli3,…,irn1-n2xmKn1,n2,n3-i3,…,nr-ir,x+n3-i3xΔn3-i3-1,…,nr-ir+⋯+nr-irxΔn3-i3,…,nr-ir-1.By expanding the last formula, we get that (15)∑i3+…+ir=li3∈0,1,…,n3⋯ir∈0,1,…,nrn3i3⋯nrirxlli3,…,irΔn3-i3,…,nr-ir=n1-n2x∑i3+…+ir=li3∈0,1,…,n3⋯ir∈0,1,…,nrn3i3⋯nrirxlli3,…,irmKn1,n2,n3-i3,…,nr-ir,x+∑i3+…+ir=li3∈0,1,…,n3⋯ir∈0,1,…,nrn3i3⋯nrirxlli3,…,irn3-i3xΔn3-i3-1,…,nr-ir+⋯+nr-irxΔn3-i3,…,nr-ir-1.
We observe that the general term in the last summation isΔ(n3-j3,…,nr-jr), in which j3,…,jr are nonnegative integers and j3+…+jr=l+1. We then study the coefficient of Δ(n3-j3,…,nr-jr).
By analyzing the above formula, we find that the coefficient ofΔ(n3-j3,…,nr-jr) consists of r-2 parts. For every 3≤k≤r, the kth part comes from the expansion of Δ(n3-j3,…,nk-jk+1…,nr-jr), and it is(16)n3j3⋯nrjrxl+1lj3,…,jk-1,…,jr.
Thus the coefficient ofΔ(n3-j3,…,nr-jr) is (17)n3j3⋯nrjrxl+1lj3-1,j4,…,jr+lj3,j4-1,…,jr+…+lj3,j4,…,jr-1.
It is well known that(18)lj3-1,j4,…,jr+lj3,j4-1,…,jr+…+lj3,j4,…,jr-1=l+1j3,j4,…,jr.It follows the coefficient of Δ(n3-j3,…,nr-jr) is equal to (19)n3j3⋯nrjrxl+1l+1j3,j4,…,jr.
Owing to the above analysis, we conclude that(20)∑i3+…+ir=li3∈0,1,…,n3⋯ir∈0,1,…,nrn3i3⋯nrirxlli3,…,irΔn3-i3,…,nr-ir=n1-n2x∑i3+…+ir=li3∈0,1,…,n3⋯ir∈0,1,…,nrn3i3⋯nrirxlli3,…,irmKn1,n2,n3-i3,…,nr-ir,x+∑i3+…+ir=l+1i3∈0,1,…,n3⋯ir∈0,1,…,nrn3i3⋯nrirxl+1l+1i3,…,irΔn3-i3,…,nr-ir.Hence, (12) holds for h=l+1. By induction, (12) is true for any 2≤h≤T.
Whenh=T, we get the final expanded form. (21)mKn1+1,n2,…,nr,x-mKn1,n2+1,…,nr,x=n1-n2x∑k=0T-1∑i3+…+ir=ki3∈0,1,…,n3⋯ir∈0,1,…,nrn3i3⋯nrirxkki3,i4,…,irmKn1,n2,n3-i3,…,nr-ir,x+n3!⋯nr!xTTn3,n4,…,nrΔ0,…,0Note that Δ(0,…,0)=n1m(Kn1-1,n2,x)-n2m(Kn1,n2-1,x). Now, considering the element n1m(Kn1-1,n2,x)-n2m(Kn1,n2-1,x), for x≠0, we have (22)n1mKn1-1,n2,x-n2mKn1,n2-1,x=n1∑k≥0xn1+n2-1-2k-1kmKn1-1,n2,k-n2∑k≥0xn1+n2-1-2k-1kmKn1,n2-1,k=∑k≥0xn1+n2-1-2k-1kn1n1-1kn2kk!-n2n1kn2-1kk!=∑k≥0xn1+n2-1-2k-1kn1-n2n1kn2kk!=∑k≥0xn1+n2-1-2k-1kn1-n2mKn1,n2,k=n1-n2xmKn1,n2,x.
From the above calculations, forx≠0, we can deduce the following result: (23)mKn1+1,n2,…,nr,x-mKn1,n2+1,…,nr,x=n1-n2x∑k=0T∑i3+…+ir=ki3∈0,1,…,n3⋯ir∈0,1,…,nrn3i3⋯nrirxkki3,i4,…,irmKn1,n2,n3-i3,…,nr-ir,x.
Thus,(24)xT+1mKn1+1,n2,…,nr,x-mKn1,n2+1,…,nr,x=n1-n2∑k=0T∑i3+…+ir=ki3∈0,1,…,n3⋯ir∈0,1,…,nrn3i3⋯nrirxT-kki3,i4,…,irmKn1,n2,n3-i3,…,nr-ir,x.
For a set of nonnegative integers{i3,…,ir}, Kn1,n2,n3-i3,…,nr-ir is a proper subgraph of Kn1,n2+1,…,nr. By Lemma 8, we get λ1(Kn1,n2+1,…,nr)>λ1(Kn1,n2,n3-i3,…,nr-ir). When x≥λ1(Kn1,n2+1,…,nr), we have m(Kn1,n2,n3-i3,…,nr-ir,x)>0. By (24), we have m(Kn1+1,n2,…,nr,x)-m(Kn1,n2+1,…,nr,x)>0. It follows that Kn1,n2+1,…,nr≻Kn1+1,n2,…,nr.
We thus complete the proof.Now, it is time to prove Theorems3 and 4.Proof of Theorem3.
Suppose that the largest matching root of completer-partite graphs is minimal for Kn1,n2,…,nr. If there are two parameters ni and nj satisfying nj≥ni>1, then (nj+1)-(ni-1)≥2. From Lemma 12, we get Kn1,…,ni,…,nj,…,nr≻Kn1,…,ni-1,…,nj+1,…,nr. By Proposition 10, we get λ1(Kn1,…,ni,…,nj,…,nr)>λ1(Kn1,…,ni-1,…,nj+1,…,nr). It is a contradiction. Hence, Kn1,n2,…,nr satisfies that all parameters are equal to 1 except one parameter equal to n-r+1. Thus, Kn1,n2,…,nr≅CS(n,r-1).Proof of Theorem4.
Suppose that the largest matching root of completer-partite graphs is maximal for Kn1,n2,…,nr. If there are two parameters ni and nj satisfying nj≥ni+2, then nj-1≥1. Owing to Lemma 12, we have Kn1,…,ni+1,…,nj-1,…,nr≻Kn1,…,ni,…,nj,…,nr. By Proposition 10, it implies that λ1(Kn1,…,ni+1,…,nj-1,…,nr)>λ1(Kn1,…,ni,…,nj,…,nr). It is a contradiction. Hence, for any i≠j, we have |ni-nj|≤1. It means that each parameter ni equals either ⌊n/r⌋ or ⌊n/r⌋+1, i.e., Kn1,n2,…,nr is isomorphic to T(n,r).


## 4. Conclusion

Recently, there are many results about the matching energy and matching roots of graphs [7, 11, 12, 18–23, 25–28, 31, 34], due to their important applications in statistical physics and chemistry. In this paper, we investigate the matching energy and the largest matching root among all the complete r-partite graphs with given order n, respectively. We find that their minimal graphs are both complete split graph CS(n,r-1), and the maximal graphs are both Turán graph T(n,r). In fact, complete split graph and Turán graph are two important graph classes which have extensive applications in extremal graph theory and network. For more details, we refer to [35]. In addition, there are many other chemical invariants, such as Laplacian energy [36], Randić energy [37], and incidence energy [38]. In the future, we would like to characterize the extremal graphs of the above invariants among the complete r-partite graphs.



---

*Source: 9728976-2019-04-16.xml*