二部多重图路因子分解的存在谱

若二部多重图λK_m,n的边集可以划分为λK_m,n 的P_v-因子,则称 λK_m,n存在P_v-因子分解.当v是偶数时, Ushio和Wang及本文的第二作者给出了λK_m,n存在P_v-因子分解的充分必要条件.同时提出了当v是奇数时λK_m,n存在P_v-因子分解的猜想.最近我们已经证明当v=4k-1时该猜想成立. 对于正整数k,文中证明λK_m,n 存在P_4k+1-因子分解的充分必要条件是: (1) 2km ≤ (2k+1)n, (2) 2kn ≤(2k+1)m, (3) m+n ≡ 0 (mod 4k+1), (4)λ (4k+1)mn/[4k(m+n)]是整数. 即证明:对于任意正整数k, 当v=4k+1时上述猜想成立，从而最终完成了该猜想成立的证明.     

二部多重图的P4k-1-因子分解

如果二部多重图λK_m,n的边集可以划分为λK_m,n 的P_v-因子, 则称 λK_m,n存在P_v-因子分解. 当v是偶数时,Ushio, Wang和本文的第2作者给出了λK_m,n存在P_v-因子分解的充分必要条件. 同时提出了当v是奇数时λK_m,n存在P_v-因子分解的猜想, 但是至今为止仅知当v=3时该猜想成立. 对于正整数k,本文证明λK_m,n存在P_4k-1-因子分解的充分必要条件是：(1)(2k-1)m ≤2kn, (2) (2k-1)n≤2km, (3) m+n ≡0(mod 4k-1), (4) λ(4k-1)mn/[2(2k-1)(m+n)]是整数, 即证明:对于任何正整数k, 当v=4k-1时上述猜想成立.     

完全二部图存在路因子分解的Ushio猜想的证明

如果完全二部图K_m,n的边集可以划分为K_m,n的P_v-因子, 则称K_m,n存在P_v-因子分解. 当v是偶数时, Ushio 和 Wang 给出了K_m,n存在P_v因子分解的充分必要条件. Ushio在其综述文章中提出了当v是奇数时K_m,n存在P_v-因子分解的猜想. 已经证明当v=4k-1时Ushio猜想成立. 对于正整数k, 本文证明K_m,n存在P_4k+1-因子分解的充分必要条件是: (1) 2km ≤ (2k+1)n, (2) 2kn ≤ (2k+1)m, (3) m+n ≡0 (mod 4k+1), (4) (4k+1)mn/[4k(m+n)]是整数. 即证明: 对于任何正整数k, 当v=4k+1时Ushio猜想成立，从而最终完成了Ushio猜想成立的证明.     

完全二部图的P4k-1-因子分解

如果完全二部图K_m,n的边集可以划分为K_m,n的P_v-因子,则称K_m,n存在P_v-因子分解. 当v是偶数时, Ushio和Wang 给出了K_m,n存在P_v-因子分解的充分必要条件. Ushio同时提出了当v是奇数时K_m,n存在P_v-因子分解的猜想, 但是至今为止仅知当v=3时Ushio猜想成立. 对于正整数k,本文证明K_m,n存在P_4k−1-因子分解的充分必要条件是: (1) (2k−1)m ≤2kn, (2) (2k−1)n ≤ 2 km, (3) m+n ≡ 0 (mod 4k−1), (4) (4k−1)mn/[2(2k−1)(m+n)]是整数. 即证明了对于任意正整数k, 当v=4k−1时Ushio猜想成立.     

K2,3的多重多部图设计的构造

λKn(t)是一个λ重完全多部图,G为一个不带孤立点的简单图.所谓的图设计G-HDλ(tn)是一个序偶(X,B),其中X是Kn(t)的顶点集,B为λKn(t)的一些子图(亦称为区组)构成的集合,使得任一区组均与图G同构,且λKn(t)的任意2个不同点组成的边恰在B的λ个区组中出现.本文讨论了G=K2,3的完全多部图设计存在性问题,证明了存在G-HDλ(tn)当且仅当λn(n-1)t2≡0(mod12),n≥2,nt≥5且(n,,λt)≠(9,1,1),(12,1,1),(3,1,2),(4,1,2).     

关于二部图Km1m2-Hm2的升分解

在文献[2]中作者定义了图的一种新分解-升分解(Ascending subgraph Decomposition简记为ASD)，并提出了一个猜想：任意有正数条边的图都可以升分解．本文主要证明了二部图Km1m2-Hm2(m1≥m2)可以升分解，其中Hm2是至多含m2条边的Km1m2的子图．     

完全二部图的Kp,p-分解大集的存在谱北大核心CSCD

令H,G是两个简单图,G是H的一个子图.H的G-分解,记为（λH,G）-GD,是指将图λH的所有边分拆为若干个与G同构的子图（称为G-区组）.H的G-分解的大集,记为（λH,G）-LGD,是指图H的所有与G同构的子图的一个分拆Β1,Β2,…,Βm,使得每个Bj（1≤j≤m）为一个（λH,G）-GD （称为小集）.本文中,我们对完全二部图的K（p,p）-分解的大集进行了研究,利用Kv的λ重Kκ-因子大集的存在性结果,采用直接构造的方法,得到了大集（λK（m,n）,K（p,p））-LGD的存在谱,其中p为任意素数.     

二部图上完美匹配的正交匹配分解

给定简单二部图G=（V,E）,最大度是k（k≥3）,G有一个完美匹配M={e1,e2,…,ek}。称边集E的划分{E1,E2,…,El}是G的一个关于肼的正交匹配分解,如果对每一个El是G的匹配并且包含且仅包含肼中的一条边。在本文中我们将证明对于简单二部图G,存在关于完美匹配肼的正交匹配分解,并给出了求这个分解的多项式时间算法。     

图的(g,f)-因子分解

设Ｇ是一个图，ｇ（ｘ）和ｆ（ｘ）是定义在图Ｇ的顶点集上的两个整数值函数且ｇ≤ｆ．图Ｇ的一个（ｇ，ｆ）－因子是Ｇ的一个支撑子图Ｆ使对任意的ｘ∈Ｖ（Ｆ），有ｇ（ｘ）≤ｄＦ（ｘ）≤ｆ（ｘ）．如果图Ｇ的边集能划分为若干个边不相交的（ｇ，ｆ）－因子，则说图Ｇ是（ｇ，ｆ）－可因子化的．本文研究了图的（ｇ，ｆ）－可因子化的问题，给出了一个图Ｇ是（ｇ，ｆ）－可因子化的若干充分条件．     

完全多部图同构于二面体群的Cayley齐次分解

设Γ=K_(s[t])是一个完全多部图,其中st是一个偶数,则存在一个二面体群R=D_(2n)(n=st/2),使得R能构造出一个同构于K_(s[t])的Cayley图.讨论了当s、t满足什么条件时,完全多部图Γ有同构于Cay(R,S)的齐次分解.     

P_(4k-1)-factorization of bipartite multigraphs

LetλKm,n be a bipartite multigraph with two partite sets having m and n vertices, respectively. A Pν-factorization ofλKm,n is a set of edge-disjoint Pν-factors ofλKm,n which partition the set of edges ofλKm,n. Whenνis an even number, Ushio, Wang and the second author of the paper gave a necessary and sufficient condition for the existence of a Pν-factorization ofλKm,n. When v is an odd number, we proposed a conjecture. However, up to now we only know that the conjecture is true forν= 3. In this paper we will show that the conjecture is true whenν= 4k-1. That is, we shall prove that a necessary and sufficient condition for the existence of a P4k-1-factorization ofλKm,n is (1) (2k-1)m≤2kn, (2) (2k-1)n≤2km, (3)m n = 0 (mod 4k-1), (4)λ(4k-1)mn/[2(2k-1)(m n)] is an integer.     

P_(4k-1)-factorization of complete bipartite graphs

Let Km,n be a complete bipartite graph with two partite sets having m and n vertices, respectively. A Pv-factorization of Km,n is a set of edge-disjoint pv-factors of Km,n which partition the set of edges of Km,n. When v is an even number, Wang and Ushio gave a necessary and sufficient condition for the existence of Pv-factorization of Km,n.When v is an odd number, Ushio in 1993 proposed a conjecture. However, up to now we only know that Ushio Conjecture is true for v = 3. In this paper we will show that Ushio Conjecture is true when v = 4k - 1. That is, we shall prove that a necessary and sufficient condition for the existence of a P4k-1-factorization of Km,n is (1) (2k - 1)m ≤ 2kn, (2) (2k -1)n≤2km, (3) m n ≡ 0 (mod 4k - 1), (4) (4k -1)mn/[2(2k -1)(m n)] is an integer.     

P4κ-1-factorization of bipartite multigraphs

LetλKm,n be a bipartite multigraph with two partite sets having m and n vertices, respectively. A Pv-factorization of λKm,n is a set of edge-disjoint Pv-factors of λKm,n which partition the set of edges of λKm,n. When v is an even number, Ushio, Wang and the second author of the paper gave a necessary and sufficient condition for the existence of a Pv-factorization of λKm,n. When v is an odd number, we proposed a conjecture. However, up to now we only know that the conjecture is true for v= 3. In this paper we will show that the conjecture is true when v= 4k- 1. That is, we shall prove that a necessary and sufficient condition for the existence of a P4k-1-factorization of λKm,n is (1) (2κ - 1)m ≤ 2kn, (2) (2k - 1)n ≤ 2km, (3) m + n ≡0 (mod 4κ - 1), (4) λ(4κ - 1)mn/[2(2κ - 1)(m + n)] is an integer.     

On K 1,k -factorization of bipartite multigraphs

A K1,k-factorization of λKm,n is a set of edge-disjoint K1,k-factors of λKm,n, which partition the set of edges of λKm,n. In this paper, it is proved that a sufficient condition for the existence of K1,k-factorization of λKm,n, whenever k is any positive integer, is that （1） m ≤ kn, （2） n ≤ km, （3） km-n = kn-m ≡ 0 （mod （k^2- 1）） and （4） λ（km-n）（kn-m） ≡ 0 （mod k（k- 1）（k^2 - 1）（m ＋ n））.     

Unbalanced Star-Factorizations of Complete Bipartite Graphs II

There are simple arithmetic conditions necessary for the complete bipartite graph K_m,n to have a complete factorization by subgraphs which are made up of disjoint copies of K_p,q. It is conjectured that these conditions are also sufficient. In any factor the copies of K_p,q have two orientations depending which side of the bipartition the p-set lies. The balance ratio is the relative proportion, x:y of these where gcd(x,y)=1. In this paper, we continue the study of the unbalanced case (y > x) where p = 1, to show that the conjecture is true whenever y is sufficiently large. We also prove the conjecture for K_1,4-factorizations.     

Decomposition of Complete Graphs into Isomorphic Complete Bipartite Graphs

A decomposition of a complete graph into disjoint copies of a complete bipartite graph is called a ‐design of order n. The existence problem of ‐designs has been completely solved for the graphs for , for , K_{2, 3} and K_{3, 3}. In this paper, I prove that for all , if there exists a ‐design of order N, then there exists a ‐design of order n for all (mod ) and . Giving necessary direct constructions, I provide an almost complete solution for the existence problem for complete bipartite graphs with fewer than 18 edges, leaving five orders in total unsolved.     

P<Subscript>4k-1</Subscript>-factorization of complete bipartite graphs

Let K_m,n be a complete bipartite graph with two partite sets having m and n vertices, respectively. A P_v-factorization of K_m,n is a set of edge-disjoint P_v-factors of K_m,n which partition the set of edges of K_m,n. When v is an even number, Wang and Ushio gave a necessary and sufficient condition for the existence of P_v-factorization of K_m,n. When v is an odd number, Ushio in 1993 proposed a conjecture. However, up to now we only know that Ushio Conjecture is true for v = 3. In this paper we will show that Ushio Conjecture is true when v = 4k - 1. That is, we shall prove that a necessary and sufficient condition for the existence of a P_4k-1-factorization of K_m,n is (1) (2k - 1)m ⩽ 2kn, (2) (2k - 1)n ⩽ 2km, (3) m + n ≡ 0 (mod 4k - 1), (4) (4k - 1)mn/[2(2k - 1)(m + n)] is an integer.     

完全偶图的[1,2]因子计数

讨论了完全偶图存在[1,2]因子的充分必要条件，并给出了[1,2]因子的计数法。     

Signed Roman (Total) Domination Numbers of Complete Bipartite Graphs and Wheels

A signed(res. signed total) Roman dominating function, SRDF(res.STRDF) for short, of a graph G =(V, E) is a function f : V → {-1, 1, 2} satisfying the conditions that(i)∑v∈N[v]f(v) ≥ 1(res.∑v∈N(v)f(v) ≥ 1) for any v ∈ V, where N [v] is the closed neighborhood and N(v) is the neighborhood of v, and(ii) every vertex v for which f(v) =-1 is adjacent to a vertex u for which f(u) = 2. The weight of a SRDF(res. STRDF) is the sum of its function values over all vertices.The signed(res. signed total) Roman domination number of G is the minimum weight among all signed(res. signed total) Roman dominating functions of G. In this paper,we compute the exact values of the signed(res. signed total) Roman domination numbers of complete bipartite graphs and wheels.     

二分(0,mf-m+1)-图的正交(0,f)-因子分解

设G=(X,Y,E(G))是一个二分图,分别用V(G)=XUY和E(G)表示G的顶点集和边集.设f是定义在V(G)上的整数值函数且对(A)x∈V(G)有f(x)≥k.设H_1,H_2,…,H_k是G的k个顶点不相交的子图,且|E(H_i)|=m,1≤i≤k.本文证明了每个二分(0,mf-m+1)-图G有一个(0,f)-因子分解正交于Hi(i=1,2,…,k).