最小1-因子覆盖集的若干结果(英文)  

Some Results of Minimum Sets of 1-Factors Covering a Graph

作　　者：翟绍辉[1] 郭晓峰[2] 

机构地区：[1]福建省厦门理工学院敦理系,福建厦门361024 [2]福建省厦门大学数学科学学院,福建厦门361005

出　　处：《数学研究》2008年第1期24-30,共7页Journal of Mathematical Study

基　　金：The project supported by NSFC(10331020);the Scientific Research Foundation of Xiamen University of Technology(YKJ07011R)

摘　　要：假设G是一个1-可扩图．G的1-因子覆盖是G的某些1-因子的集合M使得∪M∈M M=F（G）．1-因子数目最小的1．因子覆盖称为excessive factorization．一个excessive factorization中的1．因子数目称为图G的excessive index，记为x：（G）．本文我们基于G的耳朵分解和E（C）的依赖关系给出了X＇e（G）的上界．对任意正整数k≥3，我们构造出一个图G使得A（G）=3而X＇e（G）=k．进而，我们考虑了乘积图的excessive index．Let G be a 1-extendable graph. A l-factor cover of G is a set M of l-factors of G such that ∪M∈M M=f = E（G）. A 1-factor cover of minimum cardiuality is called an excessive factorization. The excessive index of G. denote X＇e（G）, is the size of an excessive factorization of G. In the present paper, we obtain a tight upper hound of Xte（G） based on dependence relation on E（G） and ear decomposition of G. For any positive integer k ≥ 3, we construct a graph G with A（G） = 3 and X＇e（G） = k. In addition, we also conider tile excessive index of the Cartesian product of two graphs.

关 键 词：1-可扩图 1-因子覆盖 EXCESSIVE INDEX 

分 类 号：O157.5[理学—数学]