On the relationship between the genus and the cardinality of the maximum matchings of a graph |
| |
Authors: | Takao Nishizeki |
| |
Institution: | Department of Electrical Communications, Faculty of Engineering, Tohoku University, Sendai, Japan 980 |
| |
Abstract: | Lower bounds on the cardinality of the maximum matchings of graphs are established in terms of a linear polynomial of p, p(1), p(2) and γ whose coefficients are functions of κ, where p is the number of the vertices of a graph, p(i) the number of the vertices of degree i (i = 1,2), γ the genus and κ the connectivity. |
| |
Keywords: | |
本文献已被 ScienceDirect 等数据库收录! |
|