The Number of Perfect Matchings in Two Types of 3-Regular Graph(PDF)

《南京师大学报（自然科学版）》[ISSN:1001-4616/CN:32-1239/N]

Issue:

2016年01期

Page:

21-

Research Field:

数学

Publishing date:

Info

Title:

The Number of Perfect Matchings in Two Types of 3-Regular Graph

Author(s):

Tang Baoxiang¹; Ren Han²

（1.School of Mathematics and Statistics，Tianshui Normal University，Tianshui 741001，China）（2.Department of Mathematics，East China Normal University，Shanghai 200062，China）

Keywords:

perfect matching; linear recurrence relation; 2-edge connected; 3-regular graph

PACS:

O157.5

DOI:

-

Abstract:

Lovász and Plummer proposed a conjecture on this problem：every 2-edge-connected cubic graph has at least exponential perfect matchings. This conjecture has not been proved or denied. In this paper，by applying differentiation，summation and the re-nested recursive method，several counting formulas of the perfect matching for three specific types of graphs are given. And the results indicate that the conjecture of Lovász and Plummer conjecture is true in the case of the three types of graphs.

References:

［1］ LOVáSZ L，PLUMMER M. Matching Theory［M］. New York：North-Holland Press，1986.

Memo

Memo:

-

Common functions