Decompositions of complete graphs into triangles and Hamilton cycles

For all odd integers n greater than or equal to 1, let G(n) denote the complete graph of order n, and for all even integers n greater than or equal to 2 let G,, denote the complete graph of order n with the edges of a 1-factor removed. It is shown that for all non-negative integers h and t and all positive integers n, G, can be decomposed into h Hamilton cycles and t triangles if and only if nh + 3t is the number of edges in G(n). (C) 2004 Wiley Periodicals, Inc.

Steiner trade spectra of complete partite graphs

The Steiner trade spectrum of a simple graph G is the set of all integers t for which there is a simple graph H whose edges can be partitioned into t copies of G in two entirely different ways. The Steiner trade spectra of complete partite graphs were determined in all but a few cases in a recent paper by Billington and Hoffman (Discrete Math. 250 (2002) 23). In this paper we resolve the remaining cases. (C) 2004 Elsevier B.V. All rights reserved.

Some equitably 3-colourable cycle decompositions of complete equipartite graphs

Let G be a graph in which each vertex has been coloured using one of k colours, say c(1), c(2),.. , c(k). If an m-cycle C in G has n(i) vertices coloured c(i), i = 1, 2,..., k, and vertical bar n(i) - n(j)vertical bar <= 1 for any i, j is an element of {1, 2,..., k}, then C is said to be equitably k-coloured. An m-cycle decomposition C of a graph G is equitably k-colourable if the vertices of G can be coloured so that every m-cycle in W is equitably k-coloured. For m = 3, 4 and 5 we completely settle the existence question for equitably 3-colourable m-cycle decompositions of complete equipartite graphs. (c) 2005 Elsevier B.V. All rights reserved.

Packing lambda-fold complete multipartite graphs with 4-cycles

A maximum packing of any lambda-fold complete multipartite graph (where there are lambda edges between any two vertices in different parts) with edge-disjoint 4- cycles is obtained and the size of each minimum leave is given. Moreover, when lambda =2, maximum 4-cycle packings are found for all possible leaves.

Decomposition of complete graphs into 5-cubes

Necessary conditions for the complete graph on n vertices to have a decomposition into 5-cubes are that 5 divides it - 1 and 80 divides it (it - 1)/2. These are known to be sufficient when n is odd. We prove them also sufficient for it even, thus completing the spectrum problem for the 5-cube and lending further weight to a long-standing conjecture of Kotzig. (c) 2005 Wiley Periodicals, Inc.

Some equitably 2-colourable cycle decompositions of multipartite graphs

Let G be a graph in which each vertex has been coloured using one of k colours, say c(1), c(2),..., c(k). If an m-cycle C in G has x(i) vertices coloured c(i), i = 1, 2,..., k, and vertical bar x(i) - x(j)vertical bar

On Hamilton cycle decomposition of 6-regular circulant graphs

The circulant graph Sn, where S ⊆ Zn \ {0}, has vertex set Zn and edge set {{x, x + s}|x ∈ Zn, s ∈ S}. It is shown that there is a Hamilton cycle decomposition of every 6-regular circulant graph Sn in which S has an element of order n.

Coloring random graphs and maximizing local diversity

We study a variation of the graph coloring problem on random graphs of finite average connectivity. Given the number of colors, we aim to maximize the number of different colors at neighboring vertices (i.e. one edge distance) of any vertex. Two efficient algorithms, belief propagation and Walksat are adapted to carry out this task. We present experimental results based on two types of random graphs for different system sizes and identify the critical value of the connectivity for the algorithms to find a perfect solution. The problem and the suggested algorithms have practical relevance since various applications, such as distributed storage, can be mapped onto this problem.

Resource allocation in sparse graphs

Resource allocation in sparsely connected networks, a representative problem of systems with real variables, is studied using the replica and Bethe approximation methods. An efficient distributed algorithm is devised on the basis of insights gained from the analysis and is examined using numerical simulations,showing excellent performance and full agreement with the theoretical results. The physical properties of the resource allocation model are discussed.

Message passing for task redistribution on sparse graphs

The problem of resource allocation in sparse graphs with real variables is studied using methods of statistical physics. An efficient distributed algorithm is devised on the basis of insight gained from the analysis and is examined using numerical simulations, showing excellent performance and full agreement with the theoretical results.

Solvable model for distribution networks on random graphs

We propose a simple model that captures the salient properties of distribution networks, and study the possible occurrence of blackouts, i.e., sudden failings of large portions of such networks. The model is defined on a random graph of finite connectivity. The nodes of the graph represent hubs of the network, while the edges of the graph represent the links of the distribution network. Both, the nodes and the edges carry dynamical two state variables representing the functioning or dysfunctional state of the node or link in question. We describe a dynamical process in which the breakdown of a link or node is triggered when the level of maintenance it receives falls below a given threshold. This form of dynamics can lead to situations of catastrophic breakdown, if levels of maintenance are themselves dependent on the functioning of the net, once maintenance levels locally fall below a critical threshold due to fluctuations. We formulate conditions under which such systems can be analyzed in terms of thermodynamic equilibrium techniques, and under these conditions derive a phase diagram characterizing the collective behavior of the system, given its model parameters. The phase diagram is confirmed qualitatively and quantitatively by simulations on explicit realizations of the graph, thus confirming the validity of our approach. © 2007 The American Physical Society.