The Number of Matching Equivalent for the Union Graph of Vertices and Cycles ()
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]:
, (1)
where
is number of t-matching for G.
If graphG and graphH satisfy
, then we say G and H are matching equivalence, denoted as
.
Set
which denotes the number of matching equivalent graphs of all different isomorphisms for graphG, if
, 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
.
Throughout the paper, K1 denotes an isolated vertex,
denotes the path including n vertices;
denotes a cycle that including m vertices;
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
separately;
denotes a graph that produced by bonding a vertex on a triangle to an end of a path
; nG denotes disjoint union of n graph G.
2. Preliminaries
Lemma 2.1 [3] Suppose graph G has k connected component:
, then
, the roots of matching polynomials are all real numbers, denote
as the maximum root of
.
Lemma 2.2 [3] Suppose G is connected graph, then
if and only if
.
Lemma 2.3 [3] (i)
.
(ii)
.
(iii)
.
(iv)
.
Lemma 2.4 [4] [5] (i) The matching equivalent graph of
is
.
(ii) The matching equivalent graph of
is:
.
(iii) The matching equivalent graph of
is
.
(iv) The matching equivalent graph of
is:
.
Lemma 2.5 [6] (i)
.
(ii)
.
(iii)
.
(iv)
.
(v)
.
(vi)
.
Lemma 2.6 [1] Suppose
or
, then G is a unique matching, that is
.
Lemma 2.7 [1] Suppose
then all matching equivalent graphs of G do not contain road branches.
Lemma 2.8 [1]
(i)
, then all matching equivalent graphs ofG do not contain
branch and also
[7],
(ii)
.
Lemma 2.9 [1] [7] If
, then
. (2)
Lemma 2.10 [1] [8] If
, then
, where
. (3)
3. Main Results
Lemma 3.1
,
where
. (4)
Proof. For simplicity, denote
.
Set
, by lemma 2.3 (iii) and lemma 2.7, we know H contains connected component
or
.
1) IfH contains
, by
, we know
.
Such
has a total of
.
2) IfH contains
, by
and lemma 2.5 (ii), we know
,
Such
has a total of
.
3) IfH contains
, by
and lemma 2.5(v), we get
,
Such
has a total of
.
4) IfH contains
and
simultaneously, such
has a total of
.
5) IfH contains
and
simultaneously, such
has a total of
.
6) IfH contains
and
simultaneously, such
has a total of
.
7) IfH contains
,
and
simultaneously, such
has a total of
.
Thus,
Then,
Repeat the application of the above formula, we obtain
Thus,
(1')
(2')
(r')
(r+1')
Add (1'), (2'),
, (r+1') together, we get
. +
Theorem 3.1
. (5)
Proof. For simplicity, denote
.
Suppose
, by lemma 2.3(iv) and lemma 2.7, we know H contains connected component
or
.
1) IfH contains
, by
we know
. Such
has a total of
.
2) IfH contains
, by
and lemma 2.5(ii), we get
. Such
has a total of
.
3) IfH contains
, by
and lemma 2.5(vi), we get
, such
has a total of
.
4) If H contains
and
, such
has a total of
.
5) IfH contains
and
, such
has a total of
.
6) If H contains
and
, such
has a total of
.
7) If H contains
,
and
, such
has a total of
.
Then
Thus,
Repeat the application of the above formula, we obtain
So,
(1'')
(2'')
(r'')
(r+1'')
Add (1''), (2''),
, (r+1'') together, we get:
. +
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
.
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).