Commuting decompositions of complete graphs

We say that two graphs G and H with the same vertex set commute if their adjacency matrices commute. In this article, we show that for any natural number r, the complete multigraph K is decomposable into commuting perfect matchings if and only if n is a 2‐power. Also, it is shown that the complete graph K_n is decomposable into commuting Hamilton cycles if and only if n is a prime number. © 2006 Wiley Periodicals, Inc. J Combin Designs     

Hamiltonian decompositions of complete graphs

It is well known that K_{2n + 1} can be decomposed into n edge-disjoint Hamilton cycles. A novel method for constructing Hamiltonian decompositions of K_{2n + 1} is given and a procedure for obtaining all Hamiltonian decompositions of of K_{2n + 1} is outlined. This method is applied to find a necessary and sufficient condition for a decomposition of the edge set of K_r (r ≤ 2n) into n classes, each class consisting of disjoint paths to be extendible to a Hamiltonian decomposition of K_{2n + 1} so that each of the classes forms part of a Hamilton cycle.     

Path decompositions of triangle-free graphs

Let G be a graph with n vertices. A path decomposition of G is a set of edge-disjoint paths containing all the edges of G. Let $p(G)$ denote the minimum number of paths needed in a path decomposition of G. Gallai Conjecture asserts that if G is connected, then $p(G)\le ?n/2?$. If G is allowed to be disconnected, then the upper bound $?\frac{3}{4}n?$ for $p(G)$ was obtained by Donald [7], which was improved to $?\frac{2}{3}n?$ independently by Dean and Kouider [6] and Yan [14]. For graphs consisting of vertex-disjoint triangles, $?\frac{2}{3}n?$ is reached and so this bound is tight. If triangles are forbidden in G, then $p(G)\le ?\frac{g+1}{2g}n?$ can be derived from the result of Harding and McGuinness [11], where g denotes the girth of G. In this paper, we also focus on triangle-free graphs and prove that $p(G)\le ?3n/5?$, which improves the above result with $g=4$.     

On decompositions of complete hypergraphs

We study the minimum number of complete r-partite r-uniform hypergraphs needed to partition the edges of the complete r-uniform hypergraph on n vertices and we improve previous results of Alon.     

More on decompositions of edge-colored complete graphs

Let G be a family of graphs whose edges are colored with elements from a set R of r colors. We assume no two vertices of G are joined by more than one edge of color i for any i∈R, for each G∈G. will denote the complete graph with r edges joining any pair of distinct vertices, one of each of the r colors. We describe necessary and asymptotically sufficient conditions on n for the existence of a family D of subgraphs of , each of which is an isomorphic copy of some graph in G, so that each edge of appears in exactly one of the subgraphs in D.     

Closed trail decompositions of complete equipartite graphs

The complete equipartite graph $K_m * {\overline{K_n}}$ has mn vertices partitioned into m parts of size n, with two vertices adjacent if and only if they are in different parts. In this paper, we determine necessary and sufficient conditions for the existence of a decomposition of $K_m * {\overline{K_n}}$ into closed trails of length k. © 2009 Wiley Periodicals, Inc. J Combin Designs 17: 374–403, 2009     

Hamiltonian decompositions of complete regular s-partite graphs

In this paper we give a procedure by which Hamiltonian decompositions of the s-partite graph K_n,n,…,n, where (s − 1)n is even, can be constructed. For 2t⩽s, 1⩽a₁⩽…⩽a_t⩽n, we find conditions which are necessary and sufficient for a decomposition of the edge-set of K_a1a2…,a_t into (s − 1)n/2 classes, each class consisting of disjoint paths, to be extendible to a Hamiltonian decomposition of the complete s-partite graph K_rmn,n,…,n so that each of the classes forms part of a Hamiltonian cycle.     

Resolvable gregarious cycle decompositions of complete equipartite graphs

The complete multipartite graph K_n(m) with n parts of size m is shown to have a decomposition into n-cycles in such a way that each cycle meets each part of K_n(m); that is, each cycle is said to be gregarious. Furthermore, gregarious decompositions are given which are also resolvable.     

Directed graphs,decompositions, and spatial linkages

The decomposition of a linkage into minimal components is a central tool of analysis and synthesis of linkages. In this paper we prove that every pinned d$d$-isostatic (minimally rigid) graph (grounded linkage) has a unique decomposition into minimal strongly connected components (in the sense of directed graphs), or equivalently into minimal pinned isostatic graphs, which we call d$d$-Assur graphs. We also study key properties of motions induced by removing an edge in a d$d$-Assur graph — defining a sharper subclass of strongly d$d$-Assur graphs by the property that all inner vertices go into motion, for each removed edge. The strongly 3-Assur graphs are the central building blocks for kinematic linkages in 3-space and the 3-Assur graphs are components in the analysis of built linkages. The d$d$-Assur graphs share a number of key combinatorial and geometric properties with the 2-Assur graphs, including an associated lower block-triangular decomposition of the pinned rigidity matrix which provides modular information for extending the motion induced by inserting one driver in a bottom Assur linkage to the joints of the entire linkage. We also highlight some problems in combinatorial rigidity in higher dimensions (d≥3$d\ge 3$) which cause the distinction between d$d$-Assur and strongly d$d$-Assur which did not occur in the plane.     

Hamilton cycle decompositions of the tensor products of complete bipartite graphs and complete multipartite graphs

In this paper, it is shown that the tensor product of the complete bipartite graph, K_r,r,r≥2, and the regular complete multipartite graph, , is Hamilton cycle decomposable.     

The decompositions of line graphs,middle graphs and total graphs of complete graphs into forests

We construct decompositions of L(K_n), M(K_n) and T(K_n) into the minimum number of line-disjoint spanning forests by applying the usual criterion for a graph to be eulerian. This gives a realization of the arboricity of each of these three graphs.     

Large sets of Hamilton cycle decompositions of complete bipartite graphs

Let K_2t+1,2t+1−I denote the complete bipartite graph K_2t+1,2t+1 minus a 1-factor. In this paper, we prove that there exist a large set of Hamilton cycle decomposition of K_2t,2t and a large set of Hamilton cycle decomposition of K_2t+1,2t+1−I.     

Cyclic hamiltonian cycle systems of the complete graph minus a 1-factor

In this paper, we prove that cyclic hamiltonian cycle systems of the complete graph minus a 1-factor, K_n-I, exist if and only if and n≠2p^α with p an odd prime and α?1.     

Almost regular edge colorings and regular decompositions of complete graphs

For k = 1 and k = 2, we prove that the obvious necessary numerical conditions for packing t pairwise edge‐disjoint k‐regular subgraphs of specified orders m₁,m₂,… ,m_t in the complete graph of order n are also sufficient. To do so, we present an edge‐coloring technique which also yields new proofs of various known results on graph factorizations. For example, a new construction for Hamilton cycle decompositions of complete graphs is given. © 2008 Wiley Periodicals, Inc. J Combin Designs 16: 499–506, 2008     

Even cycle decompositions of complete graphs minus a 1-factor

Some sufficient conditions are proven for the complete graph of even order with a 1-factor removed to be decomposable into even length cycles. © 1994 John Wiley & Sons, Inc.     

On P-quasigroups and decompositions of complete undirected graphs

In [2], A. Kotzig has introduced the concepts of P-groupoid and P-quasigroup and has shown how these concepts are related to the decomposition of a complete undirected graph into disjoint closed paths. To each closed path of the graph associated with a given P-quasigroup Q there corresponds a cyclic partial transversal in the Latin square L which is defined by the multiplication table of Q. In this paper, it is shown that cyclic transversals are connected with Hamiltonian decompositions of complete undirected graphs having an even number of vertices and a connection between the order of a particular type of P-quasigroup and the length of its cyclic partial transversals is established. An indirect connection with the work of Yap [4] is established via the concept of isotopy.     

Sharp bounds for decompositions of graphs into complete r-partite subgraphs

If G is a graph on n vertices and r ≥ 2, we let m_r(G) denote the minimum number of complete multipartite subgraphs, with r or fewer parts, needed to partition the edge set, E(G). In determining m_r(G), we may assume that no two vertices of G have the same neighbor set. For such reducedgraphs G, we prove that m_r(G) ≥ log₂ (n + r − 1)/r. Furthermore, for each k ≥ 0 and r ≥ 2, there is a unique reduced graph G = G(r, k) with m_r(G) = k for which equality holds. We conclude with a short proof of the known eigenvalue bound m_r(G) ≥ max{n₊ (G, n₋(G)/(r − 1)}, and show that equality holds if G = G(r, k). © 1996 John Wiley & Sons, Inc.