ABSTRACT

In this paper we determine the spectrum for octagon quadrangle systems [OQS] which can be partitioned into two strongly balanced 4-kitedesigns.

1. Introduction

Let be a graph defined on the vertex set X. Let G be a subgraph of K. A G-decomposition of K is a pair, where is a partition of the edge set of K into subsets isomorphic to G. If is the complete undirected graph defined on the vertex set X, a G-decomposition of is called a G-design of order v and the classes of the partition are said to be the blocks of. A G-design is called balanced if for each vertex, the number of blocks of containing x is a constant. Observe that if G is a regular graph then a G-design is always balanced, hence the notion of a balanced G-design becomes meaningful only for a non-regular graph G.

Let G be a graph and let be the orbits of the automorphism group of G on its vertex-set. Let be a G-design. We define the degree of a vertex as the number of blocks of containing x as an element of A_i. We say that is a strongly balanced G-design if, for every, there exists a constant C_i such that, for every [1-3]. Clearly, since for each vertex the relation holds, we have that “a strongly balanced G-design is always a balanced G-design”. We say that a G-design is simply balanced if it is balanced, but not strongly balanced.

A cycle of length 4 with a pendant edge, i.e. the graph, is called a 4-kite and is denoted by or, where, , , , are the edges of the 4-kite. Note that a cycle of length 3 with a pendant edge is called a 3-kite or just a kite. In the case when G is a 4-kite, a G-design is called a 4-kite-design or also a 4-kite-system. It is known that a 4-kite design of order v exists when or. Further research on 4-kite designs can be found in [2]. We will call the vertices a and c of the 4-kite the lateral vertices, b the middle vertex, d the center vertex and e the terminal vertex [4-6]. Some balanced Gdesigns, when G is a path, have been studied in [1,3]. Strongly balanced G-designs were first introduced in [1], in which the spectrum of simply balanced and strongly balanced and -designs have been determined, where denotes a path with k vertices.

An octagon quadrangle is a graph denoted by and formed by an 8- cycle with the two additional edges and. An octagon quadrangle system [OQS] is a G-design, where G is an octagon quadrangle. s have been defined and studied in [4,7-9]. In these papers, the main idea was to follow the research about hexagon triangle systems and all the others already introduced in the literature, where we can find many authors who have studied in many ways polygon triangle systems using triangulations of polygons [5,10,11]. With the study of octagon quadrangles the authors have considered quadrangulations of polygons with new ideas for the research [12,13].

In what follows, if is an in which the family of all contained in the blocks of forms a 4-kite design, we will say that is nesting or also that is nested in. Similar problems, including colorings, can be found also in [14,15].

In this paper, starting from the remark that an octagon quadrangle, can be partitioned into two 4-kites

the authors study OQSs which can be partitioned into two strongly balanced -designs, determining their spectrum.

2. Necessary Existence Conditions

If is strongly balanced 4-kite design, its vertices describe four orbits in the automorphism group of a block, which is a graph. We will indicate by C the number of blocks containing any vertex as a center of the 4-kite block, by T the number of blocks containing any vertex as a terminal, by L and M the number of blocks containing any vertex as lateral or median, respectively.

In this section, we determine necessary conditions for the existence of strongly balanced 4-kite designs (order v, index) and for the existence of OQS (order v, index) nesting strongly balanced 4-kite designs. These conditions are preliminary for conclusive Theorems of Section 3.

Theorem 2.1. If is a strongly balanced 4-kite design of order v and index, then:

1);

2);

3).

Proof. If is a strongly balanced 4-kite design of order v and index, following the terminology described above and considering that each vertex occupies C times the central position in the blocks, necessarily:

from which.

The same considerations can be done to calculate the parameters T, M, which have the same value of C. For the last parameter L, we can consider that:

hence

.

Thus, 1) and 2) are verified and from them 3) holds.

Theorem 2.2. Let be an OQS of order v and index, nesting a strongly balanced 4-kite design of index. Then:

1);

2).

Proof. 1) Since:

and necessarily, it follows. 2) From 3) of Theorem 2.1, if then.      

3. Main Existence Theorems

In what follows, if is a block of an OQ-system defined in, then the translates of B are all the blocks of type

for every. B is called a base block of.

Theorem 3.1. There exists an OQS, of order v and index two, nesting a strongly balanced 4-kite design of index one if and only if:

Proof. Let be an OQS of order v and index, nesting a 4-kite design of order v and index one. From Theorem 2.2 it is and

Consider the following octagon quadrangles:

Consider the system, defined in, having as base blocks. This means that the blocks belong to and with all their translates.

Observe that, for, the correspondent system defined in has for blocks all the translates of the following base block:

.

In every case, it is possible to verify that is an OQS of order and index. Further, if we partition every block

into the two 4-kites:

we can verify that the collection of all the upper 4-kites forms a 4-kite-design of index one. Observe also that the collection of all the lower 4-kites forms a 4-kite-design of index one.

We can verify that both the systems are strongly balanced. In fact, for them it is, and.

To verify this, it is enough to consider that the system is constructed by base blocks and difference method.

This proves that is an OQS of order, , where the two 4-kites designs nested in it have both index one and are both strongly balanced.      

At last, it follows a result about the existence of strongly balanced 4-kite designs, whose spectrum is unknown.

Theorem 3.2. For every there exists strongly balanced 4-kite designs of index one.

4. Conclusive Remarks and Problems

Theorem 3.1 gives completely the spectrum of OQS which can be partitioned into two strongly balanced 4- kite designs. For a given v belongs to the spectrum, Theorem 3.1 gives also the method to construct an OQS of order v with the said properties.

For example, if, the translates of the two base blocks:

constructed on, define an OQS of order and index. We can observe that B₁ can be partitioned into the two 4-kites

and into the two 4-kites

We can verify that the translates of and define a strongly balanced 4-kite designs of order and index. Further, a system of the same type and parameters is defined by the translates of and.

The Theorem 3.1 permits also to find values of v for which there exist strongly balanced 4-kite designs, whose spectrum is still unknown. Thus, the statement of Theorem 3.2 can be the starting point for its determination.

In conclusion, we observe that from Theorem 3.1 follows the more general:

Theorem 4.1. There exists an OQS, of order v and index, nesting a strongly balanced 4-kite design of order v and of index, if and only if:

Proof. From Theorem 2.2, it is necessarily. So, from Theorem 3.1, by a repetition of blocks, the statement follows.                            

We can also point out that, after the determination of the spectrum, found in this paper, it is possible to study other problems about octagon quadrangle systems. It is possible to study the intersection problem among them, about which there exist an important literature, following the technique introduced in [16,17]. Also, it should be interesting to examine the conjecture of Berge for linear hypergraphs, in the case in which these are OQSs, following the ideas seen in [18,19].

REFERENCES