Some equitably 3-colourable cycle decompositions

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 (i) - n(j) less than or equal to 1 for any i, j is an element of {1, 2,..., k}, then C is 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 C is equitably k-coloured. For m = 4,5 and 6, we completely settle the existence problem for equitably 3-colourable m-cycle decompositions of complete graphs and complete graphs with the edges of a 1-factor removed. (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.

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

Steiner triple systems with two disjoint subsystems

It is shown that there exists a triangle decomposition of the graph obtained from the complete graph of order v by removing the edges of two vertex disjoint complete subgraphs of orders u and w if and only if u, w, and v are odd, ((v)(2)) - ((u)(2)) - ((w)(2)) equivalent to 0 (mod 3), and v >= w + u + max {u, w}. Such decompositions are equivalent to group divisible designs with block size 3, one group of size u, one group of size w, and v - u - w groups of size 1. This result settles the existence problem for Steiner triple systems having two disjoint specified subsystems, thereby generalizing the well-known theorem of Doyen and Wilson on the existence of Steiner triple systems with a single specified subsystem. (c) 2005 Wiley Periodicals, Inc.

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.

A graphical specification of model transformations with triple graph grammars

Models and model transformations are the core concepts of OMG's MDA (TM) approach. Within this approach, most models are derived from the MOF and have a graph-based nature. In contrast, most of the current model transformations are specified textually. To enable a graphical specification of model transformation rules, this paper proposes to use triple graph grammars as declarative specification formalism. These triple graph grammars can be specified within the FUJABA tool and we argue that these rules can be more easily specified and they become more understandable and maintainable. To show the practicability of our approach, we present how to generate Tefkat rules from triple graph grammar rules, which helps to integrate triple graph grammars with a state of a art model transformation tool and shows the expressiveness of the concept.