Constructing Matching Equivalent Graphs

Tingzeng Wu¹, Huazhong Lü²

¹School of Mathematics and Statistics, Qinghai Nationalities University, Xining, China.
²School of Mathematics Science, University of Electronic Science and Technology of China, Chengdu, China.

DOI: 10.4236/am.2017.84038                

Abstract

Two nonisomorphic graphs G and H are said to be matching equivalent if and only if G and H have the same matching polynomials. In this paper, some families matching equivalent graphs are constructed. In particular, a new method to construct cospectral forests is given.

Keywords

Matching Polynomial, Matching Equivalent, Cospectral

1. Introduction

We use standard graph-theoretical notation and terminology. For concepts and notations not defined here, we refer the reader to [1] .

By a graph we always mean a simple undirected graph G with the vertex set $V\left(G\right)=\left\{v_1\mathrm{,}{v}_2\mathrm{,}\cdots \mathrm{,}{v}_n\right\}$ and the edge set $E\left(G\right)=\left\{e_1,e_2,\cdots ,e_m\right\}$ .We denote the complement of G by $\bar{G}$ . The degree of a vertex $v\in V\left(G\right)$ is denoted by $d_G\left(v\right)$ , abbreviated as $d_v$ . Let $G\cup H$ be the union of two graphs G and H which have no common vertices. For any positive integer l, let lG be the union of l disjoint copies of graph G. An acyclic graph, containing no cycles, is called a forest. A connected forest is called a tree. The complete bipartite graph with $p+q$ vertices is denoted by $K_{p\mathrm{,}q}$ . The path, star and complete graph with $n$ vertices are denoted by $P_n$ , $K_{\mathrm{1,}n-1}$ and $K_n$ , respectively.

A r-matching in G is a set of r pairwise non-incident edges. The number of r- matchings in G is denoted by $m\left(G\mathrm{,}r\right)$ . Specifically, $m\left(G,1\right)=m$ and

$m\left(G,r\right)=0$ for $r>\frac{n}{2}$ . It is both consistent and convenient to define $m\left(G,0\right)=1$ . The matching polynomial of the graph G is defined as

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

Matching polynomials have some important applications in statistical physics and structural chemistry. Up to now, the matching polynomials of graphs are extensively examined, we refer the reader to [2] - [14] and the references therein.

Two nonisomorphic graphs G and H are said to be matching equivalent, symbolically $G~H$ , if $\mu \left(G,x\right)=\mu \left(H,x\right)$ . Godsil and Gutman [15] first proposed the question to determine matching equivalent graphs. This seems difficult in the theory of graph polynomials. By now, little about the matching equivalent graphs have been published [16] [17] [18] [19] . In this paper, we plan to investigate the problem which graphs are matching equivalent.

2. Some Lemmas

In the section, we will present some lemmas which are required in the proof of the main results.

Lemma 1. [19] [20]

$\mu \left(G,x\right)={\displaystyle \underset{r=0}{\overset{n}{\sum }}}m\left(\bar{G},\left(n-r\right)/2\right)\mu \left(K_r,x\right)={\displaystyle \underset{m=0}{\overset{\lfloor n/2\rfloor }{\sum }}}m\left(\bar{G},m\right)\mu \left(K_{n-2m},x\right).$ (2)

Corollary 1. $G~H$ if and only if $\bar{G}~\bar{H}$ .

Proof. Corollary 1 follows directly by Lemma 1.

Lemma 2. [19] The matching polynomial satisfies the following identities:

1) $\mu \left(G\cup H,x\right)=\mu \left(G,x\right)\mu \left(H,x\right)$ ;

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

3) $\mu \left(G,x\right)=\mu \left(G\backslash u,x\right)-{\displaystyle {\sum }_{i~u}}\mu \left(G\backslash ui,x\right)$ , if $u\in V\left(G\right)$ .

Let G be a graph with a vertex u. The path tree $T\left(G\mathrm{,}u\right)$ is the tree with the paths in G which start at u as its vertices, and where two such paths are joined by an edge if one is a maximal subpath of the other.

Lemma 3. [21] Suppose G is a connected graph with $u\in V\left(G\right)$ , and suppose $T\left(G\mathrm{,}u\right)$ is the path tree associated with G with root u. Then $T\left(G\mathrm{,}u\right)$ has a subforest $T^{\prime }$ such that

$\mu \left(G,x\right)=\frac{\mu \left(T\left(G,u\right),x\right)}{\mu \left(T^{\prime },x\right)}.$ (3)

Remark 1. It is not difficult to derive the following description of an appropriate subforest $T^{\prime }$ : find a spanning tree $T_0$ of G by depth-first search from u, and delete from T all vertices corresponding to a path contained in $T_0$ .

Wu and Zhang [22] determined all connected graphs with matching number 2 as follows.

Lemma 4. ( [22] ) Let G be a connected graph with n vertices. Then $\nu \left(G\right)=2$ if and only if G is one of 22 graphs as shown in Figure 1, where $d\left(u\right)\ge 3$ in $G_6\left(u\right)$ , $d\left(u\right)\ge 4$ in $G_7\left(u\right)$ , $d\left(u\right)\ge 3$ in $G_{17}\left(u\right)$ , $d\left(u\right)\ge 3$ in $G_{18}\mathrm{<mo\; stretchy="false">\; (\; </mo>}u\mathrm{<mo\; stretchy="false">\; )\; </mo>}$ , $d\left(u\right)\ge 4$ in $G_{19}\mathrm{<mo\; stretchy="false">\; (\; </mo>}u\mathrm{<mo\; stretchy="false">\; )\; </mo>}$ , $d\left(u\right)\ge 3$ and $d\left(v\right)\ge 3$ in $G_{20}\left(u\mathrm{,}v\right)$ , $d\left(u\right)\ge 3$ and $d\left(v\right)\ge 3$ and $k\ge 1$ in $G_{21}\left(u\mathrm{,}v\mathrm{,}k\right)$ , $d\left(u\right)\ge 2$ and $d\left(v\right)\ge 2$ and $k\ge 1$ in $G_{22}\left(u\mathrm{,}v\mathrm{,}k\right)$ .

The eigenvalues of the adjacency matrix of G, denoted by ${\lambda }_i,\mathrm{<mi>\; </mi>}i=1,2,\cdots ,n,$ are the eigenvalues of G, and form the spectrum of G [1] . Two nonisomorphic

Figure 1. All connected graphs with the matching number 2.

graphs of the same order are cospectral if they have the same spectrum.

Lemma 5. ( [19] ) If G is a forest then $\varphi \left(G,x\right)=\mu \left(G,x\right)$ , where $\varphi \left(G,x\right)$ denotes the characteristic polynomial of G.

Lemma 5 implies the following result.

Corollary 2. Let G and H be two forests. If $G~H$ , then G and H are cospectral.

3. Main Results

For convenience, $G_{20}\left(u\mathrm{,}v\right)$ and $G_{22}\left(u\mathrm{,}v\mathrm{,}k\right)$ in Figure 1 are replaced by $G_{20}\left(d_u\mathrm{,}{d}_v\right)$ and $G_{22}\left(d_u\mathrm{,}{d}_v\mathrm{,}k\right)$ , respectively, where $d_u$ and $d_v$ denote the degree of vertices u and v, respectively, and k denotes the number of common neighbors of u and v.

Theorem 1. $G_{20}\left(n+\mathrm{4,2}n+4\right)~G_{22}\left(n+\mathrm{2,2}n+\mathrm{5,1}\right)$ .

Proof. By (2) of Lemma 2, we have

$\begin{array}{c}\mu \left(G_{20}\left(n+4,2n+4\right),x\right)=\mu \left(K_{1,n+3},x\right)\mu \left(K_{1,2n+3},x\right)-\left(3n+6\right)\mu \left(K_1,x\right)\\ =x^{3n+8}-\left(3n+7\right)x^{3n+6}+\left(2n^2+9n+9\right)x^{3n+4},\end{array}$

and

$\begin{array}{c}\mu \left(G_{22}\left(n+2,2n+5,1\right),x\right)\\ =\mu \left(K_{1,n+2},x\right)\mu \left(K_{1,2n+4},x\right)-\left(2n+4\right)\mu \left(K_1,x\right)\mu \left(K_{1,n+1},x\right)\\ =x^{3n+8}-\left(3n+7\right)x^{3n+6}+\left(2n^2+9n+9\right)x^{3n+4}.\end{array}$

Thus, $G_{20}\left(n+\mathrm{4,2}n+4\right)~G_{22}\left(n+\mathrm{2,2}n+\mathrm{5,1}\right)$ .

By Corollary 1 and Theorem 1, we have

Corollary 3. $\overline{G_{20}\left(n+\mathrm{4,2}n+4\right)}~\overline{G_{22}\left(n+\mathrm{2,2}n+\mathrm{5,1}\right)}$ .

Theorem 2. $G_{22}\left(k\mathrm{,}k+\mathrm{2,}k\right)$ and $G_{22}\left(k+\mathrm{1,}k+\mathrm{1,}k+1\right)\cup K_1$ are matching equivalent, and their complements are also matching equivalent, where $k>0$ .

Proof. By (2) of Lemma 2, we have

$\mu \left(G_{22}\left(k,k+2,k\right),x\right)=\mu \left(G_{22}\left(k,k+1,k\right),x\right)\mu \left(K_1,x\right)-\mu \left(K_1,x\right)\mu \left(K_{1,k},x\right)$

and

$\begin{array}{l}\mu \left(G_{22}\left(k+1,k+1,k+1\right)\cup K_1,x\right)\\ =\mu \left(G_{22}\left(k+1,k,k\right),x\right)\mu \left(K_1,x\right)-\left(2n+4\right)\mu \left(K_1,x\right)\mu \left(K_{1,k},x\right)\end{array}$

Checking $G_{22}\left(k\mathrm{,}k+\mathrm{1,}k\right)$ and $G_{22}\left(k+\mathrm{1,}k\mathrm{,}k\right)$ , it can be seen that $G_{22}\left(k\mathrm{,}k+\mathrm{1,}k\right)$ and $G_{22}\left(k+\mathrm{1,}k\mathrm{,}k\right)$ are isomorphic. So, $G_{22}\left(k\mathrm{,}k+\mathrm{2,}k\right)~G_{22}\left(k+\mathrm{1,}k+\mathrm{1,}k+1\right)\cup K_1$ . By Corollary 1, $\overline{G_{22}\left(k\mathrm{,}k+\mathrm{2,}k\right)}~\overline{G_{22}\left(k+\mathrm{1,}k+\mathrm{1,}k+1\right)\cup K_1}$ .

Theorem 3. Let G be a graph obtained by identifying a cycle $C_4$ to vertex u of $G_{22}\left(n-\mathrm{1,}n-\mathrm{1,}n-1\right)$ , and let H be a graph obtained by attaching a path $P_2$ to a vertex of degree two in $G_{22}\left(n\mathrm{,}n\mathrm{,}n\right)$ , where $n\ge 3$ (see Figure 2). Then $G~H$ and $\bar{G}~\bar{H}$ .

Proof. By (2) of Lemma 2, we obtain that $\mu \left(G\mathrm{,}x\right)\mathrm{<mo>\; =\; </mo>}\mu \left(G\backslash e\mathrm{,}x\right)-\text{μ}\left(K_{1,n-1},\text{x}\right)\text{μ}(P_2,\text{x})$ and $\mu \left(H\mathrm{,}x\right)=\mu \left(H\backslash e\mathrm{,}x\right)-\mu \left(K_{\mathrm{1,}n-1}\mathrm{,}x\right)\mu \left(P_2\mathrm{,}x\right)$ . Checking G and H, it can be known that $G\backslash e$ and $H\backslash e$ are isomorphic. So, $G~H$ . By Corollary 1, again we have $\bar{G}~\bar{H}$ .

Checking $G_{22}\left(d_u\mathrm{,}{d}_v\mathrm{,}k\right)$ , it is easy to find that $G_{22}\left(\mathrm{2,4,2}\right)$ and $G_{22}\left(\mathrm{3,3,3}\right)\cup K_1$ are matching equivalent. Based on the result above, we construct a pair of matching equivalent graphs as follows.

Theorem 4. Let G be a graph obtained by joining two single vertices to $v_q$ in $K_{p\mathrm{,}q}$ , and let H be a graph obtained by joining a single vertex to $v_{q-1}$ and $v_q$ in $K_{p\mathrm{,}q}$ , respectively, where $v_{q-1}$ and $v_q$ are both in the bipartition of q vertices in $K_{p\mathrm{,}q}$ (see Figure 3). Then $G~H\cup K_1$ and $\bar{G}~\overline{H\cup K_1}$ .

Proof. By (2) of Lemma 2, we obtain that $\mu \left(G,x\right)=\mu \left(G\backslash e,x\right)-\mu \left(K_{p,q-1},x\right)\mu (K_1,x）$ and $\mu \left(H\cup K_1,x\right)=\mu \left(H\backslash e,x\right)\mu (K_1,x)-\mu \left(K_{p,q-1},x\right)\mu (K_1,x)$ . Checking G and H, it can be known that $G\backslash e$ and $H\backslash e\cup K_1$ are isomorphic. So, $G~H$ . By Corollary 1, we have $\bar{G}~\overline{H\cup K_1}$ .

Figure 2. Graphs G and H in Theorem 3.

Figure 3. Graphs G and H in Theorem 4.

Theorem 5. Let G be a graph obtained by attaching a path $P_2$ to $u$ in $G_{22}\left(\mathrm{2,}n+\mathrm{1,2}\right)$ , and let H be a graph obtained by identifying the center of $K_{\mathrm{1,}{d}_v}$ to a pendant vertex of $G_{22}\left(\mathrm{2,2,3}\right)$ (see Figure 4). Then $G~H$ and $\bar{G}~\bar{H}$ .

Proof. By (2) of Lemma 2, we obtain that $\mu \left(G\mathrm{,}x\right)=\mu \left(G\backslash e\mathrm{,}x\right)-\mu \left(K_{\mathrm{1,}n}\mathrm{,}x\right)\mu \left(P_2\mathrm{,}x\right)$ and $\mu \left(H,x\right)=\mu \left(H\backslash e,x\right)-\mu \left(K_{1,n},x\right)\mu \left(P_2,x\right)$ . Checking G and H, it can be known that $G\backslash e$ is isomorphic to $H\backslash e$ . So $G~H$ . By Corollary 1, we have $\bar{G}~\bar{H}$ .

Theorem 6. Let G and H be two graphs which are defined in Theorem 5. Then $T\left(G\mathrm{,}v\right)\cup P_3~T\left(H\mathrm{,}{v}^{\prime }\right)\cup I$ and $\overline{T\left(G\mathrm{,}v\right)\cup P_3}~\overline{T\left(H\mathrm{,}{v}^{\prime }\right)\cup I}$ , where I denotes a graph obtained by attaching a single vertex $K_1$ to a pendant vertex of $K_{\mathrm{1,3}}$ , and $T\left(G\mathrm{,}v\right)$ and $T\left(H\mathrm{,}{v}^{\prime }\right)$ denote the path-trees of G and H, respec- tively (see Figure 5). In particular, $T\left(G\mathrm{,}v\right)\cup P_3$ and $T\left(H\mathrm{,}{v}^{\prime }\right)\cup I$ are cospec- tral.

Proof. By Lemma 3, we have $\mu \left(G,x\right)=\frac{\mu \left(T\left(G,v\right),x\right)}{\mu \left(I,x\right)}$ and $\mu \left(H,x\right)=\frac{\mu \left(T\left(H,v^{\prime }\right),x\right)}{\mu \left(P_3,x\right)}$ . By Theorem 5, we have $\mu \left(G,x\right)=\mu \left(H,x\right)$ . So, $\frac{\mu \left(T\left(G,v\right),x\right)}{\mu \left(I,x\right)}=\frac{\mu \left(T\left(H,v^{\prime }\right),x\right)}{\mu \left(P_3,x\right)}$ . This implies that $T\left(G\mathrm{,}v\right)\cup P_3~T\left(H\mathrm{,}{v}^{\prime }\right)\cup I$ .

By Corollary 1, we have $\overline{T\left(G\mathrm{,}v\right)\cup P_3}~\overline{T\left(H\mathrm{,}{v}^{\prime }\right)\cup I}$ . Furthermore, by Corollary 5, we know that $T\left(G\mathrm{,}v\right)\cup P_3$ and $T\left(H\mathrm{,}{v}^{\prime }\right)\cup I$ are cospectral.

4. Conclusion

In this paper, we constructed some families matching equivalent graphs in Theorems 1,..., and 4. Based on these results, using the same method in Theorem 6, we can construct some pairs of matching equivalent forests and cospectral forests, respectively.

Figure 4. Graphs G and H in Theorem 5.

Figure 5. Path trees of G and H in Theorem 6.

Acknowledgements

We thank the editor and referees for their comments. Research of Tingzeng Wu is funded by NSF of Qinghai (2016-ZJ-947Q), and high-level personnel of scientific research projects of QHMU(2016XJG07). These supports are greatly appreciated.

Conflicts of Interest

The authors declare no conflicts of interest.

References

[1]	Cvetkovic, D.M., Doob, M., Gutman, I. and Torgasev, A. (1988) Recent Results in the Theory of Graph Spectra. North-Holland, Amsterdam.
[2]	Farrell, E.J. (1979) An Introduction to Matching Polynomials. Journal of Combinatorial Theory, Series B, 27, 75-86.
[3]	Liu, W., Guo, Q., Zhang, Y., Feng, L. and Gutman, I. (2017) Further Results on the Largest Matching Root of Unicyclic Graphs. Discrete Applied Mathematics, 221, 82-88.
[4]	Gutman, I. and Wagner, S. (2012) The Matching Energy of a Graph. Discrete Applied Mathematics, 160, 2177-2187.
[5]	Ku, C. and Chen, W. (2010) An Analogue of the Gallai-Edmonds Structure Theorem for Non-Zero Roots of the Matching Polynomial. Journal of Combinatorial Theory, Series B, 100, 119-127.
[6]	Lass, B. (2004) Matching Polynomials and Duality. Combinatorica, 24, 427-440. https://doi.org/10.1007/s00493-004-0026-7
[7]	Li, X., Shi, Y. and Trinks, M. (2015) Polynomial Reconstruction of the Matching Polynomial. Electronic Journal of Graph Theory and Application, 3, 27-34. https://doi.org/10.5614/ejgta.2015.3.1.4
[8]	Wu, T., Yan, W. and Zhang, H. (2016) Extremal Matching Energy of Complements of Trees. Discussiones Mathematicae Graph Theory, 36, 505-522. https://doi.org/10.7151/dmgt.1869
[9]	Wu, T. (2016) Two Classes of Topological Indices of Phenylene Molecule Graphs. Mathematical Problems in Engineering, 2016, Article ID: 8421396. https://doi.org/10.1155/2016/8421396
[10]	Yan, W., Yeh, Y. and Zhang, F. (2005) On the Matching Polynomials of Graphs with Small Number of Cycles of Even Length. International Journal of Quantum Chemistry, 105, 124-130. https://doi.org/10.1002/qua.20670
[11]	Yan, W. and Yeh, Y. (2009) On the Matching Polynomial of Subdivision Graphs. Discrete Applied Mathematics, 157, 196-200.
[12]	Zhang, H., Lin, R. and Yu, G. (2013) The Largest Matching Root of Unicyclic Graphs. Information Processing Letters, 113, 804-806.
[13]	Zhang, H., Yu, G. and Li, S. (2015) Graphs with Six Distinct Matching Roots. Information Processing Letters, 115, 521-526.
[14]	Gutman, I. (2016) A Survey on the Matching Polynomial. In: Shi, Y., et al., Eds., Graph Polynomial, CRC Press, Boca Raton.
[15]	Godsil, C.D. and Gutman, I. (1981) On the Theory of the Matching Polynomial. Journal of Graph Theory, 5, 137-144. https://doi.org/10.1002/jgt.3190050203
[16]	Beezer, R.A. and Farrell, E.J. (1995) The Matching Polynomial of a Regular Graph. Discrete Mathematics, 137, 7-18.
[17]	Ma, H. and Ren, H. (2007) The New Methods for Constructing Matching-Equivalence Graphs. Discrete Mathematics, 307, 125-131.
[18]	Zhang, H. and Shu, J. (2012) On the Matching Polynomial of Theta Graphs. Ars Combinatoria, 104, 477-490.
[19]	Godsil, C.D. (1993) Algebraic Combinatorics. Chapman & Hall, New York, London.
[20]	Farrell, E.J. and Whitehead, E.G. (1992) Connections between the Matching and Chromatic Polynomials. International Journal of Mathematics and Mathematical Sciences, 15, 757-766. https://doi.org/10.1155/S016117129200098X
[21]	Lovász, L. and Plummer, M.D. (2009) Matching Theory. American Mathematical Society.
[22]	Wu, T. and Zhang, H. (2015) Per-Spectral Characterizations of Graphs with Extremal Per-Nullity. Linear Algebra and Its Applications, 484, 13-26.