具有(k,r)-正交的(g,f)-因子分解的子图.pdf

第3 3 卷第5 期 2 0 0 4 年9 月 中国矿业大学学报 l o r e n a lo fC h i n aU n i v e r s i t yo fM i n i n g ＆’T e c h n o l o g y V 0 1 ．3 3N o ．5 S e p 。2 0 0 4 文章缔号1 0 0 0 1 9 6 4 2 0 0 4 0 5 0 6 0 7 0 3 具有 k ，厂 一正交的 g ’，厂 一因子分解的子图 于卿枝h 2 ，孙硕1 ，黄昌华2 1 ．中国矿业大学理学院，江苏徐州2 2 1 0 0 8 ；2 ．空军后勤学院三系，江苏徐州2 2 1 0 0 0 摘要研究了图的正交因子分解，通过构造函数户 z 和q ．2 2 ，证明了 m g k ，m 厂一点 一图具有子 图，该图有 g ，厂 一因子分解与尼卜星 愚，， 一正交，从而推广了原晋江教授的关于 r a g m 一1 ，m 厂一 m 1 一图，存在 g ，厂 一因子分解与星 m ，，’ 一正交的结论． 关键词图；因子；因子分解； 尼∥ 一正交 中图分类号O1 5 7 ．5文献标识码A 志，厂’ 一O r t h o g o n a l g ’，厂 - F a c t o r i z a t i o n so fS u b g r a p h Y UQ i n g z h i l “，S U NS h o u l ，H U A N GC h a n g h u a 2 1 S c h o o lo fS c i e n c e s ，C U M T ，X u z h o u ，J i a n g s u2 2 1 0 0 8 ，C h i n a ； 2 ．D e p a r t m e n t3 ，A i rF o r c eL o g i s t i c sC o l l e g e ，X u z h o u ，J i a n g s u2 2 1 0 0 0 ，C h i n a A b s t r a c t T h eo r ’t h o g o n a lf a c t o r ’i z a t i o n so ig r a p h sw e t ‘es t u d i e d ．B yc o n s t r u c t i n gf u n c t i o n sP z a n dg z ，i tw a sp r ’o v e nt h a tt h e r ee x i s t sas u b g r a p ho t m g 志，m 厂一k - g r 。a p h ，a n dt h i ss u b g r a p h h a s g ，／ 一f a c t o r i z a t i o n s 尼，r O r ’t h o g o n a lt oa s t a rw i t hk re d g e s ，w h i c hg e n e r ’a l i z e st h er e s u l t g i v e nb yP r ’o f e s s o rJ i n g j i a n gY u a n ，i ．e ．，t h e r ee x i s t g ，厂 一f a c t o r i z a t i o n s m ，r 一o r ’t h o g o n a tt o s t a ri na r a g m 一1 ，仇，一优 1 , g i ’a p h ． K e yw o r d s g r a p h ；f a c t o r ；i a c t o i i z a t i o n ； k ，， 一O I t h o g o n a l 1 基本概念与引理 本文所考虑的图皆为有限简单图．设G 是一 个图，分别用V G 和E G 表示图G 的顶点集和 边集，用d G z 表示z 在G 中的次数．设g 和厂是 定义在y G 上的非负整数值函数且对任一z ∈V G 有g z ≤／ z ．G 的一个 g ，．厂 一因子是指G 的一个支撑子图F ，使得g ．z ≤玉 2 2 ≤厂 ．z 对所 有的z ∈y G 成立，如果G - - F ，则称G 是一个 _ g ， ／ 一图．图G 的m 星是指G 的有m 条边m 十1 个顶 点的子图，使其中一个顶点的次数为粥而其余顶 点的次数为1 ．若图G 的边集能划分为k 个边不交 的 g ，_ 厂 因子F ，，F 2 ，⋯，R ，则称F { F “ F 2 ，⋯， 凡 是图G 的一个 g ，厂 一因子分解．设H 是图G 的一个有胁条边的子图，若对1 ≤i ≤k 有1E 日 n F ，l n 则称F 与H 是 忌，，r 一正交的 ，当，一1 时 称为正交．其它未加说明的术语和符号同文献 [ 2 ] ． 设S 是图G 的顶点子集，用G S 表示从G 中 去掉S 及与S 关联的所有边得到的G 的子图．对 于S ，丁∈y G ，S N T - - ⑦，令 E G S ，丁 一{ 2 2 , y I z y ∈E G ，z ∈S ，y E T } ， 8 G S ，T 一| E G S ，丁 1 ． 设g 和厂分别是定义在V G 上的非负整数 值函数，如果C 是G 一 S U 丁 的～个分支且对所有 的z ∈y C 有‘厂 z - - g z ，则根据e T ，y C - t - ∑八z 是奇数或偶数，称c 是G 一 sU 丁 的奇 z E ‘。V ‘ C 分支或偶分支，否则称之为G ～ s U 丁 的中分支． 用 G S ，丁 表示G 一 SU T 的奇分支的个数．为 方便记，令 收稿日期2 0 0 3 1 1 1 7 作者简介子卿枝 1 9 7 2 一 ，女，内蒙古赤峰市人，空军后勤学院讲师，中国矿业大学硕士研究生，从事图论与组合优化方面的研究 万方数据 6 0 8中国矿业大学学报第3 3 卷 厂 5 一 g 了1 一 d G s 丁 一 d G q z ‘ ， 涵 5 ，丁；g ，／ d e , 一S 丁 一g ，， 一 h G S ，丁 ．f S ． 当g 厂对任意的z ∈y G 都成立时，眈 S ，7 ’ 0 ，此时 ＆ S ，7 1 ；g ，f d G q T 一g 丁 f S ． 设E ，和E 。是E G 两不交子集， D y G ＼ SU 丁 ， E S { x y E E G k ，．y E S ， E 丁 一{ z , y f f E G k ，y E T ， E 7 ，一E 。f 1 E S ，E ”1 一E ，n E S ，D ， E 72 - - E 2 n E 丁 ，E “ 2 - - E 2 nE T ，D ． 并令 ％ S ，T ；E 1 ，E 2 一2 j E ’1l I E ”1 』， 风 J S ，丁；E l ，E 2 一2 l E 72 I l E ”2 } ． 文献[ 1 ] 证明了一个 m g m I ，m ／一m 1 一 图，当g z ≥卜1 时，存在 g ，／ 一因子分解与任意 m r 一星 m ，， 一正交，本文在此基础上进一步证明了 m g 是，m 厂一k - 图当g ．z ≥，’时存在子图R ，使R 有 g ，／ 一因子分解与任意五卜星 尼，， 一正交． 引理1 ‘3 3设G 是一个图，g 和厂是定义在 y G 上的两个整数值函数，且对每个z ∈V G 有 o ≤g z 一口一口 J 9 ． 情形2 “。∈r 1 19 若m r 斗志一1 一i sl ≥o ，有 潲，T 删P ≥掣十罢 等钒 丁 ≥ 倒型喇盟 幽 m - 2 d c s r ≥ mmm f l m r k - 1 ． 幽 m ～- 2 口一 掣卢 型等酗≥』9 棚- t - p ； mP 十研 尹P 一“ ； 若m r - 是一1 一I S l o ，即m r 忌一1 毪竽 等卢≥ f l m _ m W - L l f l _ f l 娃七露． 情形31 A o ∈D 若m y 是一1 ～I T I ≥o ，且m r 斗尼一1 一I S I ≥o ， 如一z S ≥c e m r l T I 一1 忌， d a - s 丁 ≥p m ，一I S l k ， 跣 s ，T ；P ，g ≥象 r T I l 如一Y s 去 I Sl d G s 7 m 警d G - S 丁 ≥ 口 ，挖，‘ 尼一1 盆 m r m k - 1 m m - 2 _ 5 一mm ”十a 了k - 1 丝二专争i m m - 1 ， ，二≥口 p ；”十j ；- j 一 m r ，口 p ； 若优， 志一1 一I sI o ，即m y 愚一1 旧1 ，且m r 忌一1 尼一1 ，≥p ． 下面完成定理的证明由于G 。 G E F 为 m 一1 g z 志一1 ， m 一1 厂 z 一 尼一1 一 图，H ， H _ E 。为 意一1 卜星，类似于上述讨论知 G 。有 g ，厂 一因子含H 。的，条边，如此下去司证明 G 有k 个 g ，厂 一因子F ，，F 。，⋯，凡分别含有H 的 ，条边，令y R 一矿 G ，E R E yE ，则R 酉 即为所求的子图． 证毕． 参考文献 原晋江．与星 m ∥ 一正交的 g ，厂 一因子分解E J ] ．河 南科学，1 9 9 8 ，1 6 4 3 8 5 3 8 8 ． Y u a n | 『J ． g ，， - F a c t o r i z a t i o n s m ，， 一O I t h o g o n a lt O s t a r - s 口] ．H e n a nS c i e n c e ，1 9 9 8 ，1 6 4 3 8 5 3 8 8 ． B o n d yIA ，M m t yUSR ．G r 。a p h st h e o r yw i t ha p p - l i c a t i o n s [ M ] ．．L o n d o n M a c m i l l a n ，1 9 7 6 ． L o v d s zL ．．S u b g i ’a p h sw i t hp i ’e s c r i b e dv a l e n c i e s [ J ] ． J o i n n a lo fC o m b i n a t o r ’i a lT h e m y ，1 9 7 0 ，8 4 3 9 1 4 1 6 ． 李国君，刘桂真．．与任意图正交的 g ，， 一因子分解 [ ，] ．中国科学 A 辑 ，1 9 9 7 ，2 7 1 0 1 0 8 3 1 0 8 8 ． L iGJ ，L i uG Z ． g ，， 一F a c t o I i z a t i o n sO r t h o g o n a lt O a s u b g r a p hi ng i a p h [ J ] ．S c i e n c ei nC h i n a S e t i e sA ， 1 9 9 7 ，2 7 1 0 1 0 8 3 - 1 0 8 8 ， 责任编辑邓群 一一 ] ] ] 口 心 D l f 万方数据