Back
 AM  Vol.12 No.6 , June 2021
The Number of Matching Equivalent for the Union Graph of Vertices and Cycles
Abstract: For two graphs G and H, if G and H have the same matching polynomial, then G and H are said to be matching equivalent. We denote by δ (G), the number of the matching equivalent graphs of G. In this paper, we give δ (sK1 ∪ t1C9 ∪ t2C15), which is a generation of the results of in [1].

1. Introduction

This paper only considers finite undirected simple graphs. Let G be a graph with n vertices. The matching of G means a spanning subgraph of G, and each of its connected branches is either an isolated vertex or an isolated edge. t-matching means matching that there are t edges. Matching polynomial of graph G is defined as follows in [2]:

μ ( G , x ) = t 0 ( 1 ) t α t ( G ) x n 2 t , (1)

where α t ( G ) is number of t-matching for G.

If graphG and graphH satisfy μ ( G , x ) = μ ( H , x ) , then we say G and H are matching equivalence, denoted as G ~ H .

Set δ ( G ) which denotes the number of matching equivalent graphs of all different isomorphisms for graphG, if δ ( G ) = 1 , we say graphG is a unique matching. In [2], the authors gave some elegant properties of matching polynomials, and proved that to find the matching polynomial of a graph is an NP-problem. Thus, in [1], the authors studied the number of matching equivalent graphs of some vertices and some cycle-union graphs. It turns out that the problem is not simple. In this paper, we study the number of matching equivalent for the union graph of vertices and cycles, that is δ ( s K 1 t 1 C 9 t 2 C 15 ) .

Throughout the paper, K1 denotes an isolated vertex, P n ( n 2 ) denotes the path including n vertices; C m ( m 3 ) denotes a cycle that including m vertices; T i , j , k denotes a tree that has only a 3-degree vertex, three 1-degree vertex, and the distance between this 3-degree vertex and three 1-degree vertex is i , j , k separately; D n ( n 4 ) denotes a graph that produced by bonding a vertex on a triangle to an end of a path P n 2 ; nG denotes disjoint union of n graph G.

2. Preliminaries

Lemma 2.1 [3] Suppose graph G has k connected component: G 1 , G 2 , , G k , then μ ( G , x ) = i = 1 k μ ( G i , x ) , the roots of matching polynomials are all real numbers, denote M ( G ) as the maximum root of μ ( G , x ) .

Lemma 2.2 [3] Suppose G is connected graph, then M ( G ) < 2 if and only if G Γ = { K 1 , P n , T 1 , 1 , n , T 1 , 2 , 2 , T 1 , 2 , 3 , T 1 , 2 , 4 , C n , D 4 } .

Lemma 2.3 [3] (i) M ( C m ) = M ( T 1 , 1 , m 2 ) = M ( P 2 m 1 ) .

(ii) M ( C 6 ) = M ( T 1 , 1 , 4 ) = M ( T 1 , 2 , 2 ) = M ( D 4 ) = M ( P 11 ) .

(iii) M ( C 9 ) = M ( T 1 , 1 , 7 ) = M ( T 1 , 2 , 3 ) = M ( P 17 ) .

(iv) M ( C 15 ) = M ( T 1 , 1 , 13 ) = M ( T 1 , 2 , 4 ) = M ( P 29 ) .

Lemma 2.4 [4] [5] (i) The matching equivalent graph of K 1 C m ( m 6 , 9 , 15 ) is K 1 C m , T 1 , 1 , m 2 .

(ii) The matching equivalent graph of K 1 C 6 is: K 1 C 6 , T 1 , 1 , 4 , P 3 D 4 .

(iii) The matching equivalent graph of K 1 C 9 is K 1 C 9 , T 1 , 1 , 7 , C 3 T 1,2,3 .

(iv) The matching equivalent graph of K 1 C 15 is: K 1 C 15 ~ C 3 C 5 T 1,2,4 .

Lemma 2.5 [6] (i) P 2 m + 1 ~ P m C m + 1 , ( m 2 ) .

(ii) T 1 , 1 n ~ K 1 C n + 2 .

(iii) T 1 , 2 , 2 ~ P 2 D 4 .

(iv) K 1 C 6 ~ P 3 D 4 .

(v) K 1 C 9 ~ C 3 T 1,2,3 .

(vi) K 1 C 15 ~ C 3 C 5 T 1,2,4 .

Lemma 2.6 [1] Suppose G = s K 1 or t 1 C m 1 t k C m k , then G is a unique matching, that is δ ( G ) = 1 .

Lemma 2.7 [1] Suppose

G = s K 1 t 1 C m 1 t 2 C m 2 t k C m k , m i 6 ( i = 1 , 2 , , k ) ,

then all matching equivalent graphs of G do not contain road branches.

Lemma 2.8 [1]

(i) G = s K 1 a P 3 t C 6 , then all matching equivalent graphs ofG do not contain P 11 branch and also T 1 , 2 , 2 [7],

(ii) δ ( s K 1 a P 3 t C 6 ) = δ ( s K 1 t C 6 ) .

Lemma 2.9 [1] [7] If m 6 , 9 , 15 , then

δ ( s K 1 t C 6 ) = min { s , t } + 1 . (2)

Lemma 2.10 [1] [8] If m i 6 , 9 , 15 ( i = 1 , 2 ) , then

δ ( s K 1 t 1 C m 1 t 2 C m 2 ) = i = 0 r min { s i , t 1 } + r + 1 , where

r = min { s , t 2 } . (3)

3. Main Results

Lemma 3.1 δ ( s K 1 t 1 C 3 t 2 C 5 t 3 C 9 ) = j = 0 r i = j r δ ( s i , t 1 + ( i j ) , t 2 ) ,

where

r = min { s , t 3 } . (4)

Proof. For simplicity, denote δ ( s K 1 t 1 C 3 t 2 C 5 t 3 C 9 ) = δ ( s , t 1 , t 2 , t 3 ) .

Set H ~ s K 1 t 1 C 3 t 2 C 5 t 3 C 6 , by lemma 2.3 (iii) and lemma 2.7, we know H contains connected component C 9 , T 1 , 1 , 7 or T 1 , 2 , 3 .

1) IfH contains C 9 , by H = C 9 H 2 ~ s K 1 t 1 C 3 t 2 C 5 t 3 C 9 , we know H 2 ~ s K 1 t 1 C 3 t 2 C 5 ( t 3 1 ) C 9 .

Such H 2 has a total of δ ( s , t 1 , t 2 , t 3 1 ) .

2) IfH contains T 1 , 1 , 7 , by H = T 1 , 1 , 7 H 2 ~ s K 1 t 1 C 3 t 2 C 5 t 3 C 9 and lemma 2.5 (ii), we know

H 2 ~ ( s 1 ) K 1 t 1 C 3 t 2 C 5 ( t 3 1 ) C 9 ,

Such H 2 has a total of δ ( s 1 , t 1 , t 2 , t 3 1 ) .

3) IfH contains T 1 , 2 , 3 , by H = T 1 , 2 , 3 H 2 ~ s K 1 t 1 C 3 t 2 C 5 t 3 C 9 and lemma 2.5(v), we get

H 2 ~ ( s 1 ) K 1 ( t 1 + 1 ) C 3 t 2 C 5 ( t 3 1 ) C 9 ,

Such H 2 has a total of δ ( s 1 , t 1 + 1 , t 2 , t 3 1 ) .

4) IfH contains C 9 and T 1 , 1 , 7 simultaneously, such H 2 has a total of δ ( s 1 , t 1 , t 2 , t 3 2 ) .

5) IfH contains C 9 and T 1 , 2 , 3 simultaneously, such H 2 has a total of δ ( s 1 , t 1 + 1 , t 2 , t 3 2 ) .

6) IfH contains T 1 , 1 , 7 and T 1 , 2 , 3 simultaneously, such H 2 has a total of δ ( s 2 , t 1 + 1 , t 2 , t 3 2 ) .

7) IfH contains C 9 , T 1 , 1 , 7 and T 1 , 2 , 3 simultaneously, such H 2 has a total of δ ( s 2 , t 1 + 1 , t 2 , t 3 3 ) .

Thus,

δ ( s , t 1 , t 2 , t 3 ) = δ ( s , t 1 , t 2 , t 3 1 ) + δ ( s 1 , t 1 , t 2 , t 3 1 ) + δ ( s 1 , t 1 + 1 , t 2 , t 3 1 ) δ ( s 1 , t 1 , t 2 , t 3 2 ) δ ( s 1 , t 1 + 1 , t 2 , t 3 2 ) δ ( s 2 , t 1 + 1 , t 2 , t 3 2 ) + δ ( s 2 , t 1 + 1 , t 2 , t 3 3 )

Then,

δ ( s , t 1 , t 2 , t 3 ) δ ( s 1 , t 1 , t 2 , t 3 1 ) δ ( s 1 , t 1 + 1 , t 2 , t 3 1 ) + δ ( s 2 , t 1 + 1 , t 2 , t 3 2 ) = δ ( s , t 1 , t 2 , t 3 1 ) δ ( s 1 , t 1 , t 2 , t 3 2 ) δ ( s 1 , t 1 + 1 , t 2 , t 3 2 ) + δ ( s 2 , t 1 + 1 , t 2 , t 3 3 )

Repeat the application of the above formula, we obtain

δ ( s , t 1 , t 2 , t 3 ) δ ( s 1 , t 1 , t 2 , t 3 1 ) δ ( s 1 , t 1 + 1 , t 2 , t 3 1 ) + δ ( s 2 , t 1 + 1 , t 2 , t 3 2 ) = δ ( s , t 1 , t 2 , 2 ) δ ( s 1 , t 1 , t 2 , 1 ) δ ( s 1 , t 1 + 1 , t 2 , 1 ) + δ ( s 2 , t 1 + 1 , t 2 , 0 ) = δ ( s , t 1 , t 2 , 1 ) δ ( s 1 , t 1 , t 2 , 0 ) δ ( s 1 , t 1 + 1 , t 2 , 0 ) = δ ( s , t 1 , t 2 , 0 ) = δ ( s , t 1 , t 2 )

Thus,

δ ( s , t 1 , t 2 , t 3 ) δ ( s 1 , t 1 , t 2 , t 3 1 ) = δ ( s 1 , t 1 + 1 , t 2 , t 3 1 ) δ ( s 2 , t 1 + 1 , t 2 , t 3 2 ) + δ ( s , t 1 , t 2 ) = δ ( s 2 , t 1 + 2 , t 2 , t 3 2 ) δ ( s 3 , t 1 + 2 , t 2 , t 3 3 ) + δ ( s 1 , t 1 + 1 , t 2 ) + δ ( s 1 , t 1 + 1 , t 2 ) = = i = 0 r δ ( s i , t 1 + i , t 2 )

δ ( s , t 1 , t 2 , t 3 ) δ ( s 1 , t 1 , t 2 , t 3 1 ) = i = 0 r δ ( s i , t 1 + i , t 2 ) (1')

δ ( s 1 , t 1 , t 2 , t 3 1 ) δ ( s 2 , t 1 , t 2 , t 3 2 ) = i = 1 r δ ( s i , t 1 + ( i 1 ) , t 2 ) (2')

δ ( s ( r 1 ) , t 1 , t 2 , t 3 ( r 1 ) ) δ ( s r , t 1 , t 2 , t 3 r ) = i = r 1 r δ ( s i , t 1 + i ( r 1 ) , t 2 ) (r')

δ ( s r , t 1 , t 2 , t 3 r ) = i = r r δ ( s i , t 1 + ( i r ) , t 2 ) (r+1')

Add (1'), (2'), , (r+1') together, we get

δ ( s , t 1 , t 2 , t 3 ) = j = 0 r i = j r δ ( s i , t 1 + ( i j ) , t 2 ) . +

Theorem 3.1

δ ( s K 1 t 1 C 9 t 2 C 15 ) = j = 0 r i = j r δ ( s i , i j , i j , t 1 ) . (5)

Proof. For simplicity, denote

δ ( s K 1 t C 3 t C 5 t 1 C 9 t 2 C 15 ) = δ ( s , t , t t 1 , t 2 ) .

Suppose H ~ G , by lemma 2.3(iv) and lemma 2.7, we know H contains connected component C 15 , T 1 , 1 , 13 or T 1 , 2 , 4 .

1) IfH contains C 15 , by H = C 15 H 2 ~ s K 1 t 1 C 9 t 2 C 15 we know H 2 ~ s K 1 t 1 C 9 ( t 2 1 ) C 15 . Such H 2 has a total of δ ( s , 0 , 0 , t 1 , t 2 1 ) .

2) IfH contains T 1 , 1 , 13 , by H = T 1 , 1 , 13 H 2 ~ G = s K 1 t 1 C 9 t 2 C 15 and lemma 2.5(ii), we get H 2 ~ ( s 1 ) K 1 t 1 C 9 ( t 2 1 ) C 15 . Such H 2 has a total of δ ( s 1 , 0 , 0 , t 1 , t 2 1 ) .

3) IfH contains T 1 , 2 , 4 , by H = T 1 , 2 , 4 H 2 ~ G = s K 1 t 1 C 9 t 2 C 15 and lemma 2.5(vi), we get H 2 ~ ( s 1 ) K 1 C 3 C 5 t 1 C 9 ( t 2 1 ) C 15 , such H 2 has a total of δ ( s 1 , 1 , 1 , t 1 , t 2 1 ) .

4) If H contains C 15 and T 1 , 1 , 13 , such H 2 has a total of δ ( s 1 , 0 , 0 , t 1 , t 2 2 ) .

5) IfH contains C 15 and T 1 , 2 , 4 , such H 2 has a total of δ ( s 1 , 1 , 1 , t 1 , t 2 2 ) .

6) If H contains T 1 , 1 , 13 and T 1 , 2 , 4 , such H 2 has a total of δ ( s 2 , 1 , 1 , t 1 , t 2 2 ) .

7) If H contains C 15 , T 1 , 1 , 13 and T 1 , 2 , 4 , such H 2 has a total of δ ( s 2 , 1 , 1 , t 1 , t 2 3 ) .

Then

δ ( s , 0 , 0 , t 1 , t 2 ) = δ ( s , 0 , 0 , t 1 , t 2 1 ) + δ ( s 1 , 0 , 0 , t 1 , t 2 1 ) + δ ( s 1 , 1 , 1 , t 1 , t 2 1 ) δ ( s 1 , 0 , 0 , t 1 , t 2 2 ) δ ( s 1 , 1 , 1 , t 1 , t 2 2 ) δ ( s 2 , 1 , 1 , t 1 , t 2 2 ) + δ ( s 2 , 1 , 1 , t 1 , t 2 3 )

Thus,

δ ( s , 0 , 0 , t 1 , t 2 ) δ ( s 1 , 0 , 0 , t 1 , t 2 1 ) δ ( s 1 , 1 , 1 , t 1 , t 2 1 ) + δ ( s 2 , 1 , 1 , t 1 , t 2 2 ) = δ ( s , 0 , 0 , t 1 , t 2 1 ) δ ( s 1 , 0 , 0 , t 1 , t 2 2 ) δ ( s 1 , 1 , 1 , t 1 , t 2 2 ) + δ ( s 2 , 1 , 1 , t 1 , t 2 3 )

Repeat the application of the above formula, we obtain

δ ( s , 0 , 0 , t 1 , t 2 ) δ ( s 1 , 0 , 0 , t 1 , t 2 1 ) δ ( s 1 , 1 , 1 , t 1 , t 2 1 ) + δ ( s 2 , 1 , 1 , t 1 , t 2 2 ) = δ ( s , 0 , 0 , t 1 , 2 ) δ ( s 1 , 0 , 0 , t 1 , 1 ) δ ( s 1 , 1 , 1 , t 1 , 1 ) + δ ( s 2 , 1 , 1 , t 1 , 0 ) = δ ( s , 0 , 0 , t 1 , 1 ) δ ( s 1 , 0 , 0 , t 1 , 0 ) δ ( s 1 , 1 , 1 , t 1 , 0 ) = δ ( s , 0 , 0 , t 1 )

So,

δ ( s , 0 , 0 , t 1 , t 2 ) δ ( s 1 , 0 , 0 , t 1 , t 2 1 ) = δ ( s 1 , 1 , 1 , t 1 , t 2 1 ) δ ( s 2 , 1 , 1 , t 1 , t 2 2 ) + δ ( s , 0 , 0 , t 1 ) = δ ( s 2 , 2 , 2 , t 1 , t 2 2 ) δ ( s 3 , 2 , 2 , t 1 , t 2 3 ) + δ ( s , 0 , 0 , t 1 ) + δ ( s 1 , 1 , 1 , t 1 )

= δ ( s 3 , 3 , 3 , t 1 , t 2 3 ) δ ( s 4 , 3 , 3 , t 1 , t 2 4 ) + δ ( s , 0 , 0 , t 1 ) + δ ( s 1 , 1 , 1 , t 1 ) + δ ( s 2 , 2 , 2 , t 1 ) = = i = 0 r δ ( s i , i , i , t 1 )

δ ( s , 0 , 0 , t 1 , t 2 ) δ ( s 1 , 0 , 0 , t 1 , t 2 1 ) = i = 0 r δ ( s i , i , i , t 1 ) (1'')

δ ( s 1 , 0 , 0 , t 1 , t 2 1 ) δ ( s 2 , 0 , 0 , t 1 , t 2 2 ) = i = 0 r δ ( s i , i 1 , i 1 , t 1 ) (2'')

δ ( s ( r 1 ) , 0 , 0 , t 1 , t 2 ( r 1 ) ) δ ( s r , 0 , 0 , t 1 , t 2 r ) = i = r 1 r δ ( s i , i ( r 1 ) , i ( r 1 ) , t 1 ) (r'')

δ ( s r , 0 , 0 , t 1 , t 2 r ) = i = r r δ ( s i , i r , i r , t 1 ) (r+1'')

Add (1''), (2''), , (r+1'') together, we get:

δ ( s , 0 , 0 , t 1 , t 2 ) = j = 0 r i = j r δ ( s i , i j , i j , t 1 ) . +

Characterizing all graphs determined by a graph polynomial is an important subject in algebraic graph theory, among them, matching polynomial is considered to be a better algebraic tool. It is NP difficult to completely characterize the matched equivalent graphs of a class of graphs. In this paper, we study the number of matching equivalent graphs of some points and some cycli-union graphs, that is to say we calculate

δ ( s K 1 t 1 C 9 t 2 C 15 ) = j = 0 r i = j r δ ( s i , i j , i j , t 1 ) .

Acknowledgements

This work is supported by the National Natural Science Foundation of China (No. 11561056), the Natural Science Foundation of Qinghai Province (2016-ZJ-914), Teaching Reform Research Project of Qinghai Nationalities University (2021-JYQN-005).

Cite this paper: Wang, X. (2021) The Number of Matching Equivalent for the Union Graph of Vertices and Cycles. Applied Mathematics, 12, 471-476. doi: 10.4236/am.2021.126032.
References

[1]   Ma, H.C. and Wang, X.L. (2006) Matching Equivalent Graph Class of Point-Circle Union Graph. Journal of Northeast Normal University (Natural Science Edition), 4, 36-40.

[2]   Godsil, C.D. (1993) Algebraic Combinatorics. Chapman and Hall, New York, London.

[3]   Ma, H.C. (2000) Matching Equivalence Classes of Two Types of Graphs. Journal of Mathematical Study, 2, 218-222.

[4]   Ma, H.C. (2003) Matches the Matching Equivalence Class of Graphs Whose Maximum Root Is Less than 2. Journal of Systems Science and Mathematical Sciences, 3, 337-342.

[5]   Ma, H.C. and Li, Y.K. (2016) The Matching Equivalence Graphs with the Maximam Matching Root Less than or Equal to 2. Applied Mathematics, 7, 920-926.
https://doi.org/10.4236/am.2016.79082

[6]   Guo, Z.Y. and Yu, Y.S. (1989) On the Matching Uniqueness of Two Kinds of Graphs. Mathematica Applicata, 2, 25-32.

[7]   Ma, H.C. (2017) A Characterization of Graphs with Rank More than 5. Applied Mathematics, 8, 26-34.
https://doi.org/10.4236/am.2017.81003

[8]   Ma, H.C. (2017) The Energy and Operations of Graphs. Advances in Pure Mathematics, 7, 345-351.
https://doi.org/10.4236/apm.2017.76021

 
 
Top