广义Mycielskian图的匹配相关性质的研究  

The Study of Some Matching-Related Properties of Generalized Mycielskian Graphs

作　　者：周鑫 边红[1] 于海征[2] 杨晓英[1] 

机构地区：[1]新疆师范大学数学科学学院,新疆 乌鲁木齐 [2]新疆大学数学与系统科学学院,新疆 乌鲁木齐

出　　处：《应用数学进展》2020年第10期1805-1810,共6页Advances in Applied Mathematics

摘　　要：为了研究一类不含三角形,但具有任意大色数的图类时,Mycielski介绍了一种图变换μ(G),称为图G的Mycielskian图。对于任意正整数m,图G的广义Mycielskian图μm(G)是图G的Mycielskian图的一种自然推广。在本文中,我们研究了(广义) Mycielskian图的与匹配相关的一些性质,包括正则性、分数完美匹配的存在性和完美2-匹配的存在性。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图 分数完美匹配 完美2-匹配 

分 类 号：O15[理学—数学]