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

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}$ .

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.

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.

Cite this paper

Wu, T.Z. and Lü, H.Z. (2017) Constructing Matching Equivalent Graphs. Applied Mathematics, 8, 476- 482. https://doi.org/10.4236/am.2017.84038

References