3-Quasiperiodic functions on graphs and hypergraphs

Cybernetics and Systems Analysis, Vol. 36, No. 4, 2000

3-QUASIPERIODIC

FUNCTIONS

ON GRAPHS

AND

HYPERGRAPHS

UDC 519.1

O. G. Rudenskaya

Sets of solutions of the equation f (x) - f (y) = k in N -~ are described, where f is a 3-quasiperiodic and strictly monotone function in N. The descriptions are used in studying the coarseness of a complete bipartite graph.

Keywords: quasiperiodic functions, 3-quasiperiodic functions on graphs and hypergraphs, complete bipartite graph, coarseness of complete bipartite graphs, solution of equations with 3-quasiperiodic functions.

Many problems of discrete programming, combinatorics, and automaton theory are reduced to the study of coarseness of a complete bipartite graph Km, n [1 ], the achromatic and pseudoachromatic number of a graph [2], the chromatic number of the partial hypergraph generated by the set of nodes of the clique of rank 4 [3], the greatest cardinality of matching in a hypergraph [3], and a number of other characteristics of graphs [4] and hypergraphs. For their description, a class, of functions can be selected that have the property described by the definition given below. We call a function f (x) specified on a set D 3-quasiperiodic in D if (3 T)(V x ~ D ) ' [ x + 3~ D ~

f (x + 3) = f (x) + T].

T H E O R E M . The set of all discrete functions 3-quasiperiodic in N 0 can be given by the formula

f(n)=an+b(-l)

Lql 7

I

+c(-1)

Lq,,+21

+d(-1)

3

,

(1)

where a, b, c, d ~ R and q - 2 or 4 (mod 6) (in this case, T = 3a). For q - 2 (mod 6), we have a = [ f (3) - f (0)] / 3, c = [ f (3) - f (2) - f (1) - f (0)] / 2,

(2)

b =[ - f (3) + 3 f (1) + 4 f (0)] / 6, d =[ - 2 f (3) + 3 f (2) + 5 f (0)] / 6, and, for q - 4 ( m o d

6), we have (2) and b =[ - 2 f (3) + 3 f (2) + 5 f (0)] / 6, d = [ - f (3) + 3 f (1) + 4 f (0)] / 6.

r'!

As is easily verified, the relation f (n + 3) = f (n) + 3a is satisfied for function (1) and T = 3a in this case. On the other hand, if four values f (0), f (1), f (2), and f (3) are known for a function f (n) 3-quasiperiodic in N 0, then, for any q - 2 or q - 4(mod 6), the coefficients of representation (1) are found from the system that is obtained as the result of successive substitution of n = 0,1, 2, 3 in (1). 9 When T = 0 (a special case of 3-periodic functions), we have f ( 3 ) = f (0). Example 1. Since any constant is a 3-quasiperiodic function, the following identity is valid in N 0 when q is even: 1 -(-1)

-(-1)

Lq+lJ 3

+(-1)

l

3

.

9

i n N -, "~ we consider the equation f ( x ) - f ( y ) = k,

(3)

Cybernetics Institute, National Academy of Sciences of Ukraine, Kiev, Ukraine. Translated from Kibernetika i Sistemnyi Analiz, No. 4, pp. 165-168, July-August, 2000. Original article submitted April 5, 1999.

614

1060-0396/00/3604-0614525.00 02000 Kluwer Academic/Plenum Publishers

1 0

1

3

x

Fig. 1

where f is an increasing function 3-quasiperiodic in N O and k > 0. When the function decreases, we pass to the equivalent equation with the increasing function ( - f ) by multiplying both sides of the equation by (-1). When k < 0, we pass to the equation f ( x ) - f ( y ) = - k whose solutions are symmetric about the solutions of (3) with respect to the straight line y = x. Let h be the greatest solution in N O of the inequality f (1 + 3n) - f (1) < k; I L l

in this case, h = ] - ~ [ . [_ I

]

Based on the definition of an increasing 3-quasiperiodic function f , we compile in Table 1 descriptions of the set M of all solutions of Eq. (3) depending on whether the points M0(1,1) and

(4)

M3(i_l)+j(i+ j , ] ) ,

where i = 1 , 2 , j = 1 , 2 , 3 (Fig. 1), are the solutions of the equation

f ( x ) - f (y)=k-Th. We reduce the possible nineteen cases to the eight rows of Table 1. Example 2. For the coarseness ~ (K3r + 2, 3s) of a complete bipartite graph

(5)

K3r +2, 3s when r > 1, we describe the set

P of all positive values of the partial increment A s~ and, for each value, the corresponding increments zXs and arguments s assuming these values. According to (1), the coarseness

In this case, P is the set of all k ~ N for which the equation

~(r, s + As) - ~ ( r , s) = k

(6)

with the unknowns As and s is solvable in N 2. We consider (6) as an equation of the form (3), where x = s + AS, y = s, and f (n) = ~(r, n) is an increasing function" 3-quasiperiodic in N 0 with T = 3r + 1. We rewrite (6) as

(7)

Let M be the set of all its solutions. Then P is the set of all k a N ' M ~: QS. According to Table 1, M ~: ~5 r some points of (4) are solutions of the comparison k - F (x, y)(mod 3r + 1).

(8)

According to (7), we have

615

TABLE 1 The set of all solutions of Eq. (5) for points (4)

No.

(1,1)

The set M of points from NO (for r = h + p , p=0,1 .... ) The points of the straight line y = x - 3h

(i+j,j)

(i+ j + 3r, j + 3p)

(i+j,j), (i+j+l.j+l): j ~ 3

(i+j+3r, j+3p), (i+j+l+3r, j+l+3p): j ~ 3

(i+1,1), (i+2,2), (i+3, 3)

The points of the straight line y = x - 3 h - i

(i+1,1), (i+ 3,3)

(i + 1+ 3r, 1+ 3p), (i + 3 + 3r, 3 + 3p)

(i+l,i), (i+ 3, i+1)

(i+l+3r, i+3p), (i+3+3r, i+l+3p)

(3.1),(4,3)

(3 + 3r, 1+ 3p). (4+ 3r, 3 + 3p)

TABLE 2 No.

As ~=k

s (for p =0. I, ~ ...)

As

p(p~:O)

k -=0 (mod 3r + 1)

3

k =r(mod 3r+1)

k=-r + l(mod 3r + 1) r>l

l+l

3p+l or 3 p + 3

3 w k +1 3r+l

3p+2 3p+2

4

k - 2 (mod 4) 3p+3 k-

2r (mod 3r + 1)

r>l 6

k -=2r + 1(mod 3r + 1)

F (M0)=F

k 3-~-~

+2

3p+3

3

+:

3p+l or 3 p + 2

(1,1)=0,

F ( m 1) = F (2,1) = F (M 3 ) = F (4, 3) = r, F (M2)=F

(9)

(3, 2 ) = r + 1,

F ( M 4 ) = F (3,1) - F ( M s ) = F ( 4 , 2 ) = 2 r

+ 1,

F (M 6) = F (5, 3) = 2r. On the basis of (9), we note six cases of solvability of (8) for an r ~ N. Their representation in Table 2 gives all the sought-for values of A s~; the corresponding values of As and s are described on the basis of (9) and items 1, 5, 2, 6, and 3 of Table 1. REFERENCES

1. 2. 3. 4.

616

F. Harary, Graph Theory [Russian translation], Mir, M o s c o w (1973). G. Chartrand and J. Mitchum, "Graphical theorems of N o r d h a u s and G a d d u m , " in: Theory of Graphs: Coverings, Packings, and Tournaments [Russian translation], Mir, M o s c o w (1974), pp. 204-211. C. Berge, Graphes et Hypergraphes, Dunod, Paris (1970). V . E . Alekseyev, "Hereditary classes and coding of graphs " in: Probl. Ki bem. , No. 39, Nauka, M o s c o w (1982), pp. 151-164.