首页 | 本学科首页   官方微博 | 高级检索  
     检索      

ON MAXIMAL MATCHINGS OF CONNECTED GRAPHS
作者姓名:许宝刚
作者单位:School of
摘    要:Let I with |I| = k be a matching of a graph G (briefly, I is called a k-matching). If I is not a proper subset of any other matching of G, then I is a maximal k-matching and m(gk, G) is used to denote the number of maximal k-matchings of G. Let gk be a k-matching of G, if there exists a subset {e1, e2,…, ei} of E(G) \ gk, i (?)1, such that (1) for any j ∈ {1, 2,…,i}, gk + {ej} is a (k + l)-matching of G; (2) for any f ∈ E(G) \ (gk ∪ {e1,e2,…,ei}), gk + {f} is not a matching of G; then gk, is called an i wings k-matching of G and mi(gk,G) is used to denote the number of i wings k-matchings of G. In this paper, it is proved that both mi(gk,G) and m(gk,G) are edge reconstructible for every connected graph G, and as a corollary, it is shown that the matching polynomial is edge reconstructible.

关 键 词:机翼  匹配性  网络  图论  子集  子网络

ON MAXIMAL MATCHINGS OF CONNECTED GRAPHS
Xu Baogang School of Mathematics and Computer Science,Nanjing Normal University,Nanjing ,China.ON MAXIMAL MATCHINGS OF CONNECTED GRAPHS[J].Acta Mathematica Scientia,2004,24(4):603-607.
Authors:Xu Baogang School of Mathematics and Computer Science  Nanjing Normal University  Nanjing  China
Institution:Xu Baogang School of Mathematics and Computer Science,Nanjing Normal University,Nanjing 210097,China
Abstract:Let I with |I| = k be a matching of a graph G (briefly, I is called a k-matching). If I is not a proper subset of any other matching of G, then I is a maximal k-matching and m(gk, G) is used to denote the number of maximal k-matchings of G.wings k-matching of G and mi(gk, G) is used to denote the number of i wings k-matchings of G. In this paper, it is proved that both mi(gk, G) and m(gk, G) are edge reconstructible for every connected graph G, and as a corollary, it is shown that the matching polynomial is edge reconstructible.
Keywords:Wings  matching  reconstruction
本文献已被 CNKI 万方数据 等数据库收录!
设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号