文档介绍：第卷第期经济数学
年月
具有与任意图正交的,一因子分解的子图’
汪长平纪昌明
武汉水利大学应用数学系,
摘要设和分别是定义在图‘的顶点集合上的整数值函数且对每个任‘有提习
越证明了若‘是一个,十,二一一图,毛二,万是中一个给定的有条边的子图,到
有一个子图使得有一个,一因子分解与正交
关键词图,子图,因子,正交因子分解
设是一个有限无向简单图,分别用和‘表示的顶点集和边集,用氏表
示顶点在中的次数,设和分别是定义在上的两个整数值函数且对每个任
有簇,则图的一个支撑子图称为的一个,一因子,如果对每个任
有镇特别地,如果本身是一个,一因子,则称‘是一个,一图
若图的边集能划分成个边不相交的,一因子,,⋯,。,则“,⋯,,。称为图
的一个,一因子分解设和飞,⋯,尸衬分别是图的子图和因子分解,若对所有
镇有门‘二,则称与正交其它未加说明的概念和记号同〔
图的正交因子分解问题是在文献〔」中提出的,其问题之一是给定图的一个子图,
是否存在的一个具有某种性质的因子分解与正交围绕这个问题,不少学者做了许多研
究工作川一困近来文献「〕研究了具有与任意子图正交的,一因子分解的子图的存在性,
并对,一一图,成,在较强的条件下证明了若对每个任有
且时,对于的任意含条边的子图,都有一个子图使得有一个,
因子分解与正交进而提出了如下一般性猜想
猜想设是,一一图,其中对任意任,。毛
是定义在上的整数值函数,蕊镇,是的任意子图且,则存在一
个子图使得有一个,一因子分解与正交·
本文将证明此猜想是正确的
基本引理
设是图的顶点子集,用表示从中去掉顶点集及与关联的所有边所得子图·
设和是的不交子集,用,表示中连接和的边集并记。,二,
设和是定义在上的整数值函数,若是一的一个分支且对每一点
任有二根据。,十艺是奇数或偶数称是一的
二‘
, 获国家自然科学基金、国家教委优秀年轻教师基金资助
收稿日期一一
第期汪长平纪昌明具有与任意图正交的,一因子分解的子图
奇分支或偶分支其他分支称为中分支用,表示一的奇分支数为方便计,令
一万,盯一万和。一艺。并记
之任了’
灸,咙一一一,
引理〕设是一个图,和是定义在上的整数值函数使对每个任有
。成,则对的给定边‘,有一个,一因子含‘当且仅当对的任意不相
交子集和有
灸,。一一妻。,
其中。,定义为若‘“且,任,那么以,若存在一的一个中
分支使得‘任,,则。, 否则,。,
设,是的两个不交子集,,、是的两个不交子集
令二, 任,任,
任,任,,门,门,
门,,三门,,〕,孟孟
并记气,,, 斌艺。
凡,, 玉二艺万

矢,,“气,,凡,,
在不致混淆时,简写叱,,,,风,,和戊,,,为,月和△·
引理圈设是一个图,和是定义在上的两个整数值函数且对每个任
有镇镇。,,和是的不交子集,则有一个,卜因子使得
二且“中当且仅当对的任意不交子集和有
灸,。一一衡,,
以下假设是一个,一一图且对每个〔,镇镇,是整数
且蕊定义
二,。一一一

,心一一一
且记

。,一言‘一,乙“一生。
根据上述定义,运用与文献〔