图的2-正交[0,kj]m1-因子分解.pdf

第3 3 卷第1 期中国矿业大学学报 V 0 1 ．3 3N o ．I 2 0 0 4 年1 月J o u r 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 J a n 2 0 0 4 文章编号1 0 0 01 9 6 4 2 0 0 4 O l0 1 2 30 4 图的2 一正交[ o ，岛] 一因子分解 周秀宏，周思中，薛秀谦 中国矿业大学理学院，江苏徐州2 2 1 0 0 8 摘要在E o ，k 1 ⋯ 。m 1 ] 一图的正交[ o ，k j ] 一因子分解问题的基础上，讨论了E o ，k l ⋯ 。一 m 1 ] 图的2 - 正交[ o ， ，] 一因子分解问题，并给出了该问题的一个充分条件． 关键词；图；对集；因子；因子分解；2 一正交因子分解 中图分类号01 5 7 ．5文献标识码A O n2 - O r t h o g o n a lE o ，k j ] 一F a c t o r i z a t i o n so fG r a p h s Z H O UX i u h o n g ，Z H O US i z h o n g ，X U EX i u q i a n C o l l e g eo fS c i e n c e ，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 A b s t r a c t nt h eb a s i so ft h ep r o b l e mo fo r t h o g o n a lE 0 ， J ] 一f a c t o r i z a t i o no fE 0 ，k t ⋯ k m 1 ] 一 g r a p h ，t h ep r o b l e mo f2 - o r t h o g o n a l [ 0 ， ，] 一f a c t o r i z a t i o n o fE 0 ，女i ⋯ 。一m 13 - g r a p hi s d i s c u s s e d ，a n do n es u f f i c i e n tc o n d i t i o no ft h i sp r o b l e mi sg i v e n ． K e yw o r d s g r a p h ；m a t c h i n g ；f a c t o r ；f a c t o r i z a t i o n ；2 - o r t h o g a n a lf a c t o r i z a t i o n 设G 是一个有限无向简单图，V G 和E G 分别是G 的顶点集和边集．对每个z ∈V G ，用 d c z 表示z 在G 中的次数．设g 和，是定义在 v G 上的两个非负整数值函数，且对任意的x ∈ v G ，有g z ≤，o ．图G 的一个 g ，， - 因子是 指G 的一个支撑子图F ，使得g z ≤d ， z ≤f z 对所有的z ∈V G 成立，且称F 是G 的一个 g ，， 一因子．若G 本身是一个 g ，， 一因子，则称G 是一个 g ，， ．图．特别地，Vz ∈y G ，g o 一n ，， h b ，则称G 的 g ，， 一因子为[ 口，6 ] 一因子， g ， ， 一图为k ，6 ] 一图，设岛，k z ，⋯，k 是正整数，若G 的边能划分成m 个边不相交的E o ， 。] 一因子F - ， [ o ，岛] 一因子F 2 。⋯’[ o ，k ] 一因子F ．，则称F 一{ F 。， F 。，⋯，n 是G 的一个E o ， ，] 一因子分解．设日是 G 的一个2 m 一对集，F 一{ F 1 ，F2 I ．．．’F 是G 的一 个[ o ， ，] 一因子分解，如果I E H n E F ， l 一2 对 1 ≤』≤m 均成立，则称F 与H2 一正交，即F 是一个 2 一正交[ o ，岛] 一因子分解．其它未加说明的定义和 术语见文献[ 1 3 ] ． 文献E 4 一a 0 3 研究了[ o ， 。 ⋯ 。一m 1 ] 一图的 正交E o ， ，] 一因子分解，文献[ 1 1 ] 研究了 m g m 一 1 ，m f m 1 一图的2 一正交 g ，， 一因子分解．本文 主要研究了[ o ， 。 ⋯ k m 1 ] 一图的2 一正交[ o ， ，] 一因子分解． 1 基本引理 设s 和丁是图的两个不相交顶点子集，用 E G s ，丁 表示G 中连接s 和7 ’的边集，且记 e G S ，T 一I E c S ，丁 I ．并令， s 一∑， z ， x E s g 丁 一∑g z 和d a S ∑d o x ．特别地， ， o 一d c ⑦ 一0 ． 引理””3 设G 是一个图，g 和，是定义在V G 上的整数值函数，且g ／4 ； b ．若G 眵] 中仅有一条边，且e G - s ，y G ＼ s U T ≥1 ，则 品， S ，丁 ≥d e S 一。Gr 5 ，丁 1 - 3 e c S ，丁 一％- S ，丁 ≥3 ； c ．若上述情形都不满足，且G [ s ] 中仅有一条 边，或e G ， s ，y G ＼ S U 丁 ≥2 ，贝Ⅱ 如， S ，丁 ≥d c S 一0 6 ， S ，丁 ≥ 2 e c S ，丁 一∞一 S ，丁 ≥2 ； d ．若上述3 种情形都不满足，且e G ． s ，y G ＼ s U T ≥1 ，则 如， S ，了1 ≥d c S 一e G ， S ，丁 ≥ 1 幻 S ，丁 一船， S ，丁 ≥1 ； e ．否则，有 如， S ，丁 ≥d G S 一∞， S ，丁 ≥0 ． 综上，对情形2 ，总有如， 5 ，7 1 ≥￡ S ，丁 成 立． 情形3 如果l S l 2 j k ，丁。ld e 7 ’。 d G S I S I 岛S l 十d ∥ 丁 e Gr S ，了1 ≥ 壶1 T 1 Il S 【 l S d Gr S e G 5 ，T d c 一 T - d G Y 1 ≥ 1 I T 。l 一1 S 1 1 s I 一4 j I s l 2 ￡ 5 ，丁 ． 综合以上3 种情形，对V G ’ 的所有不交子集 S 和丁，都有既， S ，T ≥￡ 5 ，了’ 成立．根据引理1 ， G7 有一个 g ，， 一因子凡含e 。和“，也就是说，G 有 一个 导，／ 一因子F 2 含自和⋯但不含e ，和％又 对所有的z ∈v G ，记， z 一矗，则F 2 是G 的一 个[ o ， 。] 一因子． 另一方面，令G G E F ，则对所有 z ∈V G ，有 O ≤矗 z d G z d F 。 z ≤d c z 一g z ≤ d c z d c z - k 1 一 1 ， 所以G 是一个[ o ， 。] 一因子含日和％所以，G 有一 个[ o ， ，] } 因子分解与H2 一正交． 3 现假定m ≥3 ，E H 一{ e 。m ，⋯m 。一一， e 。 ．显然可假定每个岛≥2 1 ≤i ≤m ，否则，不失 一般性，假定k 一1 ，则如 z ≤毛 ⋯ 。一m l 一 毛 ⋯ 五。一l 一 m 一1 1 ．显然，e 2 。一1 和e 2 。是一个 [ o ， 。] 一因子，且含P 2 1 和P 2 埘．G e 2 1 一P m 是一个 [ o ， l ⋯ ．1 一 m 一1 1 ] 一图，H 7 一H 一￡2 。一l e 2 m 是G e 。。一，一‰的2 m 一1 一对集．根据归纳假 设，G e 。一，一e 。有一个[ o ，毛] 一一因子分解与H 7 2 一 正交．所以，G 有一个[ o ，毛] 一因子分解与H 2 一正 交．所以可假定每个 ，≥2 1 ≤j ≤m ． 令G ’ G 一{ e l ，⋯，e 2 。一2 ，H ’一H F 2 椭一1 e 2 。 是一个2 m 1 一对集，且E H ’ 一‰，⋯，e 一。 ， 则对所有的z 告y ∥ ，d 。． z d e s o ，对所有的 z ∈V H7 ，d c 一 z 一d c z 一1 ．对所有z ∈v G ， 定义 g z m a x { 0 ，d a z 一 五1 ⋯ k 一1 一 m ～1 1 ， f ＆ k ， 则对所有的z ∈V G7 V G ，g z 0 ，t ∈T ． 记T ’一丁1 n V ．H ’ ，￡一岛 ⋯ 。一1 一 卅一1 1 ，现考虑下面6 种情形 情形1 如果| S I l T ，{ ，则 阮一 s ，7 1 一五。 1 S I I7 1 1 1 t 五。 l T l I d c 丁1 如， 丁 一8 G ， 5 ，T ≥ k ， S 1 一I T - I T ，I d 6 ， T 一e c ．一 s ，，， ≥ 女。 I S I 一1 T 。I I T l I ≥ 2 I S l I T l f I T ，『≥『S I 1 ≥e s ，丁 ． 情形2 如果I s l I 丁。l ，则 昆r s ，丁 一fT 1 1 五。l s I d c 7 1 d G ， ，， 一P G ， S ，T ￡ 。 I S I 如r T 一d r ； r 1 一e G 一 s ，丁 ≥ 政i S I S l e Gr S ，T d e 一 T 1 一d c 丁1 一 d e S l 丁1l e G ， S ，丁 如r 了1 1 一d G 了1 1 ≥ d c S 一∞t 5 ，T ． a ．若c [ s 3 中至少有两条边，则 如一 S ，丁 ≥d G S 一e G ， S ，T ≥ 4 e c S ，丁 一e c - S ，了’ 1 4 ； b ．若G [ 印中仅有～条边，且％一 s ，y G ＼ s U 丁 ≥1 ，则 ＆- S ，丁 ≥d e S 一∞一 5 ，丁 ≥ 3 e c S ，T 一∞一 S ，丁 ≥3 ； c ．若上述情形都不满足，且G 口] 中仅有一条 边或配一 s ，y G ＼ s U ≥2 ，则 如， S ，丁 ≥d G S 一∞r S ，T ≥ 2 e a S ，丁 一∞- S ，T ≥2 ； d ．若上述3 种情形都不满足，且e G - s ，v G ＼ s U 了 ≥1 ，月9 阮一 S ，T ≥d e S 一∞一 S ，丁 ≥ 1 P G S ，T 一∞， S ，丁 ≥1 ； e ．否则，有 ＆一 S ，T ≥d e S 一∞- S ，丁 ≥O ． 综上，对情形2 ．总有如， S ，T ≥e S ，丁 成 立． 情形3 如果I S l l T ，l ，且I T 。l I S l ≥4 ，则 如， s ，T 一￡I T l l 十k I s l d G 了1 1 d c ， 丁 - - e Gr S ，7 f f 7 、f 一} S f 4 - 0 k f s f d G t 7 1 一 如 T 1 一e G ， S ，丁 ≥ f } 丁。I l S I d G S 1 5 l e Gr S ，丁 如， 了1 一d c T 1 ≥ 、 t I 丁l I I S I l S I d G 一 T 一如 丁； ≥ m 4 l Sl 一4 m 一1 ≥4 ≥E S ，T ． 情形4 如果I s l e S ，丁 ． 情形5 如果I s l I T 、l ，且旧，l I S l 2 ，则 如一 s ，7 ’ f i7 1l k I S I 一如 T ， d o t 丁 m e G ， S ，T 一 2 t 0 是。 I S I c 如一 丁 一c 七 丁1 一e Gr 5 ，丁 ≥ 2 t d a S l S I e G ， S ，T d G ， 1 1 - d c 丁1 一 2 ￡一2 十如 s 4 - l7 1 1 f - - e G ， s ，T 4 - d G 一 了’1 一如 T 1 ≥ 2 m 一1 ≥4 ≥e S ，了1 ． 情形6 如果l s } ／4 ≥￡ S ，丁 ； b ．否则，有 如- S ，T ≥t - 1 ≥m 一1 ≥2 ≥e S ，丁 ． 所以对情形6 总有如一 S ，7 1 ≥e 岱，丁 成立． 综合以上6 种情形可知，对v G 『 的所有不交 子集s 和r 。如，哂，丁 ≥e s ，丁 ．根据引理1 ，G ’有 一个 g ，， 一因子n 含‰一，和‰，也就是说，G 有 一个 g ，， 一因子F 。含‰一。和e 。但不含m ⋯， ‰_ 2 ．又对所有的2 ∈V G 7 ，有， z 五。，所以 ，k 也是一个[ o ， 。] 一因子． 另一方面，令G G E F _ ，则 0 4 d i z d G z d v z ≤d e x 一g z ≤ d e x 一d G z 岛 ⋯ 正。1 一 圻1 1 一 岛 ⋯ 矗，l 一 m 1 1 ． 所以，G 是一个[ o ，岛 ⋯ 。，一 m 一1 1 3 一图，且 日’是否的一个2 m1 一对集，根据归纳假设，石有 一个[ o ， ，] 7 ～一因子分解与H 7 2 一正交．于是，G 有 一个[ o ， ，] 一因子分解与H2 一正交． 证毕． 参考文献 [ 1 ] B o n d yJA ，M u r t yUSR ．G r a p ht 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 ．2 5 42 7 2 ． E 2 ] L i uGz ．A g ，， 一f a c t o r i z a t i o no r t h o g o n a lt oas t a r [ j ] ．C h i n e s eS c i e n c e A ，1 9 9 5 ，2 5 4 3 6 73 7 3 ． [ 3 ] L i uGz ．O ns o m en e wp r o b l e m so ff a c t o r so fg r a p h s [ J ] ．C h i n e s eJO p e r a t i o nR e s e a r c h ，1 9 9 0 ，9 1 1 1 1 6 ． [ 4 ] F e n gHD ，L i uGZ ．O r t h o g o n a l ／a c t o r i z a t i o n so f g r a p h s [ J ] ．JG r a p hT h e o r y ，2 0 0 2 ，4 0 4 2 6 72 7 6 ． [ 5 ] M aRN ，B a iGQ ．O no r t h o g o n a l [ o ，自] r f a c t o r i z a t i o n so fg r a p h s [ J ] ．A e t aM a t h e m a t i c a l S c i e n t i a ，1 9 9 8 ，1 8 4 1 1 4 1 1 8 ． [ 6 3M aRN ．X uJ ．O r t h o g o n a l [ o ， 。] r f a c t o r i z a t i o n so f g r a p h s [ J ] ．J o u r n a lo fE n g i n e e r i n gM a t h e m a t i c s ， 1 9 9 9 ，1 6 4 2 3 2 7 ． [ 7 ] 马润年．与树正交的[ o ． ．] r 一因子分解亡J ] ．西安电子 科技大学学报，1 9 9 6 ，2 3 增刊 。6 6 6 9 ． [ 8 3高安喜，马润年．图的正交因子分解口] ．陕西师范 大学学报 自然科学版 ，1 9 9 9 ，2 7 2 。2 0 2 2 ． [ 9 ] 旺长平．与任意图正交的[ o ， ，] f 因子分解[ J ] ．经 济数学。2 0 0 0 ，1 7 2 5 6 5 9 ． [ 1 0 ] 马润年，许进，高行山．与任意图正变的[ o ，t ，] T ， 因子分解[ J ] ．应用数学和力学．2 0 0 1 ，2 2 5 5 2 5 ， 5 2 8 ． [ 1 1 ] 周思中，薛秀谦．与任意图2 一正交的 g ，， 一因子分 解[ J ] ．华中师范大学学报 自然科学版 ．2 0 0 3 ，3 7 1 1 7 2 0 ． [ 1 2 3 汪长平．图的 g ，， 一因子口] ．数学杂志，1 9 9 8 ，1 8 增 刊 8 3 8 6 ． 责任编辑邓群 万方数据