19-25 June 2011

Bled, Slovenia

Europe/Ljubljana timezone

Home > Contribution List

Displaying 222
contributions
out of
222

Type: Oral presentation
Track: General session

A graph $G$ is called $(H;k)$ - {\it vertex stable} if $G$ contains a subgraph isomorphic to $H$ ever after removing any of its $k$ vertices; stab$(H;k)$ denotes the minimum size among the sizes of all $(H;k)$ - vertex stable graphs.
We show that stab $(C_{n};1)$ is one of only two possible values for each $n$ and we give the exact value for infinitely many $n$'s. Furthermore we establish an uppe
... More

Presented by Agnieszka GöRLICH

Type: Oral presentation
Track: General session

\begin{document}
\title
{$(K_n,k)$ stable graphs}
\author{A. Pawe\l Wojda\\
AGH - Krak\'ow (Pl)\\
(Joint work with J.-L. Fouquet, H. Thuillier and J.-M. Vanherpe)}
\maketitle
Let $H$ be a simple graph.
A graph $G$ is called to be {\bf $(H,k)$ stable} if it contains
a subgraph isomorphic to $H$ after deletion of any subset of $k$ vertices.
The edge version of the problem was con
... More

Presented by Prof. Adam Pawel WOJDA

Type: Oral presentation
Track: Domination, Independence and Coloring of Product Graphs

An $L(j,k)$ labeling of a graph is a vertex labeling such that the difference of
the labels of any two adjacent vertices is at least $j$ and that of any two vertices of
distance $2$ is at least $k$. The minimum span of all $L(j,k)$-labelings of the graph
is denoted by $\lambda_k^j$.
In 2008, Lin and Lam provided $\lambda_1^2(G)$ for a direct product of a complete graph and a cycle $G$ with s
... More

Presented by Dr. Yoomi RHO

Type: Oral presentation
Track: Coloring of Graphs

We give a new proof of the fact that every planar graph is 5-choosable, and use it to show that every graph drawn in the plane so that the distance between every pair of crossings is at least 19 is 5-choosable. At the same time we may allow some vertices to have lists of size four only, as long as they are far apart and far from the crossings.

Presented by Mr. Zdenek DVORAK

Type: Oral presentation
Track: Algorithmic Graph Theory

The k-path partition problem, i.e. finding the minimum number of paths of length at most k that partition a graph, is an algorithmic graph problem with many real-life applications, such as in route design or communication networks. We will discuss the complexity status of this problem for various hereditary graph classes. The concept of 'boundary classes' will be introduced -- these are defined as
... More

Presented by Mr. Nicholas KORPELAINEN

Type: Oral presentation
Track: Coloring of Graphs

Given a graph $G$ and $p \in \mathbb{N}$, a proper $n$-$[p]$coloring is a mapping $f:V(G) \rightarrow 2^{\{1,\ldots,n\}}$
such that $\left\vert f(v)\right\vert = p$ for any vertex $v\in V(G)$ and $f(v)\cap f(u)=\emptyset$ for any pair of adjacent
vertices $u$ and $v$. A $n$-$[p]$coloring is a special case of a multicoloring. Finding a multicoloring of induced subgraphs of the
triangular lattice
... More

Presented by Dr. Rafal WITKOWSKI

Type: Oral presentation
Track: Graph Spectra and its Applications

In this talk we present bounds for the variation of the spectral radius of a graph G after some perturbations (or local vertex/edge modifications) of G. The perturbations considered here are the connection of a new vertex to, say, g vertices of G, the addition of a pendant edge (the previous case when g = 1) and the addition of an edge. The proposed method is based on continuous perturbations and
... More

Presented by Dr. Cristina DALFó

Type: Oral presentation
Track: Mathematical Chemistry

A graph G is said to be 1-cycle resonant if the graph G contains a cycle and every cycle in G is alternating. It is proved that a bipartite 2-connected plane graph G in which the common boundary of adjacent faces is a simple curve is 1-cycle resonant if and only if the outer face of G is alternating and each inner vertex has degree two.

Presented by Dr. Khaled SALEM

Type: Oral presentation
Track: Representations of Graphs

Let $V$ denote a vector space with finite positive dimension. We consider an ordered pair of linear transformations
$A: V\rightarrow V$ and $A^*: V\rightarrow V$ that satisfy (i) and (ii) below:
\begin{enumerate}
\item There exists a basis for $V$ with respect to which the matrix representing $A$ is irreducible tridiagonal and the matrix representing $A^*$ is diagonal.
\item There exists a ba
... More

Presented by Edward HANSON

Type: Oral presentation
Track: Representations of Graphs

We will prove a new inequality for distance-regular graphs with diameter $d\geqslant 3$. Further, we will show that equality holds in several important cases, among others for antipodal distance-regular graphs (both nonbipartite and bipartite).
Using this new inequality we will show that an infinite family of feasible intersection arrays given by
$$
\left\{ \frac{( q^2 - 2)(q+1)}{2}, \frac{(q
... More

Presented by Dr. Jernej TONEJC

Type: Oral presentation
Track: Mathematical Chemistry

Similarity searching is a standard tool for drug design, based on the idea that, given a target structure with desired properties, similar compounds chosen in large databases should have similar properties. Also for environmental property prediction, similarity relationships are currently gaining more importance in the framework of read-across. Read-across was proposed as a non-formalised approach
... More

Presented by Prof. Roberto TODESCHINI, Dr. Viviana CONSONNI

Type: Oral presentation
Track: Coloring, independence and forbidden subgraphs

An acyclic edge $k$-colouring of a graph $G$ is a proper edge $k$-colouring of $G$ such that there are no bichromatic cycles. In other words, for every two distinct colours $i$ and $j$, the subgraph induced in $G$ by all the edges which have either colour $i$ or $j$ is acyclic. The minimum number $k$ of colours such that $G$ has an acyclic edge $k$-colouring is called an acyclic chromatic index of
... More

Presented by Anna FIEDOROWICZ

Type: Oral presentation
Track: Cayley Graphs

The Pancake graph P_n which is well known because of the open Pancake problem is the Cayley graph on the symmetric group with the generating set of all prefix-reversals. It was proved [A. Kanevsky, C. Feng, Paral. Comput. 21 (1995) 923-936; J.J. Sheu, J.J. M. Tan, K.T. Chu, Proc. 23rd Workshop on Comb. Math. Comput. Theory, 2006, 85-92] that cycles of length l, 6 <= l <= n!, can be embedded in P_
... More

Presented by Elena KONSTANTINOVA

Type: Oral presentation
Track: Representations of Graphs

In 1950 the class of generalized Petersen graphs was introduced by Coxeter and around 1970 popularized by Frucht, Graver and Watkins. The family of $I$-graphs mentioned in 1988 by Bouwer {\em et al.} represents a slight further albeit important generalization of the renowned Petersen graph. We show that each $I$-graph $I(n,j,k)$ admits a unit-distance representation in the Euclidean plane.
This i
... More

Presented by Dr. Arjana ŽITNIK

Type: Oral presentation
Track: General session

Signed graphs have found numerous applications in social network analysis, data clustering, statistical physics and portfolio management. In this paper we present a new application of signed graphs to software engineering. A component based software system is developed by integrating software components already available in the market. The aim is to select components that together achieve all syst
... More

Presented by Dr. Muhammad Ali KHAN

Type: Oral presentation
Track: Association Schemes

A finite set in a Euclidean space is called an $s$-distance set if there are $s$ distances of two distinct elements in the set.
In 1977, Larman--Rogers--Seidel proved that a certain ratio related to distances of a $2$-distance set (Larman--Rogers--Seidel's ratio) must be an integer if the cardinality of the $2$-distance set is greater enough.
A symmetric association scheme of class $d$ is natu
... More

Presented by Dr. Hirotake KURIHARA

An explicit formula for obtaining generalized quadrangles and others small regular graphs of girth 8

Type: Oral presentation
Track: Polytopes and Incidence Geometries

Let $q$ be a prime power. Minimal $(q+1,8)$-cages have been
constructed as a non-degenerate quadric surface in projective
4-space $P(4, q)$. The first contribution of this paper is a
construction of these graphs in an alternative way by means of an
explicit formula using graphical terminology. Furthermore we
derive $k$-regular graphs of girth 8 for $k\le q$ having the
smallest number of ve
... More

Presented by Dr. Camino BALBUENA

Type: Oral presentation
Track: Association Schemes

A generalized odd graph is a distance-regular graph with shortest odd cycles having length $2D+1$ (the odd-girth), where $D$ is the diameter of the graph.
We show that any connected regular graph with $d+1$ distinct eigenvalues and odd-girth $2d+1$ is distance-regular, and in particular that it is a generalized odd graph.
This generalizes a result by Huang and Liu, who showed that a graph with
... More

Presented by Prof. Edwin VAN DAM

Type: Oral presentation
Track: Association Schemes

Let $(\Omega,S)$ be an association scheme where $\Omega$ is a finite set
and $S$ is a partition of $\Omega\times \Omega$.
For a positive integer $k$
we say that $(\Omega,S)$ is $k$-\textit{equivalenced} if each nonidentity element of $S$ has valency $k$.
In this talk we focus on $3$-equivalenced association schemes to show that
they are Frobenius, i.e., it is obtained from the orbitals of a F
... More

Presented by Dr. Mitsugu HIRASAKA

Type: Oral presentation
Track: General session

Arithmetic derivative is the function in
number theory, sending each prime into 1 and satisfying the
Leibniz rule $D(ab) = D(a)b + aD(b)$ for any $a,b$.
The corresponding dynamical system: $n \rightarrow D(n)$ has two
obvious attractors: $0$ and $\infty$. One of the major conjectures
about arithmetic derivative is that the corresponding directed
graph, whose vertices correspond to nonnegat
... More

Presented by Mr. Jurij KOVIC

Type: Oral presentation
Track: Cayley Graphs

We show that almost all circulant graphs and digraphs have
automorphism groups as small as possible. Of the circulant graphs
and digraphs that do not have automorphism group as small as
possible, provided the smallest prime divisor of the order of the
(di)graph is at least $5$, we show that almost all of them are
normal circulant digraphs (that is, that the left regular
representation of the
... More

Presented by Mr. Soumya BHOUMIK

Type: Oral presentation
Track: Maps and Symmetries

e derive asymptotic expansions for the numbers $U(n)$ of isomorphism classes of sensed maps on orientable surfaces
with given number of edges $n$, where we do not specify the genus and
for the numbers $A(n)$ of reflexible
maps with $n$ edges. As expected the ratio $A(n)/U(n)\to 0$ for $n\to \infty$.
This shows that almost all maps are chiral.
Moreover, we show $\log A(n)\sim\frac{1}{2}\log U(
... More

Presented by Prof. Roman NEDELA

Type: Oral presentation
Track: Metric Graph Theory

Since Kenneth Arrow’s ground breaking work on consensus in 1951 this has been a major area in mathematical economics: how to reach consensus in a rational way. This is modeled by a consensus function that satisfies certain natural and intuitively pleasing axioms. We survey recent and new results on a special type of consensus: finding an optimal location, such as the center, the median, and the
... More

Presented by Dr. Henry Martyn MULDER

Type: Oral presentation
Track: Coloring of Graphs

We prove a conjecture due to Fujita et al. which states that the balanced decomposition number of any 2-connected graph is at most $\lfloor n/2 \rfloor +1$. We use the structural properties of minimally 2-connected graph.
\def\fnbt{{\lfloor n/2 \rfloor}}
A {\em balanced colouring} of $G$ is a partition $c:V\mapsto \{+1,0,-1\}$ such
that $\sum_{v\in V}c(v)=0$. Let $R=\{x:c(x)=+1;x\in V$ and $B=\
... More

Presented by Dr. Narayanan NARAYANAN

Type: Oral presentation
Track: Association Schemes

A schurian antisymmetric coherent configuration can be defined as the coherent configuration of a permutation group~$G$ of odd order. It is well-known that for such $G$ one can find a point set the setwise stabilizer of which is trivial, and if the group $G$ is primitive, then also a base of it of size at most~$3$. Both of these results are generalized to the coherent configuration of~$G$. As a by
... More

Presented by Dr. Ilya PONOMARENKO

Type: Oral presentation
Track: General session

In this paper we introduce bipartite divisor graph for a non-empty set of positive integers. Then we prove some of its properties such as diameter, girth and so on. Our next aim is to give a construction of bipartite divisor graph for the product of two sets of positive integers. Also some properties of this graph and applications in group theory are given.

Presented by Prof. Mohammadali IRANMANESH

Type: Oral presentation
Track: Cayley Graphs

For a group $G$ and a set $S$ of generators of $G$, the diameter of the {\em Cayley graph} $\Gamma(G,S)$ is the maximum over the group elements $g\in G$ of the shortest expression $g=s_1^{i_1}\cdots s_m^{i_m}$ with $s_k\in S$ and $i_k\in \{-1,1\}$.
A first investigation on the diameter of Cayley graphs over groups in general was undertaken by Erd\H{o}s and R\'enyi. Later Babai and Seress obtain
... More

Presented by Dr. Pablo SPIGA

Type: Oral presentation
Track: General session

A graph is said to be S-prime if, whenever it is a subgraph of
a nontrivial Cartesian product graph, it is a subgraph of one
of the factors. A diagonalized Cartesian product is obtained
from a Cartesian product graph by connecting two vertices of
maximal distance by an additional edge. We show that a
diagonalized product of S-prime graphs is again S-prime.
This in turn, solves a fund
... More

Presented by Dr. Marc HELLMUTH

Type: Oral presentation
Track: Cayley Graphs

This talk is dedicated to the memory of Henry Glover.
It has been conjectured that every Cayley graph has a Hamilton cycle. Some of the results regarding this conjecture will be reviewed; with a special emphasis given to those arising from Glover's approach based on embeddings of Cayley graphs on appropriate oriented surfaces.

Presented by Prof. Dragan MARUSIC

Type: Oral presentation
Track: Mathematical Chemistry

In this talk, we present an edge and vertex decomposition of the Wiener index that is related to the concept of betweenness centrality used in social networks studies.
Some classical methods to compute W could easily be derived from this formulation and novel invariants may de defined by this mean. Another vertex decomposition of W is the transmission. If transmission and centrality are both vert
... More

Presented by Prof. Gilles CAPOROSSI

Type: Oral presentation
Track: Polytopes and Incidence Geometries

In this talk, we will present two new atlases of chirally regular polytopes.

Presented by Prof. Dimitri LEEMANS

Type: Oral presentation
Track: Maps and Symmetries

An orientable map is edge-transitive if and only if its medial is
a vertex-transitive map. Applying the techniques of classification and
construction of vertex-transitive maps we obtain a classification of
edge-transitive maps.
Since the orientation-preserving automorphism group
is of index at most two in the automorphism group of a map we know, that the quotient of the
medial map has at
... More

Presented by Mr. Ján KARABáš

Type: Oral presentation
Track: Maps and Symmetries

In this talk I report a join work with Maria Elisa Fernandes. In a previous paper we have classified the primer hypermaps with $p$ (prime) hyperfaces. Now we use this classification to classify the regular oriented hypermaps with a prime number of hyperfaces. The action of the (orientation preserving) automorphism group on the hyperfaces is primitive and described by a semidirect product of two cy
... More

Presented by Antonio BREDA D'AZEVEDO

Type: Oral presentation
Track: Maps and Symmetries

In this talk, we will consider classification of some regular Cayley maps. Especially, we will talk about classification of regular t-balanced Cayley maps for semidirect product of two cyclic groups. Classification of regular Cayley maps for dihedral groups with small valency will be also dealt with.

Presented by Dr. Young Soo KWON

Type: Oral presentation
Track: General session

For a given simple graph $G$, we define an $i$-clique as a complete subgraph of $G$ on $i$ vertices. The generating function for the number of $i$-cliques in $G$ is called the "clique polynomial" of $G$. Using elementary tools form Calculus, Hajiabolhasan and Mehrabadi showed that this polynomial has always a real root for any given simple graph $G$. As an immediate consequence, they gave a new pr
... More

Presented by Dr. Hossein TEIMOORI FAAL

Type: Oral presentation
Track: Polytopes and Incidence Geometries

Given a $r$-graph $G$ with edge chromatic number $r$, there exist a natural construction of an abstract $r$- Polytope $P_G$, called the Colorful Polytope, such that the 1- skeleton of such polytope is the graph $G$. In particular when the graph is a Cayley graph of the symmetric group $S_p$, $P_G$ is a generalization of the Permuthahedron called the Graphicahedron. In this talk we will discuss th
... More

Presented by Dr. Deborah OLIVEROS

Type: Oral presentation
Track: Algorithmic Graph Theory

Improvements of some standard algorithms for community detection will be discussed. Three types of algorithms will be discussed: algorithms for overlapping communities, for non-overlapping communities and for community dendograms.

Presented by Prof. Damir VUKIčEVIć

Type: Oral presentation
Track: Metric Graph Theory

The majority strategy for a set of clients on a connected graph can
be described as follows: if we are at vertex $v$, then we move to
neighbor $w$ of $v$ if a majority of the clients is closer to $w$
than to $v$. Following the majority strategy by Mulder [Discrete
Applied Math. 80 (1997), 97–105], plurality strategy for clients
were proposed in [ K..Balakrishnan, M.Changat and H.M.Mulder,
... More

Presented by Dr. Manoj CHANGAT

Type: Oral presentation
Track: Graph Spectra and its Applications

Isospectrality is a recurring theme in graph theory. Several constructions are known for pairs of graphs that are non isomorphic but have the same spectrum. Those often only work for one or a few particular graph matrices. One of the most famous examples was given by Godsil/McKay. Using edge switching their classical method produces graphs that are isospectral w.r.t. both the adjacency matrix and
... More

Presented by Mr. Mario THUENE

Type: Oral presentation
Track: Configurations

Regular and other highly symmetric polytopes may serve as a scaffolding on which spatial (n_k) point-line configurations can be built. We present some classes of configurations obtained by this method. We introduce the notion of a product of point-line configurations. Using this notion, we show that powers of complete multilaterals provide an infinite series of (n_k) configurations for which both
... More

Presented by Dr. Gábor GéVAY

Type: Oral presentation
Track: Algorithmic Graph Theory

The problems Path-Contractibility and Tree-Contractibility take as input an undirected graph G and an integer k, and ask whether we can obtain a path or a tree, respectively, by contracting at most k edges of G. Both problems are NP-complete, and fixed parameter tractibility follows from Courcelle's Theorem. We present algorithms with running time c^k n^{O(1)} with small constants c<5 for both pro
... More

Presented by Dr. Pim VAN 'T HOF

Type: Oral presentation
Track: Metric Graph Theory

The set of all Eulerian subgraphs of some undirected graph G
together with the geometric difference of edges forms a vector
space over GF(2). Its bases have been intensively studied and
various kinds like minimal length, fundamental or robust
cycle bases have been described and investigated.
In this talk we introduce the concept of convex cycle bases that
entirely consists of elementary cycl
... More

Presented by Josef LEYDOLD

Type: Oral presentation
Track: Mathematical Chemistry

Explicit expressions for Coulombic energies of assemblies composed of N unit charges occupying vertices of regular polygons are obtained. The self-energy of such a ring of charges is given in terms of an asymptotic series that, when replaced by an equivalent Pade approximant, yields highly accurate energy values for any N. The energy of Coulombic interactions of two rings of charges is readily c
... More

Presented by Prof. Jerzy CIOSLOWSKI

Type: Oral presentation
Track: Coloring, independence and forbidden subgraphs

The classical Ramsey Number R(a; b) is defined as the smallest number n such that all n-graphs contain either a clique of size a or a stable set of size b. It is extremely difficult to compute Ramsey Numbers; despite extensive work, only a few Ramsey Numbers (for small a and b) are known to date.
Defective Ramsey Numbers are recently introduced by Ekim and Gimbel where the notion of cliques and s
... More

Presented by Tinaz EKIM

Type: Oral presentation
Track: General session

A corollary of the Erd\H{o}s-Stone theorem is that, for any $0 \leq \alpha < 1$, graphs with density greater than $\alpha$ contain an (arbitrarily)large subgraph of density at least $\alpha+c$ for some fixed $c = c(\alpha)$, so long as the graph itself is sufficiently large. This phenomenon is known as a jump at $\alpha$. Erd\H{o}s conjectured that similar statements should hold for hypergraphs,
... More

Presented by Dr. Paul HORN

Type: Oral presentation
Track: Algorithmic Graph Theory

The net is the graph made of a triangle with three non-incident pending edges. We give an O(n^17)-time algorithm that decides whether an input graph contains a subdivision of a net as an induced subgraph.
Joint work with Maria Chudnovsky and Paul Seymour.

Presented by Mr. Nicolas TROTIGNON

Type: Oral presentation
Track: Algorithmic Graph Theory

A graph is said to be d-distinguishable if there exists a
d-labeling of its vertices which is only preserved by the identity map. The distinguishing number of a graph G is the smallest number d for which G is d-distinguishable. We show that the distinguishing number of trees and forests can be computed in linear time, improving the previously known O(n log n) time algorithm.

Presented by Dr. Antoni LOZANO

Type: Oral presentation
Track: Coloring of Graphs

We call a graph $G$ \emph{$d$-distinguishing colorable} if there exists a $d$-coloring of $G$ such that no automorphism of $G$ except the identity preserves colors. \emph{Distinguishing chromatic number} of a graph $G$, denoted by $\chi_D(G)$, is the smallest integer $d$ so that $G$ is $d$-distinguishing colorable.
Distinguishing colorings were introduced by Collins and Trenk in 2006, building
... More

Presented by Gašper FIJAVž

Type: Oral presentation
Track: General session

Let $H$ be a hypergraph with finite vertex set $X$ and finite hyperedge set $E$ and $Y\subset\mathbb{R}$ a subset of the real numbers.
A $Y$-valued function $f\colon X\to Y$ with the property that for any hyperedge $e\in E$, the condition $f(e)=\sum_{x\in e} f(x)\ge 1$ is fulfilled is called a \emph{$Y$-transversal function} of $H$.
The set $Y$ is called \emph{weight set} and the \emph{weight} o
... More

Presented by Dr. Dirk MEIERLING

Type: Oral presentation
Track: Representations of Graphs

Let $\Gamma = (X,R)$ denote a dual polar graph.
Let $A$ denote the adjacency matrix of $\Gamma$.
Fix a vertex $x \in X$. Let $A^* = A^*(x)$ denote the dual adjacency matrix of $\Gamma$ with respect to $x$.
Let $T = T(x)$ denote the subalgebra of $\mbox{Mat}_X(\C)$ generated by $A,A^*$.
Let $V = \C^X$;
view $V$ as a left $T$-module.
In this talk we discuss certain nice maps in $T$ and show h
... More

Presented by Mr. Chalermpong WORAWANNOTAI

Type: Oral presentation
Track: Coloring, independence and forbidden subgraphs

We introduce a concept of edge-distinguishing colourings of graphs.
A closed neighbourhood of an edge e in a graph G is a subgraph N[e]induced by e and all edges adjacent to it. We say that a coloring c: E(G) → C distinguishes two edges e and e’ if there does not exist an isomorphism φ of N[e] onto N[e’] such that φ(e)=e’, and φ preserves colours of c. An edge-distinguishing index
... More

Presented by Rafal KALINOWSKI

Type: Oral presentation
Track: Graph Spectra and its Applications

In this talk, I will present new eigenvalue estimates for discrete
Laplace operators on graphs such as the normalized graph Laplace
operator or the usual combinatorial graph Laplace operator. As is
well known, the smallest eigenvalue of discrete Laplace operators
on graphs can be controlled by the Cheeger constant. I will
establish a dual construction that controls the largest eigenvalue
fro
... More

Presented by Mr. Frank BAUER

Type: Oral presentation
Track: Graph Spectra and its Applications

The decrease of the spectral radius, an important characterizer of network dynamics, by removing links is investigated. The minimization of the spectral radius by removing $m$ links is shown to be an NP-complete problem, which suggests to consider heuristic strategies. Several greedy strategies are compared and several bounds on the decrease of the spectral radius are derived. The strategy that re
... More

Presented by Prof. Dragan STEVANOVIC

Type: Oral presentation
Track: Graphs and Networks in Biology

Definitions of centrality aim at quantifying the importance of a
node in a given graph. Among many others, the degree, the
betweenness and the closeness are examples of frequently used
measures of centrality. Here we ask which notion of centrality is
best suited for predicting the influence a node has on dynamics.
The concept of dynamical influence is made rigorous for a class
of dynamical r
... More

Presented by Dr. Konstantin KLEMM

Type: Oral presentation
Track: Keynote lecture

We derive an $O(n^2)$-time algorithm for calculating the sequence of numbers $g_0(G)$, $g_1(G)$, $g_2(G)$, ... of distinct ways to embed a \hbox{3-regular} \textit{Halin graph} $G$ on the respective orientable surfaces $S_0$, $S_1$, $S_2$, ... . Key topological features are a \textit{quadrangular decomposition} of plane Halin graphs and a new \textit{recombinant-strands} reassembly process that
... More

Presented by Prof. Jonathan GROSS

Type: Oral presentation
Track: Representations of Graphs

We will show that two constructions of distance-regular graphs with
intersection array $ \{7(n-1), 6(n-2), 4(n-4); 1, 6, 28\}, $ both proposed by Muzychuk, give graphs isomorphic to the bilinear forms graphs $H_2(r, 3)$. Both constructions build the graph upon a Fano plane. The first construction comes from a Cayley graph generated by the points of a Fano subplane of a larger projective plane (wh
... More

Presented by Mr. Janoš VIDALI

Type: Oral presentation
Track: Algorithmic Graph Theory

A graph is said to be a `set graph' if it is the underlying graph of the transitive closure of a hereditarily finite set; equivalently, if it admits an acyclic orientation in which all out-neighborhoods of its vertices are distinct.
The study of set graphs was initiated only recently. Even though we argue that recognizing set graphs is NP-complete, we identify, on the one hand, several necessar
... More

Presented by Mr. Alexandru I. TOMESCU

Type: Oral presentation
Track: Metric Graph Theory

The Fibonacci dimension fdim($G$) of a graph $G$ was introduced in as the smallest integer $d$ such that $G$ admits an isometric embedding into $\Gamma_d$, the $d$-dimensional Fibonacci cube.
The Fibonacci dimension of the resonance graphs of catacondensed benzenoid systems is studied. This study is inspired by
the fact, that the Fibonacci cubes are precisely the resonance graphs of a subclass
... More

Presented by Aleksander VESEL

Type: Oral presentation
Track: Graphs and Networks in Biology

In this presentation we will discuss the analysis of chemical spaces
that are spanned by grammar-based graph transformation of
molecules. Given a set of input molecules (undirected graphs) and a
set of rules (graph grammar rules) we derive a directed hypergraph
that reflects all possible molecules that can be reached. To
constraint the size of the hypergraph we consider only molecules that
a
... More

Presented by Daniel MERKLE

Type: Oral presentation
Track: Metric Graph Theory

Dominating concepts constitute a cornerstone in Graph Theory. Part of the efforts in the field have been focused in finding different mathematical frameworks where domination notions naturally arise, providing new points of view about the matter. In this work, we introduce one of these frameworks based in convexity. The main idea consists of using a notion of convexity in graphs, which has its ori
... More

Presented by Dr. María Luz PUERTAS

Type: Oral presentation
Track: General session

We give some insight into Tutte's definition of internally and externally active edges for spanning forests. Namely we prove, that every edge subset can be constructed from the edges of exactly one spanning forest by deleting a unique subset of the internally active edges and adding a unique subset of the externally active edges.

Presented by Mr. Martin TRINKS

Type: Oral presentation
Track: Graph Spectra and its Applications

We present a survey of graph
spectral techniques used in computer sciences. The survey consists
of description of particular topics from the theory of graph
spectra independently of areas of computer science where they are
used. We have described the applications of some important graph
eigenvalues (spectral radius, algebraic connectivity, least
eigenvalue etc.), eigenvectors (principal eige
... More

Presented by Prof. Dragoš CVETKOVIć

Type: Oral presentation
Track: Keynote lecture

Many questions in extremal graph theory can be phrased like this: what is the maximum of a certain linear combination of densities of given graphs in any graph G? Perhaps we have contraints on G, also in the form of fixing certain linear combinations of subgraph densities in G. Over 60-70 years, a lot of questions of this type have been posed and many have been answered. The answers are often quit
... More

Presented by László LOVáSZ

Type: Oral presentation
Track: Mathematical Chemistry

Let G be a simple, undirected, connected and finite graph with the set of vertices V(G) and the set of edges E(G). The degree of a vertex u of G is the number of edges incident to u and it is denoted by deg(u). A topological index Top(G) of G is a real number with this property that for every graph H isomorphic to G, Top(H)=Top(G). Wiener index is the first topological index in Chemistry which w
... More

Presented by Mrs. Mahdieh AZARI

Type: Oral presentation
Track: Domination, Independence and Coloring of Product Graphs

Power domination was introduced to modelize electrical networks monitoring by placement of Phase Measurement Units. In power domination, you try to monitor every vertices, either by dominating them, or possibly by using some propagation rule to monitor some new vertices. The problem was already studied in the most frequently studied products of paths, and solved in most cases. We shall address the
... More

Presented by Dr. Paul DORBEC

Type: Oral presentation
Track: Configurations

This talk will discuss a number of different infinite families of symmetric (q,k)-configurations that can be constructed using a few simple geometric lemmas; these constructions can be carried out entirely with ruler and compass, as long as a regular convex m-gon is provided to start with. In particular, a new class of symmetric, highly incident configurations will be discussed, which typically ha
... More

Presented by Dr. Leah Wrenn BERMAN

Type: Oral presentation
Track: Mathematical Chemistry

Let $\mathcal{G}_{n,k}$ denote the set of graphs with $n$ vertices and $k$ cut
edges. In this talk a special operation $C$ on graphs, that is a
generalization of some other recently introduced graph operations, will be
discussed. It is shown that the result of operation $C$ always reduces the
values of the Wiener index, Schultz index, Szeged index and of the Revised
Szeged index (also called
... More

Presented by Dr. Petra ŠPARL

Type: Oral presentation
Track: Mathematical Chemistry

In 1937 Jahn and Teller stated their remarkable theorem that all non-linear nuclear configurations are unstable for an orbitally degenerate electronic state. The instability will trigger a distortion to a lower symmetry that removes the cause of the degeneracy. In other words symmetry and degeneracy do not seem to go together and nature will always find ways to avoid such situations.
In the cu
... More

Presented by Dr. Erwin LIJNEN

Type: Oral presentation
Track: General session

The domination polynomial of a graph $G$ of order $n$ is the
polynomial $D(G,x)=\sum_{i=1}^{n} d(G,i) x^{i}$, where $d(G,i)$ is
the number of dominating vertex sets of $G$ with cardinality $i$.
A root of $D(G,x)$ is called a domination root of $G$. In this talk, we characterize graphs with at most four distinct domination roots. Finally we state some conjectures and open problems.

Presented by Dr. Saeid ALIKHANI

Type: Oral presentation
Track: Algorithmic Graph Theory

How fast can one test whether a graph is contained in another? We will survey known algorithmic results on deciding containment relations in graphs with a focus on (induced) subgraphs, (induced) minors, and contractions.

Presented by Dr. Marcin KAMIńSKI

Type: Oral presentation
Track: Maps and Symmetries

A hamiltonian embedding of a graph $G$ is a drawing of $G$ on a surface such that no edges cross and the boundary of every face is a hamilton cycle. In this talk we develop several methods of constructing hamiltonian embeddings of the complete tripartite graph $K_{n,n,n}$. For nonorientable surfaces, we build an embedding for all values of $n$. For orientable surfaces, we build an embedding for al
... More

Presented by Mr. Justin SCHROEDER

Type: Oral presentation
Track: Association Schemes

If a graph is distance-regular with classical parameters (d,b,alpha,beta) with b negative, then Weng (1999) proves that under certain assumptions there are only three possibilities for the type of the parameters. We will propose a construction of graphs of the third type, no examples of which are known yet if the diameter is at least three. This generalizes a result by Segre (1965) on hemisyste
... More

Presented by Mr. Frédéric VANHOVE

Type: Oral presentation
Track: Algorithmic Graph Theory

An efficient dominating set (or perfect code) in a graph is a set of vertices the closed neighborhoods of which partition the graph's vertex set. It is NP-complete to determine whether a given graph contains an efficient dominating set. We study the class of hereditary efficiently dominatable graphs, that is, graphs every induced subgraph of which contains an efficient dominating set. Based on a d
... More

Presented by Dr. Martin MILANIC

Type: Oral presentation
Track: Maps and Symmetries

In this talk we present a new class of embeddings of graphs into surfaces - locally maximal embeddings. An embedding is locally maximal if its genus cannot be raised by moving one end of an edge in the local rotation at the corresponding endvertex. The locally maximal genus of a graph is the minimum genus among its locally maximal embeddings. Locally maximal embeddings have many interesting struct
... More

Presented by Michal KOTRBčíK

Type: Oral presentation
Track: Algorithmic Graph Theory

The "c-pumpkin" is the graph with two vertices linked by c>0 parallel edges. A c-pumpkin-model in a graph G is a pair A,B of disjoint subsets of vertices of G, each inducing a connected subgraph of G, such that there are at least c edges in G between A and B. We focus on covering and packing c-pumpkin-models in a given graph: On the one hand, we provide an FPT algorithm running in time 2^O(k) n^O(
... More

Presented by Dr. Gwenael JORET

Type: Oral presentation
Track: Graphs and Networks in Biology

Homology is often used to analyze graph properties but usually restricted to undirected graphs. We want to give an idea of a homology which respects the direction of the arcs of directed graphs.
This homology is applied to directed graphs themselves
and not only to their underlying undirected graphs.
Moreover, we will give examples for applying this homology to directed graphs which are used t
... More

Presented by Mr. Philipp-Jens OSTERMEIER

Type: Oral presentation
Track: General session

We investigate the question of which graphs have planar emulators(a locally-surjective homomorphism from some finite planar graph)--a problem raised already in Fellows' thesis (1985) and conceptually related to the better known planar cover conjecture by Negami (1986). For over two decades, the planar emulator problem lived poorly in a shadow of Negami's conjecture--which is still open--as the two
... More

Presented by Matej KLUSACEK

Type: Oral presentation
Track: Polytopes and Incidence Geometries

It is known that $n-1$ is the maximal rank of an abstract regular polytope with automorphism group $S_n$. In this talk we give a bound for the maximal rank of an abstract regular polytope with automorphism group $Alt(n)$.

Presented by Prof. Maria Elisa FERNANDES

Type: Oral presentation
Track: Domination, Independence and Coloring of Product Graphs

Partition of $V(G)$ into sets which are independent and dominating is called an {\em idomatic partition}.
In this talk results concerning idomatic partitions of direct product of complete graphs will be presented. More precisely, such partitions are characterized up to the product of three complete graphs. For product of four (and more) complete graphs the study is done on idomatic partitions t
... More

Presented by Mr. Gasper MEKIS

Type: Oral presentation
Track: Coloring of Graphs

There are several possible deﬁnitions of an injective homomorphism of a digraph G to a digraph H . Each of them leads to a colouring parameter for oriented graphs by deﬁning the injective oriented chromatic number of an oriented graph G to be the smallest number of vertices in an oriented graph H for which there is an injective homomorphism of G to H . One possible choice leads to colourings (
... More

Presented by Dr. Nancy CLARKE

Type: Oral presentation
Track: Crossing Number

Let $G$ be a planar graph and $F$ a set of additional edges not yet in $G$. The
{\em multiple edge insertion} problem (MEI) asks for a drawing of $G+F$ with the
minimum number of pairwise edge crossings, such that the subdrawing of $G$ is
plane. As an exact solution to MEI is NP-hard for general $F$, we present the
first approximation algorithm for MEI which achieves an additive approximati
... More

Presented by Dr. Petr HLINěNý

Type: Oral presentation
Track: Association Schemes

We survey the known cometric (or Q-polynomial) association schemes having an irrational eigenvalue. We present several results, open problems and a conjecture.

Presented by Dr. William MARTIN

Type: Oral presentation
Track: Mathematical Chemistry

Several classes of graphs based on Fibonacci strings were introduced in the last 10 years as models for
interconnection networks, among them Lucas cubes. The vertex set of a Lucas cube $\Lambda_n$ is the set of all binary strings
of length $n$ without consecutive 1's and 1 in the first and the last bit. Two vertices of a Lucas cube are
adjacent if their strings differ in exactly one bit.
... More

Presented by Dr. Petra ŽIGERT

Type: Oral presentation
Track: Graph Spectra and its Applications

Recently a new concept, the Laplacian energy of a graph, has been defined ([1], [2] ) as the sum of the absolute values of the difference between the eigenvalues of the Laplacian matrix and the average degree of the vertices of G. It is the analogue of energy for the Laplacian matrix of G.
Let G be a connected graph with n vertices and m edges, the Laplacian Energy of G is then
... More

Presented by Dr. Renata DEL-VECCHIO

Type: Oral presentation
Track: Graph Spectra and its Applications

Starting from a determinant formula that relates different minors of Laplacians, we present an approach for the enumeration of spanning trees by means of electrical network transformations. This is in particular applied to self-similar, fractal-like graphs. Finally, connections to stochastic processes on fractals are discussed.

Presented by Stephan WAGNER

Type: Oral presentation
Track: Domination, Independence and Coloring of Product Graphs

Let L denote the class of graphs closed under isomorphism, substitution and taking induced subgraphs. Let P_1, P_2 be in L. We say that a graph G belongs to the class P_1 \ circ P_2 if the vertex set of G can be divided into two subsets V_1, V_2, such that for i \ in {1,2} the graph G [V_i] induced in G by V_i belongs to P_i.
Using the theorem proved by Gallai, which concerns the modular de
... More

Presented by Ewa DRGAS-BURCHARDT

Type: Oral presentation
Track: Crossing Number

According to the famous theorem of A. Kotzig on light edges in 3-connected planar graphs we investigate light edges in certain nonplanar graphs which can be drawn in the plane in such a way that each edge is crossed by at most one other edge; such graphs are called 1-planar. We prove that each 1-planar graph of minimum degree δ≥4 contains an edge with degrees its endvertices of type (4, ≥13)
... More

Presented by Mr. Peter ŠUGEREK

Type: Oral presentation
Track: Group Actions

Majorana Theory, introduced by A. A. Ivanov, is an axiomatisation of the properties of the Monster algebra, $V_{\mathbb{M}}$.
It attempts to classify and describe subalgebras of the Monster algebra using the subgroup structure of the Monster simple group $\mathbb{M}$.
For each embedding of a group $G$ into $\mathbb{M}$ we can define a Majorana representation of $G$ which defines a subalgebra of
... More

Presented by Ms. Sophie DECELLE

Type: Oral presentation
Track: Mathematical Chemistry

A rough characterization of graphs with many large eigenvalues will be presented.

Presented by Bojan MOHAR

Type: Oral presentation
Track: Mathematical Chemistry

We present an approach towards structure elucidation of bilitranslocase (BTL) transmembrane regions. BTL is a membrane protein which transports bilirubin from blood to liver cells. The sequence and secondary structure information of transmembrane segments of proteins with known 3D structure is exploited to predict the transmembrane domains of structurally unresolved target protein. With the help o
... More

Presented by Dr. Marjana NOVIč

Type: Oral presentation
Track: Coloring of Graphs

A graph is class II, if its chromatic index is at least $\Delta+1$. There are long standing open conjectures on class II graphs, and
it is a notorious difficult open problem to characterize class II graphs or even to obtain some insight into their structural properties.
In the first part we study parameters that give us some information about how far the graph is from being class 1, and we re
... More

Presented by Eckhard STEFFEN

Type: Oral presentation
Track: Metric Graph Theory

Median graphs, one of the central classes of graphs in metric graph theory, appear in different guises and applications, and relate to several other mathematical structures. They are an important model in communication networks, mathematical biology and sociology. After a brief, incomplete presentation of the theory, related to median graphs, we will focus on some recent results. In particular we
... More

Presented by Prof. Boštjan BREšAR

Type: Oral presentation
Track: Polytopes and Incidence Geometries

{\em Abstract polytopes} are partially ordered sets that mimic many of the combinatorial properties of the face lattice of a polytope. {\em Regular} abstract polytopes are the most symmetric class of these objects, and their study and interest has been greatly assisted by their almost magical correspondence to a special class of groups generated by involutions known as {\em string C-groups}. Less
... More

Presented by Dr. Gordon WILLIAMS

Type: Oral presentation
Track: Polytopes and Incidence Geometries

In recent years the problem of describing regular covers of maps and abstract polytopes has attracted attention of several researchers. Of particular interest is the problem of determining for which abstract polytopes there exists a minimal regular cover, that is, a cover which is covered by any other regular cover of the polytope.
It is known that if the polytope has rank 3 (polyhedron) then i
... More

Presented by Dr. Daniel PELLICER

Type: Oral presentation
Track: General session

For a connected graph $G$ an edge set $S$ is a restricted edge cut if $G-S$ is disconnected and there is no isolated vertices in $G-S$. The number of edges in a restricted edge cut of minimum cardinality is known as the restricted edge connectivity of $G$, denoted by $\lambda' (G)$. A restricted edge connected graph is minimally restricted $2$-edge connected if $\lambda' (G) = 2$ and $\lambda'(G-e
... More

Presented by Dr. Juan Carlos VALENZUELA

Type: Oral presentation
Track: Metric Graph Theory

Mixed fault diameter $D_{(p,q)}(G)$ is the maximum diameter among all subgraphs obtained from graph $G$ by deleting $p$ vertices and $q$ edges.
A graph is $(p,q)$+connected if it remains connected after removal of any $p$ vertices and any $q$ edges.
Mixed connectivity is a generalization of a vertex and an edge connectivity,
and mixed fault diameter generalizes both vertex fault diameter
and
... More

Presented by Dr. Janez ŽEROVNIK

Type: Oral presentation
Track: Graphs and Networks in Biology

In the literature several competing hypotheses for the evolutionary mechanisms that shape metabolic pathways and the architecture of metabolic networks have been discussed, each of which finds support from comparative analysis of genomes. Alternatively, direct simulation studies on the the principles of metabolic evolution are rare because of the demanding pre-requisites. A central component of su
... More

Presented by Christoph FLAMM

Type: Oral presentation
Track: Configurations

We investigate the existence of multilaterals in geometric and
combinatorial configurations. While in the combinatorial case it is possible to completely answer the question about the existence of configurations with prescribed and prohibited multilaterals, this remains an open question in general setting in the geometric case. We show that this question can be at least partially answered using
... More

Presented by Dr. Marko BOBEN

Type: Oral presentation
Track: Coloring of Graphs

It is known the existence of sparse hypergraphs with hight chromatic number.
A classical measure of sparseness is the clique number. The fractional chromatic
number lies between the clique number and the chromatic number. In this work we
prove the existence of uniform hypergraphs with fixed clique number and arbi\-tra\-ri\-ly
large fractional chromatic number. Our proof is constructive and pro
... More

Presented by Mrs. Johana LUVIANO

Type: Oral presentation
Track: Coloring of Graphs

Consider a simple graph $G=(V,E)$ and its \emph{proper} edge colouring $c$ with the elements of the set $\{1,2,\ldots,k\}$ (or any other $k$-element set of real numbers). We say that $c$ is \emph{neighbour sum distinguishing} if $\sum_{w\in N_G(v)}c(wv)\neq \sum_{w\in N_G(u)}c(wu)$ for every edge $uv\in E$.
We show that such colouring exists for any graph $G$ containing no isolated edges if only
... More

Presented by Jakub PRZYBYłO

Type: Oral presentation
Track: Polytopes and Incidence Geometries

For k>0 and a set X of size 2k+1, the odd graph O_{k+1} is a (k+1)-regular graph whose vertices are the k-sets of X and in which two vertices are adjacent if and only if they are disjoint. For a subset $\Gamma$ of V(O_{k+1}), the incidence relation between the elements of X and the elements of $\Gamma$ yields an incidence structure. We define $\Gamma_1$ as the set of neighbours of $\Gamma$ in this
... More

Presented by Dr. Eugenia O'REILLY-REGUEIRO

Type: Oral presentation
Track: General session

In our paper we analyze the data about works (papers, books) from time period of 1990-2010 that are collected in Zentralblatt MATH Database. This database is produced by the Berlin editorial office of FIZ Karlsruhe in cooperation with European academies and mathematical institutes. We converted these data into four 2-mode networks (works x authors, works x journals, works x keywords and works x MS
... More

Presented by Ms. Monika CERINšEK

Type: Oral presentation
Track: Representations of Graphs

Given a set $P$ of $n$ points in a Euclidean space, let $d_1>d_2>...$ be the distances generated by the set. The graph of $k$-th largest distances on $P$ is a geometric graph with vertex set $P$ whose edges correspond to the pairs of points at distance $d_k$ (the graph of $k$-th smallest distances is defined analogously). The best studied instance of this notion are probably so called diameter gra
... More

Presented by Mr. Filip MORIC

Type: Oral presentation
Track: Maps and Symmetries

A hypermap is bipartite if we can divide its set of flags in two parts in such a way that each part is a union of hypervertices, and consecutive hypervertices around a hyperedge or a hyperface are contained in alternate parts. A bipartite hypermap is bipartite-regular if its automorphism group acts transitively on each set of flags. In this talk we classify the bipartite-regular hypermaps on non-o
... More

Presented by Mr. Rui DUARTE

Type: Oral presentation
Track: General session

A non-path hamiltonian cyclically 4-edge connected bicubic graph with 102 vertices is constructed. This is the smallest non-path hamiltonian 3-connected bicubic graph known.

Presented by Dr. Jan FLOREK

Type: Oral presentation
Track: Maps and Symmetries

It is well known that for any given hyperbolic pair $(k,m)$ there exist infinitely many regular maps of valence $k$ and face length $m$ on an orientable surface, with automorphism group isomorphic to a linear fractional group. A nonorientable analogue of this result was known to be true for all pairs $(k,m)$ as above with at least one even entry. In this paper we establish the existence of such r
... More

Presented by Martin MAčAJ

Type: Oral presentation
Track: Graph Spectra and its Applications

Since the 19th century and the work of Kirchoff scientist have been studying Laplace operator on graphs. Up until now, there has been substantial amount of work on this topic and a lot of versions of Laplace operators emerged: combinatorial graph Laplacian, combinatorial Laplacian on simplicial complexes, weighted Laplacian, normalized graph Laplacian, etc. The mainstream approach was to study the
... More

Presented by Mrs. Danijela HORAK

Type: Oral presentation
Track: General session

A connected graph $\G$ is said to be {\it distance-balanced} whenever for any pair of adjacent vertices $u,v$ of
$\G$ the number of vertices closer to $u$ than to $v$ is equal to the number of vertices closer to $v$ than to $u$.
In [Bipartite graphs with balanced $(a,b)$-partitions, {\em Ars Combin.} {\bf 51} (1999), 113--119]
Handa asked whether every bipartite distance-balanced graph that is
... More

Presented by Dr. Primož ŠPARL

Type: Oral presentation
Track: Association Schemes

The IP-graph of a naturally valenced association scheme arising from the transitive
action of a group G on a set X is an undirected graph with the vertex set
{ns|s belongs to S}, each ns is the size of an orbital of G, such that two distinct vertices
nr, ns are joined by an edge if nr, ns are not coprime. Some of the properties of
this graph has been studied recently. In this paper we investig
... More

Presented by Mrs. Roghayeh HAFEZIEH

Type: Oral presentation
Track: Representations of Graphs

\documentclass[twoside]{article}
\begin{document}
\title{On Equitable Partitions of the Johnson Graph}
\author{A.\,L.~Gavrilyuk, S.\,V.\,Goryainov, and V.\,V.\,Kabanov}
\maketitle
The {\it Johnson graph} $J(n,m)$ is the graph whose vertices are all binary vectors of length~$n$ and weight~$m$ and in which any two vectors are adjacent if and only if they differ by exactly two coordinates.
... More

Presented by Prof. Vladislav KABANOV

Type: Oral presentation
Track: Configurations

A \lambda-configuration (v_k)_\lambda is a finite incidence structure of v points and v lines such that each line contains k points, through each point there are k lines, there are at most \lambda lines through two different points, and there are at most \lambda points in the intersection of two different lines.
A 1-configuration is just called configuration (or maybe combinatorial configuration)
... More

Presented by Harald GROPP

Type: Oral presentation
Track: Algorithmic Graph Theory

Golumbic et al. recently defined the so-called EPG graphs and VPG graphs: EPG graphs are Edge intersection graphs of Paths in a Grid and VPG graphs are Vertex intersection graphs of Paths in a Grid. We investigate the subclasses in which we limit the number of bends per path: 1 for EPG graphs which gives us the B_1-EPG graphs; 0 for VPG graphs which gives us the B_0-VPG graphs. We present some cha
... More

Presented by Dr. Bernard RIES

Type: Oral presentation
Track: Association Schemes

In my talk I'll present a recent progress obtained towards
the classification of the algebras in the title. This is joint work with H. Arisha, G. Chen, E. Cohen, M. Muzychuk and B. Xu.

Presented by Prof. Zvi ARAD

Type: Oral presentation
Track: Maps and Symmetries

A Leonardo polyhedron is a polyhedral 2-manifold without boundary, embedded in Euclidean 3-space with the geometric symmetry (or rotation) group of a Platonic solid and of genus $g>1$. The polyhedra are called after Leonardo's famous illustrations. Only six regular Leonardo polyhedra are known: Coxeter's four regular skew polyhedra, and the polyhedral realizations of the regular maps by Klein of g
... More

Presented by Dr. Gábor GéVAY

Type: Oral presentation
Track: Association Schemes

An antisymmetric scheme $(\Omega,{\mathcal R})$ with $2e$ classesis is called T-amorphous if any of $2^e$ possible antisymmrtic fusion of its relations with two classes determines an antisymmetric scheme with two classes. In my talk I'll present some results about such schemes.

Presented by Mikhail MUZYCHUK

Type: Oral presentation
Track: Coloring, independence and forbidden subgraphs

We study a special case of Vertex Deletion Problem: Find a minimum weight set of vertices of a given graph whose deletion gives a graph satisfying a given property.
A subset $S$ of vertices of a graph $G$ is called a {\em $k$-path vertex cover} if the graph $G\setminus S$ is $P_k$-free.
The minimum cardinality of a $k$-path vertex cover in $G$ is denoted $\psi_k(G)$.
We show that the pr
... More

Presented by Dr. Gabriel SEMANIšIN

Type: Oral presentation
Track: Representations of Graphs

Brouwer and Mesner showed that the connectivity of a connected strongly regular graph is its valency. If you now ask what is the minimal size of a set you have to throw away such that all the remaining components have size at least 2 and there are at least two components, then a natural guess would be the size of the neighbourhood of an edge $xy$ which has size $2k-2 - \lamda$. Brower conjectured
... More

Presented by Dr. Jack KOOLEN

Type: Oral presentation
Track: Graph Spectra and its Applications

Hoffman graph may be regarded as a graph obtained by
adding cliques to a simple graph,
and is formally defined to be a graph
which consists of the vertices of the simple graph
and the fat vertices expressing the cliques.
We may consider that
the simple graphs are Hoffman graphs without fat vertices.
In \cite{hlg},
R.~Woo and A.~Neumaier considered the ``sum" of Hoffman graphs,
but
... More

Presented by Dr. Tetsuji TANIGUCHI

Type: Oral presentation
Track: Coloring, independence and forbidden subgraphs

A $k$-colouring of a graph $G$ is a mapping $c$ from the set of vertices of $G$ to the set $\{1,...,k\}$ of colours. We can also regard a $k$-colouring of $G$ as a partition of the set $V(G)$ into colour classes $V_1,...,V_k$ such that each $V_i$ is the set of vertices with colour $i$. In many situations it is desired that the particular set $V_i$ has some particular property. Let $P_1,..., P_k
... More

Presented by Elżbieta SIDOROWICZ

Type: Oral presentation
Track: Maps and Symmetries

In this talk, we prove that if the Walsh bipartite map M=W(H) of a regular oriented hypermap H is also orientably regular then both M and H have the same chirality group.
The covering core of M (smallest regular map covering M) is the Walsh bipartite map of the covering core of H and the closure cover of M (greatest regular map covered by M) is the Walsh bipartite map of the closure cover of H
... More

Presented by Prof. Ilda INáCIO RODRIGUES

Type: Oral presentation
Track: General session

A necessary and sufficient condition for connectedness of direct graph bundles where the fibers are cycles is given. It is also proved that all connected direct graph bundles of cycles over cycles are Hamiltonian.

Presented by Ms. Irena HRASTNIK LADINEK

Type: Oral presentation
Track: Association Schemes

A finite group $G$ is called a Schur group if all Schur rings over $G$ are schurian, i.e., arise from suitable permutation groups. It is an open problem to characterize the Schur groups, the answer for which is unknown even for cyclic groups. In this talk we prove that if the cyclic group of order $n$ is a Schur group, then $n$ belongs to one of the following five disjoint families of integers: $p
... More

Presented by Dr. Istvan KOVACS

Type: Oral presentation
Track: Group Actions

We compare three transitivity properties of finite graphs, namely,
for a positive integer $s$, $s$-distance transitivity, $s$-geodesic
transitivity and $s$-arc transitivity. It is known that if a finite
graph is $s$-arc transitive but not $(s+1)$-arc transitive then
$s\leq 7$ and $s\neq 6$. We show that there are infinitely many
geodesic transitive graphs with this property for each of these
... More

Presented by Mr. WEI JIN

Type: Oral presentation
Track: Association Schemes

In this talk I will give some quantifications for a distance-regular graph to be close to a Taylor graph. For example we will discuss the distance-regular graphs with the number of vertices at most 3 times its valency.
This is joint work with JongYook Park (POSTECH).

Presented by Dr. Jack KOOLEN

Type: Oral presentation
Track: General session

Let $D$ be a $k$-regular digraph and let $D^-$ be obtained by reversing all the arcs of $D$. We prove that the difference $f(D)-f(D^-)$ can be arbitrarily large if $k=2$ and $f$ is the domination number, or if $f$ is the total domination number and $k=3$. On the other hand, we show that $f(D)=f(D^-)$, if $k=2$ and $f$ is the total domination number. These statements complete the results of~\cite{n
... More

Presented by Dr. Štefan GYüRKI

Type: Oral presentation
Track: Configurations

We consider generalized configurations as defined by Konrad Zindler (1890)and study their degree of irregularity and their automorphism group. We givea construction of a family of such configurations of arbitrarily large degree of irregularity. This is joint work with Tomaz Pisanski.

Presented by Brigitte SERVATIUS

Type: Oral presentation
Track: Cayley Graphs

Some connected Cayley digraphs on solvable groups do not have hamiltonian paths, but no examples are known on nilpotent groups. The talk will describe some new examples of connected, 2-generated Cayley digraphs on solvable groups that do not have hamiltonian paths, and prove that every connected, 2-generated Cayley digraph on any nilpotent group does have a hamiltonian path.

Presented by Dave Witte MORRIS

Type: Oral presentation
Track: Cayley Graphs

For a subset $A$ of $\Z_n,$ the cyclic Haar graph $H(n,A)$ is the graph with vertex set
$\Z_n^+ \cup \Z_n^-,$ and edge set $\{ \{x^+,y^-\} : x,y \in \Z_n, y - x \in A \}$.
In this talk we describe the isomorphism classes of these graphs in the case when $|A| \le 4$. As an application, we obtain a closed form solution to the enumeration problem of cyclic 3-configurations.

Presented by Mr. Sergio Hiroki KOIKE

Type: Oral presentation
Track: Coloring, independence and forbidden subgraphs

Let $G$ be a graph and let $k$ and $j$ be positive integers. A subset $D$ of the vertex set of $G$ is a
{\it $k$-dominating set} if every vertex not in $D$ has at least $k$ neighbors in $D$. The {\it $k$-domination number} $\gamma_k(G)$ is the minimum cardinality among the $k$-dominating sets of $G$. A subset $I \subseteq V(G)$ is a {\it $j$-dependent set} of $G$ if every vertex in $I$ has at mo
... More

Presented by Dr. Adriana HANSBERG

Type: Oral presentation
Track: Crossing Number

A graph $G$ is called $k$-planar if there exists its drawing $D(G)$ in the plane such that each edge of $D(G)$ is crossed at most $k$ times. For small $k$, we survey known results on $k$-planar graphs from the point of view of global properties, algorithmic aspects of recognition, local structure, colourings and hamiltonicity. We also introduce a novel concept of outer-$k$-planar graphs which are
... More

Presented by Dr. Tomáš MADARAS

Type: Oral presentation
Track: Keynote lecture

A toroid of rank rank n+1 is the quotient of a Euclidean tessellation of n-space over a rank n subgroup of the group its translations. We derive some general results on the group of automorphisms of equivelar toroids, that is the toroids obtained from the regular tessellations. We give a complete classification of equivelar toroids in ranks 3 and 4.

Presented by Prof. Asia iIvic WEISS

Type: Oral presentation
Track: Configurations

We have combinatorial, topological, and geometric (n_k)-configurations in the projective plane, i.e., n lines (combinatorial ones, pseudolines, or straigth lines) and n points and precisely k of these points are incident with each line and, vice versa, precisely k lines are incident with each point, see Grünbaum´s research monograph: "Configurations of Points and Lines", AMS, Graduate Studies i
... More

Presented by Prof. Jürgen BOKOWSKI

Type: Oral presentation
Track: Association Schemes

A Terwilliger graph is a connected non-complete graph $\Gamma$ such that, for any two vertices $u,w\in \Gamma$ at distance $2$, the subgraph induced by the common neighbors of $u$ and $w$ is a complete graph of size $\mu$ (for some fixed $\mu \ge 1$). There are only three distance-regular Terwilliger graphs known with $\mu\ge 2$, all of them are characterized by theirs intersection arrays. The thr
... More

Presented by Alexander GAVRILYUK

Type: Oral presentation
Track: Domination, Independence and Coloring of Product Graphs

A Roman domination function of a graph is a function f: V ---> {0,1,2} such that every vertex with f(v)=0 is adjacent to some vertex with f(v)=2. The Roman domination number is then the minimum of w(f)=\sum_{v \in V}f(v) over all such functions. We give the Roman domination number of the lexicographic product of graphs using a new concept of the so-called dominating pairs and introduce some new
... More

Presented by Polona PAVLIč

Type: Oral presentation
Track: Association Schemes

We say that an association scheme $\chi$ is a \textit{polygon} scheme if each $A_i$ is the adjacency matrix of the distance-$i$ graph in the polygon of diameter $d$. In this talk, we describe explicitly the algebraic structure of the Terwilliger algebra of wreath products of polygon schemes.

Presented by Dr. Kijung KIM

Type: Oral presentation
Track: General session

Let R be a commutative ring with identity and M be a multiplication R-module. For elements x and y of M, we recall that the product of Rx and Ry is denoted by xy and is defined by (IJ)M where I and J are presentation ideals of Rx and Ry, respectively. An element x in a multiplication module M is called a zero divisor if xy=0 for some non-zero element y of M. A zero-divisor graph of a multiplicatio
... More

Presented by Dr. Rezvan VARMAZYAR

Type: Oral presentation
Track: Coloring of Graphs

The b-chromatic number of a graph G is the largest integer $k$ such that $G$ admits a proper $k$-coloring in which every color class contains at least one vertex that has a neighbor in each of the other color classes. We prove that every $d$-regular graph with
at least $2d^3$ vertices has b-chromatic number $d+1$, that the b-chromatic number of an arbitrary $d$-regular graph with girth $g=5$ is a
... More

Presented by Mr. Marko JAKOVAC

Type: Oral presentation
Track: Keynote lecture

The $q$-analogue of questions about sets and subsets are questions about vector spaces and subspaces. For a prime power $q$, and an $n$-dimensional vector space $V$ over $GF(q)$, let ${V\brack k}$ denote the family of $k$-subspaces of $V$.
The vertex set of the $q$-Kneser graph $qK_{n:k}$ is ${V\brack k}$,
where $V$ is an $n$-dimensional vector space over $GF(q)$. Two vertices of $qK_{n:k}$ ar
... More

Presented by Prof. Tamas SZONYI

Type: Oral presentation
Track: Coloring of Graphs

Several reasons will be presented why the natural extension of the notion of undirected graph colorings is to partition the vertex set of a digraph into acyclic sets. Some recent results in this area, the proofs of which use probabilistic techniques, will be outlined.

Presented by Bojan MOHAR

Type: Oral presentation
Track: Group Actions

It is known that every (simple) regular graph of degree d that has a Hamilton cycle in fact possesses a second Hamilton cycle if d is odd or d is at least 300. Sheehan conjectured that the statement is also true for d=4, which would imply that it is true for every d greater than 2. Fleischner showed that Sheehan's conjecture fails for 4-regular multigraphs, but it is easily seen to be true for ver
... More

Presented by Dr. Mateja SAJNA

Type: Oral presentation
Track: General session

For a strongly connected digraph $D$ the restricted arc-connectivity
$\lambda'(D)$ is defined as the minimum cardinality of an arc-cut
over all arc-cuts $S$ satisfying that $D-S$ has a non trivial strong
component $D_1$ such that $D-V(D_1)$ contains an arc. In this work
we prove that every digraph on at least 4 vertices and of minimum
degree at least 2 is $\lambda'$-connected and $\lambda'(
... More

Presented by Dr. Pedro GARCIA VAZQUEZ

Type: Oral presentation
Track: Group Actions

This talk is the last in a series of three presentations (together with Primo\v{z} Poto\v{c}nik and Pablo Spiga) concerning the Weiss conjecture and its generalisations.
Let $\Gamma$ be a connected $G$-vertex-transitive graph, $v$ be a vertex of $\Gamma$ and $L$ be the permutation group induced by the vertex-stabiliser $G_v$ on the neighbourhood $\Gamma(v)$ of $v$. The pair $(\Gamma,G)$ is sai
... More

Presented by Mr. Gabriel VERRET

Type: Oral presentation
Track: Metric Graph Theory

Given a set of vertices $S=\{v_1,v_2,...,v_k\}$ of a connected graph
$G$, the metric representation of a vertex $v$ of $G$ with respect
to $S$ is the vector $r(v|S)=(d(v,v_1),d(v,v_2),...,d(v,v_k))$,
where $d(v,v_i)$, $i\in \{1,...,k\}$ denotes the distance between
$v$ and $v_i$. $S$ is a resolving set of $G$ if for every pair of
vertices $u,v$ of $G$, $r(u|S)\ne r(v|S)$. The metric dimensio
... More

Presented by Mr. Ismael GONZALEZ YERO

Type: Oral presentation
Track: General session

Let $G$ a simple graph. A colouring of its vertices $\varsigma:V\rightarrow\{1,...,k\}$
is called \emph{complete} if each pair of different colours appears
in a edge. The \emph{pseudoachromatic number} $\psi(G)$ is the maximum
$k$ for which there exist a complete colouring of $G$. If the colouring
is required also to be proper (i. e., that each chromatic class is
independent), then such a max
... More

Presented by Mr. Christian RUBIO-MONTIEL

Type: Oral presentation
Track: Maps and Symmetries

In the moduli space (or classification space) of complex
algebraic curves there is so called {\it real locus}, which
corresponds to the curves that can be defined over the reals. It
leads, in a natural way, to a certain simplicial complex called
the {\it real nerve} and the aim of our study is to find its
geometrical and homological dimension. Though generally we deal
with this question by t
... More

Presented by Dr. Ewa KOZłOWSKA-WALANIA

Type: Oral presentation
Track: Coloring of Graphs

We consider a proper coloring c of edges and vertices in a simple
graph and the function f(v) of sum of colors of all the edges
incident to v and the color of a vertex v. We say that a coloring c
distinguishes adjacent vertices by sums, if every two adjacent
vertices have different values of f. We conjecture that \Delta +3
colors suffice to distinguish adjacent vertices in any simple graph.
... More

Presented by Monika PILSNIAK

Type: Oral presentation
Track: Domination, Independence and Coloring of Product Graphs

The Hall-ratio $\rho(G)$ of a graph $G$ is the ratio of the number of vertices and the independence number maximized over all subgraphs of $G$. The ultimate direct Hall-ratio of a graph $G$ is defined as $\lim _{k\to \infty} \rho (G^{\times k})$, where $G^{\times k}$ denotes the $k$th direct power of $G$ (that is, $G^{\times k}$ is defined on the $k$-length sequences over the vertex set of $G$, an
... More

Presented by Ms. Agnes TOTH

Type: Oral presentation
Track: General session

Recently we started a development of net.Plexor - a new library for large network analysis and visualization that is based on the experiences gained in the development of program Pajek. In this paper we present some results of experiments how to provide functionality and algorithms, efficiently utilizing potential of modern hardware based on preferably parallel algorithms for interactive visualiza
... More

Presented by Jernej BODLAJ

Type: Oral presentation
Track: Graphs and Networks in Biology

The evolution of a family of genes is represented by a "gene tree" T, whose leafs are labeled by the genes. The internal vertices of T represent the evolutionary events that lead to the separation of lineages: gene duplications and speciation events. Genes to no occur in isolation but have been determined from known species. The evolutionary history of the species is encoded by a species tree S. T
... More

Presented by Peter STADLER

Type: Oral presentation
Track: Domination, Independence and Coloring of Product Graphs

The packing chromatic number $\chi_{\rho}(G)$ of a graph $G$ is the smallest integer $k$ such that vertices of $G$ can be partitioned into disjoint classes $X_{1}, ..., X_{k}$ where vertices in $X_{i}$ have pairwise distance greater than $i$.
We improve bounds on the packing chromatic number of the square and hexagonal grids and discuss the packing chromatic number of distance graphs, which so
... More

Presented by Mr. Bernard LIDICKY

Type: Oral presentation
Track: Representations of Graphs

Fullerenes are 3-regular graphs with faces of size 5 or 6. The number of 5-gons is necessarily 12 and the relative position of
them allows to parametrize the fullerenes in term of 10 complex
parameters. Such set of parameters is not unique and the group acting on them is one of the Mostow monodromy groups. Such parametrization was introduced by Thurston and unifies a variety of previous existing
... More

Presented by Prof. Mathieu DUTOUR SIKIRIć

Type: Oral presentation
Track: Polytopes and Incidence Geometries

Chiral polytopes are abstract polytopes with maximum rotational combinatorial symmetry. Their automorphism groups have two flag-orbits represented by pairs of adjacent flags. Regular polytopes, which are characterized by maximum combinatorial symmetry by reflection, have been well-studied, and much work has been done on their classification and groups. By contrast, still relatively little is known
... More

Presented by Prof. Egon SCHULTE

Type: Oral presentation
Track: Polytopes and Incidence Geometries

I will report on joint work with C. Haase, B. Nill and A. Paffenholz.
The {\em Birkhoff Polytop}, also known as {\em assignement polytope}, is one of the most studied polytopes. It is the convex hull of all permutation matrices.
In the talk I will propose the systematic study of the
{\em Permutation polytopes}. They are the convex hull of a subgroup of the group of $n\times n$ permutation m
... More

Presented by Prof. Barbara baumeister BAUMEISTER

Type: Oral presentation
Track: General session

A poly-antimatroid is a finite non-empty multiset system that satisfies the basic antimatroid properties. If the underlying set of a poly-antimatroid consists of n elements, then it can be represented as a subset of the n-dimensional integer lattice.
Firstly, we focus on geometrical properties of two-dimensional poly-antimatroids (n=2), and prove that they are, actually, polygons known in en
... More

Presented by Dr. Yulia KEMPNER

Type: Oral presentation
Track: Keynote lecture

The study of highly symmetric discrete structures in ordinary euclidean 3-space has a long and fascinating history tracing back to the early days of geometry. With the passage of time, various notions of polyhedral structures have attracted attention and have brought to light new exciting figures intimately related to finite or infinite groups of isometries.
A radically new, skeletal approach
... More

Presented by Prof. Egon SCHULTE

Type: Oral presentation
Track: Algorithmic Graph Theory

Cosh et al. proved that, given a hypergraph H and local edge-connectivy requirements, finding a minimum number of graph edges to be added to H in order to satisfy the requirements is NP-complete. We prove a minimax theorem and a polynomial algorithm solving two subcases of the above problem. Our proof relies on a slight generalization of Mader’s splitting off theorem to hypergraphs.

Presented by Mr. roland GRAPPE

Type: Oral presentation
Track: Polytopes and Incidence Geometries

It is known that, for almost for almost all n, the alternating group of degree n can be represented as the automorphism group of a regular polytope of rank 3. In this talk, we present examples of polytopes of high rank for all possible alternating groups.

Presented by Dr. Mark MIXER

Type: Oral presentation
Track: Coloring of Graphs

Consider a simple graph $G$ with no isolated edges and at most one isolated vertex. A labeling $w:E(G)\rightarrow \{1, 2, \dots, m\}$ is called \textit{product - irregular}, if all product degrees $pd_G(v)=\prod_{e\ni v}w(e)$ are distinct. The goal is to obtain a product - irregular labeling that minimizes the maximal label. This minimal value is called \textit{the product irregularity strength} a
... More

Presented by Dr. Marcin ANHOLCER

Type: Oral presentation
Track: Representations of Graphs

Terwilliger and Weng defined pseudo primitive idempotents. MacLean and Terwilliger drew attention to the entrywise product of those pseudo idempotents associated with modules of the Terwilliger algebra of a distance-regular graph. We will discuss these issues, particularly in the bipartite Q-polynomial context.

Presented by Michael LANG

Type: Oral presentation
Track: Maps and Symmetries

We classify pseudo-orientable hypermaps down to characteristic -3.

Presented by Prof. Domenico CATALANO

Type: Oral presentation
Track: General session

Let $P$ be a point set on the plane, and consider whether $P$ is {¥em quadrangulatable¥/}, that is, whether there exists a 2-connected bipartite plane graph $G$ with edge edge straight segment such that $V(G)=P$, that the outer cycle of $G$ coincides with Conv($P$), that each finite face of $G$ is quadrilateral. It is easy to see that it is possible if an even number of points of $P$ lie on Conv
... More

Presented by Prof. Atsuhiro NAKAMOTO

Type: Oral presentation
Track: General session

Let G be a graph and R any non trivial equivalence relation on E(G). $R$ is said to satisfy the square-property if any two adjacent edges that belong to different equivalence classes of R span exactly one square. It is shown by \v{Z}erovnik et al. that any simple graph with nontrivial weakly 2-convex equivalence relation on the edge set satisfying the square property is a graph bundle over a simpl
... More

Presented by Lydia OSTERMEIER

Type: Oral presentation
Track: Polytopes and Incidence Geometries

Joint work with: Dimitri Leemans, Mark Mixer and Tomaz Pisanski.
It is known that the incidence graph, alias Levi graph,
of any rank 2 coset geometry is an edge-transitive graph.
Thus coset geometries can be used to construct several
edge transitive graphs. In this work we consider the reverse direction.
Starting from edge-transitive graphs, we construct and an analyze associated rank 2 coset
... More

Presented by Dr. Julie DE SAEDELEER

Type: Oral presentation
Track: Coloring, independence and forbidden subgraphs

A path in an edge colored graph $G$ is called a rainbow path if
all edges have pairwise different color. Then $G$ is rainbow connected if there
exists a rainbow path between every pair of vertices of $G$ and the least
number of colors needed to obtain a rainbow connected graph is rainbow
connection number. If we demand that there must exists a shortest rainbow
path between every pair of v
... More

Presented by Prof. Iztok PETERIN

Type: Oral presentation
Track: Coloring, independence and forbidden subgraphs

\begin{abstract}
In this talk we consider edge colourings of graphs. A subgraph $H$
of a graph $G$ is called {\it rainbow subgraph}, if all its edges are coloured distinct.
In the first part we will survey the computation of rainbow numbers.
For given graphs $G, H$ the rainbow number $rb(G,H)$ is the
smallest number $m$ of colours such that if we colour the edges of
$G$ with at least $m$ d
... More

Presented by Prof. Ingo SCHIERMEYER

Type: Oral presentation
Track: Coloring, independence and forbidden subgraphs

\begin{document}
The graph $H$ is $G$-good if the Ramsey number for the pair of
graphs $G$ and $H$ is expressed as follows:
$R(G,H)=(\chi (G)-1)(|V(H)|-1)+s(G),$
where $\chi(G)$ is the chromatic number of $G$ and $s(G)$ is the minimum cardinality of colour classes over all
chromatic colourings of $V(G).$
We give the Ramsey number for a disjoint union of some $
... More

Presented by Prof. Halina BIELAK

Type: Oral presentation
Track: Crossing Number

Crossing critical graphs have attracted much attention since Širan's introductory paper in 1984. Several general constructions were proposed (crossed fences, tiles, zip-product), several properties were investigated (path-width, average degree, bandwidth), and several other research directions were proposed (almost-planar graphs, nearly-light cycles, characterization). In the talk, we review this
... More

Presented by Drago BOKAL

Type: Oral presentation
Track: Keynote lecture

Most recent achievements and open problems within the axiomatic approach to the 196,884-dimensional algebra of the Monster sporadic simple group will be discussed.

Presented by Prof. Alexander IVANOV

Type: Oral presentation
Track: Mathematical Chemistry

Let G be a connected simple graph with the vertex-set V(G)={u_1, ..., u_n}. The distance matrix D(G)=(d_ij) of G is defined by d_ij= the distance between the vertices u_i and u_j, i.e. the number of edges in the shortest path connecting these vertices in G. The diameter of G is the maximum d_ij in the matrix D(G). We will show it by d(G) or d. The distance matrix is a rich source of many graph to
... More

Presented by Prof. Ali IRANMANESH

Type: Oral presentation
Track: Association Schemes

The starting point of this subject are the famous combinatorial objects known as two-graphs. We introduce a generalization of two-graphs due to D. G. Higman, called $t$-graphs, where our emphasis is on regular $t$-graphs with $t=3$. Higman's definition is initially formulated in cohomological terms.
It turns out that regular 3-graphs are closely related to a special class of antipodal distance
... More

Presented by Mr. Daniel KALMANOVICH

Type: Oral presentation
Track: Group Actions

A map is a $2$-cell embedding of a connected graph
or multigraph in a surface, and is called (fully) {\em regular\/} if its
automorphism group has a single orbit on incident vertex-edge-face triples.
A map on an orientable surface is said to have {\em trinity symmetry\/}
if it is isomorphic to both its dual and its Petrie dual. In that case it admits
all six of the so-called {\em standa
... More

Presented by Prof. Marston CONDER

Type: Oral presentation
Track: Polytopes and Incidence Geometries

The Janko group $J_1$ has, up to duality, exactly two rank four regular polytopes.
In this talk we shall revisit the Livingstone graph and use some of its nice properties to give a construction, as a incidence geometry, of one of these regular polytopes, of Schl\"afli type $\{5,3,5\}$.

Presented by Dr. Isabel HUBARD

Type: Oral presentation
Track: Mathematical Chemistry

Suppose $G$ is a graph, $w \in V(G)$ and $e = uv, f = ab \in E(G)$. Define $n_u(e)$ and $m_u(e)$ to be the number of vertices and edges lying closer to $u$ than $v$, respectively. The quantities $n_v(e)$ and $m_v(e)$ are defined analogously. We also define $d(w, e) = min\{ d(w,u), d(w,v)\}$ and $d(e,f) = min\{ d(u,f), d(v,f)\}$. The edge Wiener, edge Szeged and Szeged indices of $G$
are defined a
... More

Presented by Prof. Seyed Ali Reza ASHRAFI GHOMROODI

Type: Oral presentation
Track: General session

A set of vertices $S$ resolves a graph $G$ if every vertex is uniquely determined by its vector of distances to the vertices in $S$. The metric dimension of $G$ is the minimum cardinality of a resolving set of $G$. In this work, we provide different approaches to the problem of determining resolving sets of Johnson and Kneser graphs, which give rise to significant bounds for the metric dimension.
... More

Presented by Mr. Antonio GONZáLEZ

Type: Oral presentation
Track: Metric Graph Theory

Many generalizations of the well-known class of median graphs have been studied so far.
Most of them share a characterization in terms of a certain gated amalgamation procedure from Cartesian
products of the graphs that belong to a special subclass of the class, i.e., the subclass
of its prime graphs. We investigated such class of graphs in which the prime graphs are all connected
bridged gr
... More

Presented by Tanja GOLOGRANC

Type: Oral presentation
Track: Representations of Graphs

A polycirculant is a cyclic cover over a pre-graph.
We present a method for drawing a polycirculant with rotational symmetry. The method is based on the drawing of its quotient
with respect to a semi-regular automorphism. In particular, we devise an efficient spring-embedding algorithm that maintains at each stage the rotational character of the representation. Finally, it is possible
to adopt
... More

Presented by Prof. Tomaž PISANSKI

Type: Oral presentation
Track: Association Schemes

Each irreducible character of an association scheme (S,X) determines a simple component of the rational adjacency algebra QS. The center and dimension of the division algebra part of this simple component is determined by the field of character values and Schur index of this character. I will survey what is known about these fields of character values and the methods available for calculating th
... More

Presented by Herman ALLEN

Type: Oral presentation
Track: Group Actions

A simple graph is called semisymmetric if it is regular,
edge-transitive but not vertex-transitive. It is easy to see that
every semisymmetric graph must be a bipartite graph with two parts
of equal size, and its automorphism group acts transitively on each
part. The semisymmetric graphs were first studied by Folkman in
1967, who proved that there exist no semisymmstric graphs of order
$
... More

Presented by Prof. shaofei DU

Type: Oral presentation
Track: Metric Graph Theory

A convex set $X$ in a graph with vertex set $V$ is a half-space if $V-X$ is also convex.
A convexity has separation property (i) $(S_2)$ if every pair of vertices belong to complementary half-spaces; (ii) $(S_3)$ if for every convex set $A\subset V(G)$ and $b\in V(G)-A$, there exist complementary half-spaces $A'$ and $B'$ such that $A\subseteq A'$ and $b\in B'$;
(iii) $(S_4)$ if for every pair $
... More

Presented by Dr. Ortrud OELLERMANN

Type: Oral presentation
Track: Keynote lecture

Snarks are nontrivial cubic graphs whose edges cannot be
properly coloured with three colours. Since their first
occurrence in the 19th century these graphs have been an object of
continuous interest especially because of their relationship to
various important problems in graph theory, such as the four
colour problem, Tutte's 5-flow conjecture, the cycle double
cover conjecture, and Fulkers
... More

Presented by Prof. Martin SKOVIERA

Type: Oral presentation
Track: Algorithmic Graph Theory

We propose an algorithm for solving the maximum weighted stable set problem in claw-free graphs that runs in O(n^3)-time, drastically improving the previous best known complexity bound.
This algorithm is based on a novel decomposition theorem for claw-free graphs, which we also present in this talk. Despite being weaker than the well-known structure result for claw-free graphs given by Chudnovsk
... More

Presented by Dr. Yuri FAENZA

Type: Oral presentation
Track: Keynote lecture

It is known that Ramsey class and generic (and universal) graph are
related notions.
We explain this connection and complement it by some new examples of
Ramsey classes.
Particularly we characterize universal and Ramsey classes defined by
existence and non-existence of homomorphisms.

Presented by Prof. Jaroslav NEšETRIL

Type: Oral presentation
Track: General session

UNO is a well-known card game whose relations with graph theory we investigate in this talk. To a set of UNO cards, we attribute an UNO-graph: its vertices correspond to the cards, and two cards are adjacent if and only if they match according to the rules of the game. It is known that a graph G is an UNO-graph if and only if G is a line graph of a bipartite graph. We characterize UNO-graph as cla
... More

Presented by Dr. Janja JEREBIC

Type: Oral presentation
Track: Graph Spectra and its Applications

An upper bound for the sum of the squares of the entries of the principal eigenvector corresponding to a vertex subset inducing a $k$-regular
subgraph is introduced and applied to the determination of an upper bound on the order of such induced subgraphs.
Furthermore, for some connected graphs we establish a lower bound for the sum of squares of the entries of the principal
eigenvector correspo
... More

Presented by Mrs. Milica ANDELIC

Type: Oral presentation
Track: General session

Let G=(V,E) be a graph and K a subset of vertices in V. Assume now that the edges of G are failing independently with given probabilities. The K-terminal reliability R(G,K) is the probability that all vertices in K are mutually connected.
In this talk a new approach for the computation of R(G,K) at a vertex separating set of G is proposed by means of lattice theoretic methods.

Presented by Mr. Frank SIMON

Type: Oral presentation
Track: Algorithmic Graph Theory

Given a subset $H$ of $k$ vertices in a connected graph $G$ the $k$-Steiner tree problem is that of finding a connected subgraph of $G$, that contains all the $k$ vertices and has the minimum number of edges among all such subgraphs. The number of edges in this subgraph is denoted by $s_G(H)$. It is well known that for $k \geq 3$, it is generally $NP$-hard to compute $s_G(H)$. The $k$-th Steiner i
... More

Presented by Matjaž KOVšE

Type: Oral presentation
Track: Metric Graph Theory

The concept of the $k$-Steiner interval is a natural generalization
of the geodesic (binary) interval. It is defined as a mapping $S:
V\times V\cdots V \rightarrow 2^{V}$ such that $S(u_1,\ldots, u_k)$
consists of all vertices in $G$ that lie on some Steiner tree with
respect to a multiset $W=(u_1\ldots,u_k)$ of vertices from $G$. We
will focus on the the following three axioms for the k-Stei
... More

Presented by Aleksandra TEPEH

Type: Oral presentation
Track: Mathematical Chemistry

Molecular connectivity indices are identified as components of the molecular accessibility. The first and second-order connectivity indices represent molecular accessibility areas and volumes, respectively, whereas higher order indices represent magnitudes in higher dimensional spaces. In identifying accessibility perimeters, we recognized the atom degrees as a measure of the accessibility perimet
... More

Presented by Dr. Ali MADANSHEKAF

Type: Oral presentation
Track: Group Actions

A graph is edge-primitive if its automorphism
group acts primitively on edges. In 1973 Weiss [Kantenprimitive
Graphen vom Grad drei. J. Combin. Theory Ser. B 15(1973), 269-288] determined cubic edge-primitive graphs. In this paper, we present a classification of tetravalent edge-primitive graphs.

Presented by Prof. Yan-Quan FENG

Type: Oral presentation
Track: Group Actions

Let s be a positive integer. A graph is s-transitive if its automorphism group is transitive on s-arcs but not on (s+1)-arcs. In this article a complete classification of tetravalent s-transitive graphs of order twice a product of two primes is given.

Presented by Mohsen GHASEMI

Type: Oral presentation
Track: Cayley Graphs

In a perfect world in which all isomorphisms between graphs must be in some sense ``natural," it would be possible to attack the problem of determining whether or not given graphs are isomorphic, simply by checking a (hopefully small) class of ``natural" isomorphisms. For Cayley graphs, ``natural" isomorphisms between the graphs Cay$(G;S)$ and Cay$(G;S')$ on the group $G$, would consist exclusivel
... More

Presented by Joy MORRIS

Type: Oral presentation
Track: Maps and Symmetries

A regular Cayley map for the cyclic group A can be defined algebraically as a group with specified generators x,y, where x is an involution, having a complementary factorization AY, where Y is the subgroup generated by y. A complete classification is given for regular Cayley maps for the cyclic group of order n, depending only on a unit r mod n, if n is odd, or mod n/2, if n is even, where r sati
... More

Presented by Prof. Thomas TUCKER

Type: Oral presentation
Track: Algorithmic Graph Theory

For a connected graph G=(V,E), a subset U of V is called a disconnected cut if U disconnects the graph and the subgraph induced by U is disconnected as well. We show that the problem to test whether a graph has a disconnected cut is NP-complete. This problem is polynomially equivalent to the following problems: testing if a graph has a 2K2-partition, testing if a graph allows a vertex-surjective h
... More

Presented by Dr. Barnaby MARTIN

Type: Oral presentation
Track: General session

It is well known that some classic conjectures in graph theory such as the Cycle Double Cover Conjecture (CDCC) and Tutte's 5-flow conjecture can be reduced to a certain family of cubic graphs called snarks, named after the elusive creature in Lewis Carroll's poem ''The hunting of the Snark''. By using improved search methods and very big computers we have now generated (caught) all snarks on 36 v
... More

Presented by Mr. Jonas HäGGLUND

Type: Oral presentation
Track: Keynote lecture

This talk begins with an introduction to infinite graphs, describes main differences to finite graphs, and continues with the free product. The free product G*H of two-connected graphs G and H is a vertex transitive, infinite graph whose blocks are isomorphic to G or H. This product is commutative and associative, but does not have a unit unless one restricts attention to vertex transitive graphs.
... More

Presented by Prof. Wilfried IMRICH

Type: Oral presentation
Track: Mathematical Chemistry

For a given graph G its Szeged weighting is deﬁned by
w(e) =n_u(e)n_v(e), where e = uv is an edge of G, n_u(e) is the number of vertices of G closer to u than to v, and n_v(e) is deﬁned analogously. The adjacency matrix of a graph weighted in this way is called its Szeged matrix. Doslic et. al. defined Szeged energy of grph the summation of absolute value of eigenvalue of Szeged matrix. In
... More

Presented by Mr. Gholamhossein FATHTABAR FIROUZJAEI

Type: Oral presentation
Track: Domination, Independence and Coloring of Product Graphs

For a graph G=(V,E) and a permutation π of V, the prism of G with respect to π is the graph πG obtained from two copies G′ and G" of G by joining u∈V′ and v∈V" if and only if v=π(u). If π is the identity, then πG=G×K₂, the cartesian product of G and K₂. The graph G×K₂ is often referred to as the prism of G and πG is called a generalized prism of G.
A universal fixer is
... More

Presented by Dr. Kieka MYNHARDT

Type: Oral presentation
Track: Domination, Independence and Coloring of Product Graphs

Although it would be ideal for a company or security firm to have all nodes in a network monitored at all times (by a person or sensor either at the node itself or adjacent) this may well be too expensive. This gives rise to the watchman problem where a person traverses the graph (returning to the starting point) in such a way that every node is either in this closed walk or adjacent to it. In the
... More

Presented by Dr. Bert HARTNELL

Type: Oral presentation
Track: Group Actions

This talk is the second in a series of three presentations (together with
Primo\v{z} Poto\v{c}nik and Gabriel Verret) concerning the Weiss
conjecture and its generalisations. Let $\Gamma$ be a connected $G$-vertex-transitive graph, $v$ be a vertex of $\Gamma$ and $L$ be the permutation group induced by the vertex stabiliser $G_v$ on the neighbourhood $\Gamma(v)$ of $v$. The pair $(\Gamma,G)$ is
... More

Presented by Dr. Pablo SPIGA

Type: Oral presentation
Track: Coloring of Graphs

This talk sketches a proof that the fractional chromatic number of the categorical product of two graphs is equal to the minimum of the fractional chromatic numbers of the two factor graphs. Using this result, we prove a conjecture of Burr-Erdos-Lovasz concerning the chromatic Ramsey number of graphs: For any positive integer $n$, there is an $n$-chromatic graph $G$ whose chromatic Ramsey number i
... More

Presented by Prof. Xuding ZHU

Type: Oral presentation
Track: Coloring, independence and forbidden subgraphs

We consider \textit{distance graphs in $\mathbb{R}^n$}. The sets of vertices of these graphs are subsets of $\mathbb{R}^n.$ Two vertices are connected by an edge if the distance between them is exactly $d$. This work deals with distance graphs $G=G(n,m,\{a_0, a_1, \ldots, a_m\},x) = (V,E)$ of certain type. Namely, such graphs have the sets of vertices
$$V =\{y=(y_1,\ldots,y_n), y_i\in \{0,1,\l
... More

Presented by Mr. Andrey KUPAVSKII

Type: Oral presentation
Track: General session

In joint work with Nick Beaton (PhD student) and Philippe Flajolet, we have studied a range of solvable self-avoiding walk and polygon models. One of these, the so-called 3-sided prudent polygons, enumerated by area, displays quite unexpected asymptotics. Writing the dominant asymptotic form of the coefficients as $a_n \sim A \times \mu^n \times n^g,$ we find $g$ to be irrational, and more surpris
... More

Presented by Prof. Anthony J GUTTMANN

Type: Oral presentation
Track: Representations of Graphs

Let (X,R) be a cometric (or Q-polynomial) association scheme with Q-polynomial ordering E_0,E_1,...,E_d on its primitive idempotents. As is well-known, a scalar multiple of E_1 is the Gram matrix of a set of |X| unit vectors in dimension m_1=rank E_1. We aim to study the convex hull of this set of vectors and its relation to the combinatorics of the original scheme.

Presented by Dr. William MARTIN

Type: Oral presentation
Track: Metric Graph Theory

A set $S$ of vertices of a graph $G$ is a geodetic set if every
vertex of $G$ lies in an interval between two vertices from $S$.
The size of a minimum geodetic set in $G$ is the geodetic
number $g(G)$ of $G$. We find that the geodetic number of the lexicographic
product $G\circ H$ for non-complete graph $H$ lies between 2 and
$3g(G)$. We characterize the graphs $G$ and $H$ for which $g(G\cir
... More

Presented by Dr. Tadeja KRANER ŠUMENJAK

Type: Oral presentation
Track: Graph Spectra and its Applications

We establish a close connection between the largest eigenvalue of a graph and the quantity
$$ \max \frac{e(X,Y)}{\sqrt{|X||Y|}}, $$
where the maximum is over all pairs $(X,Y)$ of subsets of the vertex set of the graph. Our results are best possible up to a logarithmic factor.

Presented by Prof. Vsevolod LEV

Type: Oral presentation
Track: Group Actions

A graph $\Gamma$ is said to be locally $(G,2)$-arc transitive for $G$ a subgroup of $Aut(\Gamma)$ if, for any vertex $\alpha$ of $\Gamma$, G is transitive on the 2-arcs of $\Gamma$ starting at $\alpha.$ In this talk, we will discuss recent progress toward the classification of the locally $(G,2)$-arc transitive graphs, where $Sz(q) \leq G \leq Aut(Sz(q)),$ $q = 2^{2k+1}$ for some $k \in \mathbb{N
... More

Presented by Dr. Eric SWARTZ

Type: Oral presentation
Track: General session

A set of vertices $W$ \textit{resolves} a graph $G$ if every vertex in $G$ is uniquely determined by its vector of distances to the vertices in $W$. \ The \textit{metric dimension }of $G$ is the minimum cardinality of a resolving set of $G$. \ For $n\geq 3$, an $n$-complete partite graph $G(k_1, k_2, ..., k_n)$ is a graph whose vertex set $V$ can be partitioned into $n$ subsets $V_1, V_2, ...,V_n$
... More

Presented by Mr. Suhadi Wido SAPUTRO

Type: Oral presentation
Track: General session

Some new relations have been established between Wiener indices, stability numbers and clique numbers for several classes of composite graphs that arise via graph products.

Presented by Prof. Modjtaba GHORBANI

Type: Oral presentation
Track: Polytopes and Incidence Geometries

An abstract polytope is called {\em regular\/} if its
automorphism group has a single orbit on flags (maximal chains).
In this lecture I will report on recent work on finding for each $n$
the regular $n$-polytopes with the smallest numbers of flags.
With a few small exceptions, these are also the regular
$n$-polytopes with the smallest numbers of elements, and those
with the smallest nu
... More

Presented by Prof. Marston CONDER

Type: Oral presentation
Track: Graph Spectra and its Applications

The generalised middle graph M(n,k) of a cycle consists of vertices {v0,v1,...,vn-1,u0,u1,...,un-1} and edges {viui,viu(i+1),uiu(i+k),i=0,1,2...n}. The generalised total graph T(n,k) of a cycle consists of vertices {v0,v1,...,vn-1,u0,u1,...,un-1} and edges {viv(i+1),viui,viu(i+1),uiu(i+k),i=0,1,2...n}. In this paper we obtain the spectrum of these graphs and also the bounds for the spectral radius
... More

Presented by Dr. Indulal GOPALAPILLAI

Type: Oral presentation
Track: Group Actions

Throughout this abstract, let $\Gamma$ denote a finite connected $G$-arc-transitive graph, let $G_v$ be the stabiliser of a vertex $v$, and let $G_v^{\Gamma(v)}$ be the permutation group induced by the action of $G_v$ on the neighbourhood $\Gamma(v)$.
If the valence of $\Gamma$ is $3$, then a celebrated theorem of Tutte states that the order of $G_v$ is bounded above by $48$. Motivated by this
... More

Presented by Dr. Primož POTOčNIK

Type: Oral presentation
Track: Algorithmic Graph Theory

In order to protect privacy of social network participants, graph data should be anonymized prior to its release. Most proposals in the literature aim to achieve $k$-anonymity under different assumptions about the background information of the attacker. In this paper we present a different approach based on randomizing the location of the triangles in the graph. We show that this method preserves
... More

Presented by Dr. Nacho LOPEZ LORENZO

Type: Oral presentation
Track: Representations of Graphs

Let $\mathbb F$ denote a field and let $V$ denote a vector space over $\mathbb F$ with finite positive dimension. We consider a pair of linear transformations $A:V \to V$ and $A^*:V \to V$ that satisfy the following conditions:
\begin{enumerate}
\item[\rm (i)] Each of $A,A^*$ is diagonalizable.
\item[\rm (ii)] There exists an ordering $\lbrace V_i\rbrace_{i=0}^d$ of the eigenspaces of $A$ such
... More

Presented by Prof. Paul TERWILLIGER

Type: Oral presentation
Track: Representations of Graphs

A graph is said to be $t$-tuple regular if, for any set $S$ of vertices with $|S|\le t$, the number of common neighbours of $S$ depends only on the isomorhism type of the induced subgraph on $S$. It follows immediately that a graph is 1-tuple regular iff it is regular, and it is 2-tuple regular iff it is strongly regular. Cameron and Van Lint studied 3-tuple regular graphs, and they characterized
... More

Presented by Mr. Aleksandar JURISIC

Type: Oral presentation
Track: Polytopes and Incidence Geometries

We construct an n-dimensional polytope (with 2^n vertices and n(n+1)/2+1 facets) whose volume is equal to the Tutte polynomial of the complete graph, divided by n!. The proof is bijective and consists of a triangulation of the polytope into simplices naturally corresponding to labelled forests. We present several applications, among them an improved bound for the number of labelled connected graph
... More

Presented by Dr. Matjaz KONVALINKA

Type: Oral presentation
Track: Graph Spectra and its Applications

In this talk we will discuss how the energy (i.e., the sum of the absolute values of all eigenvalues) of so-called tadpole graphs $P_n^k$ , which are obtained by joining a vertex of a cycle $C_k$ to one of the ends of a path $P_{n-k}$, depends on $k$. Combined with earlier results [Y. Hou, I. Gutman, C.-W. Woo, Unicyclic graphs with maximal energy, Linear Algebra Appl. 356 (2002) 27-36 and E.O.D.A
... More

Presented by Mr. Eric Ould Dadah ANDRIANTIANA

Type: Oral presentation
Track: Crossing Number

We present the uniform approach to Euler and Leighton bound
optimization through new operator L(p,w). We focus on special cases
of this operator. One special case is that we can investigate
weighted subgraph of G that yields the maximum Euler bound for the
crossing number of G. We prove that there always exists an integer
optimal solution for this optimization problem. This means that the
so
... More

Presented by Ms. Mojca BRAčIč

Type: Oral presentation
Track: General session

A subset $S$ of vertices of a graph $G$ is called a $k$-path vertex cover if every path of order $k$ in $G$ contains at least one vertex from $S$. Denote by $\psi_k(G)$ the minimum cardinality of a $k$-path vertex cover in $G$. In this paper present an upper bound for $\psi_3(G)$ of graphs with given average degree. We also give a lower bound for $\psi_k(G)$ of regular graphs and some results for
... More

Presented by Dr. Andrej TARANENKO

Type: Oral presentation
Track: Domination, Independence and Coloring of Product Graphs

In the 1960’s V.G. Vizing conjectured that the domination number of the Cartesian product of two graphs is at least as large as the product of their domination numbers. In this talk we will survey progress on this conjecture and also present some open questions related to it.

Presented by Dr. Douglas RALL

Type: Oral presentation
Track: Association Schemes

The Weisfeiler-Leman (WL) method takes as input an arbitrary graph $\Gamma$, and returns the minimal coherent algebra containing the basis relations of $\Gamma$ (e.g. the set of edges and non-edges). We will discuss some well-known properties of a common higher-dimensional generalisation of this method, the $k$-dim WL method, in particular with respect to its application to the graph isomorphism p
... More

Presented by Mr. Brendan DOUGLAS

Type: Oral presentation
Track: General session

Let $R$ be a commutative ring. The idea of associating a graph with the zero-divisors $R$ was introduced by Beck in 1988, where he talked about the colorings of such graphs. By the definition he gave, every element of the ring $R$ was a vertex in the graph, and two vertices $x, y$ were adjacent if and only if $x y = 0$ (\cite{B}). Later, D. F. Anderson and P. S. Livingston (\cite{AL}) considered o
... More

Presented by Dr. Ahmad YOUSEFIAN DARANI

Type: Oral presentation
Track: Coloring, independence and forbidden subgraphs

Let $G$ be a $\lambda_k$-connected graph. $G$ is called
$\lambda_k$-optimal, if its $k$-restricted edge-connectivity
$\lambda_k(G)$ equals its minimum $k$-edge degree. $G$ is called super-$\lambda_k$ if every $\lambda_k$-cut isolates a connected subgraph of order $k$.
Firstly, we will introduce a lower bound on the order of $2$-fragments in triangle-free graphs that are not $\lambda_2$-optima
... More

Presented by Mr. Andreas HOLTKAMP