19th LL-Seminar on Graph Theory

Walecki tournaments

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.

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.]

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.

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?

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.

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.

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.

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.

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)

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.

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.

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$.

Graph products based on distance in graphs

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}.

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.

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.

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.

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.

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.

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.

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).

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).

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.]

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.

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.)

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.

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.

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$.