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.     

Decompositions of complete graphs and complete bipartite graphs into isomorphic supersubdivision graphs

A graph H is called a supersubdivison of a graph G if H is obtained from G by replacing every edge uv of G by a complete bipartite graph K_2,m (m may vary for each edge) by identifying u and v with the two vertices in K_2,m that form one of the two partite sets. We denote the set of all such supersubdivision graphs by SS(G). Then, we prove the following results.

1. Each non-trivial connected graph G and each supersubdivision graph HSS(G) admits an α-valuation. Consequently, due to the results of Rosa (in: Theory of Graphs, International Symposium, Rome, July 1966, Gordon and Breach, New York, Dunod, Paris, 1967, p. 349) and El-Zanati and Vanden Eynden (J. Combin. Designs 4 (1996) 51), it follows that complete graphs K_2cq+1 and complete bipartite graphs K_mq,nq can be decomposed into edge disjoined copies of HSS(G), for all positive integers m,n and c, where q=|E(H)|.

2. Each connected graph G and each supersubdivision graph in SS(G) is strongly n-elegant, where n=|V(G)| and felicitous.

3. Each supersubdivision graph in EASS(G), the set of all even arbitrary supersubdivision graphs of any graph G, is cordial.

Further, we discuss a related open problem.     

完全对称有向图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 the number of triangular embeddings of complete graphs and complete tripartite graphs

We prove that for every prime number p and odd m>1, as s→∞, there are at least w face 2‐colorable triangular embeddings of K_{w, w, w}, where w = m·p^s. For both orientable and nonorientable embeddings, this result implies that for infinitely many infinite families of z, there is a constant c>0 for which there are at least z nonisomorphic face 2‐colorable triangular embeddings of K_z. © 2011 Wiley Periodicals, Inc. J Graph Theory     

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

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.