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 definitions of an injective homomorphism of a digraph G to a digraph H . Each of them leads to a colouring parameter for oriented graphs by defining the injective oriented chromatic number of an oriented graph G to be the smallest number of vertices in an oriented graph H for which there is an injective homomorphism of G to H . One possible choice leads to colourings ( ... More
Presented by Dr. Nancy CLARKE
Type: Oral presentation Track: Crossing Number
Let $G$ be a planar graph and $F$ a set of additional edges not yet in $G$. The {\em multiple edge insertion} problem (MEI) asks for a drawing of $G+F$ with the minimum number of pairwise edge crossings, such that the subdrawing of $G$ is plane. As an exact solution to MEI is NP-hard for general $F$, we present the first approximation algorithm for MEI which achieves an additive approximati ... More
Presented by Dr. Petr HLINěNý
Type: Oral presentation Track: Association Schemes
We survey the known cometric (or Q-polynomial) association schemes having an irrational eigenvalue. We present several results, open problems and a conjecture.
Presented by Dr. William MARTIN
Type: Oral presentation Track: Mathematical Chemistry
Several classes of graphs based on Fibonacci strings were introduced in the last 10 years as models for interconnection networks, among them Lucas cubes. The vertex set of a Lucas cube $\Lambda_n$ is the set of all binary strings of length $n$ without consecutive 1's and 1 in the first and the last bit. Two vertices of a Lucas cube are adjacent if their strings differ in exactly one bit. ... More
Presented by Dr. Petra ŽIGERT
Type: Oral presentation Track: Graph Spectra and its Applications
Recently a new concept, the Laplacian energy of a graph, has been defined ([1], [2] ) as the sum of the absolute values of the difference between the eigenvalues of the Laplacian matrix and the average degree of the vertices of G. It is the analogue of energy for the Laplacian matrix of G. Let G be a connected graph with n vertices and m edges, the Laplacian Energy of G is then ... More
Presented by Dr. Renata DEL-VECCHIO
Type: Oral presentation Track: Graph Spectra and its Applications
Starting from a determinant formula that relates different minors of Laplacians, we present an approach for the enumeration of spanning trees by means of electrical network transformations. This is in particular applied to self-similar, fractal-like graphs. Finally, connections to stochastic processes on fractals are discussed.
Presented by Stephan WAGNER
Type: Oral presentation Track: Domination, Independence and Coloring of Product Graphs
Let L denote the class of graphs closed under isomorphism, substitution and taking induced subgraphs. Let P_1, P_2 be in L. We say that a graph G belongs to the class P_1 \ circ P_2 if the vertex set of G can be divided into two subsets V_1, V_2, such that for i \ in {1,2} the graph G [V_i] induced in G by V_i belongs to P_i. Using the theorem proved by Gallai, which concerns the modular de ... More
Presented by Ewa DRGAS-BURCHARDT
Type: Oral presentation Track: Crossing Number
According to the famous theorem of A. Kotzig on light edges in 3-connected planar graphs we investigate light edges in certain nonplanar graphs which can be drawn in the plane in such a way that each edge is crossed by at most one other edge; such graphs are called 1-planar. We prove that each 1-planar graph of minimum degree δ≥4 contains an edge with degrees its endvertices of type (4, ≥13) ... More
Presented by Mr. Peter ŠUGEREK
Type: Oral presentation Track: Group Actions
Majorana Theory, introduced by A. A. Ivanov, is an axiomatisation of the properties of the Monster algebra, $V_{\mathbb{M}}$. It attempts to classify and describe subalgebras of the Monster algebra using the subgroup structure of the Monster simple group $\mathbb{M}$. For each embedding of a group $G$ into $\mathbb{M}$ we can define a Majorana representation of $G$ which defines a subalgebra of ... More
Presented by Ms. Sophie DECELLE
Type: Oral presentation Track: Mathematical Chemistry
A rough characterization of graphs with many large eigenvalues will be presented.
Presented by Bojan MOHAR
Type: Oral presentation Track: Mathematical Chemistry
We present an approach towards structure elucidation of bilitranslocase (BTL) transmembrane regions. BTL is a membrane protein which transports bilirubin from blood to liver cells. The sequence and secondary structure information of transmembrane segments of proteins with known 3D structure is exploited to predict the transmembrane domains of structurally unresolved target protein. With the help o ... More
Presented by Dr. Marjana NOVIč
Type: Oral presentation Track: Coloring of Graphs
A graph is class II, if its chromatic index is at least $\Delta+1$. There are long standing open conjectures on class II graphs, and it is a notorious difficult open problem to characterize class II graphs or even to obtain some insight into their structural properties. In the first part we study parameters that give us some information about how far the graph is from being class 1, and we re ... More
Presented by Eckhard STEFFEN
Type: Oral presentation Track: Metric Graph Theory
Median graphs, one of the central classes of graphs in metric graph theory, appear in different guises and applications, and relate to several other mathematical structures. They are an important model in communication networks, mathematical biology and sociology. After a brief, incomplete presentation of the theory, related to median graphs, we will focus on some recent results. In particular we ... More
Presented by Prof. Boštjan BREšAR
Type: Oral presentation Track: Polytopes and Incidence Geometries
{\em Abstract polytopes} are partially ordered sets that mimic many of the combinatorial properties of the face lattice of a polytope. {\em Regular} abstract polytopes are the most symmetric class of these objects, and their study and interest has been greatly assisted by their almost magical correspondence to a special class of groups generated by involutions known as {\em string C-groups}. Less ... More
Presented by Dr. Gordon WILLIAMS
Type: Oral presentation Track: Polytopes and Incidence Geometries
In recent years the problem of describing regular covers of maps and abstract polytopes has attracted attention of several researchers. Of particular interest is the problem of determining for which abstract polytopes there exists a minimal regular cover, that is, a cover which is covered by any other regular cover of the polytope. It is known that if the polytope has rank 3 (polyhedron) then i ... More
Presented by Dr. Daniel PELLICER
Type: Oral presentation Track: General session
For a connected graph $G$ an edge set $S$ is a restricted edge cut if $G-S$ is disconnected and there is no isolated vertices in $G-S$. The number of edges in a restricted edge cut of minimum cardinality is known as the restricted edge connectivity of $G$, denoted by $\lambda' (G)$. A restricted edge connected graph is minimally restricted $2$-edge connected if $\lambda' (G) = 2$ and $\lambda'(G-e ... More
Presented by Dr. Juan Carlos VALENZUELA
Type: Oral presentation Track: Metric Graph Theory
Mixed fault diameter $D_{(p,q)}(G)$ is the maximum diameter among all subgraphs obtained from graph $G$ by deleting $p$ vertices and $q$ edges. A graph is $(p,q)$+connected if it remains connected after removal of any $p$ vertices and any $q$ edges. Mixed connectivity is a generalization of a vertex and an edge connectivity, and mixed fault diameter generalizes both vertex fault diameter and ... More
Presented by Dr. Janez ŽEROVNIK
Type: Oral presentation Track: Graphs and Networks in Biology
In the literature several competing hypotheses for the evolutionary mechanisms that shape metabolic pathways and the architecture of metabolic networks have been discussed, each of which finds support from comparative analysis of genomes. Alternatively, direct simulation studies on the the principles of metabolic evolution are rare because of the demanding pre-requisites. A central component of su ... More
Presented by Christoph FLAMM
Type: Oral presentation Track: Configurations
We investigate the existence of multilaterals in geometric and combinatorial configurations. While in the combinatorial case it is possible to completely answer the question about the existence of configurations with prescribed and prohibited multilaterals, this remains an open question in general setting in the geometric case. We show that this question can be at least partially answered using ... More
Presented by Dr. Marko BOBEN
Type: Oral presentation Track: Coloring of Graphs
It is known the existence of sparse hypergraphs with hight chromatic number. A classical measure of sparseness is the clique number. The fractional chromatic number lies between the clique number and the chromatic number. In this work we prove the existence of uniform hypergraphs with fixed clique number and arbi\-tra\-ri\-ly large fractional chromatic number. Our proof is constructive and pro ... More
Presented by Mrs. Johana LUVIANO
Type: Oral presentation Track: Coloring of Graphs
Consider a simple graph $G=(V,E)$ and its \emph{proper} edge colouring $c$ with the elements of the set $\{1,2,\ldots,k\}$ (or any other $k$-element set of real numbers). We say that $c$ is \emph{neighbour sum distinguishing} if $\sum_{w\in N_G(v)}c(wv)\neq \sum_{w\in N_G(u)}c(wu)$ for every edge $uv\in E$. We show that such colouring exists for any graph $G$ containing no isolated edges if only ... More
Presented by Jakub PRZYBYłO
Type: Oral presentation Track: Polytopes and Incidence Geometries
For k>0 and a set X of size 2k+1, the odd graph O_{k+1} is a (k+1)-regular graph whose vertices are the k-sets of X and in which two vertices are adjacent if and only if they are disjoint. For a subset $\Gamma$ of V(O_{k+1}), the incidence relation between the elements of X and the elements of $\Gamma$ yields an incidence structure. We define $\Gamma_1$ as the set of neighbours of $\Gamma$ in this ... More
Presented by Dr. Eugenia O'REILLY-REGUEIRO
Type: Oral presentation Track: General session
In our paper we analyze the data about works (papers, books) from time period of 1990-2010 that are collected in Zentralblatt MATH Database. This database is produced by the Berlin editorial office of FIZ Karlsruhe in cooperation with European academies and mathematical institutes. We converted these data into four 2-mode networks (works x authors, works x journals, works x keywords and works x MS ... More
Presented by Ms. Monika CERINšEK
Type: Oral presentation Track: Representations of Graphs
Given a set $P$ of $n$ points in a Euclidean space, let $d_1>d_2>...$ be the distances generated by the set. The graph of $k$-th largest distances on $P$ is a geometric graph with vertex set $P$ whose edges correspond to the pairs of points at distance $d_k$ (the graph of $k$-th smallest distances is defined analogously). The best studied instance of this notion are probably so called diameter gra ... More
Presented by Mr. Filip MORIC
Type: Oral presentation Track: Maps and Symmetries
A hypermap is bipartite if we can divide its set of flags in two parts in such a way that each part is a union of hypervertices, and consecutive hypervertices around a hyperedge or a hyperface are contained in alternate parts. A bipartite hypermap is bipartite-regular if its automorphism group acts transitively on each set of flags. In this talk we classify the bipartite-regular hypermaps on non-o ... More
Presented by Mr. Rui DUARTE
Type: Oral presentation Track: General session
A non-path hamiltonian cyclically 4-edge connected bicubic graph with 102 vertices is constructed. This is the smallest non-path hamiltonian 3-connected bicubic graph known.
Presented by Dr. Jan FLOREK
Type: Oral presentation Track: Maps and Symmetries
It is well known that for any given hyperbolic pair $(k,m)$ there exist infinitely many regular maps of valence $k$ and face length $m$ on an orientable surface, with automorphism group isomorphic to a linear fractional group. A nonorientable analogue of this result was known to be true for all pairs $(k,m)$ as above with at least one even entry. In this paper we establish the existence of such r ... More
Presented by Martin MAčAJ
Type: Oral presentation Track: Graph Spectra and its Applications
Since the 19th century and the work of Kirchoff scientist have been studying Laplace operator on graphs. Up until now, there has been substantial amount of work on this topic and a lot of versions of Laplace operators emerged: combinatorial graph Laplacian, combinatorial Laplacian on simplicial complexes, weighted Laplacian, normalized graph Laplacian, etc. The mainstream approach was to study the ... More
Presented by Mrs. Danijela HORAK
Type: Oral presentation Track: General session
A connected graph $\G$ is said to be {\it distance-balanced} whenever for any pair of adjacent vertices $u,v$ of $\G$ the number of vertices closer to $u$ than to $v$ is equal to the number of vertices closer to $v$ than to $u$. In [Bipartite graphs with balanced $(a,b)$-partitions, {\em Ars Combin.} {\bf 51} (1999), 113--119] Handa asked whether every bipartite distance-balanced graph that is ... More
Presented by Dr. Primož ŠPARL
Type: Oral presentation Track: Association Schemes
The IP-graph of a naturally valenced association scheme arising from the transitive action of a group G on a set X is an undirected graph with the vertex set {ns|s belongs to S}, each ns is the size of an orbital of G, such that two distinct vertices nr, ns are joined by an edge if nr, ns are not coprime. Some of the properties of this graph has been studied recently. In this paper we investig ... More
Presented by Mrs. Roghayeh HAFEZIEH
Type: Oral presentation Track: Representations of Graphs
\documentclass[twoside]{article} \begin{document} \title{On Equitable Partitions of the Johnson Graph} \author{A.\,L.~Gavrilyuk, S.\,V.\,Goryainov, and V.\,V.\,Kabanov} \maketitle The {\it Johnson graph} $J(n,m)$ is the graph whose vertices are all binary vectors of length~$n$ and weight~$m$ and in which any two vectors are adjacent if and only if they differ by exactly two coordinates. ... More
Presented by Prof. Vladislav KABANOV
Type: Oral presentation Track: Configurations
A \lambda-configuration (v_k)_\lambda is a finite incidence structure of v points and v lines such that each line contains k points, through each point there are k lines, there are at most \lambda lines through two different points, and there are at most \lambda points in the intersection of two different lines. A 1-configuration is just called configuration (or maybe combinatorial configuration) ... More
Presented by Harald GROPP
Type: Oral presentation Track: Algorithmic Graph Theory
Golumbic et al. recently defined the so-called EPG graphs and VPG graphs: EPG graphs are Edge intersection graphs of Paths in a Grid and VPG graphs are Vertex intersection graphs of Paths in a Grid. We investigate the subclasses in which we limit the number of bends per path: 1 for EPG graphs which gives us the B_1-EPG graphs; 0 for VPG graphs which gives us the B_0-VPG graphs. We present some cha ... More
Presented by Dr. Bernard RIES
Type: Oral presentation Track: Association Schemes
In my talk I'll present a recent progress obtained towards the classification of the algebras in the title. This is joint work with H. Arisha, G. Chen, E. Cohen, M. Muzychuk and B. Xu.
Presented by Prof. Zvi ARAD
Type: Oral presentation Track: Maps and Symmetries
A Leonardo polyhedron is a polyhedral 2-manifold without boundary, embedded in Euclidean 3-space with the geometric symmetry (or rotation) group of a Platonic solid and of genus $g>1$. The polyhedra are called after Leonardo's famous illustrations. Only six regular Leonardo polyhedra are known: Coxeter's four regular skew polyhedra, and the polyhedral realizations of the regular maps by Klein of g ... More
Presented by Dr. Gábor GéVAY
Type: Oral presentation Track: Association Schemes
An antisymmetric scheme $(\Omega,{\mathcal R})$ with $2e$ classesis is called T-amorphous if any of $2^e$ possible antisymmrtic fusion of its relations with two classes determines an antisymmetric scheme with two classes. In my talk I'll present some results about such schemes.
Presented by Mikhail MUZYCHUK
Type: Oral presentation Track: Coloring, independence and forbidden subgraphs
We study a special case of Vertex Deletion Problem: Find a minimum weight set of vertices of a given graph whose deletion gives a graph satisfying a given property. A subset $S$ of vertices of a graph $G$ is called a {\em $k$-path vertex cover} if the graph $G\setminus S$ is $P_k$-free. The minimum cardinality of a $k$-path vertex cover in $G$ is denoted $\psi_k(G)$. We show that the pr ... More
Presented by Dr. Gabriel SEMANIšIN
Type: Oral presentation Track: Representations of Graphs
Brouwer and Mesner showed that the connectivity of a connected strongly regular graph is its valency. If you now ask what is the minimal size of a set you have to throw away such that all the remaining components have size at least 2 and there are at least two components, then a natural guess would be the size of the neighbourhood of an edge $xy$ which has size $2k-2 - \lamda$. Brower conjectured ... More
Presented by Dr. Jack KOOLEN
Type: Oral presentation Track: Graph Spectra and its Applications
Hoffman graph may be regarded as a graph obtained by adding cliques to a simple graph, and is formally defined to be a graph which consists of the vertices of the simple graph and the fat vertices expressing the cliques. We may consider that the simple graphs are Hoffman graphs without fat vertices. In \cite{hlg}, R.~Woo and A.~Neumaier considered the ``sum" of Hoffman graphs, but ... More
Presented by Dr. Tetsuji TANIGUCHI
Type: Oral presentation Track: Coloring, independence and forbidden subgraphs
A $k$-colouring of a graph $G$ is a mapping $c$ from the set of vertices of $G$ to the set $\{1,...,k\}$ of colours. We can also regard a $k$-colouring of $G$ as a partition of the set $V(G)$ into colour classes $V_1,...,V_k$ such that each $V_i$ is the set of vertices with colour $i$. In many situations it is desired that the particular set $V_i$ has some particular property. Let $P_1,..., P_k ... More
Presented by Elżbieta SIDOROWICZ
Type: Oral presentation Track: Maps and Symmetries
In this talk, we prove that if the Walsh bipartite map M=W(H) of a regular oriented hypermap H is also orientably regular then both M and H have the same chirality group. The covering core of M (smallest regular map covering M) is the Walsh bipartite map of the covering core of H and the closure cover of M (greatest regular map covered by M) is the Walsh bipartite map of the closure cover of H ... More
Presented by Prof. Ilda INáCIO RODRIGUES
Type: Oral presentation Track: General session
A necessary and sufficient condition for connectedness of direct graph bundles where the fibers are cycles is given. It is also proved that all connected direct graph bundles of cycles over cycles are Hamiltonian.
Presented by Ms. Irena HRASTNIK LADINEK
Type: Oral presentation Track: Association Schemes
A finite group $G$ is called a Schur group if all Schur rings over $G$ are schurian, i.e., arise from suitable permutation groups. It is an open problem to characterize the Schur groups, the answer for which is unknown even for cyclic groups. In this talk we prove that if the cyclic group of order $n$ is a Schur group, then $n$ belongs to one of the following five disjoint families of integers: $p ... More
Presented by Dr. Istvan KOVACS
Type: Oral presentation Track: Group Actions
We compare three transitivity properties of finite graphs, namely, for a positive integer $s$, $s$-distance transitivity, $s$-geodesic transitivity and $s$-arc transitivity. It is known that if a finite graph is $s$-arc transitive but not $(s+1)$-arc transitive then $s\leq 7$ and $s\neq 6$. We show that there are infinitely many geodesic transitive graphs with this property for each of these ... More
Presented by Mr. WEI JIN
Type: Oral presentation Track: Association Schemes
In this talk I will give some quantifications for a distance-regular graph to be close to a Taylor graph. For example we will discuss the distance-regular graphs with the number of vertices at most 3 times its valency. This is joint work with JongYook Park (POSTECH).
Presented by Dr. Jack KOOLEN
Type: Oral presentation Track: General session
Let $D$ be a $k$-regular digraph and let $D^-$ be obtained by reversing all the arcs of $D$. We prove that the difference $f(D)-f(D^-)$ can be arbitrarily large if $k=2$ and $f$ is the domination number, or if $f$ is the total domination number and $k=3$. On the other hand, we show that $f(D)=f(D^-)$, if $k=2$ and $f$ is the total domination number. These statements complete the results of~\cite{n ... More
Presented by Dr. Štefan GYüRKI
Type: Oral presentation Track: Configurations
We consider generalized configurations as defined by Konrad Zindler (1890)and study their degree of irregularity and their automorphism group. We givea construction of a family of such configurations of arbitrarily large degree of irregularity. This is joint work with Tomaz Pisanski.
Presented by Brigitte SERVATIUS
Type: Oral presentation Track: Cayley Graphs
Some connected Cayley digraphs on solvable groups do not have hamiltonian paths, but no examples are known on nilpotent groups. The talk will describe some new examples of connected, 2-generated Cayley digraphs on solvable groups that do not have hamiltonian paths, and prove that every connected, 2-generated Cayley digraph on any nilpotent group does have a hamiltonian path.
Presented by Dave Witte MORRIS
Type: Oral presentation Track: Cayley Graphs
For a subset $A$ of $\Z_n,$ the cyclic Haar graph $H(n,A)$ is the graph with vertex set $\Z_n^+ \cup \Z_n^-,$ and edge set $\{ \{x^+,y^-\} : x,y \in \Z_n, y - x \in A \}$. In this talk we describe the isomorphism classes of these graphs in the case when $|A| \le 4$. As an application, we obtain a closed form solution to the enumeration problem of cyclic 3-configurations.
Presented by Mr. Sergio Hiroki KOIKE
Type: Oral presentation Track: Coloring, independence and forbidden subgraphs
Let $G$ be a graph and let $k$ and $j$ be positive integers. A subset $D$ of the vertex set of $G$ is a {\it $k$-dominating set} if every vertex not in $D$ has at least $k$ neighbors in $D$. The {\it $k$-domination number} $\gamma_k(G)$ is the minimum cardinality among the $k$-dominating sets of $G$. A subset $I \subseteq V(G)$ is a {\it $j$-dependent set} of $G$ if every vertex in $I$ has at mo ... More
Presented by Dr. Adriana HANSBERG
Type: Oral presentation Track: Crossing Number
A graph $G$ is called $k$-planar if there exists its drawing $D(G)$ in the plane such that each edge of $D(G)$ is crossed at most $k$ times. For small $k$, we survey known results on $k$-planar graphs from the point of view of global properties, algorithmic aspects of recognition, local structure, colourings and hamiltonicity. We also introduce a novel concept of outer-$k$-planar graphs which are ... More
Presented by Dr. Tomáš MADARAS
Type: Oral presentation Track: Keynote lecture
A toroid of rank rank n+1 is the quotient of a Euclidean tessellation of n-space over a rank n subgroup of the group its translations. We derive some general results on the group of automorphisms of equivelar toroids, that is the toroids obtained from the regular tessellations. We give a complete classification of equivelar toroids in ranks 3 and 4.
Presented by Prof. Asia iIvic WEISS
Type: Oral presentation Track: Configurations
We have combinatorial, topological, and geometric (n_k)-configurations in the projective plane, i.e., n lines (combinatorial ones, pseudolines, or straigth lines) and n points and precisely k of these points are incident with each line and, vice versa, precisely k lines are incident with each point, see Grünbaum´s research monograph: "Configurations of Points and Lines", AMS, Graduate Studies i ... More
Presented by Prof. Jürgen BOKOWSKI
Type: Oral presentation Track: Association Schemes
A Terwilliger graph is a connected non-complete graph $\Gamma$ such that, for any two vertices $u,w\in \Gamma$ at distance $2$, the subgraph induced by the common neighbors of $u$ and $w$ is a complete graph of size $\mu$ (for some fixed $\mu \ge 1$). There are only three distance-regular Terwilliger graphs known with $\mu\ge 2$, all of them are characterized by theirs intersection arrays. The thr ... More
Presented by Alexander GAVRILYUK
Type: Oral presentation Track: Domination, Independence and Coloring of Product Graphs
A Roman domination function of a graph is a function f: V ---> {0,1,2} such that every vertex with f(v)=0 is adjacent to some vertex with f(v)=2. The Roman domination number is then the minimum of w(f)=\sum_{v \in V}f(v) over all such functions. We give the Roman domination number of the lexicographic product of graphs using a new concept of the so-called dominating pairs and introduce some new ... More
Presented by Polona PAVLIč
Type: Oral presentation Track: Association Schemes
We say that an association scheme $\chi$ is a \textit{polygon} scheme if each $A_i$ is the adjacency matrix of the distance-$i$ graph in the polygon of diameter $d$. In this talk, we describe explicitly the algebraic structure of the Terwilliger algebra of wreath products of polygon schemes.
Presented by Dr. Kijung KIM
Type: Oral presentation Track: General session
Let R be a commutative ring with identity and M be a multiplication R-module. For elements x and y of M, we recall that the product of Rx and Ry is denoted by xy and is defined by (IJ)M where I and J are presentation ideals of Rx and Ry, respectively. An element x in a multiplication module M is called a zero divisor if xy=0 for some non-zero element y of M. A zero-divisor graph of a multiplicatio ... More
Presented by Dr. Rezvan VARMAZYAR
Type: Oral presentation Track: Coloring of Graphs
The b-chromatic number of a graph G is the largest integer $k$ such that $G$ admits a proper $k$-coloring in which every color class contains at least one vertex that has a neighbor in each of the other color classes. We prove that every $d$-regular graph with at least $2d^3$ vertices has b-chromatic number $d+1$, that the b-chromatic number of an arbitrary $d$-regular graph with girth $g=5$ is a ... More
Presented by Mr. Marko JAKOVAC
Type: Oral presentation Track: Keynote lecture
The $q$-analogue of questions about sets and subsets are questions about vector spaces and subspaces. For a prime power $q$, and an $n$-dimensional vector space $V$ over $GF(q)$, let ${V\brack k}$ denote the family of $k$-subspaces of $V$. The vertex set of the $q$-Kneser graph $qK_{n:k}$ is ${V\brack k}$, where $V$ is an $n$-dimensional vector space over $GF(q)$. Two vertices of $qK_{n:k}$ ar ... More
Presented by Prof. Tamas SZONYI
Type: Oral presentation Track: Coloring of Graphs
Several reasons will be presented why the natural extension of the notion of undirected graph colorings is to partition the vertex set of a digraph into acyclic sets. Some recent results in this area, the proofs of which use probabilistic techniques, will be outlined.
Presented by Bojan MOHAR
Type: Oral presentation Track: Group Actions
It is known that every (simple) regular graph of degree d that has a Hamilton cycle in fact possesses a second Hamilton cycle if d is odd or d is at least 300. Sheehan conjectured that the statement is also true for d=4, which would imply that it is true for every d greater than 2. Fleischner showed that Sheehan's conjecture fails for 4-regular multigraphs, but it is easily seen to be true for ver ... More
Presented by Dr. Mateja SAJNA
Type: Oral presentation Track: General session
For a strongly connected digraph $D$ the restricted arc-connectivity $\lambda'(D)$ is defined as the minimum cardinality of an arc-cut over all arc-cuts $S$ satisfying that $D-S$ has a non trivial strong component $D_1$ such that $D-V(D_1)$ contains an arc. In this work we prove that every digraph on at least 4 vertices and of minimum degree at least 2 is $\lambda'$-connected and $\lambda'( ... More
Presented by Dr. Pedro GARCIA VAZQUEZ
Type: Oral presentation Track: Group Actions
This talk is the last in a series of three presentations (together with Primo\v{z} Poto\v{c}nik and Pablo Spiga) concerning the Weiss conjecture and its generalisations. Let $\Gamma$ be a connected $G$-vertex-transitive graph, $v$ be a vertex of $\Gamma$ and $L$ be the permutation group induced by the vertex-stabiliser $G_v$ on the neighbourhood $\Gamma(v)$ of $v$. The pair $(\Gamma,G)$ is sai ... More
Presented by Mr. Gabriel VERRET
Type: Oral presentation Track: Metric Graph Theory
Given a set of vertices $S=\{v_1,v_2,...,v_k\}$ of a connected graph $G$, the metric representation of a vertex $v$ of $G$ with respect to $S$ is the vector $r(v|S)=(d(v,v_1),d(v,v_2),...,d(v,v_k))$, where $d(v,v_i)$, $i\in \{1,...,k\}$ denotes the distance between $v$ and $v_i$. $S$ is a resolving set of $G$ if for every pair of vertices $u,v$ of $G$, $r(u|S)\ne r(v|S)$. The metric dimensio ... More
Presented by Mr. Ismael GONZALEZ YERO
Type: Oral presentation Track: General session
Let $G$ a simple graph. A colouring of its vertices $\varsigma:V\rightarrow\{1,...,k\}$ is called \emph{complete} if each pair of different colours appears in a edge. The \emph{pseudoachromatic number} $\psi(G)$ is the maximum $k$ for which there exist a complete colouring of $G$. If the colouring is required also to be proper (i. e., that each chromatic class is independent), then such a max ... More
Presented by Mr. Christian RUBIO-MONTIEL
Type: Oral presentation Track: Maps and Symmetries
In the moduli space (or classification space) of complex algebraic curves there is so called {\it real locus}, which corresponds to the curves that can be defined over the reals. It leads, in a natural way, to a certain simplicial complex called the {\it real nerve} and the aim of our study is to find its geometrical and homological dimension. Though generally we deal with this question by t ... More
Presented by Dr. Ewa KOZłOWSKA-WALANIA
Type: Oral presentation Track: Coloring of Graphs
We consider a proper coloring c of edges and vertices in a simple graph and the function f(v) of sum of colors of all the edges incident to v and the color of a vertex v. We say that a coloring c distinguishes adjacent vertices by sums, if every two adjacent vertices have different values of f. We conjecture that \Delta +3 colors suffice to distinguish adjacent vertices in any simple graph. ... More
Presented by Monika PILSNIAK
Type: Oral presentation Track: Domination, Independence and Coloring of Product Graphs
The Hall-ratio $\rho(G)$ of a graph $G$ is the ratio of the number of vertices and the independence number maximized over all subgraphs of $G$. The ultimate direct Hall-ratio of a graph $G$ is defined as $\lim _{k\to \infty} \rho (G^{\times k})$, where $G^{\times k}$ denotes the $k$th direct power of $G$ (that is, $G^{\times k}$ is defined on the $k$-length sequences over the vertex set of $G$, an ... More
Presented by Ms. Agnes TOTH
Type: Oral presentation Track: General session
Recently we started a development of net.Plexor - a new library for large network analysis and visualization that is based on the experiences gained in the development of program Pajek. In this paper we present some results of experiments how to provide functionality and algorithms, efficiently utilizing potential of modern hardware based on preferably parallel algorithms for interactive visualiza ... More
Presented by Jernej BODLAJ
Type: Oral presentation Track: Graphs and Networks in Biology
The evolution of a family of genes is represented by a "gene tree" T, whose leafs are labeled by the genes. The internal vertices of T represent the evolutionary events that lead to the separation of lineages: gene duplications and speciation events. Genes to no occur in isolation but have been determined from known species. The evolutionary history of the species is encoded by a species tree S. T ... More
Presented by Peter STADLER
Type: Oral presentation Track: Domination, Independence and Coloring of Product Graphs
The packing chromatic number $\chi_{\rho}(G)$ of a graph $G$ is the smallest integer $k$ such that vertices of $G$ can be partitioned into disjoint classes $X_{1}, ..., X_{k}$ where vertices in $X_{i}$ have pairwise distance greater than $i$. We improve bounds on the packing chromatic number of the square and hexagonal grids and discuss the packing chromatic number of distance graphs, which so ... More
Presented by Mr. Bernard LIDICKY
Type: Oral presentation Track: Representations of Graphs
Fullerenes are 3-regular graphs with faces of size 5 or 6. The number of 5-gons is necessarily 12 and the relative position of them allows to parametrize the fullerenes in term of 10 complex parameters. Such set of parameters is not unique and the group acting on them is one of the Mostow monodromy groups. Such parametrization was introduced by Thurston and unifies a variety of previous existing ... More
Presented by Prof. Mathieu DUTOUR SIKIRIć
Type: Oral presentation Track: Polytopes and Incidence Geometries
Chiral polytopes are abstract polytopes with maximum rotational combinatorial symmetry. Their automorphism groups have two flag-orbits represented by pairs of adjacent flags. Regular polytopes, which are characterized by maximum combinatorial symmetry by reflection, have been well-studied, and much work has been done on their classification and groups. By contrast, still relatively little is known ... More
Presented by Prof. Egon SCHULTE
Type: Oral presentation Track: Polytopes and Incidence Geometries
I will report on joint work with C. Haase, B. Nill and A. Paffenholz. The {\em Birkhoff Polytop}, also known as {\em assignement polytope}, is one of the most studied polytopes. It is the convex hull of all permutation matrices. In the talk I will propose the systematic study of the {\em Permutation polytopes}. They are the convex hull of a subgroup of the group of $n\times n$ permutation m ... More
Presented by Prof. Barbara baumeister BAUMEISTER
Type: Oral presentation Track: General session
A poly-antimatroid is a finite non-empty multiset system that satisfies the basic antimatroid properties. If the underlying set of a poly-antimatroid consists of n elements, then it can be represented as a subset of the n-dimensional integer lattice. Firstly, we focus on geometrical properties of two-dimensional poly-antimatroids (n=2), and prove that they are, actually, polygons known in en ... More
Presented by Dr. Yulia KEMPNER
Type: Oral presentation Track: Keynote lecture
The study of highly symmetric discrete structures in ordinary euclidean 3-space has a long and fascinating history tracing back to the early days of geometry. With the passage of time, various notions of polyhedral structures have attracted attention and have brought to light new exciting figures intimately related to finite or infinite groups of isometries. A radically new, skeletal approach ... More
Presented by Prof. Egon SCHULTE
Type: Oral presentation Track: Algorithmic Graph Theory
Cosh et al. proved that, given a hypergraph H and local edge-connectivy requirements, finding a minimum number of graph edges to be added to H in order to satisfy the requirements is NP-complete. We prove a minimax theorem and a polynomial algorithm solving two subcases of the above problem. Our proof relies on a slight generalization of Mader’s splitting off theorem to hypergraphs.
Presented by Mr. roland GRAPPE
Type: Oral presentation Track: Polytopes and Incidence Geometries
It is known that, for almost for almost all n, the alternating group of degree n can be represented as the automorphism group of a regular polytope of rank 3. In this talk, we present examples of polytopes of high rank for all possible alternating groups.
Presented by Dr. Mark MIXER
Type: Oral presentation Track: Coloring of Graphs
Consider a simple graph $G$ with no isolated edges and at most one isolated vertex. A labeling $w:E(G)\rightarrow \{1, 2, \dots, m\}$ is called \textit{product - irregular}, if all product degrees $pd_G(v)=\prod_{e\ni v}w(e)$ are distinct. The goal is to obtain a product - irregular labeling that minimizes the maximal label. This minimal value is called \textit{the product irregularity strength} a ... More
Presented by Dr. Marcin ANHOLCER
Type: Oral presentation Track: Representations of Graphs
Terwilliger and Weng defined pseudo primitive idempotents. MacLean and Terwilliger drew attention to the entrywise product of those pseudo idempotents associated with modules of the Terwilliger algebra of a distance-regular graph. We will discuss these issues, particularly in the bipartite Q-polynomial context.
Presented by Michael LANG
Type: Oral presentation Track: Maps and Symmetries
We classify pseudo-orientable hypermaps down to characteristic -3.
Presented by Prof. Domenico CATALANO
Type: Oral presentation Track: General session
Let $P$ be a point set on the plane, and consider whether $P$ is {¥em quadrangulatable¥/}, that is, whether there exists a 2-connected bipartite plane graph $G$ with edge edge straight segment such that $V(G)=P$, that the outer cycle of $G$ coincides with Conv($P$), that each finite face of $G$ is quadrilateral. It is easy to see that it is possible if an even number of points of $P$ lie on Conv ... More
Presented by Prof. Atsuhiro NAKAMOTO
Type: Oral presentation Track: General session
Let G be a graph and R any non trivial equivalence relation on E(G). $R$ is said to satisfy the square-property if any two adjacent edges that belong to different equivalence classes of R span exactly one square. It is shown by \v{Z}erovnik et al. that any simple graph with nontrivial weakly 2-convex equivalence relation on the edge set satisfying the square property is a graph bundle over a simpl ... More
Presented by Lydia OSTERMEIER
Type: Oral presentation Track: Polytopes and Incidence Geometries
Joint work with: Dimitri Leemans, Mark Mixer and Tomaz Pisanski. It is known that the incidence graph, alias Levi graph, of any rank 2 coset geometry is an edge-transitive graph. Thus coset geometries can be used to construct several edge transitive graphs. In this work we consider the reverse direction. Starting from edge-transitive graphs, we construct and an analyze associated rank 2 coset ... More
Presented by Dr. Julie DE SAEDELEER
Type: Oral presentation Track: Coloring, independence and forbidden subgraphs
A path in an edge colored graph $G$ is called a rainbow path if all edges have pairwise different color. Then $G$ is rainbow connected if there exists a rainbow path between every pair of vertices of $G$ and the least number of colors needed to obtain a rainbow connected graph is rainbow connection number. If we demand that there must exists a shortest rainbow path between every pair of v ... More
Presented by Prof. Iztok PETERIN
Type: Oral presentation Track: Coloring, independence and forbidden subgraphs
\begin{abstract} In this talk we consider edge colourings of graphs. A subgraph $H$ of a graph $G$ is called {\it rainbow subgraph}, if all its edges are coloured distinct. In the first part we will survey the computation of rainbow numbers. For given graphs $G, H$ the rainbow number $rb(G,H)$ is the smallest number $m$ of colours such that if we colour the edges of $G$ with at least $m$ d ... More
Presented by Prof. Ingo SCHIERMEYER
Type: Oral presentation Track: Coloring, independence and forbidden subgraphs
\begin{document} The graph $H$ is $G$-good if the Ramsey number for the pair of graphs $G$ and $H$ is expressed as follows: $R(G,H)=(\chi (G)-1)(|V(H)|-1)+s(G),$ where $\chi(G)$ is the chromatic number of $G$ and $s(G)$ is the minimum cardinality of colour classes over all chromatic colourings of $V(G).$ We give the Ramsey number for a disjoint union of some $ ... More
Presented by Prof. Halina BIELAK
Type: Oral presentation Track: Crossing Number
Crossing critical graphs have attracted much attention since Širan's introductory paper in 1984. Several general constructions were proposed (crossed fences, tiles, zip-product), several properties were investigated (path-width, average degree, bandwidth), and several other research directions were proposed (almost-planar graphs, nearly-light cycles, characterization). In the talk, we review this ... More
Presented by Drago BOKAL
Type: Oral presentation Track: Keynote lecture
Most recent achievements and open problems within the axiomatic approach to the 196,884-dimensional algebra of the Monster sporadic simple group will be discussed.
Presented by Prof. Alexander IVANOV
Type: Oral presentation Track: Mathematical Chemistry
Let G be a connected simple graph with the vertex-set V(G)={u_1, ..., u_n}. The distance matrix D(G)=(d_ij) of G is defined by d_ij= the distance between the vertices u_i and u_j, i.e. the number of edges in the shortest path connecting these vertices in G. The diameter of G is the maximum d_ij in the matrix D(G). We will show it by d(G) or d. The distance matrix is a rich source of many graph to ... More
Presented by Prof. Ali IRANMANESH
Type: Oral presentation Track: Association Schemes
The starting point of this subject are the famous combinatorial objects known as two-graphs. We introduce a generalization of two-graphs due to D. G. Higman, called $t$-graphs, where our emphasis is on regular $t$-graphs with $t=3$. Higman's definition is initially formulated in cohomological terms. It turns out that regular 3-graphs are closely related to a special class of antipodal distance ... More
Presented by Mr. Daniel KALMANOVICH
Type: Oral presentation Track: Group Actions
A map is a $2$-cell embedding of a connected graph or multigraph in a surface, and is called (fully) {\em regular\/} if its automorphism group has a single orbit on incident vertex-edge-face triples. A map on an orientable surface is said to have {\em trinity symmetry\/} if it is isomorphic to both its dual and its Petrie dual. In that case it admits all six of the so-called {\em standa ... More
Presented by Prof. Marston CONDER
Type: Oral presentation Track: Polytopes and Incidence Geometries
The Janko group $J_1$ has, up to duality, exactly two rank four regular polytopes. In this talk we shall revisit the Livingstone graph and use some of its nice properties to give a construction, as a incidence geometry, of one of these regular polytopes, of Schl\"afli type $\{5,3,5\}$.
Presented by Dr. Isabel HUBARD
Type: Oral presentation Track: Mathematical Chemistry
Suppose $G$ is a graph, $w \in V(G)$ and $e = uv, f = ab \in E(G)$. Define $n_u(e)$ and $m_u(e)$ to be the number of vertices and edges lying closer to $u$ than $v$, respectively. The quantities $n_v(e)$ and $m_v(e)$ are defined analogously. We also define $d(w, e) = min\{ d(w,u), d(w,v)\}$ and $d(e,f) = min\{ d(u,f), d(v,f)\}$. The edge Wiener, edge Szeged and Szeged indices of $G$ are defined a ... More
Presented by Prof. Seyed Ali Reza ASHRAFI GHOMROODI
Type: Oral presentation Track: General session
A set of vertices $S$ resolves a graph $G$ if every vertex is uniquely determined by its vector of distances to the vertices in $S$. The metric dimension of $G$ is the minimum cardinality of a resolving set of $G$. In this work, we provide different approaches to the problem of determining resolving sets of Johnson and Kneser graphs, which give rise to significant bounds for the metric dimension. ... More
Presented by Mr. Antonio GONZáLEZ
Type: Oral presentation Track: Metric Graph Theory
Many generalizations of the well-known class of median graphs have been studied so far. Most of them share a characterization in terms of a certain gated amalgamation procedure from Cartesian products of the graphs that belong to a special subclass of the class, i.e., the subclass of its prime graphs. We investigated such class of graphs in which the prime graphs are all connected bridged gr ... More
Presented by Tanja GOLOGRANC
Type: Oral presentation Track: Representations of Graphs
A polycirculant is a cyclic cover over a pre-graph. We present a method for drawing a polycirculant with rotational symmetry. The method is based on the drawing of its quotient with respect to a semi-regular automorphism. In particular, we devise an efficient spring-embedding algorithm that maintains at each stage the rotational character of the representation. Finally, it is possible to adopt ... More
Presented by Prof. Tomaž PISANSKI
Type: Oral presentation Track: Association Schemes
Each irreducible character of an association scheme (S,X) determines a simple component of the rational adjacency algebra QS. The center and dimension of the division algebra part of this simple component is determined by the field of character values and Schur index of this character. I will survey what is known about these fields of character values and the methods available for calculating th ... More
Presented by Herman ALLEN
Type: Oral presentation Track: Group Actions
A simple graph is called semisymmetric if it is regular, edge-transitive but not vertex-transitive. It is easy to see that every semisymmetric graph must be a bipartite graph with two parts of equal size, and its automorphism group acts transitively on each part. The semisymmetric graphs were first studied by Folkman in 1967, who proved that there exist no semisymmstric graphs of order $ ... More
Presented by Prof. shaofei DU
Type: Oral presentation Track: Metric Graph Theory
A convex set $X$ in a graph with vertex set $V$ is a half-space if $V-X$ is also convex. A convexity has separation property (i) $(S_2)$ if every pair of vertices belong to complementary half-spaces; (ii) $(S_3)$ if for every convex set $A\subset V(G)$ and $b\in V(G)-A$, there exist complementary half-spaces $A'$ and $B'$ such that $A\subseteq A'$ and $b\in B'$; (iii) $(S_4)$ if for every pair $ ... More
Presented by Dr. Ortrud OELLERMANN
Type: Oral presentation Track: Keynote lecture
Snarks are nontrivial cubic graphs whose edges cannot be properly coloured with three colours. Since their first occurrence in the 19th century these graphs have been an object of continuous interest especially because of their relationship to various important problems in graph theory, such as the four colour problem, Tutte's 5-flow conjecture, the cycle double cover conjecture, and Fulkers ... More
Presented by Prof. Martin SKOVIERA
Type: Oral presentation Track: Algorithmic Graph Theory
We propose an algorithm for solving the maximum weighted stable set problem in claw-free graphs that runs in O(n^3)-time, drastically improving the previous best known complexity bound. This algorithm is based on a novel decomposition theorem for claw-free graphs, which we also present in this talk. Despite being weaker than the well-known structure result for claw-free graphs given by Chudnovsk ... More
Presented by Dr. Yuri FAENZA
Type: Oral presentation Track: Keynote lecture
It is known that Ramsey class and generic (and universal) graph are related notions. We explain this connection and complement it by some new examples of Ramsey classes. Particularly we characterize universal and Ramsey classes defined by existence and non-existence of homomorphisms.
Presented by Prof. Jaroslav NEšETRIL
Type: Oral presentation Track: General session
UNO is a well-known card game whose relations with graph theory we investigate in this talk. To a set of UNO cards, we attribute an UNO-graph: its vertices correspond to the cards, and two cards are adjacent if and only if they match according to the rules of the game. It is known that a graph G is an UNO-graph if and only if G is a line graph of a bipartite graph. We characterize UNO-graph as cla ... More
Presented by Dr. Janja JEREBIC
Type: Oral presentation Track: Graph Spectra and its Applications
An upper bound for the sum of the squares of the entries of the principal eigenvector corresponding to a vertex subset inducing a $k$-regular subgraph is introduced and applied to the determination of an upper bound on the order of such induced subgraphs. Furthermore, for some connected graphs we establish a lower bound for the sum of squares of the entries of the principal eigenvector correspo ... More
Presented by Mrs. Milica ANDELIC
Type: Oral presentation Track: General session
Let G=(V,E) be a graph and K a subset of vertices in V. Assume now that the edges of G are failing independently with given probabilities. The K-terminal reliability R(G,K) is the probability that all vertices in K are mutually connected. In this talk a new approach for the computation of R(G,K) at a vertex separating set of G is proposed by means of lattice theoretic methods.
Presented by Mr. Frank SIMON
Type: Oral presentation Track: Algorithmic Graph Theory
Given a subset $H$ of $k$ vertices in a connected graph $G$ the $k$-Steiner tree problem is that of finding a connected subgraph of $G$, that contains all the $k$ vertices and has the minimum number of edges among all such subgraphs. The number of edges in this subgraph is denoted by $s_G(H)$. It is well known that for $k \geq 3$, it is generally $NP$-hard to compute $s_G(H)$. The $k$-th Steiner i ... More
Presented by Matjaž KOVšE
Type: Oral presentation Track: Metric Graph Theory
The concept of the $k$-Steiner interval is a natural generalization of the geodesic (binary) interval. It is defined as a mapping $S: V\times V\cdots V \rightarrow 2^{V}$ such that $S(u_1,\ldots, u_k)$ consists of all vertices in $G$ that lie on some Steiner tree with respect to a multiset $W=(u_1\ldots,u_k)$ of vertices from $G$. We will focus on the the following three axioms for the k-Stei ... More
Presented by Aleksandra TEPEH
Type: Oral presentation Track: Mathematical Chemistry
Molecular connectivity indices are identified as components of the molecular accessibility. The first and second-order connectivity indices represent molecular accessibility areas and volumes, respectively, whereas higher order indices represent magnitudes in higher dimensional spaces. In identifying accessibility perimeters, we recognized the atom degrees as a measure of the accessibility perimet ... More
Presented by Dr. Ali MADANSHEKAF
Type: Oral presentation Track: Group Actions
A graph is edge-primitive if its automorphism group acts primitively on edges. In 1973 Weiss [Kantenprimitive Graphen vom Grad drei. J. Combin. Theory Ser. B 15(1973), 269-288] determined cubic edge-primitive graphs. In this paper, we present a classification of tetravalent edge-primitive graphs.
Presented by Prof. Yan-Quan FENG
Type: Oral presentation Track: Group Actions
Let s be a positive integer. A graph is s-transitive if its automorphism group is transitive on s-arcs but not on (s+1)-arcs. In this article a complete classification of tetravalent s-transitive graphs of order twice a product of two primes is given.
Presented by Mohsen GHASEMI
Type: Oral presentation Track: Cayley Graphs
In a perfect world in which all isomorphisms between graphs must be in some sense ``natural," it would be possible to attack the problem of determining whether or not given graphs are isomorphic, simply by checking a (hopefully small) class of ``natural" isomorphisms. For Cayley graphs, ``natural" isomorphisms between the graphs Cay$(G;S)$ and Cay$(G;S')$ on the group $G$, would consist exclusivel ... More
Presented by Joy MORRIS
Type: Oral presentation Track: Maps and Symmetries
A regular Cayley map for the cyclic group A can be defined algebraically as a group with specified generators x,y, where x is an involution, having a complementary factorization AY, where Y is the subgroup generated by y. A complete classification is given for regular Cayley maps for the cyclic group of order n, depending only on a unit r mod n, if n is odd, or mod n/2, if n is even, where r sati ... More
Presented by Prof. Thomas TUCKER
Type: Oral presentation Track: Algorithmic Graph Theory
For a connected graph G=(V,E), a subset U of V is called a disconnected cut if U disconnects the graph and the subgraph induced by U is disconnected as well. We show that the problem to test whether a graph has a disconnected cut is NP-complete. This problem is polynomially equivalent to the following problems: testing if a graph has a 2K2-partition, testing if a graph allows a vertex-surjective h ... More
Presented by Dr. Barnaby MARTIN
Type: Oral presentation Track: General session
It is well known that some classic conjectures in graph theory such as the Cycle Double Cover Conjecture (CDCC) and Tutte's 5-flow conjecture can be reduced to a certain family of cubic graphs called snarks, named after the elusive creature in Lewis Carroll's poem ''The hunting of the Snark''. By using improved search methods and very big computers we have now generated (caught) all snarks on 36 v ... More
Presented by Mr. Jonas HäGGLUND
Type: Oral presentation Track: Keynote lecture
This talk begins with an introduction to infinite graphs, describes main differences to finite graphs, and continues with the free product. The free product G*H of two-connected graphs G and H is a vertex transitive, infinite graph whose blocks are isomorphic to G or H. This product is commutative and associative, but does not have a unit unless one restricts attention to vertex transitive graphs. ... More
Presented by Prof. Wilfried IMRICH
Type: Oral presentation Track: Mathematical Chemistry
For a given graph G its Szeged weighting is defined 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 defined analogously. The adjacency matrix of a graph weighted in this way is called its Szeged matrix. Doslic et. al. defined Szeged energy of grph the summation of absolute value of eigenvalue of Szeged matrix. In ... More
Presented by Mr. Gholamhossein FATHTABAR FIROUZJAEI
Type: Oral presentation Track: Domination, Independence and Coloring of Product Graphs
For a graph G=(V,E) and a permutation π of V, the prism of G with respect to π is the graph πG obtained from two copies G′ and G" of G by joining u∈V′ and v∈V" if and only if v=π(u). If π is the identity, then πG=G×K₂, the cartesian product of G and K₂. The graph G×K₂ is often referred to as the prism of G and πG is called a generalized prism of G. A universal fixer is ... More
Presented by Dr. Kieka MYNHARDT
Type: Oral presentation Track: Domination, Independence and Coloring of Product Graphs
Although it would be ideal for a company or security firm to have all nodes in a network monitored at all times (by a person or sensor either at the node itself or adjacent) this may well be too expensive. This gives rise to the watchman problem where a person traverses the graph (returning to the starting point) in such a way that every node is either in this closed walk or adjacent to it. In the ... More
Presented by Dr. Bert HARTNELL
Type: Oral presentation Track: Group Actions
This talk is the second in a series of three presentations (together with Primo\v{z} Poto\v{c}nik and Gabriel Verret) concerning the Weiss conjecture and its generalisations. Let $\Gamma$ be a connected $G$-vertex-transitive graph, $v$ be a vertex of $\Gamma$ and $L$ be the permutation group induced by the vertex stabiliser $G_v$ on the neighbourhood $\Gamma(v)$ of $v$. The pair $(\Gamma,G)$ is ... More
Presented by Dr. Pablo SPIGA
Type: Oral presentation Track: Coloring of Graphs
This talk sketches a proof that the fractional chromatic number of the categorical product of two graphs is equal to the minimum of the fractional chromatic numbers of the two factor graphs. Using this result, we prove a conjecture of Burr-Erdos-Lovasz concerning the chromatic Ramsey number of graphs: For any positive integer $n$, there is an $n$-chromatic graph $G$ whose chromatic Ramsey number i ... More
Presented by Prof. Xuding ZHU
Type: Oral presentation Track: Coloring, independence and forbidden subgraphs
We consider \textit{distance graphs in $\mathbb{R}^n$}. The sets of vertices of these graphs are subsets of $\mathbb{R}^n.$ Two vertices are connected by an edge if the distance between them is exactly $d$. This work deals with distance graphs $G=G(n,m,\{a_0, a_1, \ldots, a_m\},x) = (V,E)$ of certain type. Namely, such graphs have the sets of vertices $$V =\{y=(y_1,\ldots,y_n), y_i\in \{0,1,\l ... More
Presented by Mr. Andrey KUPAVSKII
Type: Oral presentation Track: General session
In joint work with Nick Beaton (PhD student) and Philippe Flajolet, we have studied a range of solvable self-avoiding walk and polygon models. One of these, the so-called 3-sided prudent polygons, enumerated by area, displays quite unexpected asymptotics. Writing the dominant asymptotic form of the coefficients as $a_n \sim A \times \mu^n \times n^g,$ we find $g$ to be irrational, and more surpris ... More
Presented by Prof. Anthony J GUTTMANN
Type: Oral presentation Track: Representations of Graphs
Let (X,R) be a cometric (or Q-polynomial) association scheme with Q-polynomial ordering E_0,E_1,...,E_d on its primitive idempotents. As is well-known, a scalar multiple of E_1 is the Gram matrix of a set of |X| unit vectors in dimension m_1=rank E_1. We aim to study the convex hull of this set of vectors and its relation to the combinatorics of the original scheme.
Presented by Dr. William MARTIN
Type: Oral presentation Track: Metric Graph Theory
A set $S$ of vertices of a graph $G$ is a geodetic set if every vertex of $G$ lies in an interval between two vertices from $S$. The size of a minimum geodetic set in $G$ is the geodetic number $g(G)$ of $G$. We find that the geodetic number of the lexicographic product $G\circ H$ for non-complete graph $H$ lies between 2 and $3g(G)$. We characterize the graphs $G$ and $H$ for which $g(G\cir ... More
Presented by Dr. Tadeja KRANER ŠUMENJAK
Type: Oral presentation Track: Graph Spectra and its Applications
We establish a close connection between the largest eigenvalue of a graph and the quantity $$ \max \frac{e(X,Y)}{\sqrt{|X||Y|}}, $$ where the maximum is over all pairs $(X,Y)$ of subsets of the vertex set of the graph. Our results are best possible up to a logarithmic factor.
Presented by Prof. Vsevolod LEV
Type: Oral presentation Track: Group Actions
A graph $\Gamma$ is said to be locally $(G,2)$-arc transitive for $G$ a subgroup of $Aut(\Gamma)$ if, for any vertex $\alpha$ of $\Gamma$, G is transitive on the 2-arcs of $\Gamma$ starting at $\alpha.$ In this talk, we will discuss recent progress toward the classification of the locally $(G,2)$-arc transitive graphs, where $Sz(q) \leq G \leq Aut(Sz(q)),$ $q = 2^{2k+1}$ for some $k \in \mathbb{N ... More
Presented by Dr. Eric SWARTZ
Type: Oral presentation Track: General session
A set of vertices $W$ \textit{resolves} a graph $G$ if every vertex in $G$ is uniquely determined by its vector of distances to the vertices in $W$. \ The \textit{metric dimension }of $G$ is the minimum cardinality of a resolving set of $G$. \ For $n\geq 3$, an $n$-complete partite graph $G(k_1, k_2, ..., k_n)$ is a graph whose vertex set $V$ can be partitioned into $n$ subsets $V_1, V_2, ...,V_n$ ... More
Presented by Mr. Suhadi Wido SAPUTRO
Type: Oral presentation Track: General session
Some new relations have been established between Wiener indices, stability numbers and clique numbers for several classes of composite graphs that arise via graph products.
Presented by Prof. Modjtaba GHORBANI
Type: Oral presentation Track: Polytopes and Incidence Geometries
An abstract polytope is called {\em regular\/} if its automorphism group has a single orbit on flags (maximal chains). In this lecture I will report on recent work on finding for each $n$ the regular $n$-polytopes with the smallest numbers of flags. With a few small exceptions, these are also the regular $n$-polytopes with the smallest numbers of elements, and those with the smallest nu ... More
Presented by Prof. Marston CONDER
Type: Oral presentation Track: Graph Spectra and its Applications
The generalised middle graph M(n,k) of a cycle consists of vertices {v0,v1,...,vn-1,u0,u1,...,un-1} and edges {viui,viu(i+1),uiu(i+k),i=0,1,2...n}. The generalised total graph T(n,k) of a cycle consists of vertices {v0,v1,...,vn-1,u0,u1,...,un-1} and edges {viv(i+1),viui,viu(i+1),uiu(i+k),i=0,1,2...n}. In this paper we obtain the spectrum of these graphs and also the bounds for the spectral radius ... More
Presented by Dr. Indulal GOPALAPILLAI
Type: Oral presentation Track: Group Actions
Throughout this abstract, let $\Gamma$ denote a finite connected $G$-arc-transitive graph, let $G_v$ be the stabiliser of a vertex $v$, and let $G_v^{\Gamma(v)}$ be the permutation group induced by the action of $G_v$ on the neighbourhood $\Gamma(v)$. If the valence of $\Gamma$ is $3$, then a celebrated theorem of Tutte states that the order of $G_v$ is bounded above by $48$. Motivated by this ... More
Presented by Dr. Primož POTOčNIK
Type: Oral presentation Track: Algorithmic Graph Theory
In order to protect privacy of social network participants, graph data should be anonymized prior to its release. Most proposals in the literature aim to achieve $k$-anonymity under different assumptions about the background information of the attacker. In this paper we present a different approach based on randomizing the location of the triangles in the graph. We show that this method preserves ... More
Presented by Dr. Nacho LOPEZ LORENZO
Type: Oral presentation Track: Representations of Graphs
Let $\mathbb F$ denote a field and let $V$ denote a vector space over $\mathbb F$ with finite positive dimension. We consider a pair of linear transformations $A:V \to V$ and $A^*:V \to V$ that satisfy the following conditions: \begin{enumerate} \item[\rm (i)] Each of $A,A^*$ is diagonalizable. \item[\rm (ii)] There exists an ordering $\lbrace V_i\rbrace_{i=0}^d$ of the eigenspaces of $A$ such ... More
Presented by Prof. Paul TERWILLIGER
Type: Oral presentation Track: Representations of Graphs
A graph is said to be $t$-tuple regular if, for any set $S$ of vertices with $|S|\le t$, the number of common neighbours of $S$ depends only on the isomorhism type of the induced subgraph on $S$. It follows immediately that a graph is 1-tuple regular iff it is regular, and it is 2-tuple regular iff it is strongly regular. Cameron and Van Lint studied 3-tuple regular graphs, and they characterized ... More
Presented by Mr. Aleksandar JURISIC
Type: Oral presentation Track: Polytopes and Incidence Geometries
We construct an n-dimensional polytope (with 2^n vertices and n(n+1)/2+1 facets) whose volume is equal to the Tutte polynomial of the complete graph, divided by n!. The proof is bijective and consists of a triangulation of the polytope into simplices naturally corresponding to labelled forests. We present several applications, among them an improved bound for the number of labelled connected graph ... More
Presented by Dr. Matjaz KONVALINKA
Type: Oral presentation Track: Graph Spectra and its Applications
In this talk we will discuss how the energy (i.e., the sum of the absolute values of all eigenvalues) of so-called tadpole graphs $P_n^k$ , which are obtained by joining a vertex of a cycle $C_k$ to one of the ends of a path $P_{n-k}$, depends on $k$. Combined with earlier results [Y. Hou, I. Gutman, C.-W. Woo, Unicyclic graphs with maximal energy, Linear Algebra Appl. 356 (2002) 27-36 and E.O.D.A ... More
Presented by Mr. Eric Ould Dadah ANDRIANTIANA
Type: Oral presentation Track: Crossing Number
We present the uniform approach to Euler and Leighton bound optimization through new operator L(p,w). We focus on special cases of this operator. One special case is that we can investigate weighted subgraph of G that yields the maximum Euler bound for the crossing number of G. We prove that there always exists an integer optimal solution for this optimization problem. This means that the so ... More
Presented by Ms. Mojca BRAčIč
Type: Oral presentation Track: General session
A subset $S$ of vertices of a graph $G$ is called a $k$-path vertex cover if every path of order $k$ in $G$ contains at least one vertex from $S$. Denote by $\psi_k(G)$ the minimum cardinality of a $k$-path vertex cover in $G$. In this paper present an upper bound for $\psi_3(G)$ of graphs with given average degree. We also give a lower bound for $\psi_k(G)$ of regular graphs and some results for ... More
Presented by Dr. Andrej TARANENKO
Type: Oral presentation Track: Domination, Independence and Coloring of Product Graphs
In the 1960’s V.G. Vizing conjectured that the domination number of the Cartesian product of two graphs is at least as large as the product of their domination numbers. In this talk we will survey progress on this conjecture and also present some open questions related to it.
Presented by Dr. Douglas RALL
Type: Oral presentation Track: Association Schemes
The Weisfeiler-Leman (WL) method takes as input an arbitrary graph $\Gamma$, and returns the minimal coherent algebra containing the basis relations of $\Gamma$ (e.g. the set of edges and non-edges). We will discuss some well-known properties of a common higher-dimensional generalisation of this method, the $k$-dim WL method, in particular with respect to its application to the graph isomorphism p ... More
Presented by Mr. Brendan DOUGLAS
Type: Oral presentation Track: General session
Let $R$ be a commutative ring. The idea of associating a graph with the zero-divisors $R$ was introduced by Beck in 1988, where he talked about the colorings of such graphs. By the definition he gave, every element of the ring $R$ was a vertex in the graph, and two vertices $x, y$ were adjacent if and only if $x y = 0$ (\cite{B}). Later, D. F. Anderson and P. S. Livingston (\cite{AL}) considered o ... More
Presented by Dr. Ahmad YOUSEFIAN DARANI
Type: Oral presentation Track: Coloring, independence and forbidden subgraphs
Let $G$ be a $\lambda_k$-connected graph. $G$ is called $\lambda_k$-optimal, if its $k$-restricted edge-connectivity $\lambda_k(G)$ equals its minimum $k$-edge degree. $G$ is called super-$\lambda_k$ if every $\lambda_k$-cut isolates a connected subgraph of order $k$. Firstly, we will introduce a lower bound on the order of $2$-fragments in triangle-free graphs that are not $\lambda_2$-optima ... More
Presented by Mr. Andreas HOLTKAMP