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 complete multipartite graphs with 4-cycles

In this paper we completely solve the problem of finding a maximum packing of any complete multipartite graph with edge-disjoint 4-cycles, and the minimum leaves are explicitly given.

Decomposition of complete tripartite graphs into gregarious 4-cycles

A 4-cycle in a tripartite graph with vertex partition {V-1, V-2, V-3} is said to be gregarious if it has at least one vertex in each V-i, 1 less than or equal to i less than or equal to 3. In this paper, necessary and sufficient conditions are given for the existence of an edge-disjoint decomposition of any complete tripartite graph into gregarious 4-cycles.

Decomposing complete tripartite graphs into cycles of lengths 3 and 4

Necessary and sufficient conditions are given for the edge-disjoint decomposition of a complete tripartite graph K-r,K-s,K-t into exactly alpha 3-cycles and beta 4-cycles. (C) 1999 Elsevier Science B.V. All rights reserved.

Decompositions of complete multipartite graphs into cycles of even length

Necessary and sufficient conditions for the existence of an edge-disjoint decomposition of any complete multipartite graph into even length cycles are investigated. Necessary conditions are listed and sufficiency is shown for the cases when the cycle length is 4, 6 or 8. Further results concerning sufficiency, provided certain small decompositions exist, are also given for arbitrary even cycle lengths.

A family of perfect factorisations of complete bipartite graphs

A 1-factorisation of a graph is perfect if the union of any two of its 1-factors is a Hamiltonian cycle. Let n = p(2) for an odd prime p. We construct a family of (p-1)/2 non-isomorphic perfect 1-factorisations of K-n,K-n. Equivalently, we construct pan-Hamiltonian Latin squares of order n. A Latin square is pan-Hamiltoilian if the permutation defined by any row relative to any other row is a single Cycle. (C) 2002 Elsevier Science (USA).

Trade spectra of complete partite graphs

The trade spectrum of a graph G is essentially the set of all integers t for which there is a graph H whose edges can be partitioned into t copies of G in two entirely different ways. In this paper we determine the trade spectrum of complete partite graphs, in all but a few cases.

Further decompositions of complete tripartite graphs into 5-cycles

Let K(r,s,t) denote the complete tripartite graph with partite sets of sizes r, s and t, where r less than or equal to s less than or equal to t. Necessary and sufficient conditions are given for decomposability of K(r, s, t) into 5-cycles whenever r, s and t are all even. This extends work done by Mahmoodian and Mirza-khani (Decomposition of complete tripartite graphs into 5-cycles, in: Combinatorics Advances, Kluwer Academic Publishers, Netherlands, 1995, pp. 235-241) and Cavenagh and Billington. (C) 2002 Elsevier Science B.V. All rights reserved.

Decompositions of complete tripartite graphs into triangles with an edge attached

Let K(r, s, t) denote the complete tripartite graph with partite sets of size r, s and t, where r less than or equal to s less than or equal to t. Let D be the graph consisting of a triangle with an edge attached. We show that K(r, s, t) may be decomposed into copies of D if and only if 4 divides rs + st + rt and t less than or equal to 3rs/(r + s).

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.

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.

Star factorizations of graph products

A k-star is the graph K-1,K-k. We prove a general theorem about k-star factorizations of Cayley graphs. This is used to give necessary and sufficient conditions for the existence of k-star factorizations of any power (K-q)(S) of a complete graph with prime power order q, products C-r1 x C-r2 x ... x C-rk of k cycles of arbitrary lengths, and any power (C-r)(S) of a cycle of arbitrary length. (C) 2001 John Wiley & Sons, Inc.

Génération efficace de graphes d’appels dynamiques complets

Analyser le code permet de vérifier ses fonctionnalités, détecter des bogues ou améliorer sa performance. L’analyse du code peut être statique ou dynamique. Des approches combinants les deux analyses sont plus appropriées pour les applications de taille industrielle où l’utilisation individuelle de chaque approche ne peut fournir les résultats souhaités. Les approches combinées appliquent l’analyse dynamique pour déterminer les portions à problèmes dans le code et effectuent par la suite une analyse statique concentrée sur les parties identifiées. Toutefois les outils d’analyse dynamique existants génèrent des données imprécises ou incomplètes, ou aboutissent en un ralentissement inacceptable du temps d’exécution. Lors de ce travail, nous nous intéressons à la génération de graphes d’appels dynamiques complets ainsi que d’autres informations nécessaires à la détection des portions à problèmes dans le code. Pour ceci, nous faisons usage de la technique d’instrumentation dynamique du bytecode Java pour extraire l’information sur les sites d’appels, les sites de création d’objets et construire le graphe d’appel dynamique du programme. Nous démontrons qu’il est possible de profiler dynamiquement une exécution complète d’une application à temps d’exécution non triviale, et d’extraire la totalité de l’information à un coup raisonnable. Des mesures de performance de notre profileur sur trois séries de benchmarks à charges de travail diverses nous ont permis de constater que la moyenne du coût de profilage se situe entre 2.01 et 6.42. Notre outil de génération de graphes dynamiques complets, nommé dyko, constitue également une plateforme extensible pour l’ajout de nouvelles approches d’instrumentation. Nous avons testé une nouvelle technique d’instrumentation des sites de création d’objets qui consiste à adapter les modifications apportées par l’instrumentation au bytecode de chaque méthode. Nous avons aussi testé l’impact de la résolution des sites d’appels sur la performance générale du profileur.