Partizan octal games: Partizan subtraction games

A subtraction gameS=(s ₁, ...,s _k)is a two-player game played with a pile of tokens where each player at his turn removes a number ofm of tokens providedmεS. The player first unable to move loses, his opponent wins. This impartial game becomes partizan if, instead of one setS, two finite setsS _L andS _R are given: Left removes tokens as specified byS _L, right according toS _R. We say thatS _L dominatesS _R if for all sufficiently large piles Left wins both as first and as second player. We exhibit a curious property of dominance and provide two subclasses of games in which a dominance relation prevails. We further prove that all partizan subtraction games areperiodic, and investigatepure periodicity.     

On the maximal order of cyclicity of antisymmetric directed graphs

A directed graph G without loops or multiple edges is said to be antisymmetric if for each pair of distinct vertices of G (say u and v), G contains at most one of the two possible directed edges with end-vertices u and v. In this paper we study edge-sets M of an antisymmetric graph G with the following extremal property: By deleting all edges of M from G we obtain an acyclic graph, but by deleting from G all edges of M except one arbitrary edge, we always obtain a graph containing a cycle. It is proved (in Theorem 1) that if M has the above mentioned property, then the replacing of each edge of M in G by an edge with the opposite direction has the same effect as deletion: the graph obtained is acyclic. Further we study the order of cyclicity of G (= theminimalnumberofedgesinsuchasetM) and the maximal order of cyclicity in an antisymmetric graph with given number n of vertices. It is shown that for n < 10 this number is equal to the maximal number of edge-disjoint circuits in the complete (undirected) graph with n vertices and for n = 10 (and for an infinite set of n's) the first number is greater than the latter.     

The minimum number of components in 4-regular perfect systems of difference sets

The number of components m in regular (m, 5, c)-systems is given in the literature to date by the inequality m ? 4c ? 2 (Bermond et al., “Proceedings, 18th Hungarian Combin. Colloq.”, North-Holland, Amsterdam, 1976). The case m = 4c ? 2 is called extremal. It is proved that (4c ? 2, 5, c)-systems do not exist. An example of a (4c, 5, c)-system with c = 2, is given. Since, in a 4-regular system, m must be even, loc. cit., it is concluded that the lower bound on the number of components is given by m >/ 4c.     

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.     

Decompositions of complete graphs into regular bichromatic factors

The proof of the following theorem is given: A complete graph with n vertices can be decomposed into r regular bichromatic factors if and only if n is even and greater than 4 and there exists a natural number k with the properties that k ≤ r and 2^{k ? 1} < n ≤ 2^k.     

Some results on the Oberwolfach problem

Aequationes mathematicae -     

On a variation of the Oberwolfach problem

We consider the following “spouse-avoiding” variant of the Oberwolfach problem (briefly NOP): “At a gathering there are n couples. Is it possible to arrange a seating for the 2n people present at s round tables T₁,T₂,…,T_s (where T_i can accomodate k_i ? 3 people and Σk_i=2n) for m different meals so that each person has every other person except his spouse for a neighbour exactly once?” We prove several results concerning the existence of solutions to NOP. In particular, we settle the cases when the tables accomodate the same “small” number of people or when there are only two tables one of them accomodating a “small” number of people or when the total number of people is “small”.     

Transformations of edge-colourings of cubic graphs

In this paper we shall study and describe all possible forms of the so-called change-graph which is the subgraph of a cubic graph G containing all the edges (and only the edges) having different colours in two different edge-colourings of G.     

Quasigroups defining Eulerian paths in complete graphs

This paper provides a graph theoretical contribution to the solution of a problem that was so far dealt with purely combinatorial methods: For which values of r does a P-quasigroup exist which defines an Eulerian path in the complete graph K_{2r + 1}? We start with a nearly linear factor F₀ whose edges are all of different “lengths” and obtain a rotative partition of K_{2r + 1} into nearly linear factors. At every vertex V_h, the 2r edges adjacent to V_h are thus partitioned into r transitions. Successive transitions so defined by F₀ are associated to edges of F₀ forming a sequence of the form (?i₀, i₁), (?i₁, i₂), (?i₂, i₃),…. If S is any closed path made up of these successive transitions, then S is described cyclically by a transition sequence of edges of F₀ of the form: I(S) = {(?i₀, i₁), (?i₁, i₂),…, (?i_t?1, i₀)}, used cyclically m times; S is Eulerian if and only if m = 2r + 1 and t = r. In particular, if t = r and G.C.D. (Σ_{j = 1}^ri_j, 2r + 1) = 1, then I(S) describes an Eulerian path. A numerical example is given, which solves the given problem whenever 2r + 10 (mod 7). Incidentally, Kotzig has shown that the problem has no solution when r = 2.