﻿ 有向三角形树的匹配数

# 有向三角形树的匹配数On the Matching Number of Directed Triangle Trees

Abstract: A matching of a directed graph G is a set of some directed edges without common starting-node and end-node. K-matching of a digraph G is the matching with the k (k = 1, 2,…, n) edges; k-matching number of a graph G is the number of distinct matchings containing k (k = 1, 2,…, n) edges. The matching of a graph G refers to the number of all k-matchings. Liu and Barabasi put forward: the number of controllable nodes in directed networks is equal to the number of nodes of directed networks minus the number of edges of the maximum matching. It illustrates that the matching number and controllability of directed networks have a close connection. Thus, the research of the number of all matchings of directed networks is of applied significance. This article mainly studies the counting problems and the extremal problems on the number of matchings in a class of directed triangle trees. We investigate the calculation method and the expression of the matching number in a class of directed triangle trees with n triangles and determine the bounds for the matching number in directed triangle trees with n triangles and the correspond graphs.

 汪小帆, 李翔, 陈关荣. 网络科学导论[M]. 北京: 高等教育出版社, 2012.

 郭世泽, 陆哲明. 复杂网络基础理论[M]. 北京: 科学出版社, 2012.

 Liu, Y.Y., Slotine, J.J. and Barabasi, A.L. (2011) Controllability of Complex Networks. Nature, 473, 167-173.
http://dx.doi.org/10.1038/nature10011

 陈关荣. 复杂动态网络环境下控制理论遇到的问题与挑战[J]. 自动化学报. 2013, 39(4): 312-321.

 Wagner, S. (2008) Extremal Trees with Respect to Hosoya Index and Merri-field-Simmons Index. MATCH Communications in Mathematical and in Computer Chemistry, 59, 203-216.

 Wagner, S. and Gutman, I. (2010) Maxima and Minima of the Hosoya Index and Merrifield-Simmons Index A Survey of Result and Techniques. Acta Applicandae Mathematicae, 112, 323-346.
http://dx.doi.org/10.1007/s10440-010-9575-5

 West, D.B., 著. 图论导引[M]. 李建中, 骆吉洲, 译. 北京: 机械工业出版社, 2005.

 Jogen, B.J. and Gutin, G., 著. 有向图理论, 算法及其应用[M]. 姚兵, 张忠辅, 译. 北京: 科学出版社, 2009.

 邓辉文. 离散数学[M]. 北京: 清华大学出版社, 2013.

Top