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. Whe...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.展开更多
The pebbling number of a graph G,f(G),is the least n such that,no matter how n pebbles are placed on the vertices of G,we can move a pebble to any vertex by a sequence of moves,each move taking two pebbles off one ver...The pebbling number of a graph G,f(G),is the least n such that,no matter how n pebbles are placed on the vertices of G,we can move a pebble to any vertex by a sequence of moves,each move taking two pebbles off one vertex and placing one on an adjacent vertex.Graham conjectured that for any connected graphs G and H,f(G×H)≤f(G)f(H).We show that Graham's conjecture holds true of a complete bipartite graph by a graph with the two-pebbling property.As a corollary,Graham's conjecture holds when G and H are complete bipartite graphs.展开更多
Let Km,n be a completebipartite graph with two partite sets having m and n vertices,respectively. A Kp,q-factorization of Km,n is a set ofedge-disjoint Kp,q-factors of Km,n which partition theset of edges of Km,n. Whe...Let Km,n be a completebipartite graph with two partite sets having m and n vertices,respectively. A Kp,q-factorization of Km,n is a set ofedge-disjoint Kp,q-factors of Km,n which partition theset of edges of Km,n. When p=1 and q is a prime number,Wang, in his paper 'On K1,k-factorizations of a completebipartite graph' (Discrete Math, 1994, 126: 359-364),investigated the K1,q-factorization of Km,n and gave asufficient condition for such a factorization to exist. In the paper'K1,k-factorizations of complete bipartite graphs' (DiscreteMath, 2002, 259: 301-306), Du and Wang extended Wang's resultto the case that q is any positive integer. In this paper, we give a sufficient condition for Km,n to have aKp,q-factorization. As a special case, it is shown that theMartin's BAC conjecture is true when p:q=k:(k+1) for any positiveinteger k.展开更多
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. Whe...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.展开更多
一个图H称为一个双星(Doub le Star),当H由2个不交的星K1,m1,K1,m2加上连接它们最大度点的一条边所构成.图G的一个支撑子图F称为一个双星(DS)因子,当F的每一个连通分支是一个双星.本文研究完全偶图Km,n的DS-因子计数,给出了Km,n的DS-因...一个图H称为一个双星(Doub le Star),当H由2个不交的星K1,m1,K1,m2加上连接它们最大度点的一条边所构成.图G的一个支撑子图F称为一个双星(DS)因子,当F的每一个连通分支是一个双星.本文研究完全偶图Km,n的DS-因子计数,给出了Km,n的DS-因子计数公式.展开更多
基金supported by the National Natural Science Foundation of China(Grant No.10571133).
文摘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.
基金This work was supported by the National Natural Science Foundation of China (Grant Nos. 49873002, 10001005).
文摘The pebbling number of a graph G,f(G),is the least n such that,no matter how n pebbles are placed on the vertices of G,we can move a pebble to any vertex by a sequence of moves,each move taking two pebbles off one vertex and placing one on an adjacent vertex.Graham conjectured that for any connected graphs G and H,f(G×H)≤f(G)f(H).We show that Graham's conjecture holds true of a complete bipartite graph by a graph with the two-pebbling property.As a corollary,Graham's conjecture holds when G and H are complete bipartite graphs.
基金This work was supported by the National Natural Science Foundation of China(Grant No.10071056).
文摘Let Km,n be a completebipartite graph with two partite sets having m and n vertices,respectively. A Kp,q-factorization of Km,n is a set ofedge-disjoint Kp,q-factors of Km,n which partition theset of edges of Km,n. When p=1 and q is a prime number,Wang, in his paper 'On K1,k-factorizations of a completebipartite graph' (Discrete Math, 1994, 126: 359-364),investigated the K1,q-factorization of Km,n and gave asufficient condition for such a factorization to exist. In the paper'K1,k-factorizations of complete bipartite graphs' (DiscreteMath, 2002, 259: 301-306), Du and Wang extended Wang's resultto the case that q is any positive integer. In this paper, we give a sufficient condition for Km,n to have aKp,q-factorization. As a special case, it is shown that theMartin's BAC conjecture is true when p:q=k:(k+1) for any positiveinteger k.
基金This work was supported by the National Natural Science Foundation of China(Grant No.10071056).
文摘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.
