On the minimum number of edge-disjoint complete m-partite subgraphs into which Kn can be decomposed

Let α_m(n) denote the minimum number of edge-disjoint complete m-partite subgraphs into which K_n can be decomposed. In [2] the author proved that when m ≥ 3, if (i) n ≡ m and n ≡ m (mod m ?1), or (ii) b ∈ [2, m ?1], n ≥ b(m ?1) + m ? (b ?1), and n ≡ b(m ?1) + m ? (b ?1) (mod m? 1), then α_m(n) = ?(n + m ?3)/(m ?1)? (= ?(n ?1)/(m ?1)?), and that for every integer n, if K_n has an edge-disjoint complete m-partite subgraph decomposition, then α_m(n) ≥ ?(n? 1)/(m? 1)?. In this paper we generally discuss the question as to which integers n's satisfy (or do not) α_m(n) = ?(n ?1)/(m ?1)?. Here we also study the methods to find these integers; the methods are themselves interesting. Our main results are Theorem 2.11, 2.12, and 2.16. Besides, Theorem 2.4 and 2.6 are interesting results too. © 1993 John Wiley & Sons, Inc.     

On the decomposition of kn into complete bipartite graphs

A short proof is given of the impossibility of decomposing the complete graph on n vertices into n-2 or fewer complete bipartite graphs.     

Isomorphic decomposition of complete graphs into linear forests

The well-known theorem of Kirkman states that every complete graph K_2n of order 2n is 1-factorable or, equivalently, is nK₂-decomposable. This result is generalized to any linear forest of size n without isolated vertices.     

完全对称有向图Dn的偶长圈分解

证明了将奇数阶完全对称有向图Dn分拆为偶长有向圈的必要条件也是充分的。     

On decomposition of r-partite graphs into edge-disjoint hamilton circuits

Let K(n;r) denote the complete r-partite graph K(n, n,…, n). It is shown here that for all even n(r ? 1) ? 2, K(n;r) is the union of $\text{n(r ? 1)}\text{2}$ of its Hamilton circuits which are mutually edge-disjoint, and for all odd n(r ? 1) ? 1, K(n;r) is the union of $\text{(n(r ? 1) ? 1)}\text{2}$ of its Hamilton circuits and a 1-factor, all of which are mutually edge-disjoint.     

Partitioning graphs into complete and empty graphs

Given integers j and k and a graph G, we consider partitions of the vertex set of G into j+k parts where j of these parts induce empty graphs and the remaining k induce cliques. If such a partition exists, we say G is a (j,k)-graph. For a fixed j and k we consider the maximum order n where every graph of order n is a (j,k)-graph. The split-chromatic number of G is the minimum j where G is a (j,j)-graph. Further, the cochromatic number is the minimum j+k where G is a (j,k)-graph. We examine some relations between cochromatic, split-chromatic and chromatic numbers. We also consider some computational questions related to chordal graphs and cographs.     

On cyclic decompositions of the complete graph into the 2-regular graphs

The symbol C(m₁ ⁿ ₁m₂ ⁿ ₂...m_s ⁿ _s) denotes a 2-regular graph consisting ofn _i cycles of lengthm _i , i=1, 2,…,s. In this paper, we give some construction methods of cyclic(K _v ,G)-designs, and prove that there exists a cyclic(K _v , G)-design whenG=C((4m ₁) ⁿ ₁(4m ₂) ⁿ ₂...(4m _s ) ⁿ _s andv ≡ 1 (mod 2¦G¦).     

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.     

On the Ramsey multiplicity of complete graphs

We show that, for n large, there must exist at least $$\frac{{n^t }} {{C^{(1 + o(1)t^2 } )}}$$ monochromatic K _t s in any two-colouring of the edges of K _n , where C??2.18 is an explicitly defined constant. The old lower bound, due to Erd?s [2], and based upon the standard bounds for Ramsey??s theorem, is $$\frac{{n^t }} {{4^{(1 + o(1)t^2 } )}}. $$      

Decomposition of complete multigraphs into crown graphs

Let λ K _v be the complete multigraph, G a finite simple graph. A G-design of λ K _v is denoted by GD(v,G,λ). The crown graph Q _n is obtained by joining single pendant edge to each vertex of an n-cycle. We give new constructions for Q _n -designs. Let v and λ be two positive integers. For n=4, 6, 8 and λ≥1, there exists a GD(v,Q _n ,λ) if and only if either (1) v>2n and λ v(v?1)≡0 (mod 4n), or (2) v=2n and λ≡0 (mod 4). Let n≥4 be even. Then (1) there exists a GD(2n,Q _n ,λ) if and only if λ≡0 (mod 4). (2) There exists a GD(2n+1,Q _n ,λ) when λ≡0 (mod 4).     

Decompositions of complete graphs into isomorphic cubes

It is shown that, for any positive integer d, the d-dimensional cube W_d has an α-valuation. This implies that any complete graph K_2cn+1 (where n = d2^d-1 is the number of edges of W_d and c is an arbitrary positive integer) can be decomposed into edge disjoint copies of W_d.     

An asymptotic solution to the cycle decomposition problem for complete graphs

Let m₁,m₂,…,mt be a list of integers. It is shown that there exists an integer N such that for all n?N, the complete graph of order n can be decomposed into edge-disjoint cycles of lengths m₁,m₂,…,mt if and only if n is odd, 3?mi?n for i=1,2,…,t, and . In 1981, Alspach conjectured that this result holds for all n, and that a corresponding result also holds for decompositions of complete graphs of even order into cycles and a perfect matching.     

On resolvable tree-decompositions of complete graphs

A partition of the edge set of a graph H into subsets inducing graphs H₁,…,H_s isomorphic to a graph G is said to be a G-decomposition of H. A G-decomposition of H is resolvable if the set {H₁,…,H_s} can be partitioned into subsets, called resolution classes, such that each vertex of H occurs precisely once in each resolution class. We prove that for every graceful tree T of odd order the obvious necessary conditions for the existence of a resolvable T-decomposition of a complete graph are asymptotically sufficient. This generalizes the results of Horton and Huang concerning paths and stars.     

On the seidel integral complete multipartite graphs

For a simple undirected graph G, denote by A(G) the (0,1)-adjacency matrix of G. Let thematrix S(G) = J-I-2A(G) be its Seidel matrix, and let S _G (??) = det(??I-S(G)) be its Seidel characteristic polynomial, where I is an identity matrix and J is a square matrix all of whose entries are equal to 1. If all eigenvalues of S _G (??) are integral, then the graph G is called S-integral. In this paper, our main goal is to investigate the eigenvalues of S _G (??) for the complete multipartite graphs G = $G = K_{n_1 ,n_2 ,...n_t } $ . A necessary and sufficient condition for the complete tripartite graphs K _m,n,t and the complete multipartite graphs to be S-integral is given, respectively.     

Partitioning edge-coloured complete graphs into monochromatic cycles

A conjecture of Erdös, Gyárfás, and Pyber says that in any edge-colouring of a complete graph with r colours, it is possible to cover all the vertices with r vertex-disjoint monochromatic cycles. So far, this conjecture has been proven only for $r=2$. In this note we show that in fact this conjecture is false for all $r⩾3$. We also discuss some weakenings of this conjecture which may still be true.     

On the flow numbers of signed complete and complete bipartite graphs

We determine the flow numbers of signed complete and signed complete bipartite graphs.