P_3-FACTORIZATION OF COMPLETE MULTIPARTITE GRAPHS

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

Fundamental cycles and graph embeddings

In this paper, we investigate fundamental cycles in a graph G and their relations with graph embeddings. We show that a graph G may be embedded in an orientable surface with genus at least g if and only if for any spanning tree T, there exists a sequence of fundamental cycles C 1,C 2,…,C 2g with C 2i?1 ∩ C 2i ≠ /0 for 1 ? i ? g. In particular, among β(G) fundamental cycles of any spanning tree T of a graph G, there are exactly 2γM (G) cycles C 1, C 2,…,C 2γM(G) such that C 2i?1 ∩ C 2i ≠ /0 for 1 ? i ? γM (G), where β(G) and γM (G) are the Betti number and the maximum genus of G, respectively. This implies that it is possible to construct an orientable embedding with large genus of a graph G from an arbitrary spanning tree T (which may have very large number of odd components in G E(T)). This is different from the earlier work of Xuong and Liu, where spanning trees with small odd components are needed. In fact, this makes a common generalization of Xuong, Liu and Fu et al. Furthermore, we show that (1) this result is useful for locating the maximum genus of a graph having a specific edge-cut. Some known results for embedded graphs are also concluded; (2) the maximum genus problem may be reduced to the maximum matching problem. Based on this result and the algorithm of Micali-Vazirani, we present a new efficient algorithm to determine the maximum genus of a graph in $ O((\beta (G))^{\frac{5} {2}} ) $ steps. Our method is straight and quite different from the algorithm of Furst, Gross and McGeoch which depends on a result of Giles where matroid parity method is needed.

On Enomoto's problems in a bipartite graph

In this paper, we obtain the following result: Let k, n 1 and n 2 be three positive integers, and let G = (V 1,V 2;E) be a bipartite graph with |V1| = n 1 and |V 2| = n 2 such that n 1 ? 2k + 1, n 2 ? 2k + 1 and |n 1 ? n 2| ? 1. If d(x) + d(y) ? 2k + 2 for every x ∈ V 1 and y ∈ V 2 with xy $ \notin $ E(G), then G contains k independent cycles. This result is a response to Enomoto’s problems on independent cycles in a bipartite graph.

The spectrum of path 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 have proposed a conjecture. Very recently, we have proved that the conjecture is true when v = 4k ? 1. In this paper we shall show that the conjecture is true when v = 4k + 1, and then the conjecture is true. That is, we will prove that the necessary and sufficient conditions for the existence of a P 4k+1-factorization of λK m,n are (1) 2km ? (2k + 1)n, (2) 2kn ? (2k + 1)m, (3) m + n ≡ 0 (mod 4k + 1), (4) λ(4k + 1)mn/[4k(m + n)] is an integer.