广义Mycielskian图的匹配相关性质的研究
The Study of Some Matching-Related Properties of Generalized Mycielskian Graphs
DOI: 10.12677/AAM.2020.910208, PDF,    国家自然科学基金支持
作者: 周 鑫, 边 红*, 杨晓英：新疆师范大学数学科学学院，新疆 乌鲁木齐；于海征：新疆大学数学与系统科学学院，新疆 乌鲁木齐
关键词: 广义Mycielskian图；分数完美匹配；完美2-匹配；Generalized Mycielskian； Fractional Perfect Matching； Perfect 2-Matching
摘要: 为了研究一类不含三角形，但具有任意大色数的图类时，Mycielski介绍了一种图变换μ(G)，称为图G的Mycielskian图。对于任意正整数m，图G的广义Mycielskian图μm(G)是图G的Mycielskian图的一种自然推广。在本文中，我们研究了(广义) Mycielskian图的与匹配相关的一些性质，包括正则性、分数完美匹配的存在性和完美2-匹配的存在性。
Abstract: In order to study triangle-free graphs with arbitrarily large chromatic number, Mycielski introduced a graph transformation that transforms a graph G into a new graph μ(G), which is called the Mycielskian of G. The generalized Mycielskian graph μm(G) is natural generalized of Mycielskian of G, where m is any positive integer. In this paper, we proved some properties of (generalized) Mycielskian of graph G related to matchings, such as regularizability, the existence of fractional perfect matchings and perfect 2-matchings.
文章引用：周鑫, 边红, 于海征, 杨晓英. 广义Mycielskian图的匹配相关性质的研究[J]. 应用数学进展, 2020, 9(10): 1805-1810. https://doi.org/10.12677/AAM.2020.910208

参考文献

[1] Mycieslski, J. (1995) Sur le coloriage des graphes. Colloqutum Mathematicum, 3, 23-29.
[2] Larsen, M., Propp, J. and Ullman, D. (1995) The Fractional Chromatic Number of Mycielski’s Graphs. Journal of Graph Theory, 19, 411-416. [Google Scholar] [CrossRef] 
[3] Fisher, D.C., McKenna, P. and Boyer, E.D. (1998) Hamiltionicity, Diameter, Domination Number, Packing Number, and Biclique Partitions of Mycielski’s Graphs. Discrete Applied Mathematics, 84, 93-105. [Google Scholar] [CrossRef] 
[4] Chang, G.J., Huang, L. and Zhu, X. (1999) Circular Chromatic Numbers of Mycielski’s Graphs. Discrete Mathematics, 205, 23-37. [Google Scholar] [CrossRef] 
[5] Došlić, T. (2005) Mycielskians and Matchings, Discussiones. Discussiones Mathematicae Graph Theory, 25, 261-266. [Google Scholar] [CrossRef] 
[6] Bar Lam, P.C., Lin, W., Gu, G.H. and Song, Z.M. (2003) Circular Chromatic Number and a Generalization of the Construction of Mycielskian. Journal of Combinatorial Theory, Series B, 89, 195-205. [Google Scholar] [CrossRef] 
[7] Lin, W., Wu, J., Bar Lam, P.C. and Gu, G.H. (2006) Several Parameters of Generalized Mycielskians. Discrete Applied Mathematics, 154, 1173-1182. [Google Scholar] [CrossRef] 
[8] Ma, L., Bian, H. and Yu, H. (2020) Hamiltonicity and Factor-Critical of Generalized Mycielskian.
[9] Lovász, L. and Plummer, M.D. (1986) Matching Theory, Annual Discrete Mathematics, North-Holland, Amsterdam

为你推荐