Czech and Slovak Conference on Graph Theory and Combinatorics

GRAPHS 2002

Rejvíz, May 27 – 31, 2002

Abstracts

Edited by Petr Kovář and Tereza Kovářová

web: graphs.vsb.cz

Organizing Committee:

Dalibor Fronček Department of Mathematics and Statistics, University of Minnesota Duluth, and Department of Applied Mathematics, Technical University of Ostrava (Chair)

Petr Kovář Department of Mathematics and Descriptive Geometry, Technical University of Ostrava

Tereza Kovářová Department of Mathematics and Descriptive Geometry, Technical University of Ostrava

ISBN 80-248-0109-4 RANKING NUMBERS OF PLATONIC SOLIDS

Erik Bruoth^{∗}, Mirko Horňák

A k-ranking of a graph G is a colouring φ : V (G) → {1, ..., k} such that any path in G with endvertices x, y fulfilling φ(x) = φ(y) contains an internal vertex z with φ(z) > φ(x)(off-line version).Offline ranking χ_{r}(G) number of a graph G is a minimum k such that G has a k-ranking. On-line ranking number χ_{r}^{∗}(G) of a graph G is a minimum k such that G has a k-ranking constructed step by step if vertices of G are coming and coloured one by one in an arbitrary order; when colouring a vertex, only edges between already present vertices are known. Here we present off-line ranking numbers for all Platonic solids and also on-line ranking numbers except for the dodecahedron.

LIST DISTANCE-LABELINGS OF GRAPHS

Jiří Fiala^{∗}, Riste Škrekovski

In this paper, we study the distance choosability — the list counterpart of the distance constrained labelings, a notion stemming from channel assignment.

The task is to label vertices of a given graph by integers, such that

1. the label of a vertex belongs to a set prespecified for the vertex (list), and also

2. vertices at graph distance at most i should have been assigned integers that differ by at least p_{i}, where p_{i} is a fixed parameter of the problem. (Such sequence of parameters is called distance constraints.)

We first show that the Alon-Tarsi theorem for choosability in graphs has an analogous version for the choosability of distance constrained labelings. The existance of such labeling will be given in terms of the number of odd and even Eulerian subgraph. Then we apply this result to paths and cycles for the distance constrained labeling with two parameters (p_{1}, p_{2}) = (2, 1).

ERDÖS’S CONJECTURE ON MULTICIPLITIES OF COMPLETE SUBGRAPHS

František Franěk

In 1962 Paul Erdös in On the number of complete subgraphs contained in certain graphs conjectured that the proportion of monochromaitic t-cliques in complete graphs coloured by two colours tends to 2^{1−\binom{t}{2}}. The conjecture is related to Ramsey’s theorem and in more precise terms states that lim_{n→∞} c_{t}(n) = 2^{1−\binom{t}{2}}, where

c_{t}(n) = min\{c_{t}(G) : G graph of order n\}, c_{t}(G) = \frac{k_{t}(G)+k_{t}\overline{G}}{\binom{n}{t}} ,

k_{t}(G) denotes the numbere of t-cliques in graph G, and \overline{G} denotes a complement of graph G. The conjecture holds true for t = 3 (Goodman) and can easily be shown true for pseudorandom graphs - ”graphs that behave like random graphs”. To some surprise the conjecture was proven false by A. Thomason in 1989 who showed that the limit was less than expected. In 1992 Franek and Rödl showed that the conjecture was true for nearly pseudorandmom graphs (graphs obtained from pseudorandom by small perturberations) and in a sense is thus ”locally true”. Later Franek and Rödl improved on some of the upper bounds using computational techniques and generated many counter-examples to the conjecture with wide range of properties. Interestingly enough, some of the counter-examples defy the common belief that the way to minimize the proportion of monochromatic cliques is to have them distributed as evenly as possible (which, for instance, is the case for pseudorandom graphs).

The talk presents the background of the problem and focuses in some details on the nearly pseudorandom graphs and the techniques to prove the conjecture true for them. In the second part of the talk the computational techniques for improving the upper bounds are presented and discussed and some recent results are shown. The talk concludes with showing the limitations of the computational techniques and their inability to improve the upper bounds any further.

DECOMPOSITIONS OF COMPLETE GRAPHS

OF EVEN ORDER INTO ISOMORPHIC SPANNING TREES

Dalibor Fronček^{∗}, Michael Kubesa

Graph factorizations, most often these of complete graphs, have been extensively studied by many authors. It is not surprising that factorizations into isomorphic factors received special attention over the years. There are many results on factorizations of complete graphs into isomorphic trees of smaller order. Surprisingly enough, almost nothing has been published on factorizations into isomorphic spanning trees. A simple arithmetic condition shows that only complete graphs with an even number of vertices can be factorized into spanning trees. It is a well known fact that each such graph K_{2n} can be factorized into hamiltonian paths P_{2n}. On the other hand, it is easy to observe that each K_{2n} can be also factorized into double stars; that is, two stars K_{1,n−1} joined by an edge. But what about trees between these two extremal cases? While methods of such decompositions into symmetric trees have been known, we develop a more general method based on new types of vertex labelling, flexible q-labelling and blended ρ-labelling. This labellings are generalizations of labellings introduced by Rosa and Eldergill. We present several classes of trees that allow factorization of complete graphs with an even number of vertices.

Supported by University of Minnesota Duluth grant 177-1009

NON-REPETITIVE COLORINGS OF GRAPHS

Jaros law Grytczuk^{∗}, Mariusz Ha luszczak

A sequence a = a_{1}a_{2}...a_{n} is said to be non-repetitive if no two adjacent blocks of a are exactly the same. For instance the sequence 12323 21 contains a repetition 2323, while 123132123213 is nonrepetitive. A theorem of Thue asserts that, using only three symbols, one can produce arbitrarily long non-repetitive sequences.

We consider a natural generalization of Thue’s sequences for colorings of graphs. A coloring of the set of edges of a given graph G is non-repetitive if the sequence of colors on any path in G is non-repetitive. We call the minimal number of colors needed for such a coloring the Thue number of G and denote it by π(G).

The main problem is the relation between the numbers π(G) and Δ(G). In a joint paper with Noga Alon and Oliver Riordan we show, using the probabilistic method, that π(G) ≤ cΔ(G)^{2} for some absolute constant c. However, for certain special classes of graphs linear upper bounds on π(G) are possible by explicit colorings. For instance, the Thue number of the complete graph K_{n} is at most 2n − 3, and π(T) ≤ 4(Δ(T) − 1) for any tree T with at least two edges. A lot of challenging problems that arose are still left open.

ON INTEGRAL TREES OF THE LARGE ORDER

Pavel Híc^{∗}, Milan Pokorný

A graph G is called integral if all the zeros of the characteristic polynomial P(G;x) are integers. The first studies of integral graphs were made by Harary and Schwenk [3]. So far, there are many results on some particular classes of integral graphs, for instance: cubic graphs [2]; trees [4, 6, 7]; graphs with maximum degree 4 [1]. In general, the problem of characterizing of integral graphs seems to be difficult.

A tree T is called balanced if all the vertices at the same distance from the centre of T have the same degree. The investigation of balanced integral trees has been made in [4]. There are many unanswered questions related with this problem. For instance, all the balanced integral trees constructed so far have diameter at most 8, but there is none of diameter 9 (see [4]).

We investigate the problem of existence of balanced integral trees of diameter 10. We have already proved that the problem of characterizing integral trees of diameter 3 (nonbalanced) is equivalent with the problem of solving Pell‘s diophantine equations (see also [5]).

AMS Subject Classification (1991): Primary 05C50. Key words: integral tree, characteristic polynomial.

Research partially supported by VEGA grant 1/7152/20

Reference

[1] K. T. Balińska and S. K. Simić: The nonregular, bipartite, integral graphs with maximum degree 4. Part I.: basic properties, Discrete Mathematics 236, (2001),13-24.

[2] F. C. Bussemaker and D. Cvetković: There are exactly 13 connected cubic integral graphs, Publ. Elektrotech. Fak. Ser. Mat. Fiz. 544 (1976), 43-48.

[3] F.Harary and A. J. Schwenk : Which graphs have integral spectra? In: Graphs and Combinatorics. Lecture Notes in Math. 406, Springer-Verlag, Berlin, (1974), 45-51.

[4] P. Híc and R. Nedela : Balanced integral trees, Math. Slovaca, 48, (1998), No. 5, 429-445.

[5] P. Híc: On balanced integral trees of diameter 6, In: CO-MAT-TECH 97’, Trnava, (1997) 125-129.

[6] A. J. Schwenk and M. Watanabe : Integral starlike trees, J. Austral. Math. Soc. Ser. A, 28, (1979), 120-128.

[7] M. Watanabe: Note on integral trees, Math. Rep. Toyama Univ. 2, (1979), 95-100.

BRANCH-DECOMPOSITIONS AND THE TUTTE POLYNOMIAL OF REPRESENTABLE MATROIDS

Petr Hliněný

It is a classical result of Jaeger, Vertigan and Welsh that evaluating the Tutte polynomial of a graph is #P -hard in all but few special points. On the other hand, several papers in past years have shown that the Tutte polynomial of a graph can be efficiently computed using a bounded-width tree-decomposition. We present a recursive formula computing the Tutte polynomial of a matroid M represented over a finite field (which includes all graphic matroids) using the parse tree of a bounded-width branchdecomposition of M. This formula provides, given such a parse tree, an algorithm computing the Tutte polynomial of M in polynomial time with a fixed exponent.

DISTANCE LOCAL CONNECTIVITY AND HAMILTONIAN INDEX

Přemysl Holub^{∗}, L. Xiong

A graph G is said to be ℓ-distance-locally connected if, for every vertex x ∈ V (G), the set of vertices at distance at most ℓ from x induces a connected graph. Clearly, every 2-connected graph is ℓ-distance-locally connected for some integer ℓ.

We prove sufficient conditions of Chvátal-Erdös and of Dirac type for distance local connectivity, and we obtain upper bounds for the hamiltonian index of a graph in terms of its distance local connectivity.

Finally, we show that every N_{2}-locally connected graph has a dominating closed trail, and hence its hamiltonian index is at most 1.

ON THE POINT-DISTINGUISHING CHROMATIC INDEX OF COMPLETE BIPARTITE GRAPHS

Mirko Horňák^{∗}, Norma Zagaglia Salvi

Let G be a graph having no component K_{2} and at most one component K_{1}. The point-distinguishing chromatic index of G, in symbol χ_{0}(G), is a smallest number of colours in a (not necessarily proper) edge colouring of G such that any two distinct vertices of G are distinguished by sets of colours of their incident edges.

It is immediately seen that χ_{0}(K_{1,n}) = n for any n ≥ 2. Further, if m, n are integers, 2 ≤ m ≤ n, then χ_{0}(K_{m,n}) ≥ ⌈log_{2} m⌉ + 1. Let [p, q] be the interval of all integers z with p ≤ z ≤ q. For positive integers k, m define

d_{m}^{(k)} := \{ \begin{matrix}2m, & if k ≤ m, \\ 2m − 1, & if k = m + 1, \\ m, & k ≥ m + 2 \end{matrix}

b_{m}^{(k)} := ∑_{i=0}^{m} \binom{k}{i} − d_{m}^{(k)} ,
I_{m}^{(k)} := [b_{m}^{(k−1)} + 1, b_{m}^{(k)} ],

where \binom{k}{i} = 0 if k < i. In what follows k, l, m, n are integers with 2 ≤ m ≤ n, l = ⌈log_{2} m⌉ and k ≥ l + 1.

Theorem 1. If either m ≤ 9 or k ≥ 2l + 2, then χ_{0}(K_{m,n}) =

k ⇔ n ∈ I_{m}^{(k)}.

Theorem 2. If k = l + 1 and n ∈ I_{m}^{(k)}, then χ_{0}(K_{m,n}) = k.

If k ∈ [l + 2, 2l + 1], then the interval I_{m}^{(k)} decomposes into two subintervals, the left one,

L_{m}^{(k)} := [b_{m}^{(k−1)} + 1, 2^{k−1} − m − l − 1],

and the right one,

R_{m}^{(k)} := [2^{k−1} − m − l, b_{m}^{(k)} ].

Theorem 3. If k ∈ [l+2, 2l+1] and n ∈ R_{m}^{(k)}, then χ_{0}(K_{m,n}) =

k. Proposition 4. If k ∈ [l + 2, 2l + 1] and n ∈ L_{m}^{(k)}, then

χ_{0}(K_{m,n}) ∈ {k − 1, k}.

Theorem 5. If m = 10, k ∈ [l + 2, 2l + 1] and n ∈ L_{m}^{(k)}, then χ_{0}(K_{m,n}) = k − 1 ⇔ (k, n) = (6, 13).

In Theorem 5 we have l = 4 and the unique “extremal” value of k is k = 6 = l + 2.

Open problem. Decide if there is a triple of integers

(k, m, n) such that m ≥ 11, k ∈ [l + 3, 2l + 1], n ∈ L_{m}^{(k)} and χ_{0}(K_{m,n}) = k − 1.

SKEW-MORPHISM OF ABELIAN GROUPS

Robert Jajcay

The concept of a skew-morphism is a generalization of the concepts of a group automorphism and of an anti-automorphism (introduced in the theory of regular Cayley maps). The existence of certain skew-morphisms is known to be a necessary and sufficient condition for embeddability of Cayley graphs into orientable surfaces in the form of regular Cayley maps. Although skew-morphisms possess many interesting algebraic properties, a general theory of skew-morphisms of finite groups is far from reach. In our talk, we shall present results on skew-morphisms of abelian groups - a part of an ongoing effort to classify regular Cayley maps of abelian groups. We will pay particular attention to a generalization of the so-called antibalanced case (introduced by Širáň and Škoviera) - t-antibalanced Cayley maps.

DECOMPOSITIONS OF PLANAR GRAPHS

Tomáš Kaiser^{∗}, Riste Škrekovski

At the Czech–Slovak Graph Theory conference last year, J. Kratochvíl cited the following conjecture:

The vertices of any planar graph can be decomposed into two sets inducing no cycle of length 3 or 4.

The conjecture has subsequently been proved by R. Škrekovski and myself. I shall discuss several facts and open problems related to this result and, more generally, to vertex decompositions of planar graphs.

G-MINIMAL REPRESENTATIVES OF 3-MANIFOLDS OF GENUS 2

Jan Karabas

One of the most interesting problems for 3-manifolds is the isomorphism problem. Since 70’s several methods to solve it were developed. The method introduced in a paper of Ferri and Gagliardi is not easy to use, since no bound for the number of steps in a computer representation is known. Some approximations of solution was introduced in the paper of Grasselli, Mulazzani and Nedela. The present method based on these approximations leads to a simple algorithm finding representatives of the given equivalence classes of 3-manifolds of genus two.

CROSSING GRAPHS

Sandi Klavžar^{∗}, Henry Martyn Mulder

Let G be an isometric subgraph of a hypercube—a partial cube. Then its crossing graph G^{#} is introduced as the graph whose vertices are the equivalence classes of the Djoković-Winkler relation Θ. Equivalently, a vertex of G^{#} corresponds to the class of edges of G that in the embedding differ in a fixed position. Two vertices of G^{#} are adjacent if they cross on a common cycle.

It will be shown that every graph is the crossing graph of some median graph. A partial cube G has a triangle-free crossing graph if and only if G is a cube-free median graph. This result can be used to characterize the partial cubes having a tree or a forest as crossing graph. An expansion theorem for the partial cubes with complete crossing graphs will also be mentioned. Cartesian products will also be considered, in particular, G^{#} is a complete bipartite graph if and only if G is the Cartesian product of two trees.

EVERY CUBIC GRAPH IS STS(381)-COLOURABLE.

Mike Grannell, Terry Griggs, Martin Knor^{∗}, ^{1)} and Martin Škoviera

A Steiner triple system on n points, ST S(n), is a set of triples of these points such that every pair is contained in a unique triple. Colouring of a cubic graph by Steiner triple system is an assignment of points of the system to the edges of a graph in such a way, that triples of colours appearing at edges incident with one vertex form a block (triple) of the system.

It is well-known that every cubic graph is 4-colourable. However, in colouring of edges of a cubic graph by four colours there is plenty of freedom. Namely, if there are already assigned colours to two edges incident with a given vertex, then there are two possibilities for choosing the colour of the third edge. This is not the case of colouring by Steiner triple system. As every pair of points of Steiner triple system is contained in a unique triple, colours of two edges incident with a given vertex determine the colour of the third edge. Therefore, it is suprising that every bridgeless cubic graph is colourable by every non-trivial STS(n), see [1]. Further, if G is a cubic graph and S is a projective geometry, then G is colourable by S if and only if G is bridgeless, see [1]. Hence, the situation is not clear for graphs with bridges. In the talk we present an ST S(381) such that every cubic graph is ST S(381)-colourable.

1) Supported by VEGA grant 1/6293/99

EDGE-DISJOINT ODD CYCLES IN PLANAR GRAPHS

Daniel Kráľ^{∗}, Heinz-Juergen Voss

We prove τodd(G) ≤ 2νodd(G) for each planar graph G where νodd(G) is the maximum number of edge–disjoint odd cycles and τodd(G) is the minimum number of edges whose removal makes G to be bipartite, i.e. which meet all the odd cycles. This improves a previous fast growing function of νodd(G) bounding τodd(G) for planar graphs G due to Berge and Reed. For each k, there is a 3–connected planar graph G_{k} with τodd(G) = 2k and νodd(G) = k, so the factor 2 is best possible. There exist graphs G in the projective plane with τodd(G) arbitrary large and νodd(G) = 1.

Our proof is based on the duality of linear programming. It uses a well–known connection between the maximum cut problem in planar graphs and the T-join problem explored by Hadlock which led to a polynomial time algorithm for the maximum cut problem for planar graphs.

SPANNING TREE FACTORIZATIONS OF COMPLETE GRAPHS

Michael Kubesa

We examine decompositions of complete graphs with an even number of vertices into isomorphic spanning trees. We develop a cyclic factorization of K_{2n} into non-symmetric spanning trees. Our factorization methods are based on flexible q-labeling and blended ρ-labeling, introduced by Fronček.

In this paper we present several infinite classes of non-sym-metric trees, namely brooms and caterpillars with diameter 4, which have flexible q-labeling or blended ρ-labeling. A caterpillar is a tree in which each edge has at least one end-vertex in a single path and a broom is a caterpillar, which contains a single star joined to a path.

Supported by University of Minnesota Duluth grant 177-1009

A NOTE ON THE THOMASSEN’S CONJECTURE

Roman Kužel^{∗}, Liming Xiong

The well-known Thomassen’s conjecture says that every 4-connec-ted line graph contains a hamiltonian cycle. We show that this conjecture is equivalent to the statement that every essentially 4-edge connected 3-regular graph has a dominating cycle which contains any two prescribed disjoint edges (a dominating cycle in G is a cycle C such that every edge of G has at least one vertex on C).

ON LIGHT CYCLES IN FAMILIES OF PLANE GRAPHS

Tomáš Madaras

A connected graph H is said to be light in a class of graphs H if there exists a positive integer φ(H, H) such that each graph G ∈ H that contains an isomorphic copy of H contains also a subgraph K isomorphic to H such that ∑_{v∈V (K)} deg_{G}(v) ≤ φ(H, H). We present various results concerning the existence of light cycles in families of plane graphs of restricted minimum vertex degree or minimum edge weight.

THE DISTANCE COLOURING OF REGULAR TILINGS OF THE PLANE.

Peter Jacko, Andrea Marcinová^{∗}

Let G be a multigraph. For any positive integer t, the t-distance vertex (edge,face) chromatic number of G, in symbols χ^{(t)}(G) (χ_{e}^{(t)} (G), χ_{f}^{(t)} (G)), is defined to be the minimum number of colours required to colour the vertrices (edges, faces) of G so that any two vertices (edges, faces) whose distance apart is ≤ t receive distinct colours. We present distance colouring results for three regular tilings of the plane.

DECOMPOSITIONS OF COMPLETE DIGRAPHS INTO SELF-CONVERSE PARTS

Mariusz Meszka^{∗}, Zdzis law Skupień

Arc decompositions of the complete digraph DK_{n} into t isomorphic parts are considered. Moreover, in the case when a numerical divisibility condition is not satisfied, two sets of nearly t^{th} parts are defined, namely the floor t^{th} class ⌊DK_{n}/t⌋_{R} := (DK_{n} − R)/t and the ceiling t^{th} class ⌈DK_{n}/t⌉_{S} := (DK_{n}+S)/t, where R and S are sets of arcs of the smallest possible cardinalities. We prove that for every n and t there exist R and S such that both the floor and ceiling classes contain self-converse digraphs and moreover these nearly t^{th} parts are oriented graphs (with two exceptions when t = 3 and n = 3, 5). We also prove that DK_{n} is decomposable into nonhamiltonian directed paths whenever their lengths sum up to n(n − 1).

CRITERIA OF THE EXISTENCE OF UNIQUELY PARTITIONABLE GRAPHS AND COMBINATORIAL STRUCTURES.

Peter Mihók^{∗}, Izak Broere and Jozef Bucko

Let P_{1}, P_{2}, …, P_{n} be graph properties, a graph G is said to be uniquely (P_{1}, P_{2}, …, P_{n})-partitionable if there is exactly one (unordered) partition {V_{1}, V_{2}, … V_{n}} of V (G) such that G[V_{i}] ∈ P_{i} for i = 1, 2, …, n. We will show that for additive and inducedhereditary properties of graphs uniquely (P_{1}, P_{2}, …, P_{n})-parti-tionable graphs exist if and only if P_{i} and P_{j} are either coprime or equal irreducible properties of graphs for every i ≠ j, i, j ∈ {1, 2, …, n}.

Some generalization for hypergraphs, digraphs and other combinatorial structures will be presented.

SIGNPOSTS IN A GRAPH

Ladislav Nebeský

Let G be a connected graph, and let d denote the distance function of G. By a signpost in G we mean an ordered triple (u, v, w), where u, v and w are vertices of G, u and v are adjacent, and w is different from u. We say that a signpost (u′, v′, w′) in G is geodetic if d(v′, w′) = d(u′, w′) − 1.

Roughly speaking, a geodetic signpost (x, y, z) in G shows the direction of a shortest path, say P, from x to z; the direction of P is determined by y. In a certain sense, every signpost (x′, y′, z′) in G shows a ”direction” from x′ to z′.

The topic of this paper is looking for sets of signposts which enable ”reliable traveling” in G.

SOME REMARKS ON GENERALISATIONS OF CAYLEY GRAPHS

Roman Nedela

Several generalisations of the notion of Cayley graphs will be discussed. We shall derive some combinatorial properties of the considered classes of graphs. The results will be demostrated on examples.

SENSE OF DIRECTION AND SHORTEST-PATH ROUTING ON RANDOM REGULAR GRAPHS

Martin Nehéz

A research of the sense of direction (SD) in the graph theory is motivated by communication problems in distributed systems, especially in point-to-point message-passing communication networks. Study of SD is a part of the larger investigation on the structural knowledge of distributed systems. Formal definitions and related problems are contained in the survey of P. Flocchini, B. Mans and N. Santoro, [ ”Sense of Direction in Distributed Computing”, Proc. DISC’98, LNCS 1499, Springer-Verlag, pp. 1-15, 1998 ]. A simple and very natural example of SD is the compass SD defined on two-dimensional tori T_{n×n} which allows four labels: north, south, east and west. An important kind of SD was defined by S. Dobrev in [ ”Yet Another Look at Structural Information”, Proc. SIROCCO’98, Carleton Scientific, pp. 114-128, 1998 ]. It is a group-based structural information (G-SI) on Cayley graphs in which each edge (its port) has assigned the label of the corresponding generator. (Cayley assignment of labels represents the traditional labelling for a large class of Cayley graphs, including rings, tori, hypercubes, e. t. c.) In several recent works (see the survey of Flocchini, Mans and Santoro) there was shown that SD has a positive impact on the complexity of several type of distributed algorithms such as broadcasting, leader election, depth-first traversal, spanning tree construction and minimum finding.

We study the impact of SD on the number of routing decisions in this paper. We assume a Δ-regular point-to-point communication networks with crash faults such that their occurrence have a probabilistic distribution. Such a network is modelled by a random regular graph from a probability space G(Δ − reg, p), since p is a constant probability of an edge (0 < p < 1). We consider the Tajibnapis’ Netchange routing algorithm with complete routing tables. A routing decision in a node is one access to the routing table. We show that with respect to a given routing scheme, the problem of determining the number of routing decisions along a routing path according to the minimum-hop requirement is closely related to the enumeration of a degree distribution in the probability space G(Δ − reg, p). We also compare the average number of routing decisions for two class of graphs: random regular graphs with degree Δ without SD and random k-dimensional tori with G-SI, where 2k = Δ. For a k-dimensional torus T_{n}^{k} we define the corresponding SD according to the Dobrev’s definition, since T_{n}^{k} = Cay(Z_{n}^{k}, {±ε_{i} | 0 ≤ i ≤ k − 1}) and this SD is the same also for the probability space G(T_{n}^{k}, p). For a graph G and for a destination vertex u ∈ G, let us denote the number of vertices in which at least one routing decision is performed along a shortest routing path to the destination u as rd(G, v). The following table contains the comparison of average values rd(G, v) for regular random graphs without SD and for random tori with G-SI relative to the order of a graph denoted by N. (Note that for tori T_{n}^{k} it holds N = n^{k}.)

Δ  rd(G, u)/N, where  k  rd(T, u)/N, where
G ∈ G(Δ − reg, 1/2)  T ∈ G(T_{n}^{k}, 1/2)
without SD  with G-SI
3  0.125
4 0.313 2 0.188
5  0.5
6 0.656 3 0.438
7  0.773
8 0.855 4 0.645
9  0.910
10  0.945  5  0.787

These results can be understood as the enumeration of the upper bound on the number of routing decisions for a given fault-tolerant network in average case. The determination of related nontrivial lower bounds is still open.

The author thanks for a support to the VEGA grant No. 1/7152/20.

EMBEDDING STEINER TRIPLE SYSTEMS INTO STEINER SYSTEMS S(2,4,V)

Alexander Rosa^{∗}, Mariusz Meszka

While embeddings of Steiner systems S(t, k, v) into Steiner systems S(t′, k′, v′) have been widely considered, e.g. for t = t′ = 2, k = k′ = 3 or 4, and for t = t′ = 3, k = k′ = 4, this seems not to be the case when k < k′. We initiate a systematic study of embeddings of Steiner systems S(2, 3, v) (i.e. Steiner triple systems) into Steiner systems S(2, 4, w). There are marked differences to the previously studied cases. We settle the existence of embeddings of the unique ST S(7), and, with one possible exception of the unique ST S(9), into Steiner systems S(2, 4, w). We also obtain bounds on embedding sizes of Steiner triple systems of other small orders.

FORBIDDEN SUBGRAPHS AND CLOSURE CONCEPTS

Zdeněk Ryjáček

Let X_{1}, …, X_{k} be graphs. A graph G is X_{1} … X_{k}-free if G does not contain a copy of any of the graphs X_{1}, …, X_{k} as an induced subgraph. The graphs X_{1}, …, X_{k} are called forbidden subgraphs in this context.

It is known [Bedrossian 1991; Faudree and Gould 1997] that if X, Y is a pair of connected graphs, then, for any 2-connected graph G, G being XY -free implies G is hamiltonian if and only if X is the claw C ≃ K_{1,3} and Y belongs to a finite list of graphs, one of them being the net N (the net N is the only connected graph with degree sequence 333111). Similar characterizations of pairs and triples of forbidden subgraphs for some other properties are also known.

Let G be a claw-free graph and let cl(G) be its closure. Using a characterization of all connected graphs A such that the class of all CA-free graphs is stable under the closure operation (i.e., G being CA-free implies cl(G) is CA-free), we extend some known results on hamiltonicity by characterizing classes of all exceptional graphs. We then show that, although the classes of CA-free graphs in which 2-connectedness implies hamiltonicity (by the Bedrossian’s characterization) are independent in general, this is not the case for their closures. By introducing a strengthening of the closure concept, we fully describe the structure of the (strong) closures of graphs from these classes. Several open questions and problems will be discussed.

GRAPH EXPONENTIATION

Eliška Ochodková, Václav Snášel^{∗}

We want to introduce a concept of graphic algebra, of hypercubes and median graphs and exponentiation of graphs. We’ll show that normal graphic algebra is a median graph and if every hypercube is a median graph, then exponentiation of median graph is also median graph. We want to show some necessary concepts and prove proposition mentioned above.

Some concepts (without all necessary definitions, propositions and proves):

Proposition 1: Every normal graphic algebra has a localizator.

Proposition 2: Let A be a simple graphic algebra, G is its graph. When G has a finite diameter, then D_{G} is the localizator of A.

Hypercubes are the simplest class of Cartesian products, they are also known as r-cubes.

Definition 2: A median of triple of vertices u, v, w, of a graph G is a vertex z that lies on a shortest u, v-path, on a shortest u, w-path and on a shortest v, w-path.

Definition 3: A graph G is a median graph if every triple of vertices of G has a unique median, namely if |I(u, v) ∩ I(u, w) ∩ I(v, w)| = 1.

Proposition 3: Every hypercube is a median graph.

Definition 4: Let G and H be graphs. Then the vertex set of the direct power G^{H} is the set of all homomorphisms from H into G. Two homomorphisms f, g ∈ V (G^{H}) are called adjacent if [f(u), g(u) ∈ E(G)] for all u ∈ H.

Proposition 4: Graph of normal graphic algebra is a median graph.

Theorem: Let G and H be median graphs. Then G^{H} is median graph.

CANTANKEROUS MAPS Jozef Širáň

Cantankerous regular maps are surface embeddings of graphs with doubled edges, such that the automorphism group of the embedding acts regularly on flags, and where each doubled edge is a centre of a Möbius band on the surface. We present an abstract characterisation of cantankerous maps and apply it to description of all such maps that have automorphism group isomorphic to P SL_{2}(q); other simple groups will be discussed in this connection as well. In the case of valence 6 we exhibit an interesting correspondence between cantankerous maps and 3-arc-transitive cubic graphs.

COMPUTING GRAPH INVARIANTS ON ROTAGRAPHS USING DYNAMIC ALGORITHM APPROACH: THE CASE OF DOMINATION NUMBERS Aleksander Vesel

Rotagraphs generalize all standard products of graphs in which one factor is a cycle. A computer based approach for searching graph invariants on rotagraphs has been proposed in [1]. The main idea of the approach is to build a function (an invariant) on a rotagraph from corresponding functions on its basic building blocks. Then the problem reduces to a search for a certain subgraph in an associated directed graph. In particular, if the function in question is local and hereditary, one has to look for directed cycles.

We will show that in certain cases the approach can be used for the functions which are not hereditary as well. Moreover, we will give some new results on the domination numbers of the Cartesian products of two cycles.

References S. Klavžar, A. Vesel, Computing graph invariants on rotagraphs using dynamic algorithm approach: the case of L(2,1)-colorings and independence numbers, Prepr. ser. - Univ. Ljubl. Inst. Math., 39, 2001, 779, 1-13.

DOMINATION IN INFINITE GRAPHS

Bohdan Zelinka

Let G be a finite undirected graph with the vertex set V (G), let V be a subset of the set R of all real numbers. Let f be a mapping of V (G) into Y. If f(N[v]) ≥ 1 for each v V (G), where f(N[v]) is the sum of values f(x) over all vertices x from the closed neighbourhoood N[v] of v; then f is called a Y-dominating function on G.

A Y-dominating function for Y = {0, 1} is called a dominating function, for Y = {−1, 1} a signed dominating function, for Y = {−1, 0, 1} a minus dominating function These concepts are described in [1].

In this communication, whenever it is possible, the mentioned concepts are transferred to the case of infinite graphs and their properties are studied.

LIST OF PARTICIPANTS GRAPHS 2002

May 27–31, 2002, Rejvíz, Czech Republic

Brousek Jan Západočeská univerzita v Plzni Univerzitní 8, 306 14 Plzeň, Czech Republic

Bruoth Erik Ústav matematických vied, Prírodovedecká fakulta Univerzity P. J. Šafárika, Jesenná 5, 041 54 Košice, Slovakia e-mail: ebruoth@science.upjs.sk

Fiala Jiří KAM MFF UK, Malostranské náměstí 25, 118 00 Praha, Czech Republic e-mail: fiala@kam.mff.cuni.cz

Franěk František Department of Computing and Software, Faculty of Engineering, McMaster University, 1280 Main Street West, ITB-202, Hamilton, Ontario, L8S 4L7, Canada e-mail: franek@mcmaster.ca

Fronček Dalibor Department of Mathematics and Statistics, University of Minnesota Duluth, Duluth, MN 55812-3000, USA e-mail: dfroncek@d.umn.edu

Grytczuk Jaroslaw Institute of Mathematics, University of Zielona Gora, ul. Podgorna 50, 65-246 Zielona Gora, Poland Ha luszczak Mariusz

Institute of Mathematics, University of Zielona Gora, ul. Podgorna 50, 65-246 Zielona Gora, Poland e-mail: M.Haluszczak@im.uz.zgora.pl

Híc Pavel Pedagogická fakulta, Trnavská univerzita, Priemyselná 4, 918 43 Trnava, Slovakia e-mail: phic@truni.sk

Hliněný Petr Institut teoretické informatiky, MFF UK, Malostranské náměstí 25, 118 00 Praha, Czech Republic e-mail: hlineny@member.ams.org

Holub Přemysl Západočeská univerzita v Plzni Univerzitní 8, 306 14 Plzeň, Czech Republic e-mail: holubpre@kma.zcu.cz

Horňák Mirko Ústav matematických vied, Prírodovedecká fakulta Univerzity P. J. Šafárika, Jesenná 5, 041 54 Košice, Slovakia e-mail: hornak@duro.science.upjs.sk

Jajcay Robert Department of Mathematics, Indiana State University, Terre Haute, IN 47807, USA e-mail: jajcay@laurel.indstate.edu Jendroľ Stanislav

Ústav matematických vied, Prírodovedecká fakulta Univerzity P. J. Šafárika, Jesenná 5, 041 54 Košice, Slovakia e-mail: jendrol@kosice.upjs.sk

Kaiser Tomáš Západočeská univerzita v Plzni Univerzitní 8, 306 14 Plzeň, Czech Republic e-mail: kaisert@kma.zcu.cz

Karabas Jan Institut matematiky a informatiky, Matematický ústav SAV, Severná 5, 974 01 Banská Bystrica, Slovakia e-mail: 6karabas@fpv.umb.sk

Klavžar Sandi Deptartment of Mathematics, University of Maribor, Koroška cetsa 160, SI- 2000 Maribor, Slovenia e-mail: sandi.klavzar@uni-lj.si

Knor Martin Katedra matematiky, Stavebná fakulta, Slovenská technická univerzita, Radlinského 11, 813 68 Bratislava, Slovakia e-mail: knor@cvt.stuba.sk

Kovář Petr Katedra matematiky a deskriptivní geometrie, Vysoká škola báňská – Technická univerzita Ostrava,

17. listopadu 15, 708 33 Ostrava – Poruba, Czech Republic e-mail: Petr.Kovar@vsb.cz Kovářová Tereza

Katedra matematiky a deskriptivní geometrie, Vysoká škola báňská – Technická univerzita Ostrava,

17. listopadu 15, 708 33 Ostrava – Poruba, Czech Republic e-mail: Tereza.Kovarova@vsb.cz

Kráľ Daniel ITI MFF UK, Malostranské náměstí 25, 110 00 Praha 1, Czech Republic e-mail: kral@kam.mff.cuni.cz

Kratochvíl Jan KAM MFF UK, Malostranské náměstí 25, 118 00 Praha 1, Czech Republic e-mail: honza@kam.mff.cuni.cz

Kubesa Michael Katedra aplikované matematiky, Vysoká škola báňská – Technická univerzita Ostrava,

17. listopadu 15, 708 33 Ostrava – Poruba, Czech Republic e-mail: Michael.Kubesa@vsb.cz

Kužel Roman Západočeská univerzita v Plzni Univerzitní 8, 306 14 Plzeň, Czech Republic e-mail: rkuzel@kma.zcu.cz

Madaras Tomáš Ústav matematických vied, Prírodovedecká fakulta Univerzity P. J. Šafárika, Jesenná 5, 041 54 Košice, Slovakia e-mail: madaras@science.upjs.sk Marcinová Andrea

Ústav matematických vied, Prírodovedecká fakulta Univerzity P. J. Šafárika, Jesenná 5, 041 54 Košice, Slovakia e-mail: amarcino@science.upjs.sk

Meszka Mariusz Faculty of Applied Mathematics, University of Mining and Metallurgy, al. Mickiewicza 30, 30-059 Krakow, Poland e-mail: grmeszka@cyf-kr.edu.pl

Mihók Peter KAMaHI, Ekonomicka fakulta TU Košice, Němcovej 32, 040 01 Košice, Slovakia e-mail: Peter.Mihok@tuke.sk

Nebeský Ladislav Filozofická fakulta, Univerzita Karlova, 116 38 Praha, Czech Republic e-mail: Ladislav.Nebesky@ff.cuni.cz

Nedela Roman Institut matematiky a informatiky, Matematický ústav SAV, Severná 5, 974 01 Banská Bystrica, Slovakia e-mail: nedela@financ.umb.sk

Nehéz Martin Katedra informatiky a výppčetní techniky, FEI, Slovenská technická univezita, Bratislava, Ilkovičova 3, 812 19 Bratislava, Slovakia e-mail: nehez@dcs.elf.stuba.sk Ochodková Eliška

Katedra informatiky, Vysoká škola báňská – Technická univerzita Ostrava,

17. listopadu 15, 708 33 Ostrava – Poruba, Czech Republic e-mail: eliska.ochodkova@vsb.cz

Proskurowski Andrzej Computer Science Department, University of Oregon, 256 Deschutes Hall, 1477 East 13th Ave. Eugene, OR 97403-1202, USA e-mail: andrzej@cs.uoregon.edu

Ptáčníková Dagmar Katedra informatiky, Pedagogická fakulta Jihočeské Univerzity, Jeronýmova 10, 370 15 České Budějovice, Czech Republic e-mail: dapo@pf.jcu.cz

Ricanyová Edita Katedra Informatiky, Fakulta matematiky, fyziky a informatiky, Univerzita Komenského, Mlynská dolina, 842 48 Bratislava, Slovakia e-mail: ricanyov@dcs.fmph.uniba.sk

Rosa Alexander Department of Mathematics and Statistics, McMaster University, Hamilton, Ontario, L8S 4K1, Canada e-mail: rosa@mcmail.cis.McMaster.ca

Ryjáček Zdeněk Západočeská univerzita v Plzni Univerzitní 8, 306 14 Plzeň, Czech Republic e-mail: ryjacek@kma.zcu.cz Snášel Václav

Katedra informatiky, Vysoká škola báňská – Technická univerzita Ostrava,

17. listopadu 15, 708 33 Ostrava – Poruba, Czech Republic e-mail: vaclav.snasel@vsb.cz

Širáň Jozef Katedra matematiky, Stavebná fakulta, Slovenská technická univerzita, Radlinského 11, 813 68 Bratislava, Slovakia e-mail: siran@lux.svf.stuba.sk

Tesková Libuše Západočeská univerzita v Plzni Univerzitní 8, 306 14 Plzeň, Czech Republic

Tuchanová Milena Západočeská univerzita v Plzni Univerzitní 8, 306 14 Plzeň, Czech Republic

Vesel Aleksander PEF, University of Maribor, Koroška cetsa. 160, SI-2000 Maribor, Slovenia e-mail: vesel@uni-mb.si

Zelinka Bohdan Katedra aplikované matematiky TU, Voroněžská 13, 460 01 Liberec 1, Czech Republic e-mail: Bohdan.Zelinka@vslib.cz The organizers thank to Eltodo EG and Bernard Brewery

for their financial support.