University of Ljubljana

**Walecki tournaments**

TU München

**Minimum cycle bases in graphs - a new algorithm**

A minimum cycle basis in an undirected graph *G* is a set of
simple cycles whose incidence vectors span the cycle space of *G* and
whose overall edge sum is minimal.

A polynomial algorithm to construct such a basis has been proposed by
J.D. Horton in 1987. The algorithm works by extracting a minimum cycle
basis from a large set of candidate cycles.

Our new approach answers affirmatively a question posed in his article:
whether it is possible to obtain a minimum cycle basis without first
constructing and storing all candidate cycles.

Wirtschaftsuniversität Wien

**The number of nodal domains of hypercubes**

Let $f$ be a real function on the vertices of a graph $G=(V,E)$.
A strong (weak) nodal domain of $f$ is a maximal connected induced
subgraph $G[W]$ of $G$ with
vertex set $W$ such that $f(x)f(y)>0$ ($f(x)f(y)\ge 0$) for all $x,y\in W$.
I will talk about the number
of strong and weak nodal domains of hypercubes, where the function $f$
is an eigenvector of Laplacian matrix of a hypercube.

[This is a joint work with Wim Hordjik, Josef Leydold and Peter F. Stadler.]

University of Ljubljana

**The circular chromatic number of a digraph**

We introduce the circular chromatic number $\chic$ of a digraph and
establish various basic results. They show that the coloring theory
for digraphs is similar to the coloring theory for undirected graphs
when independent sets of vertices are replaced by acyclic sets.
Since the directed $k$-cycle has circular chromatic number $k/(k-1)$,
for $k\ge 2$, values of $\chic$ between 1 and 2 are possible.
We show that in fact, $\chic$ takes on all rational values greater
than $1$. Furthermore, there exist digraphs of arbitrarily large
digirth and circular chromatic number. It is NP-complete to decide
if a given digraph has $\chic$ at most 2.

This is a joint work with Ga\v{s}per Fijav\v{z}, Martin Juvan, P. Mark Kayll, and Bojan Mohar.

University of Vienna

**Continuous optimization approaches to the Maximum Weighted Clique Problem**

This presentation deals with several possibilities to attack the MWCP,
which differ from the usual combinatorial solution strategies.
The central model is that of a standard quadratic optimization
problem, which consists of maximizing a quadratic form over the
standard simplex. Interconnections between dynamical systems, game
theory and optimization will be specified, which enable synergy
effects of the methods employed in these fields. Finally, we deal with
the question whether all graphs with rational weights allow for
efficient implementation of the procedures proposed. This gives rise
to a seemingly unsolved problem from number theory/combinatorics (?):
consider a symmetric matrix with positive integers on its diagonal,
such that every off-diagonal entry either is zero or equals
the sum of the diagonal entries in the same row and the same column;
is such a matrix always nonsingular?

University of Maribor

**On the natural imprint function of a graph**

The imprint function as introduced by Tardif generalizes the
notions of medians (imprints) in hypercubes (resp. Hamming
graphs) to arbitrary graphs. To a triple of vertices $x,y,z$ it
sets the unique vertex which is the closest to $y$ in the
smallest gated set that includes $x$ and $z$. The natural
algebraic question is discussed: which graphs that are
isometrically embedded in a Cartesian product of graphs are
closed for the imprint function of the product graph? We present
two characterizations of such graphs that imply an old and a new
characterization of median graphs (and of related
classes). Several questions are posed.

Slovak Academy of Sciences, Bratislava

**Directed graphs in control synthesis of DEDS modelled by Petri nets**

Discrete event dynamic systems (DEDS) are frequently used in human
practice (e.g. flexible manufacturing systems, communication systems,
some kinds of transport systems, etc.). Behaviour of such systems
depends on the occurrency of discrete events. Often, the systems are
modelled by Petri nets (PN). As to the structure PN are bipartite
graphs where one kind of vertices - places $p_1,\,p_2,\,...,\,p_n$
represent some subsystems, elementary operations, etc. and the second
kind of vertices - transitions $t_1,\,t_2,\,...,\,t_m$ represent
discrete events - e.g. starting or ending some activities. PN have
also their "dynamics" represented by marking of the places. The PN
dynamics can be described by a system of linear difference equation

**x**_{k+1} = **x**_{k} + **B**.**u**_{k}, k = 0, N

**B** = **G**^{T} - **F**

**F** **u**_{k} <= **x**_{k}

where the vector ${\bf x}_k = (\sigma^{(k)}_{p_1}, ...,
\sigma^{(k)}_{p_n})^T$ expresses the states of elementary places and
the vector ${\bf u}_k = (\gamma^{(k)}_{t_1}, ...,
\gamma^{(k)}_{p_m})^T$ represents the state of elementary transitions
in the step $k$. Here $\sigma^{(k)}_{p_i}\in \langle 0,
c_{p_i}\rangle$ with $c_{p_i}$ being the capacity (as to the integer
number of marks) of the place $p_i$ and $\sigma^{(k)}_{t_j} \in
\langle 0,\,1 \rangle$ represents the enabled (when 1) or disabled
(when 0) transition $t_j$.
${\bf F}$ is the incidence matrix of arcs oriented from positions to
transitions and ${\bf G}$ is the incidence matrix of arcs oriented
from transitions to positions. In these matrices the multiplicity of
arcs is expressed by corresponding integers greather than $1$.

During the dynamics development the system in question can achieve
different marking of places - different states. Starting from a given
initial state ${\bf x}_0$ the so called reachability tree can be
developed. Its vertices correspond to the state vectors of places and
its edges correspond to transitions making the transit between two
adjacent states possible. The reachability tree can be convert to
reachability graph. In general the number of vertices and the
structure of the reachability graph are completely different from
those of the original PN. This directed graph is very important at
testing the properties of the model (\ref{Capkovic:model}) as well as in the DEDS
control synthesis. By means of the control synthesis we mean finding
the most suitable sequence of control vectors ${\bf u}_k$, $k=0,1,
...$ that makes possible the transit of the system from the given
initial state ${\bf x}_0$ to a prescribed terminal state ${\bf x}_t$
with respect to prescribed control task specifications (like criteria,
constraints, etc.). Intersecting both the straight-lined reachability
tree developed from the initial state ${\bf x}_0$ towards the terminal
one and the backtracking reachability tree developed from the terminal
state ${\bf x}_t$ towards the initial one the solution of the control
synthesis problem can be found.

Österreichische Akademie der Wissenschaften, Wien

**Connectedness in Edge-Colored Graphs**

Given a connected graph G and an arbitrary edge-coloring of G ,
we call a path/cycle K properly colored (p.c.) if any two edges
adjacent in K have different colors.

We deal withe the question whether a connected graph with given
edge-coloring is 'color-connected', i.e. whether it is possible to find
p.c. paths between any two vertices of G . It is easy to show that G
is color-connected if every edge of G lies on a p.c. cycle; that is, if
G is 'p.c.c. covered'.

By transforming G into a new graph H having a perfect matching, it
follows that G is p.c.c. covered if and only if H is 1-extendable.
Using a result by C.H.C.Little et al., 1-extendability of H is then
translated into a criterion on when G is p.c.c. covered.

This concept of connectedness can be applied to certain questions
in logic, where formula graphs can be interpreted as edge-colored
graphs.

University of Zagreb

Montanuniversität Leoben

**Free groups, free products, and all that!**

The existence of spanning trees in connected graphs is one of the many
equivalents of the axiom of choice. In this talk it is shown how the
existence of spanning trees and forests can help to find transparent,
surprisingly simple proofs for well known theorems in combinatorial group
theory, most prominently for the Nielsen-Schreier Theorem and the subgroup
theorems of Grushko and Kurosh.

Moreover. an alternative way for the definition of free groups via groups
acting on trees is presented and a theorem that combines the
Nielsen-Schreier Theorem and the subgroup theorems of Grushko and Kurosh.

Universität Köln

University of Ljubljana

**Planar graphs without cycles of specific lengths**

A graph $G$ is $d$-degenerate if every subgraph $H$ of $G$ contains
a vertex of degree at most $d$ in $H$. For example, planar graphs are
5-degenerate. It is easy to see that planar graphs without cycles of
length 3 are 3-degenerate. It is also known that the same holds for
planar graphs without cycles of length 5. In the talk I will try to convince
the audience that planar graphs without cycles of length 6 are also
3-degenerate. Some connections with list colourings of planar graphs
will also be mentioned.

(joint work with G. Fijav\v{z}, B. Mohar, R. \v{S}krekovski)

Hungarian Academy of Sciences, Budapest

**How to use Hamiltonian theorems for combinatorial constructions**

Let $X$ be an $n$--element finite set, $0<k<n/2$ an integer.
Suppose that $(A_1,B_1)$ and $(A_2,B_2)$ are pairs of disjoint $k$-element
subsets of $X$ (that is, $|A_1|=|B_1|=|A_2|=|B_2|=k, A_1\cap B_1=\emptyset ,
A_2\cap B_2=\emptyset $). Define the distance of these pairs by
$d((A_1,B_1),(A_2,B_2))=\min \{ |A_1-A_2|+|B_1-B_2|, |A_1-B_2|+|B_1-A_2|\} $.
One can see that this is really a distance on the space of such pairs.
H. Enomoto and the author proved that the family of all $k$--element subsets
of $X$ can be paired (with one exception if their number is odd) in such a way
that the distance of the pairs is at least $k$. The proof used a Hamiltonian
theorem. Another example for this method is shown, too.

Budapest University of Technology

**Hamiltonian Chains in Hypergraphs**

Let ${\cal H}$ be a $r$--uniform hypergraph on the vertex set
$V({\cal H})=\{v_1, v_2,\ldots,v_n\}$ where $n>r$.
A cyclic ordering $(v_1, v_2,\ldots , v_n)$ of the vertex set is called a
*hamiltonian chain* iff for every $1\leq i\leq n$ there exists an
edge $E_j$ of ${\cal H}$ such that $\{v_i, v_{i+1},\ldots, v_{i+r-1}\}=E_j$.

An $r$-uniform hypergraph is *$k$-edge-hamiltonian* iff it still
contains a hamiltonian chain after deleting any $k$ edges of the
hypergraph. What is the minimum number of edges of such a hypergraph?
We give lower and upper bounds for this question for several values of
$r$ and $k$. We also give a Dirac-type theorem for the existence of a
Hamiltonian chain.

University of Ljubljana

**Constant-length TSP-tours and well-spread integer sequences**

A sequence $(a_i)$ of integers is *well-spread* if the
sums $a_i+a_j$, for $i<j$, are all different.
Let $f(N)$ denote the maximum integer $n$ for which there exists a
constant-parity, well-spread sequence $0\leq a_1<\cdots<a_n\leq N$.
We'll prove that $f(N)<(N/2)^{1/2}+O(N^{1/4})$ and give an
application concerning the
growth-rate of the maximum label $\Psi(n)$ in a certain
edge-labelling of $K_n$. Namely, in a ``most-efficient''
metric, injective edge-labelling with the property that every
Hamilton cycle has the same length, we'll show that
$2n^2-O(n^{3/2})<\Psi(n)<2n^2+O(n^{61/40})$ as $n\rightarrow\infty$.

Gunma University, Japan

**Graph products based on distance in graphs**

University of Maribor

**Crossing graphs**

Let $G$ be an isometric subgraph of a hypercube---{\em a partial cube}.
Then its crossing
graph $G^\#$ is introduced as the graph whose vertices are the
equivalence classes of the Djokovi\'c-Winkler relation $\Theta$.
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.

This is a joint work with {\em Henry Martyn Mulder}.

Universität Wien

**Quasi-isometries and metric ends**

In non-locally finite graphs there are up to now three different notions
of ends. Edge ends, vertex ends and the metric ends. Their constructions
are based on the principle of removing finitely many edges, finitely many
vertices and bounded sets of vertices, respectively. These ends are
closely related to topological spaces defined on the union of the set of
vertices and the set of ends. Especially concerning quasi-isometries there
are nice applications of the metric end topology:

1) Quasi-isometries between graphs are homeomorphisms of their metric end
spaces.

2) A graph is quasi-isometric to a tree if and only if the thicknesses of
its metric ends are all bounded by a constant.

The second theorem is joint work with R.~M\"oller. We are investigating
these geometric methods to study groups that were not finitely generated.

Wirtschaftsuniversität Wien

**Sign Pattern of Graph Eigenvectors and Hyperplane Arrangements**

Given the eigenspace of the graph Laplacian for a degenerated
eigenvalue. We show that the problem of finding all possible sign
patterns of eigenvectors to this eigenvalue is related to hyperplane
arrangements induced by a basis of this eigenspace.

This is a joint work with T{\"u}rker B{\i}y{\i}ko{\u g}lu, Wim Hordijk, and Toma{\v z} Pisanski.

University of Maribor

**Edge-deleted isometric subgraphs of hypercubes**

Isometric subgraphs of hypercubes are known as partial cubes.
We consider edge-extremal partial cubes.
Edge-critical partial cubes are introduced as the partial cubes
$G$ for which $G-e$ is not a partial cube for any edge $e$ of $G$.
An expansion theorem is proved using which one can generate many
edge-critical partial cubes. Edge-critical partial cubes are
characterized among the Cartesian product graphs. We also show
that the 3-cube and the subdivision graph of $K_4$ are the only
edge-critical partial cubes on at most 10 vertices. A list,
confirmed by computer search,
of edge-critical partial cubes up to 14 vertices, is
presented.
On the
other hand, a partial cube $G$ is called an edge-complete partial
cube if for any edge $e$ of $G$, $G-e$ is a partial cube as well.
We show some interesting properties of such graphs and
introduce a notion of cycle graph whose structure might help
in deciding which edges may be deleted in partial cubes.

University of Ljubljana

**Elementary Abelian Covers of Graphs**

Let $\mathcal{C}_G(X)$ be the set of all (equivalence classes of)
regular covers of a given connected graph $X$ along which a given
group $G \leq {\rm Aut}\,X$ of automorphisms lifts. There is
a natural lattice structure on $\mathcal{C}_G(X)$, where
$\wp_1 \leq \wp_2$ whenever $\wp_2$ factors through $\wp_1$.
The sublattice $\mathcal{C}_G(\wp)$ of covers which are below
a given cover $\wp \colon \tilde{X} \to X$
naturally corresponds to a lattice $\mathcal{N}_G(\wp)$ of
certain subgroups of the group of covering transformations. In order
to study this correspondence, some general theorems regarding
morphisms and decomposition of regular covering projections are
proved. All theorems are stated and proved combinatorially in terms of
voltage assignments, in order to facilitate computation in concrete
applications.

For a given prime $p$, let $\mathcal{C}_G^p(X) \leq {\cal C}_G(X)$
denote the sublattice of all regular covers with an elementary abelian
$p$-group of covering transformations.
There is an algorithm which explicitly constructs
$\mathcal{C}_G^p(X)$ in the sense that, for each member of
$\mathcal{C}_G^p(X)$, a concrete voltage assignment on $X$ which
determines this cover up to equivalence, is genereted.
The algorithm uses
the well known algebraic tools for finding
invariant subspaces of a given linear representation of a
group.
This is a joint work with Dragan Maru{\v s}i{\v c} and Primo{\v z} Poto{\v c}nik.

University of Ljubljana

Slovak Academy of Sciences, Kosice

**Unique Factorization Theorem for Graphs, Hypergraphs and Systems of Objects**

The Unique Factorization of Additive Hereditary Properties of Graphs into
irreducible factors has interesting corollaries with respect to the
existence of uniquely partitionable graphs. A generalization for
hypergraphs have been presented in Budapest 2001. We will discuss the
existence of uniquely partitionable systems of discrete structures
considered as objects of concrete categories.

University of Ljubljana

**Tree amalgamation of graphs and tessellations of the Cantor plane**

A general method is described which gives rise to highly symmetric
tessellations
of the Cantor sphere, i.e. the 2-sphere with the Cantor set removed and
endowed with the hyperbolic geometry with constant negative curvature.
These tessellations correspond to (almost) vertex-transitive planar graphs
with infinitely many ends. Their symmetry groups have infinitely many ends
and are amalgamations of other planar groups, possibly one or two ended or
finite ones. It is conjectured that all vertex-transitive tessellations of
the Cantor sphere can be obtained in this way.

Although the amalgamation construction is rather simple, it gives rise to some
extraordinary examples with properties that are far beyond expected. For
example, for every integer $k$, there exists a $k$-connected
vertex-transitive planar graph such that each vertex of this graph lies on
at least $k$ infinite faces. These examples disprove a conjecture of
Bonnington and Watkins that
there are no 5-connected vertex-transitive planar graphs with infinite faces.
It also disproves another conjecture of Bonnington and Watkins that in a
4-connected vertex-transitive planar graph each vertex lies on the boundary
of at most one infinite face.

TU Wien

Univerzita Mateja Bela, Banská Bystrica

**Classification of Regular Maps with a Fixed Genus**

A map is a 2-cell decomposition of a compact connected
surface. Every map can be viewed as a cellular embedding of a
graph into a compact connected surface. By the classification
theorem compact surfaces split into two infinite families: the
family of orientable surfaces and the family of non-orientable
surfaces. An automorphism of a map $\cal M$ is an automorphism of
the embedded (combinatorial) graph which extends to a
self-homeomorphism of the surface. Thus a map automorphism
permutes the vertices, the edges and the faces of the map and
preserves their incidence. Let us denote by $D$ the set of darts
of $\cal M$, edges of $\cal M$ endowed with an orientation, and by
$\Omega$ the set of f\/lags of $\cal M$, (mutually incident
triples of the form vertex-edge-face). It is not difficult to see
that the group of orientation preserving automorphisms acts
semi-regularly on the set of darts of $\cal M$ while the group of
all automorphisms acts semi-regularly on the set of f\/lags. Hence
the order of the automorphism group is bounded by $|D|$ in the
oriented case and by $|\Omega|$ in the general case. If the
equality holds the action of the group is regular and the map
itself is called orientably regular, or regular, respectively.

There are several classification problems related with the (orientable) regular maps. One of them is motivated by the well-known Hurwitz bound establishing that the number automorphisms of a compact Riemann surface of genus $g>1$ (that is the number of its conformal self-mappings) is bounded by $84(g-1)$ in the case we restrict ourselves to the orientation preserving automorphisms, and by $168(g-1)$ in the general case. Since with any map there is associated a Riemann surface, the Hurwitz bound applies for maps as well. In particular, it follows that there are only finitely many (orientable) regular maps on a surface of genus $g>1$! Thus the following two classification problems arise:

{\bf Problem 1}. Given a surface $S$ of genus $g$ classify (up to isomorphism) all the regular maps of genus $g$.

{\bf Problem 2}. Given an orientable surface $S$ of genus $g$ classify (up to isomorphism) all the orientably regular maps of genus $g$.

Although many authors have been dealt with the above problems, only particular solutions are known. In fact, the list of all (orientable) regular maps is known only for finitely many small genera in both orientable and non-orientable cases. In particular, recently Conder and Dobcs\' anyi with the help of a computer programme have produced a list of all orientably regular maps up to genus 15, and the list of all non-orientable regular maps up to genus 16. Since the family of all regular maps seems to be very complex there is some pessimism as concerns the possibility to solve Problems 1 and 2 generally.

Our goal is to solve the classification problem for an infinite sequence of non-orientable genera. As far as we know it is the first result of this sort.

The presented results were done in collaboration with A. Breda D'Azevedo (Univ. Aveiro).

University of Maribor

**Induced subgraph of Hamming graphs and flag graphs**

Two similar edge labeling are presented. One is characteristic for induced
subgraphs of Hamming graphs and the other for flag graphs of pure poset (i.e.
partialy ordered set).

University of Ljubljana

**The Genus of Gray Graph is Seven**

Using and old result one can easily prove that the genus of the
Gray graph is indeed 7. Most of the surprisingly large
number of tools taken from algebraic, geometric and topological graph
theory that were needed in the solution to this singular problem will be
addressed.

[This is a joint work in progress with Dragan Marusic and Steve Wilson.]

Université de Montréal

**The Cayley isomorphism property**

In dealing with the structure of the automorphism group of Cayley
graphs one is led to consider the following two properties that
link the automorphism group of the graph to the automorphism group
of the underlying group:
(1) A Cayley graph G = Cay(A,S) has the Cayley Isomorphism Property
if any Cayley graph on A isomorphic to G is the image ofG under an
automorphism of the group A;
(2) G = Cay(A,S) has the Cayley Automorphism Property if its
automorphism group is completely determined by the underlying group
A in the sense that the stabiliser in Aut(G) of the identity of A
(considered as a vertex of G) coincides with the stabiliser of the
generating set S in Aut(A).
Computer evidence suggests that both properties are common
among Cayley graphs. The talk will deal with work - both old and
new - concerning the relations between the two properties.

Montanuniversität Leoben

Hungarian Academy of Sciences, Budapest

**Different levels of randomness in Random Ramsey theorems**

Extremal graph theory, Ramsey theory and the theory of Random graphs are
strongly connected to each other. In the last 10 years some result concerning
Ramsey properties of random graphs were also formulated.

Starting from this field, we formulate some problems and results
which are related to different levels of randomness.
The first one is completely non-random, being the ordinary
Ramsey--Tur\'an problems and in the subsequent three problems
we formulate some randomized variations of the problem.

(Joint work with Vera T. S\'os.)

Universität Wien

**Short and Not-So-Short Cycles**

Bases of the cycle space of undirected graphs that consist of short cycles
play a significant role in computational chemistry and biology as well as
in engineering. While minimum length cycle bases can be obtained in
polynomial time it is sometimes perferable to consider other types of bases
e.g. bases derived from spanning trees or ear decompositions. Kainen's
robust cycle bases are another intersting class. Some of these notions have
a natural counterparts for strongly connected digraphs. This presentation
will focus on the open questions.

Universität Wien

**A Few Thoughts on Graphs in Chemistry and Biology**

Application of graphs in the two disciplines mentioned above has a long
tradition and originated in the nineteenth century from entirely different
needs: (i) The great diversity of molecular structures in chemistry
required some ordering principle based on molecular properties. It was
necessary, for example, to distinguish isomers and the design of formulas
based on close neighborhood relations, which, in essence, are graphs. (ii)
In biology the use of graphs, or more precisely trees, became an issue,
when neighborhood relations were introduced by Charles Darwin's theory of
descent through evolution. Phylogenetic trees are listings of time ordered
neighbors and thus correspond to directed graphs. The basis for the
ordering relation in evolutionary biology was derived since the nineteen
sixties through comparison of biopolymer sequences. (iii) Similar to
phylogenetic trees with respect to the usage of directed graphs but much
more general in the richness of graph structures is the application of
directed graphs to describe chemical reaction networks. In the light of
functional genomics chemical reaction networks became a hot topic for
representation and analysis of cellular metabolism.

Current molecular biology combines all three usages of graphs: The
representation of chemical structures, mostly based on useful
simplifications, the evolutionary aspect as well as the process oriented
reaction mechanisms. By means of RNA evolution in the test tube and a
simplified model based on properties of RNA we shall try to show how the
different aspect of molecular processes merge into a comprehensive view of
optimization through variation and selection. Neutrality with respect to
structure and function plays an essential role in this model. The RNA case
turns out to be a very appropriate and instructive example for an
explanation of origin and consequences of neutrality resulting from neutral
networks in the space of sequences.

IMFM and University of Maribor

University of Maribor

**Clar number and cuts of the benzenoid graphs**

The Clar number $CL(G)$ is the number of circles (aromatic sextets) in any of the
Clar formulas of a benzenoid graph $G$. We will see a remarkably simple method for
determining the Clar number of the cacatondensed benzenoid graph $G$:
$CL(G)$ is equal to the minimum number of cuts
that cover $G$. This result is in connection with the concept of the
resonance graph $R(G)$ of a benzenoid graph $G$.

Josef Leydold <leydold@statistik.wu-wien.ac.at> Last modified: Tue Apr 17 14:18:44 CET 2002