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(k2-1)) and(4) λ(km-n)(kn-m) ≡ 0(mod k(k -1)(k2 -1)(m n)).     

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））.     

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.     

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.     

P4k?1-factorization of bipartite multigraphs

Let λK _m,n be a bipartite multigraph 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, Ushio, Wang and the second author of the paper gave a necessary and sufficient condition for the existence of a P _v -factorization of λK _m,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 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.     

The proof of Ushio''''s conjecture concerning path 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 existence of Pv-factorization of Km,n. When k is an odd number, Ushio in 1993 proposed a conjecture. Very recently, we have proved that Ushio's conjecture is true when v = 4k-1. In this paper we shall show that Ushio Conjecture is true when v = 4k 1, and then Ushio's conjecture is true. That is, we will prove that a necessary and sufficient condition for the existence of a P4k 1-factorization of Km,n is (i) 2km≤ (2k 1)n, (ii) 2kn≤ (2k 1)m, (iii) m n = 0 (mod 4k 1), (iv) (4k 1)mn/[4k(m n)] is an integer.     

Excessive factorizations of bipartite multigraphs

An excessive factorization of a multigraph G is a set F={F₁,F₂,…,F_r} of 1-factors of G whose union is E(G) and, subject to this condition, r is minimum. The integer r is called the excessive index of G and denoted by . We set if an excessive factorization does not exist. Analogously, let m be a fixed positive integer. An excessive[m]-factorization is a set M={M₁,M₂,…,M_k} of matchings of G, all of size m, whose union is E(G) and, subject to this condition, k is minimum. The integer k is denoted by and called the excessive [m]-index of G. Again, we set if an excessive [m]-factorization does not exist. In this paper we shall prove that, for bipartite multigraphs, both the parameters and are computable in polynomial time, and we shall obtain an efficient algorithm for finding an excessive factorization and excessive [m]-factorization, respectively, of any bipartite multigraph.     

The proof of Ushio’s conjecture concerning path 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 existence of P _v -factorization of K _m,n . When k is an odd number, Ushio in 1993 proposed a conjecture. Very recently, we have proved that Ushio’s conjecture is true when v = 4k − 1. In this paper we shall show that Ushio Conjecture is true when v = 4k − 1, and then Ushio’s conjecture is true. That is, we will prove that a necessary and sufficient condition for the existence of a P _4k+1-factorization of K _m,n is (i) 2km≤(2k+1)n, (ii) 2kn≤(2k+1)m, (iii) m+n≡0 (mod 4k+1), (iv) (4k+1)mn/[4k(m+n)] is an integer.     

The maximum and minimum degrees of random bipartite multigraphs

In this paper the authors generalize the classic random bipartite graph model, and define a model of the random bipartite multigraphs as follows:let m = m（n） be a positive integer-valued function on n and ζ（n,m;{pk}） the probability space consisting of all the labeled bipartite multigraphs with two vertex sets A ={a₁,a₂,...,a_n} and B = {b₁,b₂,...,b_m}, in which the numbers t_ai,b_j of the edges between any two vertices a_i∈A and b_j∈ B are identically distributed independent random variables with distribution P{t_ai,b_j=k}=pk,k=0,1,2,...,where pk ≥0 and ∞Σk=0 pk=1. They obtain that X_c,d,A, the number of vertices in A with degree between c and d of G_n,m∈ζ（n, m;{pk}） has asymptotically Poisson distribution, and answer the following two questions about the space ζ（n,m;{pk}） with {pk} having geometric distribution, binomial distribution and Poisson distribution, respectively. Under which condition for {pk} can there be a function D（n） such that almost every random multigraph G_n,m∈ζ（n,m;{pk}） has maximum degree D（n）in A? under which condition for {pk} has almost every multigraph G（n,m）∈ζ（n,m;{pk}） a unique vertex of maximum degree in A?     

Balanced bipartite graphs may be completely star-factored

We conclude the study of complete K_1,q-factorizations of complete bipartite graphs of the form K_n,n and show that, so long as the obvious Basic Arithmetic Conditions are satisfied, such complete factorizations must exist. © 1997 John Wiley & Sons, Inc. J Combin Designs 5: 407–415, 1997     

One‐factorizations of complete multigraphs and quadrics in PG(n,q)

A new infinite family of simple indecomposable one‐factorizations of the complete multigraphs is constructed by using quadrics of finite projective spaces. © 2002 Wiley Periodicals, Inc. J Combin Designs 10: 139–143, 2002; DOI 10.1002/jcd.997     

Kp,q-factorization of complete bipartite graphs

Let K_(m,n) be a complete bipartite graph with two partite sets having m and nvertices, respectively. A K_(p,q)-factorization of K_(m,n) is a set of edge-disjoint K_(p,q)-factorsof K_(m,n) which partition the set of edges of K_(m,n). When p=i and q is a prime number,Wang, in his paper "On K_(1,k)-factorizations of a complete bipartite graph" (Discrete Math,1994, 126; 359-364), investigated the K_(1,q)-factorization of K_(m,n) and gave a sufficientcondition for such a factorization to exist. In the paper "K_(1,k)-factorizations of completebipartite graphs" (Discrete Math, 2002, 259: 301-306), Du and Wang extended Wang'sresult to the case that q is any positive integer In this paper, we give a sufficient conditionfor K_(m,n) to have a K_(p,q)-factorization. As a special case, it is shown that the Martin's BACconjecture is true when p: q=k: (k+1) for any positive integer k.     

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.     

The degree distribution of the random multigraphs

In this paper, as a generalization of the binomial random graph model, we define the model of multigraphs as follows: let G(n; {p _k }) be the probability space of all the labelled loopless multigraphs with vertex set V = {υ ₁, υ ₂, …, υ _n }, in which the distribution of t_{vi ,vj} t_{v_i ,v_j } , the number of the edges between any two vertices υ _i and υ _j is

The chromatic index of nearly bipartite multigraphs

We determine the chromatic index of any multigraph which contains a vertex whose detetion results in a bipartite multigraph.     

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.     

An extension of bipartite multigraphs

Usual edge colorings have been generalized in various ways; we will consider here essentially good edge colorings as well as equitable edge colorings. It is known that bipartite multigraphs present the property of having an equitable k-coloring for each k ? 2. This implies that they also have a good k-coloring for each k ? 2. In this paper, we characterize a class of multigraphs which may be considered as a generalization of bipartite multigraphs, in the sense that for each k ? 2 they have a good k-coloring. A more restrictive class is derived where all multigraphs have an equitable k-coloring for each k ? 2.     

Decomposition of balanced complete bipartite multigraphs into multistars

In this paper, we obtain a criterion for the decomposition of the λ-fold balanced complete bipartite multigraph λK_n,n into (not necessarily isomorphic) multistars with the same number of edges. We also give a necessary and sufficient condition of decomposing 2K_n,n into isomorphic multistars.     

Characterizations of competition multigraphs

The notion of a competition multigraph was introduced by C. A. Anderson, K. F. Jones, J. R. Lundgren, and T. A. McKee [C. A. Anderson, K. F. Jones, J. R. Lundgren, and T. A. McKee: Competition multigraphs and the multicompetition number, Ars Combinatoria 29B (1990) 185-192] as a generalization of the competition graphs of digraphs.In this note, we give a characterization of competition multigraphs of arbitrary digraphs and a characterization of competition multigraphs of loopless digraphs. Moreover, we characterize multigraphs whose multicompetition numbers are at most m, where m is a given nonnegative integer and give characterizations of competition multihypergraphs.