The Quasi-Order of Matching Energy of Circum Graph with Chord

Ning Zhao, Yinkui Li

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

DOI: 10.4236/am.2017.88088                

Abstract

The matching energy of graph G is defined as , where be the roots of matching polynomial of graph G. In order to compare the energies of a pair of graphs, Gutman and Wager further put forward the concept of quasi-order relation. In this paper, we determine the quasiorder relation on the matching energy for circum graph with one chord.

Keywords

Matching Polynomial, Matching Energy, Matching Root

1. Introduction

All graphs considered are finite, undirected, loopless and without multiple edges. The terminology and nomenclature of [1] will be used. Throughout this paper, G will denote a graph with vertex set $V\left(G\right)=\left\{u,v,v_1,v_2,\cdots ,v_{n-2}\right\}$ and edge set $E\left(G\right)$ . By $G-u$ denote the induced subgraph obtained from G by deleting vertex u together with its incident edges and by $G-e$ the edge-induced subgraph obtained from G by deleting edge e. As usual, use $P_n$ and $C_n$ to denote the path and cycle on n vertices, respectively.

Let $m\left(G\mathrm{,}k\right)$ be the number of k-matchings in graph G. The matching polynomial of a graph G is defined in [2] as

$\alpha \left(G,\lambda \right)={\displaystyle \underset{k\ge 0}{\sum }}{\left(-1\right)}^{k}m\left(G,k\right){\lambda }^{n-2k}.$ (1)

where $m\left(G,0\right)=1$ and $m\left(G\mathrm{,}k\right)\ge 0$ for all $k=1,2,\cdots ,\lfloor \frac{n}{2}\rfloor$ .

Gutman and Wager defined the quasi-order “ $\succcurlyeq$ ” of two graphs G and H as follows:

If G and H have the matching polynomials in the form (1), then the quasi- order “ $\succcurlyeq$ ” is defined by

$G\succcurlyeq H\iff m\left(G\mathrm{,}k\right)\ge m\left(H\mathrm{,}k\right)\text{for}\text{all}k=\mathrm{0,1,}\cdots \mathrm{,}\lfloor n/2\rfloor \mathrm{.}$ (2)

In particular, if $G\succcurlyeq H$ and $m\left(G\mathrm{,}k\right)>m\left(H\mathrm{,}k\right)$ for some k, then we write $G\succ H$ .

We call G and H matching-equivalent if both $G\succcurlyeq H$ and $H\succcurlyeq G$ hold and denoted by $G~H$ . Further, Gutman and Wagner introduced the concept of matching energy $ME\left(G\right)$ of a graph G in [3] and defined in different expressions as follows:

$ME\left(G\right)=\frac{2}{\text{π}}{\displaystyle {\int }_0^{\infty }}\frac{1}{x^2}ln\left[{\displaystyle \underset{k\ge 0}{\sum }}m\left(G\mathrm{,}k\right)x^{2k}\right]\text{d}x\mathrm{.}$ (3)

and

$ME\left(G\right)={\displaystyle \underset{i=1}{\overset{n}{\sum }}}\left|{\lambda }_i\right|$

where ${\lambda }_1\mathrm{,}{\lambda }_2\mathrm{,}\cdots \mathrm{,}{\lambda }_n$ be the roots of matching polynomial of graph G.

The matching energy $ME\left(G\right)$ of a graph G is an important index, which is widely used in the field of molecular orbital theory. There are many literatures about this parameter. See [4] - [14] .

By the above definitions, it is immediately to get

$G\succcurlyeq H\Rightarrow ME\left(G\right)\ge ME\left(H\right)\text{and}G\succ H\Rightarrow ME\left(G\right)>ME\left(H\right)\mathrm{.}$ (4)

In fact, this property provide an important technique to determine the order relation of the matching energy for graphs. In this paper, we discuss the order of the matching energy for circum graph with chord.

Let $C_n=uv{v}_1{v}_2\cdots v_{n-2}u$ be a cycle with order n, the circum graph with chord is obtained by adding one edge $u{v}_i$ for some $i\in \left\{\mathrm{1,2,}\cdots \mathrm{,}n-3\right\}$ to $C_n$ , which is denoted by $G\left(n\mathrm{<mo>\; ;\; </mo>}i\mathrm{,}n-2-i\right)$ and simplified as $G_{u~v_i}$ .

2. Preliminaries

Lemma 1. [2] Let $e=uv$ be an edge of graph G and $k\ge 1$ . Then $m\left(G,k\right)=$ Math_39#.

By Lemma 1, it is easy to get

Lemma 2. Let e be an edge of graph G. Then $ME\left(G-e\right)<ME\left(G\right)$ .

Lemma 3. [15] Let u be a vertex of graph G. Then $m\left(G,k\right)=m\left(G-u,k\right)+{\displaystyle \underset{v}{\sum }}m\left(G-u-v,k-1\right)$ , where the summation goes over all vertices v adjacent to the vertex u.

Lemma 4. [16] Let $n=4k+i,i\in \left\{0,1,2,3\right\}$ for $k\ge 1$ . Then $P_n\succ P_2\cup P_{n-2}$ $\succ P_4\cup P_{n-4}\succ \cdots \succ P_{2k}\cup P_{n-2k}\succ P_{2k+1}\cup P_{n-2k-1}\succ P_{2k-1}\cup P_{n-2k+1}\succ \cdots \succ P_3\cup P_{n-3}$ $\succ P_1\cup P_{n-1}$ .

By the definition of graph $G_{u~v_i}$ , we can immediately get

Lemma 5. $G_{u~v_i}~G_{u~v_{n-2-i}}$ for $i\in \left\{\mathrm{1,2,}\cdots \mathrm{,}n-3\right\}$ .

Proof. Since $G_{u~v_i}=G\left(n;i,n-2-i\right)$ and $G_{u~v_{n-2-i}}=G\left(n;,n-2-i,i\right)$ , so we get $G_{u~v_i}~G_{u~v_{n-2-i}}$ .,

3. Main Results

Theorem 6. Let $G_{u~v_i}$ be a circum graph with chord and n is an even. Then $G_{u~v_1}\prec G_{u~v_3}\prec \cdots \prec G_{u~v_{\frac{n-2}{2}-1}}\prec G_{u~v_{\frac{n-2}{2}}}\prec G_{u~v_{\frac{n-2}{2}-2}}\prec \cdots \prec G_{u~v_4}\prec G_{u~v_2}$ .

Proof. First we consider the graph $G_{u~v_s}$ and $G_{u~v_{s-2}}$ . Since n is even, by Lemma 5, we only consider $1\le s\le \frac{n-2}{2}$ . By Lemma 3, we obtain that

$\begin{array}{c}m\left(G_{u~v_s},k\right)=m\left[G\left(n;s,n-2-s\right),k\right]\\ =m\left(P_{s+\left(n-2-s\right)+1},k\right)+m\left(P_{\left(s-1\right)+\left(n-2-s\right)+1},k-1\right)\\ +m\left(P_{s+\left(n-2-s-1\right)+1},k-1\right)+m\left(P_s\cup P_{n-2-s},k-1\right)\\ =m\left(P_{n-1},k\right)+2m\left(P_{n-2},k-1\right)+m\left(P_s\cup P_{n-2-s},k-1\right)\end{array}$ (5)

Similarly,

$\begin{array}{c}m\left(G_{u~v_{s-2}},k\right)=m\left[G\left(n;s-2,n-s\right),k\right]\\ =m\left(P_{\left(s-2\right)+\left(n-s\right)+1},k\right)+m\left(P_{\left(s-2-1\right)+\left(n-s\right)+1},k-1\right)\\ +m\left(P_{\left(s-2\right)+\left(n-s-1\right)+1},k-1\right)+m\left(P_{s-2}\cup P_{n-s},k-1\right)\\ =m\left(P_{n-1},k\right)+2m\left(P_{n-2},k-1\right)+m\left(P_{s-2}\cup P_{n-s},k-1\right)\end{array}$ (6)

Based on (5) and (6), we immediately get $m\left(G_{u~v_s},k\right)-m\left(G_{u~v_{s-2}},k\right)=m\left(P_s\cup P_{n-2-s},k-1\right)-m\left(P_{s-2}\cup P_{n-s},k-1\right)$ .

Case 1. s is even.

By Lemma 4, we can obtain that $P_s\cup P_{n-2-s}\prec P_{s-2}\cup P_{n-s}$ . Thus, for some k, there be $m\left(G_{u~v_{s-2}},k\right)>m\left(G_{u~v_s},k\right)$ . This means that $G_{u~v_2}\succ G_{u~v_4}\succ G_{u~v_6}\succ \cdots$

$\succ G_{u~v_{\frac{n-2}{2}}}$ .

Case 2. $s$ is odd.

By Lemma 4, using a similar argument as in the previous proof we conclude that $P_s\cup P_{n-2-s}\succ P_{s-2}\cup P_{n-s}$ . Thus, for some k, there be $m\left(G_{u~v_s},k\right)>m\left(G_{u~v_{s-2}},k\right)$ . This imply that $G_{u~v_{\frac{n-2}{2}-1}}\succ G_{u~v_{\frac{n-2}{2}-3}}\succ \cdots \succ G_{u~v_3}\succ G_{u~v_1}$ .

For graph $G_{u~v_{\frac{n-2}{2}}}$ and $G_{u~v_{\frac{n-2}{2}-1}}$ , we get that

$m\left(G_{u~v_{\frac{n-2}{2}}},k\right)-m\left(G_{u~v_{\frac{n-2}{2}-1}},k\right)=m\left(P_{\frac{n-2}{2}}\cup P_{\frac{n-2}{2}},k-1\right)-m\left(P_{\frac{n-2}{2}-1}\cup P_{\frac{n-2}{2}+1},k-1\right)$

Repeating the same argument as in the previous proof, combine the fact n is even, we have $P_{\frac{n-2}{2}}\cup P_{\frac{n-2}{2}}\succ P_{\frac{n-2}{2}-1}\cup P_{\frac{n-2}{2}+1}$ . Thus $G_{u~v_{\frac{n-2}{2}}}\succ G_{u~v_{\frac{n-2}{2}-1}}$ . Sum up all, we get $G_{u~v_1}\prec G_{u~v_3}\prec \cdots \prec G_{u~v_{\frac{n-2}{2}-1}}\prec G_{u~v_{\frac{n-2}{2}}}\prec G_{u~v_{\frac{n-2}{2}-2}}\prec G_{u~v_2}$ . ,

Theorem 7. Let n is an odd number. Then

1) If $\lfloor \frac{n-2}{2}\rfloor$ is also odd, then $G_{u~v_2}\succ G_{u~v_4}\succ G_{u~v_{\lfloor \frac{n-2}{2}\rfloor -1}}\succ G_{u~v_{\lfloor \frac{n-2}{2}\rfloor }}$ $\succ G_{u~v_{\lfloor \frac{n-2}{2}\rfloor -2}}\succ \cdots \succ G_{u~v_3}\succ G_{u~v_1}$ ;

2) If $\lfloor \frac{n-2}{2}\rfloor$ is even, then $G_{u~v_2}\succ G_{u~v_4}\succ G_{u~v_{\lfloor \frac{n-2}{2}\rfloor }}\succ G_{u~v_{\lfloor \frac{n-2}{2}\rfloor -1}}\succ G_{u~v_{\lfloor \frac{n-2}{2}\rfloor -3}}$ $\succ \cdots \succ G_{u~v_3}\succ G_{u~v_1}$ .

Proof. First consider the graph $G_{u~v_s}$ and $G_{u~v_{s-2}}$ . Since n is odd, similar as Lemma 5, we only consider $1\le s\le \lfloor \frac{n-2}{2}\rfloor$ . By Lemma 1, we get $m\left(G_{u~v_s},k\right)-m\left(G_{u~v_{s-2}},k\right)=m\left(P_s\cup P_{n-2-s},k-1\right)-m\left(P_{s-2}\cup P_{n-s},k-1\right)$ .

Case 1. s is even.

By Lemma 4, we have $P_s\cup P_{n-2-s}\prec P_{s-2}\cup P_{n-s}$ . Thus, $m\left(G_{u~v_{s-2}}\mathrm{,}k\right)>$ Math_87#.

If $\lfloor \frac{n-2}{2}\rfloor$ is odd, then $G_{u~v_2}\succ G_{u~v_4}\succ G_{u~v_6}\succ \cdots \succ G_{u~v_{\lfloor \frac{n-2}{2}\rfloor -1}}$ .

If $\lfloor \frac{n-2}{2}\rfloor$ is even, then $G_{u~v_2}\succ G_{u~v_4}\succ G_{u~v_6}\succ \cdots \succ G_{u~v_{\frac{n-2}{2}}}$ .

Case 2. s is odd.

By Lemma 4, we have $P_s\cup P_{n-2-s}\succ P_{s-2}\cup P_{n-s}$ . Thus, $m\left(G_{u~v_s}\mathrm{,}k\right)>m\left(G_{u~v_{s-2}}\mathrm{,}k\right)$ .

If $\lfloor \frac{n-2}{2}\rfloor$ is odd, then $G_{u~v_{\lfloor \frac{n-2}{2}\rfloor }}\succ G_{u~v_{\lfloor \frac{n-2}{2}\rfloor -2}}\succ \cdots \succ G_{u~v_3}\succ G_{u~v_1}$ .

If $\lfloor \frac{n-2}{2}\rfloor$ is even, then $G_{u~v_{\lfloor \frac{n-2}{2}\rfloor -1}}\succ G_{u~v_{\lfloor \frac{n-2}{2}\rfloor -3}}\succ \cdots \succ G_{u~v_3}\succ G_{u~v_1}$ .

Based on the above analysis, if $\lfloor \frac{n-2}{2}\rfloor$ is odd,

$\begin{array}{l}m\left(G_{u~v_{\lfloor \frac{n-2}{2}\rfloor }-1}\mathrm{,}k\right)-m\left(G_{u~v_{\lfloor \frac{n-2}{2}\rfloor }}\mathrm{,}k\right)\\ =m\left[G\left(n\mathrm{<mo>\; ;\; </mo>}\lfloor \frac{n-2}{2}\rfloor -\mathrm{1,}\lceil \frac{n-2}{2}\rceil +1\right)\mathrm{,}k\right]-m\left[G\left(n\mathrm{<mo>\; ;\; </mo>}\lfloor \frac{n-2}{2}\rfloor \mathrm{,}\lceil \frac{n-2}{2}\rceil +1\right)\mathrm{,}k\right]\\ =m\left(P_{\lfloor \frac{n-2}{2}\rfloor -1}\cup P_{\lceil \frac{n-2}{2}\rceil +1}\mathrm{,}k-1\right)-m\left(P_{\lfloor \frac{n-2}{2}\rfloor }\cup P_{\lceil \frac{n-2}{2}\rceil }\mathrm{,}k-1\right)\end{array}$

By lemma 4, $P_{\lfloor \frac{n-2}{2}\rfloor -1}\cup P_{\lceil \frac{n-2}{2}\rceil +1}\succ P_{\lfloor \frac{n-2}{2}\rfloor }\cup P_{\lceil \frac{n-2}{2}\rceil }$ . Thus for some k, we have $m\left(G_{u~v_{\lfloor \frac{n-2}{2}\rfloor -1}}\mathrm{,}k\right)>m\left(G_{u~v_{\lfloor \frac{n-2}{2}\rfloor }}\mathrm{,}k\right)$ . This means $G_{u~v_{\lfloor \frac{n-2}{2}\rfloor }-1}\succ G_{u~v_{\lfloor \frac{n-2}{2}\rfloor }}$ .

If $\lfloor \frac{n-2}{2}\rfloor$ is even, then

$\begin{array}{l}m\left(G_{u~v_{\lfloor \frac{n-2}{2}\rfloor }},k\right)-m\left(G_{u~v_{\lfloor \frac{n-2}{2}\rfloor -1}},k\right)\\ =m\left[G\left(n;\lfloor \frac{n-2}{2}\rfloor ,\lceil \frac{n-2}{2}\rceil \right),k\right]-m\left[G\left(n;\lfloor \frac{n-2}{2}\rfloor -1,\lceil \frac{n-2}{2}\rceil +1\right),k\right]\\ =m\left(P_{\lfloor \frac{n-2}{2}\rfloor }\cup P_{\lceil \frac{n-2}{2}\rceil },k-1\right)-m\left(P_{\lfloor \frac{n-2}{2}\rfloor -1}\cup P_{\lceil \frac{n-2}{2}\rceil +1},k-1\right)\end{array}$

By Lemma 4, $P_{\lfloor \frac{n-2}{2}\rfloor }\cup P_{\lceil \frac{n-2}{2}\rceil }\succ P_{\lfloor \frac{n-2}{2}\rfloor -1}\cup P_{\lceil \frac{n-2}{2}\rceil +1}$ . Thus for some k, we have $m\left(G_{u~v_{\lfloor \frac{n-2}{2}\rfloor }}\mathrm{,}k\right)>m\left(G_{u~v_{\lfloor \frac{n-2}{2}\rfloor -1}}\mathrm{,}k\right)$ . This means that $G_{u~v_{\lfloor \frac{n-2}{2}\rfloor }}\succ G_{u~v_{\lfloor \frac{n-2}{2}\rfloor -1}}$ . Sum up all, for n is an odd, if $\lfloor \frac{n-2}{2}\rfloor$ is also odd, then $G_{u~v_2}\succ G_{u~v_4}\succ G_{u~v_{\lfloor \frac{n-2}{2}\rfloor -1}}$ Math_110#;

If $\lfloor \frac{n-2}{2}\rfloor$ is an even, then $G_{u~v_2}\succ G_{u~v_4}\succ G_{u~v_{\lfloor \frac{n-2}{2}\rfloor }}\succ G_{u~v_{\lfloor \frac{n-2}{2}\rfloor -1}}\succ G_{u~v_{\lfloor \frac{n-2}{2}\rfloor -3}}$ $\succ \cdots \succ G_{u~v_3}\succ G_{u~v_1}$ .

By Theorems 6 and 7, we immediately get our main result as follow.

Theorem 8. Let $G_{u~v_i}\left(i=1,2,\cdots ,n-3\right)$ be a circum graphs with chord.

1) If n is an even, then

$\begin{array}{c}ME\left(G_{u~v_1}\right)<ME\left(G_{u~v_3}\right)<\cdots <ME\left(G_{u~v_{\lfloor \frac{n-2}{2}\rfloor }}\right)<ME\left(G_{u~v_{\lfloor \frac{n-2}{2}\rfloor -1}}\right)\\ <ME\left(G_{u~v_{\lfloor \frac{n-2}{2}\rfloor -3}}\right)<\cdots <ME\left(G_{u~v_2}\right)<ME\left(G_{u~v_2}\right)\end{array}$ (7)

2) If n and $\lfloor \frac{n-2}{2}\rfloor$ are both odd, then

$\begin{array}{c}ME\left(G_{u~v_1}\right)<ME\left(G_{u~v_3}\right)<\cdots <ME\left(G_{u~v_{\lfloor \frac{n-2}{2}\rfloor -2}}\right)<ME\left(G_{u~v_{\lfloor \frac{n-2}{2}\rfloor }}\right)\\ <ME\left(G_{u~v_{\lfloor \frac{n-2}{2}\rfloor -1}}\right)<\cdots <ME\left(G_{u~v_4}\right)<ME\left(G_{u~v_2}\right)\end{array}$ (8)

3) If n is an odd and $\lfloor \frac{n-2}{2}\rfloor$ is an even, then

$\begin{array}{c}ME\left(G_{u~v_1}\right)<ME\left(G_{u~v_3}\right)<\cdots <ME\left(G_{u~v_{\lfloor \frac{n-2}{2}\rfloor -3}}\right)<ME\left(G_{u~v_{\lfloor \frac{n-2}{2}\rfloor -1}}\right)\\ <ME\left(G_{u~v_{\lfloor \frac{n-2}{2}\rfloor }}\right)<\cdots <ME\left(G_{u~v_4}\right)<ME\left(G_{u~v_2}\right)\end{array}$ (9)

4. Conclusions and Suggestions

In this paper, we determine the quasi-order relation on the matching energy for circum graph with one chord. If the chord here can be see $P_2$ . Then the general case, determining the quasi-order relation on the matching energy for circum graph with one generalized chord $P_k$ for $2\le k\le n-3$ is more meaningful.

Acknowledgements

Sincere thanks to the members of JAMP for their professional performance, and special thanks to managing editor for a rare attitude of high quality. This research supported by NSFC (11561056, 11661066) and QHAFP (2017-ZJ-701).

Conflicts of Interest

The authors declare no conflicts of interest.

References

[1]	Godsil, C.D. (1993) Algebraic Combinatorics. Chapman and Hall, Academic Press, New York.
[2]	Farrell, E.J. (1979) An Introduction to Matching Polynomials. Journal of Combinatorial Theory, Series B, 27, 75-86. https://doi.org/10.1016/0095-8956(79)90070-4
[3]	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
[4]	Chen, L. and Shi, Y. (2015) The Maximal Matching Energy of Tricyclic Graphs. MATCH Communications in Mathematical and in Computer Chemistry, 73, 105- 119.
[5]	Chen, L., Liu, J. and Shi, Y. (2015) Matching Energy of Unicyclic and Bicyclic Graphs with a Given Diameter. Complexity, 21, 224-238. https://doi.org/10.1002/cplx.21599
[6]	Chen, L., Liu, J. and Shi, Y. (2016) Bounds on the Matching Energy of Unicyclic Odd-Cycle Graphs. MATCH Communications in Mathematical and in Computer Chemistry, 75, 315-330.
[7]	Chen, L., Li, X. and Lian, H. (2015) The Matching Energy of Random Graphs. Discrete Applied Mathematics, 193, 102-109. https://doi.org/10.1016/j.dam.2015.04.022
[8]	Feng, L., Liu, W., Ili?, A. and Yu, G. (2013) The Degree Distance of Unicyclic Graphs with Given Matching Number. Graphs Comb., 29, 353-360. https://doi.org/10.1007/s00373-012-1143-5
[9]	Ji, S., Li, X. and Shi, Y. (2013) Extremal Matching Energy of Bicyclic Graphs. MATCH Communications in Mathematical and in Computer Chemistry, 70, 697- 706.
[10]	Li, H., Zhou, Y. and Su, L. (2014) Graphs with Extremal Matching Energies and Prescribed Parameters. MATCH Communications in Mathematical and in Computer Chemistry, 72, 239-248.
[11]	Li, S. and Yan, W. (2014) The Matching Energy of Graphs with Given Parameters. Discrete Applied Mathematics, 162, 415-420. https://doi.org/10.1016/j.dam.2013.09.014
[12]	Xu, K., Zheng, Z. and Das, K.C. (2015) Extremal t-Apex Trees with Respect to Matching Energy. Complexity, 21, 238-247.
[13]	Xu, K., Das, K.C. and Zheng, Z. (2015) The Minimum Matching Energy of (n,m)-Graphs with a Given Matching Number. MATCH Communications in Mathematical and in Computer Chemistry, 73, 93-104.
[14]	Yan, W.G. and Yeh, Y.N. (2009) On the Matching Polynomial of Subdivision Graphs. Discrete Applied Mathematics, 157, 195-200. https://doi.org/10.1016/j.dam.2008.05.005
[15]	Gutman, I. (1979) The Matching Polynomial. MATCH Communications in Mathematical and in Computer Chemistry, 6, 75-91.
[16]	Gutman, I. (1977) The Acyclic Polynomial of a Graph. Publications de l’Institut Mathématique (Beograd), 22, 63-69.