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.     

P 4k−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.     

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

P 3-factorization of complete multipartite graphs

In this paper, it is shown that a necessary and sufficient condition for the existence of aP ₃-factorization ofK _m ⁿ is (i)mn 0(mod 3) and (ii) (m – 1)n 0(mod 4).     

P 3-factorization of complete multipartite graphs

In this note it is shown that a necessary and sufficient condition for the existence of a P3-factorizatlon of complete multipartite graph λK, is (1) m≥3, (2) mn≡0(mod 3) and (3)λ(m-1)n≡0(mod 4).     

A 1-factorization of the line graphs of complete graphs

A 1-factorization is constructed for the line graph of the complete graph K_n when n is congruent to 0 or 1 modulo 4.     

Unbalanced bipartite factorizations of complete bipartite graphs

We construct a new infinite family of factorizations of complete bipartite graphs by factors all of whose components are copies of a (fixed) complete bipartite graph K_p,q. There are simple necessary conditions for such factorizations to exist. The family constructed here demonstrates sufficiency in many new cases. In particular, the conditions are always sufficient when q=p+1.     

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.     

Pagenumber of complete bipartite graphs

Given an ordering of the vertices of a graph around a circle, a page is a collection of edges forming noncrossing chords. A book embedding is a circular permutation of the vertices together with a partition of the edges into pages. The pagenumber t(G) (also called book thickness) is the minimum number of pages in a book embedding of G. We present a general construction showing t(K_m,n) ? ?(m + 2n)/4?, which we conjecture optimal. We prove a result suggesting this is optimal for m ? 2n ? 3. For the most difficult case m = n, we consider vertex permutations that are regular, i.e., place vertices from each partite set into runs of equal size. Book embeddings with such orderings require ?(7n ? 2)/9? pages, which is achievable. The general construction uses fewer pages, but with an irregular ordering.     

Matching graphs of hypercubes and complete bipartite graphs

Kreweras’ conjecture [G. Kreweras, Matchings and hamiltonian cycles on hypercubes, Bull. Inst. Combin. Appl. 16 (1996) 87–91] asserts that every perfect matching of the hypercube Q_d can be extended to a Hamiltonian cycle of Q_d. We [Jiří Fink, Perfect matchings extend to hamilton cycles in hypercubes, J. Combin. Theory Ser. B, 97 (6) (2007) 1074–1076] proved this conjecture but here we present a simplified proof.The matching graph of a graph G has a vertex set of all perfect matchings of G, with two vertices being adjacent whenever the union of the corresponding perfect matchings forms a Hamiltonian cycle of G. We show that the matching graph of a complete bipartite graph is bipartite if and only if n is even or n=1. We prove that is connected for n even and has two components for n odd, n≥3. We also compute distances between perfect matchings in .     

The inducibility of complete bipartite graphs

For any s ≥ 1 and t ≥ (^S₂), we prove that among all graphs with n vertices the graph that contains the maximal number of induced copies of K_{t, t+s} for any fixed s ≥ 1 and t ≥ (^s₂) is K_{(n/2)+α(n/2)-α} for some function α = o(n). We show that this is not valid for t < (^s₂). Analogous results for complete multipartite graphs are also obtained.     

Identity orientation of complete bipartite graphs

An identity orientation of a graph G=(V,E) is an orientation of some of the edges of E such that the resulting partially oriented graph has no automorphism other than the identity. We show that the complete bipartite graph K_s,t, with st, does not have an identity orientation if t3^s-log₃(s-1). We also show that if (r+1)(r+2)2s then K_s,3^s-r does have an identity orientation. These results improve the previous bounds obtained by Harary and Jacobson (Discuss. Math. - Graph Theory 21 (2001) 158). We use these results to determine exactly the values of t for which an identity orientation of K_s,t exists for 2s17.     

Total edge irregularity strength of complete graphs and complete bipartite graphs

A total edge irregular k-labelling ν of a graph G is a labelling of the vertices and edges of G with labels from the set {1,…,k} in such a way that for any two different edges e and f their weights φ(f) and φ(e) are distinct. Here, the weight of an edge g=uv is φ(g)=ν(g)+ν(u)+ν(v), i. e. the sum of the label of g and the labels of vertices u and v. The minimum k for which the graph G has an edge irregular total k-labelling is called the total edge irregularity strength of G.We have determined the exact value of the total edge irregularity strength of complete graphs and complete bipartite graphs.     

Unextendible product bases and 1-factorization of complete graphs

Let f(k₁,…,k_m) be the minimal value of size of all possible unextendible product bases in the tensor product space . We have trivial lower bounds and upper bound k₁?k_m. Alon and Lovász determined all cases such that f(k₁,…,k_m)=n(k₁,…,k_m). In this paper we determine all cases such that f(k₁,…,k_m)=k₁?k_m by presenting a sharper upper bound. We also determine several cases such that f(k₁,…,k_m)=n(k₁,…,k_m)+1 by using a result on 1-factorization of complete graphs.     

Multicolored forests in complete bipartite graphs

If the edges of a graph G are colored using k colors, we consider the color distribution for this coloring a=(a₁,a₂,…,a_k), in which a_i denotes the number of edges of color i for i=1,2,…,k. We find inequalities and majorization conditions on color distributions of the complete bipartite graph K_n,n which guarantee the existence of multicolored subgraphs: in particular, multicolored forests and trees. We end with a conjecture on partitions of K_n,n into multicolored trees.     

Rotation numers for complete bipartite graphs

A rooted graph is a pair (G, x) where G is a simple undirected graph and x ? V(G). If G if rooted at x, then its rotation number h(G, x) is teh minimum number of edges in a graph F, of the same order as G, such that for all v ? V(F) we can find a copy of G in F with the root x at v. Rotation numbers for complete bipartite graphs were itroduced in [4] by Cockayne and Lorimer. Several cases were evaluated by Bollobás and Cockayne in [2], and in this paper we give a full solution.     

On 4-semiregular 1-factorizations of complete graphs and complete bipartite graphs

A 4-semiregular 1-factorization is a 1-factorization in which every pair of distinct 1-factors forms a union of 4-cycles. LetK be the complete graphK _2nor the complete bipartite graphK _{n, n} .We prove that there is a 4-semiregular 1-factorization ofK if and only ifn is a power of 2 andn2, and 4-semiregular 1-factorizations ofK are isomorphic, and then we determine the symmetry groups. They are known for the case of the complete graphK _2n ,however, we prove them in a different method.     

Complete graphs and complete bipartite graphs without rainbow path

Motivated by Ramsey-type questions, we consider edge-colorings of complete graphs and complete bipartite graphs without rainbow path. Given two graphs $G$ and $H$, the $k$-colored Gallai–Ramsey number $g{r}_k(G:H)$ is defined to be the minimum integer $n$ such that $\left(\genfrac{}{}{0ex}{}{n}{2}\right)\ge k$ and for every $N\ge n$, every rainbow $G$-free coloring (using all $k$ colors) of the complete graph $K_N$ contains a monochromatic copy of $H$. In this paper, we first provide some exact values and bounds of $g{r}_k(P_5:K_t)$. Moreover, we define the $k$-colored bipartite Gallai–Ramsey number $bg{r}_k(G:H)$ as the minimum integer $n$ such that $n^2\ge k$ and for every $N\ge n$, every rainbow $G$-free coloring (using all $k$ colors) of the complete bipartite graph $K_{N,N}$ contains a monochromatic copy of $H$. Furthermore, we describe the structures of complete bipartite graph $K_{n,n}$ with no rainbow $P_4$ and $P_5$, respectively. Finally, we find the exact values of $bg{r}_k(P_4:K_{s,t})$ ($1\le s\le t$), $bg{r}_k(P_4:F)$ (where $F$ is a subgraph of $K_{s,t}$), $bg{r}_k(P_5:K_{1,t})$ and $bg{r}_k(P_5:K_{2,t})$ by using the structural results.