# Bled'11 - 7th Slovenian International Conference on Graph Theory

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 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 kth 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
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