|
|
次三正则图最小极大匹配上界的改进
|
Abstract:
图G的边控制数是图中最大匹配的最小大小。众所周知，这个参数计算起来很困难。Julien Baste根据正则图和非正则图的阶数及最大度给出了最优可能上界。研究了边支配数的上界和相关算法，他给出了次三正则二部不含T*图的最小极大匹配的上界。其中T*是由爪形图的两条边恰好细分一次而形成的树。本文在此基础上，改进了其中次三正则图边控制数的上界，并作出一些推论。
The edge control number Υ(G) of graph G is the minimum size of a maximal match in the graph. This parameter is notoriously difficult to calculate. Julien Baste gives the optimal possible upper bound according to the order and maximum degree of regular graph and non-regular graph. In this paper, we study the upper bound and correlation algorithm of edge dominating numbers. He gives the upper bound of minimum maximal matching of subcubic bipartite T*-free graph, where T* is the tree formed by subdividing the two edges of the claw graph exactly once. On this basis, we improve the upper bound of the edge control numbers of the subcubic graphs, and make some inferences.
| [1] | Yannakakis, M. and Gavril, F. (1980) Edge Dominating Sets in Graphs. SIAM Journal on Applied Mathematics, 38, 364- 372. https://doi.org/10.1137/0138030 |
| [2] | Matsumoto, Y., Kamiyama, N. and Imai, K. (2011) An Approximation Algorithm Dependent on Edge-Coloring Number for Minimum Maximal Matching Problem. Information Processing Letters, 111, 465-468.
https://doi.org/10.1016/j.ipl.2011.02.006 |
| [3] | Cardoso, D.M., Cerdeira, J.O., Delorme, C. and Silva, P.C. (2008) Efficient Edge Domination in Regular Graphs. Discrete Applied Mathematics, 156, 3060-3065. https://doi.org/10.1016/j.dam.2008.01.021 |
| [4] | Orlovich, Y., Finke, G., Gordon, V. and Zverovich, I. (2007) Approximability Results for the Maximum and Minimum Maximal Induced Matching Problems. Discrete Optimization, 5, 584-593. https://doi.org/10.1016/j.disopt.2007.11.010 |
| [5] | Baste, J., Fürst, M., Henning, M.A., Mohr, E. and Rautenbach, D. (2021) Bounding and Approximating Minimum Maximal Matchings in Regular Graphs. Discrete Mathematics, 344, Article ID: 112243.
https://doi.org/10.1016/j.disc.2020.112243 |
| [6] | Song, W.Y., Miao, L.Y., Wang, H.C. and Zhao, Y.C. (2014) Maximal Matching and Edge Domination in Complete Multipartite Graphs. International Journal of Computer Mathematics, 91, No. 5.
https://doi.org/10.1080/00207160.2013.818668 |
