[1]叶银珠,陈海燕.树线图的最大匹配数[J].集美大学学报(自然科学版),2024,29(5):463-467.
YE Yinzhu,CHEN Haiyan.On the Number of Maximum Matchings in the Line Graph of a Tree[J].Journal of Jimei University,2024,29(5):463-467.
点击复制
树线图的最大匹配数(PDF)
YE Yinzhu,CHEN Haiyan.On the Number of Maximum Matchings in the Line Graph of a Tree[J].Journal of Jimei University,2024,29(5):463-467.
《集美大学学报（自然科学版）》[ISSN:1007-7405/CN:35-1186/N]
- 卷:
- 第29卷
- 期数:
- 2024年第5期
- 页码:
- 463-467
- 栏目:
- 数理科学与信息工程
- 出版日期:
- 2024-09-28
文章信息/Info
- Title:
- On the Number of Maximum Matchings in the Line Graph of a Tree
- Author(s):
- YE Yinzhu; CHEN Haiyan
- School of Science,Jimei University,Xiamen 361021,China
- Keywords:
- maximum matching; line graph; tree; caterpillar tree; ternary tree
- 分类号:
- -
- DOI:
- -
- 文献标志码:
- A
- 摘要:
- 设T是n个顶点的树,令Max(L(T))表示T的线图L(T)最大匹配的数目。当n是奇数时,Max(L(T))就是L(T)的完美匹配数。当n是偶数时,研究线图L(T)的最大匹配,给出其最大匹配所含的边数,得到最大匹配数Max(L(T))的一个一般表达式。作为应用，得到了一些特殊的毛毛虫树和三元树线图最大匹配数的具体表达式。
- Abstract:
- Let T be a tree with n vertices,and let Max(L(T)) denote the number of maximum matchings in the line graph of T.When n is odd,Max(L(T)) is the number of perfect matchings of L(T).In this paper,the maximum matchings of L(T) for even n were studied.The number of edges in a maximum matching was firstly determined,and then a general expression for Max(L(T)) was given.As applications,for some special caterpillar trees and ternary trees,explicit expressions of Max(L(T)) were got.
参考文献/References:
相似文献/References:
备注/Memo
- 备注/Memo:
常用功能
统计/Statistics
- 摘要浏览/Viewed186
- 全文下载/Downloads197
- 评论/Comments
更新日期/Last Update:
2024-12-10