Contribution List

Showing 247 of 247 submitted abstracts

Gabriel Verret, The University of Western Australia
Over the past few years, there has been an explosion of results classifying arc-transitive (or $2$-arc-transitive, arc-regular, etc...) graphs of valency $d$ and order $kp^n$, where $d,k,n$ are fixed integers and $p$ is a prime that is allowed to vary. These results are often proved by standard methods and thus t... More
Mr. Martin Knor, Slovak University of Technology in Bratislava
Wiener index, the sum of all distances in a graph, is probably the most important topological descriptor. There are several papers establishing congruence relations for the Wiener index in various classes of graphs. We generalized the results of Lin and we obtained congruence relations for large families of graphs w... More
Let $V$ be the set of vertices of a regular polygon in the plane and let $L(V)$ be the set of all lengths of all open polygonal curves with vertex-set $V$. Which is the size of $L(V)$? I conjecture that if $|V|=2n+1$ is a prime, then the answer is ${3n-1\choose n-1}$. I will show that this conjecture is equivalent t... More
Product graphs and product-like structures play a central role in theoretical biology. To determine traits that can vary independently through evolution one can equivalently ask for the (local) prime factors of the underlying phenotypespace. The topology of the phenotypespace corresponds (at least locally) to the di... More
Prof. Daniel Marques Pinto, University of Coimbra
If we take three perfect binary trees of the same height we can build a trivalent graph, that we will call \emph{quasi-binary tree}, by adding an edge from each one of the three root vertices of the original trees to a new vertex. We will show that, for all $n \in \mathbb{N}$, there is a way of gluing three quasi-b... More
Dr. Rastislav Krivoš-Belluš, P. J. Šafárik University in Košice
$k$-Path Vertex Cover Problem is NP-hard for several classes of graphs. We have focused on the weighted version of this problem. We will analyze complexity of exact algorithms for finding minimum $k$-Path Vertex Cover for trees and cacti graphs using dynamic programming and with parametrized complexity depending on ... More
Dr. Nicolas Lichiardopol, Lycée Craponne, Salon
An oriented graph $D$ is said to be traceable if it admits a hamiltonian path. For $k\geq 2$, an oriented graph $D$ of order at least $k$, is said to be $k$-traceable if any subset of $k$ vertices of $D$ induces a traceable oriented graph. We denote by $t(k)$ the smallest integer bigger than or equal to $k$ such th... More
Prof. Jianfeng Wang, Qinghai Normal University
In this report, we will introduce a new lower bound for the first Zagreb index and determine all the extreme graphs. These results not only contain many previous ones but are helpful to find new graphs determined by the Laplcian spectra. More
Prof. Martyn Mulder, Econometrisch Instituut, Erasmus Universiteit
In social choice theory the process of achieving consensus can be modeled by a function $L$ on the set of all finite sequences of vertices of a graph. It returns a nonempty subset of vertices. To guarantee rationality of the process {\em consensus axioms} are imposed on $L$. Three such axioms are Anonymity, Betweenn... More
The Maximum Independent Set Problem (MISP for short) and the Minimum $k$-Path Vertex Cover Problem (M$k$PVCP for short) are known to be NP-hard [2,1]. For the first problem, there exists lots of graph classes in terms of forbidden subgraphs, where polynomial algorithms compute optimal solutions. A celebrated result ... More
Dr. Aleksandra Tepeh, FEECS, University of Maribor and FIŠ, Novo mesto
The Wiener index $W(G)$ of a connected graph $G$ is defined to be the sum $\sum_{u,v} d(u,v)$ of distances between all unordered pairs of vertices in $G$. Similarly, the edge-Wiener index $W_e(G)$ of $G$ is defined to be the sum $\sum_{e,f} d(e,f)$ of distances between all unordered pairs of edges in $G$, or equ... More
Iztok Peterin, FEECS, University of Maribor and IMFM Ljubljana
In [Discrete Math. 307 (2007) 472--483] a linear algorithm for the prime factor decomposition of a graph with respect to Cartesian product is presented. Hence the paper establishes the best possible complexity for this important fundamental problem. Unfortunately this algorithm has a big constant and its linearity b... More
Dr. Izolda Gorgol, Lublin University of Technology
A subgraph of an edge-coloured graph is {\it rainbow} if all of its edges have different colours. For graphs $G$ and $H$ the {\it anti-Ramsey number} $ar(G,H)$ is the maximum number of colours in an edge-colouring of $G$ with no rainbow copy of $H$. The notion was introduced by Erd\H os, Simonovits and V.~S\'os and... More
Kenneth Walter Johnson, Penn State University
Given any finite quasigroup $Q$ an association scheme can be automatically constructed from the "class algebra". Moreover if $Q$ is a loop (i.e there is an identity element) the association scheme may be regarded as an S-ring over $Q$ (with suitable modifications to the definition). Recently Humphries and I have... More
Dr. Sho Suda, Aichi University of Education
Hadamard matrices have been widely studied from the view point of design theory, coding theory, quantum information theory. Algebraic combinatorics also contributes the study for Hadamard matrices. For example, it was shown that Hadamard matrices have a structure of a distance regular graph of diameter 4. In this ta... More
Mr. Uffe Thorsen, IMADA, University of Southern Denmark
By modeling molecules as graphs it is possible to infer atom to atom mappings of chemical reactions by solving the minimum edge edit distance problem. This can among other things be used to generate graph grammar rules for use in generative chemistry. Another application is to complete chemical or biological network... More
Mr. Richard Hammack, Virginia Commonwealth University
We are concerned with automorphism groups of thin direct products. (A graph is {\it thin} if no two vertices have the same neighborhood.) It is known that if $\varphi$ is an automorphism of a connected non-bipartite thin graph $G$ that factors (uniquely) into primes as $G=G_1\times G_2\times\cdots\times G_k$, t... More
Prof. Halina Maria Bielak, Inst. of Math., UMCS, Lublin
Let $\mathcal{H}=(V,\mathcal{E})$ be a simple linear hypergraph. We consider a blow-up hypergraph $\mathcal{G}[\mathcal{H}]$ of $\mathcal{H}$. We are interested in the following problem. We have to decide whether there exists a blow-up hypergraph $\mathcal{B}[\mathcal{H}]$ of $\mathcal{H}$, with given hypere... More
Dr. Pablo Spiga, University of Milano-Bicocca
The celebrated Erdos-Ko-Rado theorem determines the cardinality and also describes the structure of a set of maximal size of intersecting k-subsets from a set of size n. Analogous results hold for many other combinatorial objects and in this talk we are concerned with a weak extension of the Erdos-Ko-Rado theorem to... More
The \emph{chromatic polynomial} $P(G,t)$ of a graph $G$ is a polynomial with integer coefficients which counts, for each non-negative integer $t$, the number of proper $t$-colourings of $G$. A real number $t$ is called a \emph{chromatic root} of $G$ if $P(G,t) = 0$. An interval $I\subseteq \mathbb{R}$ is called \emp... More
Dr. Binod Kumar Sahoo, National Institute of Science Education and Research, Bhubaneswar
Let $q$ be a prime power and $W(q)$ be the symplectic generalized quadrangle of order $q$. For $q$ even, let $\mathcal{O}$ (respectively, $\mathcal{E}$, $\mathcal{T}$) be the binary linear code spanned by the ovoids (respectively, elliptic ovoids, Tits ovoids) of $W(q)$ and $\Gamma$ be the graph defined on the set ... More
Prof. Fuji Zhang, Xiamen University
In this paper, we find all binary Hamming tilings (i.e. the tilings corresponding to binary Hamming graphs) in Archimedean tilings and show the only four such tilings are (4; 4; 4; 4),(6; 6; 6),(4; 8; 8) and (4; 6; 12). Then we compute the Wiener number of some plane connected subgraphs of binary Hamming tili... More
Let $\Gamma$ denote a bipartite distance-regular graph with diameter $D \ge 4$ and valency $k \ge 3$. Let $X$ denote the vertex set of $\Gamma$. Fix $x \in X$ and let $T=T(x)$ denote the corresponding Terwilliger algebra of $\Gamma$. In this talk we consider the situation where, up to isomorphism, $\Gamma$ has exa... More
Dr. Kenta Ozeki, National Institute of Informatics
A {\em book embedding\/} of a graph $G$ is to put the vertices along the {\em spine\/} (a segment) and each edge of $G$ on a single {\em page\/} (a half-plane with the spine as its boundary) so that no two edges intersect transversely in the same page. We say that a graph $G$ is {\em $k$-page embeddable\/} if $G$ h... More
Dr. Michael Giudici, The University of Western Australia
Given a finite graph $\Gamma$ with $n$ vertices, can we obtain useful bounds on the number of automorphisms of $\Gamma$? If $\Gamma$ is vertex transitive then $|\mathrm{Aut}(\Gamma)|=n|G_v|$ and so the question becomes one about $|G_v|$. When $\Gamma$ is a cubic arc-transitive graph then Tutte showed that $|G_v|$ di... More
Mr. Alexander Mednykh, Sobolev Institute of Mathematics
In this lecture we give a short survey of old and new results about branched coverings of graphs. This notion was introduced independently by T.~D. Parsons, T.~Pisanski, P.~Jackson (1980), H.~Urakawa (2000), B.~Baker, S.~Norine (2009) and others. The branched covering of graphs are also known as harmonic maps or v... More
Dr. Kieka Mynhardt, University of Victoria
A \emph{broadcast} on a nontrivial connected graph $G=(V,E)$ is a function $f:V\rightarrow\{0,1,\dots,$ $\operatorname{diam}G\}$ such that $f(v)\leq e(v)$ (the eccentricity of $v$) for all $v\in V$. The \emph{cost} of $f$ is $\sigma(f)=\sum_{v\in V}f(v)$. A broadcast $f$ is a \emph{dominating broadcast }if every... More
Dr. Allen Herman, University of Regina
Given two finite association schemes $(X,T)$ and $(X,S)$ of the same order, we say that $T$ is a fusion of $S$ if every relation in $T$ is a union of relations in $S$. This talk will discuss two computer algorithms for detecting the fusions of a given association scheme. The first directly calculates fusions of... More
In calculations of genus polynomials for a recursively specifiable sequence of graphs, the imbeddings of each of the graphs are partitioned into \textit{imbedding-types}. The effects of a recursively applied graph operation $\tau$ on each imbedding-type are represented by a \textit{production matrix}. We demonstra... More
Carbon nanotubes are chemical compounds made of carbon which possess a cylindrical structure. Open-ended single-walled carbon nanotubes are called tubulenes. The resonance graph of a tubulene reflects the interference among its Kekul\'e structures. First we will present some basic properties of tubulenes and their ... More
Mr. Connor Thomas, Université libre de Bruxelles
C-groups are smooth quotients of Coxeter groups. It is well known that there is a one-to-one correspondence between string C-groups and abstract regular polytopes. Recently, some results were obtained in the more general case of C-groups without any condition on the diagram. I will present the classification o... More
Mr. Jeremie Moerenhout, University of Auckland
We discuss the existence of chiral polyhedra with automorphism group isomorphic to an almost simple groups with socle $PSL(2,q)$. We prove that there exists such a chiral polyhedron if and only if its group is not $M(1,9)$, $PSL(2,q)$ or $PGL(2,q)$ for any prime power $q$. More
Prof. Ingo Schiermeyer, Technische Universität Bergakademie Freiberg
In this talk we study the chromatic number of $P_5$-free graphs. Gy\'arfas has shown \medskip \noindent{\bf{Theorem}} Let $G$ be a $P_k$-free graph for $k \geq 4$ with clique number $\omega(G) \geq 2.$ Then $\chi(G) \leq (k-1)^{\omega(G)-1}.$ \medskip and has posed the following question: \medskip ... More
Partial cubes are graphs isometrically embeddable into hypercubes. In the talk I will present a complete classification of cubic, vertex-transitive partial cubes. Results can be seen as a generalization of results of Bre\v sar et. al. from 2004 on cubic mirror graphs, and a contribution to the classification of all ... More
The distance multigraph of a graph $G$ is the multigraph having the same vertex set as $G$ with $d_G(u, v)$ edges connecting each pair of vertices $u$ and $v$, where $d_G(u, v)$ is the distance between vertices $u$ and $v$ in a graph $G$. This work gives a technique to find a clique decomposition of the distance mul... More
Phylogenomics heavily relies on well-curated sequence data sets that consist, for each gene, exclusively of 1:1-orthologs, i.e., of genes that have arisen through speciation events. Paralogs, which arose from duplication events, are treated as a dangerous nuisance that has to be detected and removed. Building upon ... More
Dr. Ewa Maria Kubicka, University of Louisville
Given graphs $G$ and $H$, a vertex coloring $c:V(G) \rightarrow \mathbb{N}$ is an $H$-free coloring of $G$ if no color class contains a subgraph isomorphic to $H$. The $H$-free chromatic number of $G$, $\chi(H,G)$, is the minimum number of colors in an $H$-free coloring of $G$. The $H$-free chromatic sum of $G$, $... More
Prof. Douglas B West, Zhejiang Normal University and University of Illinois
A {\it proper coloring} of a graph $G$ assigns colors to its vertices so that adjacent vertices receive distinct colors. The {\it chromatic number} of $G$ is the least $k$ such that $G$ has a proper coloring from a set of $k$ colors. A {\it list assignment} $L$ on $G$ assigns a list $L(v)$ of available colors to e... More
Dr. Rezvan Varmazyar, Department of Mathematics, Khoy Branch, Islamic Azad University, Khoy
Let $R$ be a commutative ring. An $R$-module $M$ is called a multiplication $R$-module provided that for every submodule $N$ of $M$ there exists an ideal $I$ of $R$ such that $N=IM$. Let $N=IM$ and $K=JM$ be submodules of a multiplication $R$-module $M$ ,for some ideals $I, J$ of $R$. The product of $N$ and $K$, ... More
Prof. Joy Morris, University of Lethbridge
A Cayley graph Cay$(G;S)$ on a group $G$ with connection set $S=S^{-1}$ is the graph whose vertices are the elements of $G$, with $g \sim h$ if and only if $g^{-1}h \in S$. If we assign a colour $c(s)$ to each $s \in S$ so that $c(s)=c(s^{-1})$ and $c(s)\neq c(s')$ when $s' \neq s, s^{-1}$, this is a natural (but no... More
Ms. Eszter Gyimesi, Institute of Mathematics, University of Debrecen
T. A. Dowling introduced Whitney numbers of the first and second kind concerning the so-called Dowling lattices of finite groups. It turned out that they are generalizations of Stirling numbers. Later, I. Mez\H{o} defined $r$-Whitney numbers as a common generalization of Whitney numbers and $r$-Stirling numbers. ... More
Prof. Stephen Peter Humphries, Brigham Young University, Provo, Ut
We study commutative Schur rings over the symmetric group $S_n$ that contain the sum of the transpositions in $S_n$, by determining the possibilities for the partition of the class of transpositions that such a Schur ring gives. We note a connection with Gallai colorings of complete graphs. More
Mr. Vincent Pilaud, CNRS & LIX, École Polytechnique
Generalizing the classical associahedron, M.~Carr and S.~Devadoss constructed graph associahedra which provide polytopal realizations of the nested complex of a graph $G$. This talk will present multiple alternative realizations of graphical nested complexes as complete simplicial fans, using ideas coming from compa... More
Mr. Gašper Fijavž, IMFM and University of Ljubljana
Assume that a graph $G$ embeds in a surface $\Sigma$. A theorem of Robertson and Seymour states that there exists a constant $c_\Sigma$, so that every graph which embeds in $\Sigma$ with face-width $\ge c_\Sigma$ contains $G$ as a minor. Let $\Sigma$ be an arbitrary \emph{orientable} surface of genus $\ge 1$. ... More
Daniel Merkle, University of Southern Denmark
Graph rewriting has been applied successfully to model chemical and biological systems at different levels of abstraction. To this end chemical reactions are modelled as graph transformations and in a generative fashion a hypergraph is expanded that allows for subsequent network flow analysis. A particularly pow... More
Dr. Modjtaba Ghorbani, Srtt University
A fullerene is a three connected cubic planar graph whose faces are squares, pentagons, hexagons or heptagons. In this paper, for given fullerene graph F, we compute the order of automorphism group Aut(F). More
Prof. Kiyoshi Ando, Natinal Institute of Informatics, JST ERATO Kawarabayashi Large Graph Project
An edge of a $k$-connected graph is said to be $k$-contractible if the contraction of it results a $k$-connected graph. When $k\le 3$, each $k$-connected graph on more then $k+1$ vertices has a $k$-contractible edge. When $k\ge 4$, there are infinitely many $k$-connected graphs with no $k$-contractible edge. He... More
Klara Stokes, University of Skövde
The existence of configurations in surfaces is a classical topic in algebraic geometry. In this talk I will describe some interesting configurations of points and circles coming from maps on surfaces. I will also discuss some details regarding the points of a configuration in a surface. More
Prof. Gareth Aneurin Jones, University of Southampton
I shall consider how many conjugacy classes of reflections a map can have, under various transitivity conditions. For vertex- and for face-transitive maps there are no restrictions on their number or size, whereas edge-transitive maps can have at most four classes of reflections. This upper bound is attained only by... More
Gábor Gévay, University of szeged
Configurations of points and circles in the plane go back to the classical incidence theorems of Miquel and Clifford, but relatively few results are known in the period since then. In this talk we present some constructions for new classes of such configurations, among them, of the point-circle versions of a general... More
Mr. Ligang Jin, Paderborn University
The Fan-Raspaud Conjecture states that every bridgeless cubic graph has three 1-factors with empty intersection. A weaker one than this conjecture is that every bridgeless cubic graph has two 1-factors and one join with empty intersection. Both of these two conjectures can be related to conjectures on Fano-flows. ... More
Zoltán L. Blázsik, Department of Computer Science, Eötvös University
At the 22nd British Combinatorial Conference Prof. Willem H. Haemers posed a question if there exists a pair of cospectral $d$-regular graphs, where one has a perfect matching and the other one not. We solved this question by finding a family of such pair of graphs for $d\ge 5$ using the Godsil-McKay switching argum... More
Prof. Tomislav Došlić, University of Zagreb
A matching $M$ in a graph $G$ is maximal if it cannot be extended to a larger matching in $G$. We show how several chemical and technical problems can be successfully modeled in terms of maximal matchings. Then we enumerate maximal matchings in several classes of graphs made by a linear or cyclic concatenation o... More
Dr. Jurij Kovič, IMFM, UP FAMNIT
This talk will reveal a natural correspondence between rhombic tilings of planar polygonal regions and circle graphs. This correspondence leads to a simple coding of graphs with cyclical sequences that can be used for the classification of graphs. Using this code we can define also various new operations on gr... More
Dr. Mariusz Grech, Mathematical Institute Uniwersity of Wrocław
In 1978 and 1981, S. P. Mohanty, M. R. Sridharan, and S. K. Shukla [2,3] started to consider cyclic automorphism groups, of graphs, of prime and prime power order. Unfortunately the main results were false or had wrong proofs. In [1], I gave a full description of cyclic automorphism groups, of graphs and edge... More
Prof. Marston Conder, University of Auckland
A skew morphism of a group is a variant of an automorphism, which arises in the study of regular Cayley maps (regular embeddings of Cayley graphs on surfaces, with the property that the ambient group induces a vertex-regular group of automorphisms of the embedding). More generally, skew morphisms arise in th... More
A Hamiltonian cycle system (HCS) for a graph or multigraph $\Gamma$ is a set $\cal B$ of Hamiltonian cycles of $\Gamma$ whose edges partition the edge set of $\Gamma$. A cycle system is {\em regular} if there is an automorphism group $G$ of the graph $\Gamma$ acting sharply transitively on the vertices of $\Gamm... More
Mr. Martin Merker, Technical University of Denmark
The Tree Decomposition Conjecture by B\'arat and Thomassen states that for every tree $T$ there exists a natural number $k(T)$ such that the following holds: If $G$ is a $k(T)$-edge-connected graph with size divisible by the size of $T$, then $G$ can be edge-decomposed into subgraphs isomorphic to $T$. So far this c... More
Dr. Christoph Flamm, University of Vienna
Various measures e.g. atom economy or number of used reactions are frequently used in Organic Synthesis to evaluate and compare different total synthesis'. These measures shape the strategies how organic chemists design a synthesis to a target molecule. Metabolic engineering, a sub-field of Synthetic Biology, inve... More
A {\it determining set} $S$ is a set of vertices with the property that each automorphism of the graph is uniquely identified by its action on $S$. The {\it distinguishing number} is the smallest number of colors necessary to color the vertices so that no nontrivial automorphism preserves the color classes. If a g... More
Dr. Atsuhiro Nakamoto, Yokohama National University
Wagner proved that any two plane {\em triangulations} with $n > 3$ vertices can be transformed into each other by diagonal flips. His proof gives us an algorithm to transform them by $O(n^2)$ diagonal flips. However, Komuro has given an algorithm with $O(n)$ diagonal flips, and proved that the order is best possib... More
Prof. Edwin van Dam, Tilburg University
A directed graph is called strongly $\ell$-walk regular if the number of walks of length $\ell$ from one vertex to another depends only on whether the two vertices are the same, adjacent, or not adjacent. This generalizes the concept of directed strongly regular graphs and a problem introduced by Hoffman. It also ge... More
Gábor Somlai, Ben Gurion University of Negev
The investigation of CI-groups started with the conjecture of \'Ad\'am. Using the terminology later introduced by Babai, he conjectured that every cyclic group is a CI-group. A group $G$ is called a CI-group when two Cayley graphs of $G$ are isomorphic only if there is an automorphism of the group $G$ which indu... More
Prof. Zsolt Tuza, MTA Rényi Institute & University of Pannonia
We consider a variation of the graph domination problem, which involves two positive integer parameters $k$ and $d$. Given a connected graph $G$ and a partition $(V_1,\dots,V_k)$ of its vertex set $V(G)$, the task is to find subsets $D_1,\dots,D_k$ of $V(G)$ such that for each $v\in V_i$ there is a vertex $v'\in D_i... More
Dr. Marcin Anholcer, Poznan University of Economics
Let $G=(V,E)$ be a graph of order $n$. A distance magic labeling of $G$ is a bijection $\ell \colon V(G)\rightarrow \{1,\ldots ,n\}$ for which there exists a positive integer $k$ such that $\sum_{x\in N(v)}\ell (x)=k$ for all $v\in V $, where $N(v)$ is the neighborhood of $v$. We show how the analysis of graph s... More
Dr. Sara Sabrina Zemljic, Science Institute, University of Iceland
Sierpi\'nski graphs form a family of graphs which has been studied thoroughly especially due to its connections to the problem of the Tower of Hanoi puzzle. The puzzle is interesting because of several open problems, for example an optimal solution for 4 (or more) pegs. These can be linked to the state graphs of the... More
Prof. Yoomi Rho, Incheon National university
An $L(h,k)$-labeling of a graph $G=(V,E)$ is a function $f$ on $V$ such that $|f(u)-f(v)|\ge h$ if ${\rm dist}(u,v)=1$ and $|f(u)-f(v)|\ge k$ if ${\rm dist}(u,v)=2$. The span of $f$ is the difference between the maximum and the minimum of $f$. The $L(h,k)$-labeling number $\lambda_{h,k}(G)$ of $G$ is the minimu... More
Ms. Aline Parreau, CNRS - Université Lyon 1
We consider the problems of finding optimal identifying codes, (open) locating-dominating sets and resolving sets of an interval or a permutation graph. In these problems, one asks to distinguish all vertices of a graph by a subset of the vertices, using either the neighbourhood within the solution set or the dis... More
Dr. Marcin Krzywkowski, University of Johannesburg
A subset $D$ of the set of vertices of a graph $G$ is a dominating set if any vertex not in $D$ is adjacent to some vertex of $D$. The domination number $\gamma(G)$ is the minimum cardinality of a dominating set of $G$. The concept of domination stability was introduced in [1]. The domination stability, or just $\ga... More
Mr. Antonio González, University of Seville
In this talk, we discuss several relationships among some special sets of vertices of graphs such as metric-locating-dominating sets, locating-dominating sets and doubly resolving sets. First, we extend a result of Henning and Oellermann (2004) by proving that the location-domination number of a graph is... More
Prof. Kirsti Wash, Trinity College
Given two disjoint copies of a graph $G$, denoted $G^1$ and $G^2$, and a permutation $\pi$ of $V(G)$, the graph $\pi G$ is constructed by joining $u \in V(G^1)$ to $\pi(u) \in V(G^2)$ for all $u \in V(G^1)$. $G$ is said to be a universal fixer if the domination number of $\pi G$ is equal to the domination number of ... More
Mr. Cherif Sellal, Polytechnique de Montréal
We study necessary and sufficient conditions for existence of a simple graph $G$, and for a simple and connected graph $G'$ with given numbers $m_{ij}$ of edges with end-degrees $i$, $j$ for $i \le j \in \{1, 2, . . . , \Delta \}$ where $\Delta$ denotes the maximum degree of $G$ or $G'$. Applications in Mathemati... More
Dr. Hanna Furmanczyk, University of Gdansk
The minimum number of total independent sets of $V \cup E$ of graph $G(V,E)$ is called the \emph{total chromatic number} of $G$, denoted by $\chi''(G)$. If difference of cardinalities of any two total independent sets is at most one, then the minimum number of total independent partition sets of $V \cup E$ is calle... More
Benzenoid systems or hexagonal systems are subgraphs of a hexagonal lattice. Open-ended carbon nanotubes alias tubulenes can be seen as an embedding of a benzenoid system to a surface of a cylinder with some perimeter edges being joined. Carbon nanotubes are interesting materials with some unusual properties and ... More
Mr. Thomas William Tucker, Colgate University
Given a finite group $G$ of orientation-preserving isometries of euclidean 3-space $E^3$ and a closed surface $S$, an immersion $f: S\rightarrow E^3$ is in $G$-general position if $f(S)$ is invariant under $G$, points of $S$ have disk neighborhoods whose images are in general position, and no singular points of $f... More
Dr. Mateja Šajna, University of Ottawa
A {\em flag} of a hypergraph $H=(V,E)$ is an ordered pair $(v,e)$ with $v \in V$, $e \in E$, and $v \in e$. A {\em closed trail} of $H$ is a sequence $W=v_0e_0v_1e_1v_2\ldots v_{k-1}e_{k-1}v_0$ with $v_i \in V$, $e_i \in E$, and $v_i,v_{i+1} \in e_i$ for each $i \in \mathbb{Z}_k$ such that no flag --- that is, $(v_i... More
Dr. Domenico Labbate, Dipartimento di Matematica, Informatica ed Economia - Università degli Studi della Basilicata - Potenza
A graph $G$ is $1$--extendable if every edge belongs to at least one $1$--factor. %An orientation of a graph $G$ is an assignment of a {\em direction} to each %edge of $G$. Now suppose that Let $G$ be a graph with a $1$--factor $F$. Then an {\em even $F$--orientation} of $G$ is an orientation in which each $F$-... More
Prof. Stanislav Jendroľ, P. J. Šafárik University in Košice
Let $G=(V,E,F)$ be a connected loopless and bridgeless plane graph, with vertex set $V$, edge set $E$, and face set $F$. Let $X\in\{V,E,F,V\cup E,V\cup F,E\cup F,V\cup E\cup F\}$: Two elements $x$ and $y$ of $X$ are \emph{facially adjacent} in $G$ if they are incident, or they are adjacent vertices, or adjacent face... More
Mr. Mate Vizer, MTA Alfréd Rényi Institute of Mathematics
Suppose we are given a set of $n$ balls $\{b_1,\ldots,b_n\}$ each colored either red or blue in some way unknown to us. To find out some information about the colors, we can query any triple of balls $\{b_{i_1},b_{i_2},b_{i_3}\}$. As an answer to such a query we obtain (the index of) a {\em majority ball}, that is... More
Mr. Pierre Hansen, HEC Montréal
Computers have been used extensively to solve exactly or approximately a large variety of combinatorial otimization problems defined on graphs. It has also been noticed, in the last two decades, that computers can be used to advance graph theory {\it per se}. Several systems (e.g., Graph, Graffiti, AutoGraphiX, Grap... More
Prof. Liming Xiong, Beijing Insititute of Technology
In this talk, we present some results relation between forbidden subgraphs and hamiltonian propertices (such as the existence of hamiltonian cycles, hamiltonian paths and spanning closed trails In particular, our results show how it affects the forbidden subgraphs to guarteeing the same hamiltonian propertic... More
Dr. Valentina Pepe, Sapienza University of Rome
Let $H$ be a fixed graph. The {\em Tur\'an number} of $H$, denoted $ex(n,H)$, is the maximum number of edges that a graph with $n$ vertices and not containing a copy of $H$ can have. When $H$ is bipartite, in many cases, even the question of determining the right order of magnitude for $ex(n,H)$ is not known. We hav... More
We show that every $\frac{1}{k-1}$-tough $2K_2$-free graph admits a $k$-walk, and it can be found in polynomial time. For this class of graphs, this proves a long-standing conjecture due to Jackson and Wormald (1990). Furthermore, we prove that every $(1+\epsilon)$-tough $2K_2$-free graph is prism-Hamiltonian. ... More
Graph structures may be used to model computer networks. Each vertex in a graph is a possible location for an intruder (fault in a computer network, spoiled device). So, a correct surveillance of each vertex of the graph to control such a possible intruder would be worthwhile. In this sense, Slater (1975) brought in... More
Mr. Barry Monson, University of New Brunswick
If you truncate an equilateral triangle $\{3\}$ to its edge midpoints you get another, smaller $\{3\}$. If you truncate a regular tetrahedron $\{3, 3\}$ to its edge midpoints, you get (a little unexpectedly) a regular octahedron $\{3, 4\}$. In higher ranks, the fully truncated n-simplex $\mathcal{T}_n$ is no ... More
Mr. Simon Schmidt, Joseph Fourier's University Grenoble
The domination game is played on a graph $G$ by Dominator and Staller. The two players are taking turns choosing a vertex from $G$ such that at least one previously undominated vertex becomes dominated. Dominator wants to finish the game as fast as possible, while Staller wants to prolong it. The game is called D-ga... More
Prof. Emrah Akyar, Anadolu University
In this study we consider a graph coloring game invented by Bodlaender and Brams independently. Let $G=(V,E)$ be a finite simple graph and $X$ be a set of colors. The game chromatic number of $G$ is defined via a two-person finite game. Two players, generally called Alice and Bob, with Alice going first, alternative... More
Mr. Jesus Leanos Macias, University of Maribor
Gauss has given necessary but not sufficient conditions for a sequence of letters to represent the sequence of self-crossings of some closed planar curve. Such sequences of letters were called Gaussian words and recently generalized to Gaussian paragraphs, sets of words that arise from sequences of crossings of seve... More
Dr. Gábor Nyul, Institute of Mathematics, University of Debrecen
B. Duncan and R. Peele were the first who studied enumeration of independent partitions of graphs from a combinatorial point of view, and introduced Stirling numbers of the second kind and Bell numbers for graphs. In our talk, we present properties of these numbers and values for special graphs, as well as their ... More
Dr. Ademir Hujdurović, University of Primorska
For a given group G, an automorphism $\alpha$ of $G$ of order two, and a subset $S$ of $G$, we define a generalized Cayley graph to be the graph with the vertex set $G$, and the edge set ${ { x, \alpha(x) } | x in G }$. In order to get an undirected graph without loops we add some additional constrains on the set $S... More
Dr. Csilla Bujtás, University of Pannonia, Veszprém
In the domination game, Dominator and Staller alternately choose a vertex of a graph $G$ and take it into a set $D$. The number of vertices dominated by the set $D$ must increase with each move and the game ends when $D$ becomes a dominating set of $G$. Dominator aims to minimize while Staller aims to maximize the n... More
Mr. Jian Bing Liu, Beijing Jiaotong University
The genus distribution of a graph $G$ is defined to be the sequence ${g_m}$, where $g_m$ is the number of different embeddings of $G$ in the closed orientable surface of genus $m$. In this paper, we examine the genus distribution of Cayley maps for several Cayley graphs. It will be shown that the genus distribution... More
Michal Kotrbčik, Masaryk University
The talk is concerned with genus of ring-like graphs obtained by repeatedly amalgamating complete or complete bipartite graphs over one vertex in a path-like manner, and then identifying two vertices, one from each graph at the end of the path. A theorem of Decker, Glover, and Huneke easily yields that the genus of ... More
Dr. Stefano Pasotti, Università degli Studi di Brescia
Over the last ten years several authors established and studied the correspondence between geometric structures, loops and regular permutation sets. These relationships were first introduced in [2] in order to associate to the point-set of a general hyperbolic geometry over a Euclidean field the algebraic structure ... More
Prof. Brendan Damien McKay, Australian National University
We give a brief overview of the art of generating graph classes on the computer, with particular attention to avoidance of isomorphs. Our examples will include two recent projects. One is to generate fullerenes without adjacent pentagons (joint with Jan Goedgebeur) and the other is to catalogue all small Turan grap... More
The classification of regular graphs with second largest eigenvalue at most 1 is equivalent to the classification of regular graphs with smallest eigenvalue at least -2. Such graphs have received a great deal of attention. Another well-studied family of graphs are regular graphs having precisely three distinct eig... More
Mr. Atthakorn Sakda, Chulalongkorn University
A \textit{group divisible design} GDD($g = g_1+g_2+ \cdots + g_s,s,k;\lambda_1,\lambda_2$) is an ordered pair ($G, \mathcal{B}$) where $G$ is a $g$-set of treatments which is partitioned into $s$ sets (called \textit{groups}) of sizes $g_1,g_2,\ldots,g_s$, and $\mathcal{B}$ is a collection of $k$-subsets of $G$ ca... More
Mr. Primož Moravec, University of Ljubljana
A subgroup $H$ of a group $G$ is called self-centralizing if $C_G(H)$ is contained in $H$. In this talk we describe finite groups in which every non-cyclic subgroup is self-centralizing, and apply this information to certain classes of infinite groups with the same property. We also consider groups in which every no... More
A Gr\"{u}nbaum coloring of a triangulation $T$ of a surface $F^2$ is a 3-edge-coloring of $T$ such that every face of $T$ receives all the three colors. A Gr\"{u}nbaum coloring of $T$ 1-to-1 corresponds to a proper 3-edge-coloring of the dual $T^*$ of $T$. Robertson conjectured that every locally planar triangula... More
Dr. Simona Bonvicini, University of Modena and Reggio Emilia
A graph is Hamiltonian if it contains a spanning cycle (Hamiltonian cycle). A cubic Hamiltonian graph has a perfect matching (actually, three edge-disjoint perfect matchings). There are cubic graphs that have a perfect matching but are not Hamiltonian, see for instance the Petersen graph. Nevertheless, we may restr... More
Dr. Aaron Williams, Bard College at Simon's Rock
\emph{Buttons \& Scissors} is a free single-player puzzle available on iOS and Android. The puzzle is played on an $n$-by-$n$ grid, where each position is empty or has a coloured button sewn onto it. The player's goal is to remove all of the buttons using a sequence of horizontal, vertical, and diagonal scissor cu... More
Prof. Zbigniew Lonc, Warsaw University of Technology
A \emph{harmonious} coloring of a $k$-uniform hypergraph $H$ is a rainbow vertex coloring such that each $k$-set of colors appears on at most one edge. A rainbow coloring of $H$ is \emph{achromatic} if each $k$-set of colors appears on at least one edge. The \emph{harmonious number} (resp. \emph{achromatic number}) ... More
It is shown that an undirected graph $G$ is cospectral with the Hermitian adjacency matrix of a mixed graph $D$ obtained from a subgraph $H$ of $G$ by orienting some of its edges if and only if $H=G$ and $D$ is obtained from $G$ by a four-way switching operation; if $G$ is connected, this happens if and only if $\la... More
Dr. Tetsuji Taniguchi, Hiroshima Institute of Technology
Hoffman graphs were introduced by Woo and Neumaier [2] to extend the results of Hoffman [1]. Hoffman proved what we would call Hoffman's limit theorem which asserts that, in the language of Hoffman graphs, the smallest eigenvalue of a fat Hoffman graph is a limit of the smallest eigenvalues of a sequence of ... More
In this talk, we first give a relation between the Homfly polynomal and the weighted Tutte polynomial. Then we discuss applications of the relation to DNA double crossover polyhedra. More
Mr. Gábor Tardos, Rényi Institute, Budapest
Homomorphism duality pairs play a crucial role in the theory of relational structures and in the Constraint Satisfaction Problem. In this talk we concentrate on infinite-finite duality pairs of directed graphs. We find a characterization of infinite antichains that allow for a finite dual. The characterization rese... More
In the domination game, two players alternate turns marking a vertex in a graph. When it is marked, a vertex must dominate at least one new vertex, either itself or one of its neighbours. When the set of marked vertices forms a dominating set (not necessarily minimal), the game comes to an end and the score of the g... More
Prof. Paul-Hermann Zieschang, Department of Mathematics, University of Texas, Brownsville, TX 78520
Let $S$ be a set, and let $\mu$ be a map from $S\times S$ to the power set of $S$. For any two elements $p$ and $q$ of $S$, we write $pq$ instead of $\mu(p,q)$ and assume that $pq$ is not empty. For any two non-empty subsets $P$ and $Q$ of $S$, we define the {\em complex product}\index{complex product} $PQ$ to be th... More
Dr. Dimitri Leemans, University of Auckland
In this talk we will show that all hypertopes whose automorphism group is a Suzuki simple group are necessarily hyperpolyhedra. We will also discuss future research directions in the same vein. More
Mr. Thomas William Tucker, Colgate University
e genus polynomial $g_G(z)=\Sigma a_iz^i$ of graph $G$ is the generating function where $a_i$ is the number of imbeddings of $G$ in the surface of genus $i$. A genus polynomial is always {\em interpolating}, that is the nonzero coefficients form an interval. Little else is known; for example the number of imbeddin... More
Prof. Xueliang Li, Center for Combinatorics, Nankai University
In this talk we will give a unified viewpoint on indices, polynomials and matrices of graphs. Starting from a graph with weights on edges or vertices, one can get various kinds of graph indices, graph polynomials, and graph matrices. Then, we can see that a lot of new and interesting objects can be taken into accoun... More
Prof. Rögnvaldur G. Möller, University of Iceland
Tutte's two papers from 1947 and 1959 on cubic graphs were the starting point of the in-depth study of the interplay between the structure of a group and the structure of a graph that the group acts on. In this talk I will describe applications of Tutte's ideas where it is assumed that the graph is infinite and the... More
Dr. Simon Mark Smith, City University of New York
We say that two permutation groups $A, B$ on the same set $X$ are {\em strongly orbit equivalent} if $A$ and $B$ have the same orbits on the power set $2^X$. Groups strongly orbit equivalent to finite symmetric groups were first considered by J. von Neumann and O. Morgenstern in 1947. We call a group $B$ {\em str... More
A permutation of the affine space $AG(n,q)$ is called an integral automorphism if it preserves the integral distance defined among the points. The integral automorphisms which are also semiaffine transformations were determined by Kurz and Meyer (2009). In this talk, we show that there is no additional integral au... More
Mr. Hrant Khachatrian, Yerevan State University
An edge-coloring of a graph $G$ with colors $1,\ldots,t$ is an interval $t$-coloring if all colors are used, and the colors of edges incident to each vertex of $G$ are distinct and form an interval of integers. A graph $G$ is interval colorable if it has an interval $t$-coloring for some positive integer $t$. Fo... More
Dr. Yusuke Suzuki, Niigata University
We discuss the existence of minors of given graphs in optimal $1$-planar graphs. As our first main result, we prove that for any graph $H$, there exists an optimal $1$-planar graph which contains $H$ as a topological minor. Next, we consider minors of complete graphs, and prove that every optimal $1$-planar graph ... More
Dr. Susana Clara López, Universitat Politècnica de Catalunya
For $m\le n$, we denote the set $\{m,m+1,\ldots, n\}$ by $[m,n]$. Let $d$ be a positive integer. A {\it Langford sequence} of order $m$ and defect $d$ is a sequence $(l_1,l_2,\ldots, l_{2m})$ of $2m$ numbers such that (i) for every $k\in [d,d+m-1]$ there exist exactly two subscripts $i,j\in [1,2m]$ with $l_i=l_j=k$... More
Mr. Jozef Siran, Open University and Slovak University of Technology
It has been known that for diameters $k\in \{2,3,5\}$, graphs of diameter $k$ and maximum degree $q+1$ for infinite sets of prime powers $q$ and with orders asymptotically approaching the corresponding Moore bounds can be obtained from generalised triangles, quadrangles and hexagons. These graphs, however, are not v... More
Dr. Hiroshi Nozaki, Aichi University of Education
It is known that for any given integer $k\geq 3$ and real number $\lambda<2\sqrt{k-1}$, there are only finitely many $k$-regular graphs whose second largest eigenvalue is at most $\lambda$. In this talk, we give a new upper bound for the order of such a graph for given $k$ and $\lambda$. The main tool is the linear ... More
Prof. Gabor Korchmaros, Department of Mathematics, Informatics and Economy of University of Basilicata
We deal with some problems in Finite geometry arising from current research on $AG$ (algebraic-geometry) codes defined over the Hermitian curve. In $PG(2,q^2)$, let $\mathcal H$ be the Hermitian curve. For a fixed positive integer $d$, let $\mathbf{S}_d$ be the family of all degree $d$ plane algebraic curve... More
Prof. Paul Horn, University of Denver
Harnack inequalities relate the maximum and minimum values of eigenfunctions or positive solutions to the heat equation. These are classical in the manifold setting, and versions are also known for functions on graphs. It is known that a graph satisfying a so-called parabolic Harnack inequality is equivalent to the... More
Mr. Jakub Przybyło, AGH University of Science and Technology
It is well known that there are no \emph{irregular graphs}, understood as simple graphs with pairwise distinct vertex degrees, except the trivial $1$-vertex case. A graph invariant called the \emph{irregularity strength} was thus introduced aiming at capturing a level of irregularity of a graph. Suppose that given a... More
Dr. Marietjie Frick, University of South Africa
We say a graph $G$ has a property ${\cal P}$ \emph{locally} (or $G$ is \emph{locally} $\cal P$) if for every vertex $v$ in $G$, the graph induced by the open neighbourhood $N(v)$ of $G$ has property $\cal P$. For example, a graph $G$ is \emph{locally connected} if $G[N(v)]$ is connected for every vertex $v$ in $G$. ... More
Dr. Florent Foucaud, Université Blaise Pascal, Clermont-Ferrand
A locating-dominating set of a graph is a dominating set such that each vertex not in the set has a unique neighbourhood within the set. In 2014, Garijo, Gonz\'alez and M\'arquez conjectured that any twin-free graph without isolated vertices admits a locating-dominating set of size at most half the order. We discus... More
Ms. He Chen, Department of Mathematics, Southeast University
Let $G$ be an edge-colored graph. A rainbow (heterochromatic, or multicolored) path of $G$ is such a path in which no two edges have the same color. Let the color degree of a vertex $v$ to be the number of different colors that are used on edges incident to $v$, and denote it to be $d^c(v)$. It was showed that i... More
Mr. Riste Škrekovski, FMF, FIS, IMFM, FAMNIT
The Wiener index (i.e., the total distance or the transmission number), defined as the sum of distances between all unordered pairs of vertices in a graph, is one of the most popular molecular descriptors. In this talk, I will summarize some results, conjectures, and problems on this molecular descriptor, with emph... More
Prof. Irene Sciriha, University of Malta
A graph $G$ is singular of nullity $\eta $ if the nullspace of its adjacency matrix ${\bf G}$ has dimension $\eta $. Such a graph contains $\eta $ cores determined by a basis, with minimum support sum, for the nullspace of ${\bf G}$. These are induced subgraphs of singular configurations, the latter occurrin... More
Andrej Taranenko, Faculty of Natural Sciences and Mathematics, University of Maribor
We introduce an apparatus to measure closeness or relationship of two given objects. This is a topology based apparatus that uses graph representations of the compared objects. In more detail, we obtain a metric on the class of all pairwise non-isomorphic connected simple graphs to measure closeness of two such gra... More
Dr. Robert Bailey, Grenfell Campus, Memorial University
The metric dimension of a graph $\Gamma$ is the least size of a set of vertices $\{v_1, \ldots, v_m\}$ with the property that, for any vertex $w$, the list of distances from $w$ to each of $v_1, \ldots, v_m$ uniquely identifies $w$. In this talk, we consider the metric dimension of imprimitive distance-regular gr... More
We consider the following problem: Over the class of all simple connected unicyclic graphs on $n$ vertices with girth $g$ ($n,g$ being fixed), which graph minimizes the Laplacian spectral radius? Let $U_{n,g}$ be the lollipop graph obtained by appending a pendent vertex of a path on $n-g\;(n> g)$ vertices to a verte... More
Dr. Ida Kantor, Charles University, Prague
In this talk, we want to represent the vertices of a graph with finite sets in such a way that two vertices are adjacent if and only if their sets are ``very different" (this is similar, e.g., to the notion of Kneser graphs). More precisely, a {\em $k$-min-difference representation} of $G$ is an assignment of a set ... More
Mr. Mustafa Kemal Tural, Middle East Technical University
Given a weighted simple graph, the minimum weighted maximal matching (MWMM) problem is the problem of finding a maximal matching of minimum weight. The MWMM problem is NP-hard in general, but is polynomial-time solvable in some special classes of graphs. For instance, it has been shown that the MWMM problem can be s... More
Prof. Irene Sciriha, University of Malta
According to the Source and Sink Potential (SSP) model, for a chosen two--vertex--connection, a molecule is a conductor or an insulator, at the Fermi–-level. Of particular interest are two classes of graphs that have analogous vertex pairs, that is the molecule shows the same behaviour for any two-... More
Dr. Bert Hartnell, Saint Mary's University
Rather than guarding a network with a minimum dominating set, consider having two types of monitors available, cameras (can see adjacent nodes) and listeners (can detect the distance to an intruder). Preliminary results for finding the minimum number of such monitors for trees will be outlined. More
Prof. Anita Pasotti, Università degli Studi di Brescia
Let $K_v$ be the complete graph with vertex-set $\{0,1,\ldots,v-1\}$. The length of any edge $[x,y]$ of $K_v$ is defined by $d(x,y)=min(|x-y|,v-|x-y|)$. In 2007 Buratti conjectured that if $v$ is a prime, then there exists a Hamiltonian path of $K_v$ whose list of edge-lengths is ANY prescribed multiset $L$ of $... More
Dr. Eugenia O'Reilly-Regueiro, IMUNAM
Given $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 any two are adjacent if and only if they are disjoint. For a subset $\Gamma$ of $V(O_{k+1})$, there is an incidence structure $D$ between the elements of $X$ and those of $\Gamma$. ... More
Prof. Peter Dankelmann, University of Johannesburg
Let $G$ be a connected graph of order $n$. The {\it eccentricity} ${\rm ecc}(v)$ of a vertex $v$ of $G$ is the distance from $v$ to a vertex farthest from $v$, i.e., ${\rm ecc}(v) = \max_{w\in V(G)} d(v,w)$, where $V(G)$ is the vertex set of $G$ and $d(v,w)$ denotes the distance between $v$ and $w$ in $G$. ... More
Prof. Edward D. Hanson, SUNY New Paltz
Roughly speaking, a Leonard pair can be thought of as an algebraic generalization of a $Q$-polynomial distance-regular graph. Because of this connection, there are sequences of parameters associated with Leonard pairs that generalize the intersection numbers of a distance-regular graph. In this talk, we will discuss... More
I will report of recent work with Gernot Stroth and others focussed on the classification of finite simple groups of local characteristic $p$. More
Ms. Irena Momčilo Jovanović, School of Computing, Union University
In this talk, digraphs will be considered by means of eigenvalues of the matrix $AA^T$ (or $A^TA$) where $A$ is the adjacency matrix of a digraph. The common spectrum of these matrices is called the \emph{non-negative spectrum} or the \emph{$N$-spectrum} of a digraph. Several properties of the $N$-spectrum together ... More
Mr. Alexander Farrugia, University of Malta
A NSSD is an undirected, non--singular graph on $n$ vertices with weighted edges and no loops whose $n$ vertex--deleted subgraphs are all singular. A graph with adjacency matrix {\bf G} is a NSSD if and only if the graph with adjacency matrix ${\bf G}^{-1}$ is a NSSD. We show that this also holds for the subclass of... More
Prof. Eckhard Steffen, Paderborn University
Tutte's 5-Flow Conjecture from 1954 states that every bridgeless graph has a nowhere-zero 5-flow. We prove that every cyclically 6-edge-connected cubic graph with oddness at most 4 has a nowhere-zero 5-flow. Therefore, every possible minimum counterexample to the 5-flow conjecture has oddness at least 6. More
Prof. Tomaž Pisanski, University of Primorska and University of Ljubljana
Odin, a magnificent 13 ton steel sculpture is used as a case study of mathematical analysis of art. In particular, it shows the connection between geometry (circle packing) and topological graph theory (medial of a map). Recently a Symposium on Odin has been hosted by the Colgate University ( More
Mr. Grigory Ryabov, Novosibirsk State University
Let $G$ be a finite group. If $\Gamma$ is a permutation group with $G_{right}\leq\Gamma\leq Sym(G)$ and $\mathcal{S}$ is the set of orbits of the stabilizer of the identity $e$ in $\Gamma$, then the $\mathbb{Z}$-submodule $\mathcal{A}(\Gamma,G)=Span_{\mathbb{Z}}\{\underline{X}:\ X\in\mathcal{S}\}$ of the group ring... More
Mr. Wilfried Imrich, Montanuniversitaet Leoben
The talk begins with a new, concise proof of a generalization of a theorem of Halin about locally finite, infinite graphs to graphs with unbounded degrees. Then it investigates when such graphs have finite set of vertices whose stabilizer is the identity automorphism. A bound on the size of such sets, which are c... More
Mr. Safet Penjić, University of Primorska
Let $\Gamma$ denote a $Q$-polynomial bipartite distance-regular graph with diameter $D$, valency $k \ge 3$ and intersection number $c_2\le 2$. In this talk we show the following two results: (1) If $D \ge 6$, then $\Gamma$ is either the $D$-dimensional hypercube, or the antipodal quotient of the $2D$-dimensional ... More
Combining a lower bound due to El-Zahar and Pareek with an upper bound of Vizing we get that for any pair of graphs $G$ and $H$, \[ \min\{|V(G)|,|V(H)|\}\le \gamma(G\,\Box\, H) \le \min \{\gamma(G)|V(H)|, \gamma(H)|V(G)|\}\,.\] We give a complete characterization of the pairs that achieve the lower bound and give ... More
Prof. Misha Muzychuk, Netanya Academic College
Let $\mathcal{A}\subseteq M_\Omega[\mathbb{F}]$ be a coherent algebra. It's Terwilliger algebra $\mathcal{T}_\omega (\mathcal{A})$ is called {\it coherent} if $\mathcal{T}_\omega$ is closed with respect to Schur-Hadamard product. In our talk we'll present some properties of coherent Terwilliger algebra. We als... More
Prof. Bhaskar DasGupta, University of Illinois at Chicago
We show that the problem of computing the strong metric dimension of a graph can be reduced to the problem of computing a minimum node cover of a transformed graph within an additive logarithmic factor. This implies both a 2-approximation algorithm and a $(2-\varepsilon)$-inapproximability for the problem of computi... More
Marko Orel, University of Primorska (Koper); Institute of Mathematics, Physics, and Mechanics (Ljubljana)
I will present two results from matrix theory (two preserver problems), which are closely related to (non)existence of ovoids in certain classical polar spaces. While in the first problem, the nonexistence of ovoids or spreads in polar spaces is just applied to deal with one of the key steps in the proof, the second... More
Prof. Dragan Stevanović, Mathematical Institute, Serbian Academy of Sciences and Arts and University of Primorska, Slovenia
While discussing his spectral bound on the independence number of a graph, Herbert Wilf asked back in 1986 what kind of a graph can have an eigenvector consisting solely of $\pm 1$ entries? This question reappeared independently more than twenty years later while we were studying Jerry Ray Dias' question on the exis... More
Ms. Dan He, Department of mathematics, Southeast university
Let $G$ be a graph. For two nonnegative integers $s$ and $t$, an $(s,t)$-relaxed strong $k$-edge-coloring is an assignment of $k$ colors to the edges of $G$, such that for any edge $e$, there are at most $s$ edges adjacent to $e$ and $t$ edges which are distance two apart from $e$ assigned the same color as $e$.... More
Dr. Ilya Ponomarenko, St. Petersburg Department of V.A. Steklov Institute of Mathematics of the Russian Academy of Sciences
A finite group $G$ is called a Schur group, if any Schur ring over~$G$ is the transitivity module of a point stabilizer in a subgroup of Sym($G$) that contains all right translations. We complete a classification of abelian 2-groups by proving that the group $Z_2\times Z_{2^n}$ is Schur. We also prove that any no... More
A graph is a strongly regular graph with parameters $(n,k,\lambda,\mu)$ if it is a $k$-regular graph of order $n$ such that each pair of adjacent vertices has in $G$ exactly $\lambda$ common neighbors and each pair of non-adjacent vertices has in $G$ exactly $\mu$ common neighbors. There exist several necessa... More
Ms. Bojana Mihailović, University of Belgrade - School of Electrical Engineering
For a simple graph $G$ (a non-oriented graph without loops or multiple edges), with the $\left( 0,1\right) $-adjacency matrix $A$, we define $P_G\left( \lambda \right) =\det \left( \lambda I-A\right) $ to be its \textit{characteristic polynomial}. The roots of the characteristic polynomial are the \textit{eigenva... More
Dr. Boris Furtula, Faculty of Science, University of Kragujevac
A number of topological indices ($TI$s) was increasing rapidly in the past decade. However, their applications do not follow such trend. This fact significantly decreases the reputation of chemical graph theory in scientific community. As a remedy for such problem, stringent criteria for the introducing a "new" ... More
Prof. Heping Zhang, Lanzhou University
The anti-forcing number of a connected graph $G$ is the smallest number of edges such that the remaining graph obtained by deleting these edges has a unique perfect matching. In this paper, we show that the anti-forcing number of every fullerene has at least four. We give a procedure to construct all fullerenes ... More
Dr. Qiuli Li, Lanzhou University
The anti-Kekul\'{e} number of a connected graph $G$ is the smallest number of edges to be removed to create a connected subgraph without perfect matchings. In this article, we show that the anti-Kekul\'{e} number of a 2-connected cubic graph is either 3 or 4, and the anti-Kekul\'{e} number of a connected cubi... More
Dr. Sergio Hiroki Koike Quintanar, University of Primorska
Let $G$ be a finite group. A Cayley object is a relational structure with underlying set $G$ which is invariant under all right translations $x \mapsto xg$, $x,g \in G$. Given a class $\mathcal{K}$ of Cayley objects of $G$, the group $G$ is said to satisfy the CI-property for $\mathcal{K}$ if for any two isomorphic... More
Dr. Vedrana Mikulić Crnković, University of Rijeka
Let $G$ be a transitive group acting on a set $\Omega$, $P$ a subgroup of $G$ and $\Delta$ be a union of some $P$ orbits on $\Omega$. Then $\Delta$ is the base block of the $1$-design. In this talk we will apply this known method of construction of $1$-designs, on which the group $G$ acts as the transitive automorph... More
Dr. Francesco Belardo, University of Primorska
In this talk we will consider the spectra of signed graphs, namely graphs with signs $\{+,-\}$ mapped on the edges. Recently, given a signed graph $\Gamma$, we have defined the signed line graph $\mathcal{L}(\Gamma)$ and the signed subdivision graph $\mathcal{S}(\Gamma)$ in a way that some well-known formulas on the... More
Ms. Claire Pennarun, University of Bordeaux
Eulerian planar maps are planar maps with all vertices of even degree. The number of Eulerian planar maps with a fixed number of edges $m$ is well known, and they are in bijection with many combinatorial families, such as balanced Eulerian trees or bi-cubic maps. Planar Eulerian orientations are directed planar ma... More
Dr. Tommaso Traetta, Ryerson University, Toronto (ON) Canada
The Hamilton--Waterloo problem HWP($\Gamma; m,n; \alpha$, $\beta$) asks for a factorization of the simple graph $\Gamma$ into $\alpha$ $C_m$--factors and $\beta$ $C_n$--factors. The classic version of the problem, that is, the case in which $\Gamma$ is the complete graph is still open, although it has been th... More
Dr. Andrea Burgess, University of New Brunswick
The Hamilton-Waterloo problem $\mathrm{HWP}(K_v;m,n;\alpha,\beta)$ asks whether there exists a decomposition of $K_v$ into $\alpha$ $m$-cycle factors and $\beta$ $n$-cycle factors, where $3 \leq m \leq n$. Necessarily, if such a decomposition exists, then $m$, $n$ and $v$ are all odd, $m$ and $n$ are divisors of $v... More
Mr. Aleksander Kelenc, Faculty of Natural Sciences and Mathematics, University of Maribor
In chemistry, the problem known as similarity searching involves finding a set of molecules that are similar to a given sample molecule. The problem is tackled using graph theory and related algorithmic approaches involving some kind of measure of similarity of two graphs. In this talk we present some results about ... More
Given a finite connected graph $\Gamma$ and a group $G$ acting transitively on the arcs of $\Gamma$, one defines the {\em local group} $G_v^{\Gamma(v)}$ as the permutation group induced by the action of the stabiliser $G_v$ on the neighbourhood $\Gamma(v)$ of a vertex $v$. I will address the following question: ... More
Prof. Susan Antoinette van Aardt, University of South Africa
We give a short survey on old and new results on the orders of hypohamiltonian and hypotraceable graphs, digraphs and oriented graphs. In particular we show that there exists a hypohamiltonian oriented graph of order $n$ if and only if $n\geq 9$ and there exists a planar hypotraceable oriented graph of order $n$... More
Prof. Mirko Horňák, P.J. Šafárik University Košice
Let $G$ be a graph, $C$ a set of colours and $\varphi:E(G)\to C$ a proper edge colouring of $G$. The $\varphi$-palette of a vertex $v\in V(G)$ is the set $\{\varphi(vw):vw\in E(G)\}$. The $\varphi$-diversity is the number of distinct $\varphi$-palettes of vertices of $G$ and the palette index of $G$ is the minimum o... More
Polona Repolusk, University of Maribor, Faculty of natural sciences and mathematics
Given a graph $G$ and a set of $t$ colors $\lbrace 1,2,\ldots , t \rbrace$, assume that we assign an arbitrary subset of these colors to each vertex of $G$. If we require that each vertex to which an empty set is assigned has in its neighborhood all $t$ colors, then this assignment is called a $t$-rainbow dominating... More
A vertex subset $X\subseteq V$ of a graph $G=(V,E)$ is an {\em independent set} of $G$ if no two vertices in $X$ are adjacent in $G$. The cardinality of a largest independent set of $G$ is called the (vertex) {\em independence number} of $G$. A nonempty graph $G$ is {\em $p$-stable} if $p$ is the largest number of ... More
Let $G$ be a simple connected $n$-vertex graph with the vertex set $V(G)=\{ v_{1} ,v_{2} ,...,v_{n} \}$ and let ${\rm P} =(p_{1} ,p_{2} ,...,p_{n} )$ be an $n$-tuple of nonnegative integers. The thorn graph $G_{{\rm P} }$ is the graph obtained by attaching $p_{i}$ pendent vertices to the vertex $v_{i} $ of $G$, ... More
Mr. Matjaž Krnc, Institute of Mathematics, Physics and Mechanics
The well studied Wiener index $W(G)$ of a graph $G$ is equal to the sum of distances between all pairs of vertices of $G$. Denote by $\mathrm{Im}\left(n\right)$ the set of all values of the Wiener Index over all connected graphs on $n$ vertices. Also, let $\mathcal{I}_{n}$ be the largest interval which is fully... More
Dr. Carl Yerger, Davidson College
Given a distribution of pebbles on the vertices of a connected graph $G$, a \textit{pebbling move} is defined as the removal of two pebbles from some vertex and the placement of one of these on an adjacent vertex. The \textit{pebbling number} of a graph $G$ is the smallest integer $k$ such that for each vertex $v$ ... More
Grzegorz Kubicki, University of Louisville, USA, and University of Opole, Poland
We want to maximize the number of moves for a random walk on an even cycle before visiting the vertex opposite to the starting position. Our payoff is the number of moves but it is reduced to 0 if we are not able to avoid the opposite vertex. Optimal stopping time and the expected value of the payoff are determined ... More
Prof. Russ Woodroofe, Mississippi State University
The lattice of order congruences of a poset P is the subposet O(P) of the lattice of partitions of P, consisting of all partitions that satisfy a certain order-convexity property. The partition lattice is both semi-modular and supersolvable, but Körtesi, Radelecki and Szilágyi gave examples of order congruence latt... More
Prof. Tomaž Pisanski, University of Primorska and University of Ljubljana
A maniplex is a discrete structure, introduced in 2012 by Steve Wilson, that generalizes the concept of a map on the one hand, and the concept of an abstract polytope on the other. In a preprint in 2013 Isabel Hubard et al. have defined the notions of orientable and oriented maniplex. In this talk we revisit these... More
Mrs. Katarína Hriňáková, Slovak University of Technology in Bratislava
In this talk we will present an enumeration of orientably-regular maps with automorphism group isomorphic to the twisted linear fractional group $M(q^2)$ for any odd prime power $q$. More
Prof. Carsten Thomassen, Technical University of Denmark
Let $\Gamma$ be an abelian group and $F$ a set of elements of $\Gamma$. We consider the following general problem: Given a graph $G$, is it possible to give every edge a direction and an element from $F$ such that, at every vertex, the in-sum equals the out-sum. Tutte's flow conjectures and the $(2+\epsilon)$-flow c... More
Mr. Ján Karabáš, University of Primorska, Koper and Matej Bel University, Banská Bystrica
An oriented map $M$ is edge-transitive if its group of automorphisms, $\mathrm{Aut}\,M$, acts transitively on the edges of the underlying graph of $M$. The group of orientation-preserving automorphisms, $\mathrm{Aut}^+\,M$, of index at most two of $\mathrm{Aut}\,M$. It follows that the quotient map of an edge... More
Dr. Mingquan Zhan, Millersville University of Pennsylvania
A graph $G$ is said to be pancyclic if $G$ contains cycles of lengths from 3 to $|V(G)|$. The net $B(i,j)$ is obtained by associating one endpoint of each of the path $P_{i+1}$ and $P_{j+1}$ with distinct vertices of a triangle. Ferrara et al. (2013) \cite{FGGMP2013} showed that every 4-connected $\{K_{1,3},B(i,j)\... More
We would like to report recent developments on Ramsey-type problems connected to the cycle partition number. We colour the edges of a graph $G$ by red and blue. In this context, it is conventional to accept {\it empty graphs and one-vertex graphs} as a cycle (of any colour) and also {\it any edge} as a cycle (in... More
Mr. Nino Bašić, University of Ljubljana
Recently a class of molecular graphs, called \emph{altans}, became a focus of attention of several theoretical chemists and mathematicians. In this talk I will present iterated altans and show, among other things, their connections with nanotubes and nanocaps. Using a result of Gutman we are able to enumerate Kekul\... More
Dr. Tomasz Popiel, University of Western Australia
We present some recent results about generalised polygons with collineation groups that act primitively on points. In particular, a group acting point-primitively on a generalised hexagon or octagon must be almost simple of Lie type. More
Prof. Mark E Watkins, Syracuse University
We describe our progress during the past year on the so-called ``GFR problem.'' A {\em GFR}, or {\em graphical Frobenius representation}, is a graph whose automorphism group acts as a Frobenius permutation group, that is, it acts vertex-transitively but not regularly and only the identity automorphism fixes more th... More
Dr. Gabriela Araujo-Pardo, Mathematics Institute, National University of Mexico
In this paper we study these two parameters for the complete graph $K_n$. First, we prove that, when $q$ is a power of $2$ and $n=q^2+q+1$, the pseudoachromatic index $\psi'(K_n)$ of the complete graph $K_n$ is at least $q^3+2q-3$; which improves the bound $q^3+q$ given by Araujo, Montellano and Strausz [J Graph The... More
Mrs. Gloria Rinaldi, University of Modena and Reggio Emilia
A $k-$cycle system of order $v$ is a decomposition of the complete graph on $v$ vertices into cycles of length $k$. An automorphism group of the system is a permutation group on the vertex set preserving the decomposition into cycles. If we ask the group to satisfy some particular requests, then we have two probl... More
Nonsymmetric Askey-Wilson polynomials were defined by Sahi in 1999. Roughly speaking, they are the eigenfunctions of the Cherednik-Dunkl operator and form a linear basis of the space of the Laurent polynomials in one variable. In my thesis (2013), we found a relationship between $Q$-polynomial distance-regular graph... More
Prof. Sunil Chandran Leela, Indian Institute of Science, Bangalore
Rainbow connection number, $rc(G)$, of a connected graph $G$ is the minimum number of colors needed to color its edges so that every pair of vertices is connected by at least one path in which no two edges are colored the same (note that the coloring need not be proper). In this paper we study the rainbow connection... More
A colouring of a graph G is called distinguishing if it is not preserved by any nontrivial automorphism of G. Equivalently, a colouring is distinguishing if its stabiliser in the automorphism group is trivial, i.e., only consists of the identity. Tucker conjectured that, if each automorphism of a graph moves infinit... More
Dr. Primož Šparl, University of Ljubljana and University of Primorska
In 2002 Maru\v si\v c and Poto\v cnik introduced an infinite family of relations (now called {\em reachability relations}) on (finite) digraphs and proved various interesting results regarding them. In 2008 these relations were studied in the context of infinite digraphs by Malni\v c, Maru\v si\v c, Seifter, \v S... More
Dr. Roghayeh Hafezieh, Gebze Technical University
Let X be a finite set of positive integers. Let P(X) be the set of all primes dividing the elements of X and X* be the set of all elements of X different from 1. The bipartite divisor graph of X, which is denoted by B(X), has the disjoint union of P(X) with X* as its vertex set and one vertex like p from the first ... More
Prof. Stephan Wagner, Stellenbosch University
This talk reviews some recent results on the number of subtrees of a tree and related tree invariants. Specifically, we will be looking at extremal trees (maximising or minimising the number of subtrees) under various conditions, bounds on the average subtree order (average size of a randomly chosen subtree of a tre... More
Aleksander Vesel, University of Maribor, IMFM
A benzenoid graph is a finite connected plane graph with no cut-vertices in which every interior region is bounded by a regular hexagon of a side length one. A coronoid $G$ is a connected subgraph of a benzenoid graph such that every edge lies in a hexagon of $G$ and $G$ contains at least one non-hexagon interior ... More
Mr. Daniele Bartoli, Department of Mathematics - Gent University
Let $\Gamma=(V,E)$ be a graph. A vertex $v\in V$ is resolved by a vertex-set $S = \{v_1, \ldots, v_n\}$ if its (ordered) distance list $(d(v, v_1), \ldots, d(v, v_n))$ with respect to $S$ is unique. S is a resolving set in $\Gamma$ if every vertex $v\in V$ is resolved by $S$. The metric dimension of $\Gamma$ is the... More
Prof. Ian Wanless, Monash University
An {\em $r$-partite hypergraph} has a partition of the vertices into disjoint sets $V_1,\dots,V_r$ and every edge includes exactly one vertex from each $V_i$. A {\em matching} in a hypergraph $H$ is a set of disjoint edges. The largest size of a matching in $H$ is denoted $\nu(H)$. A {\em cover} in a hypergraph ... More
Prof. Christopher Perkins French, Grinnell College
We say a group $K$ is an extension of $G$ by $N$ if $K$ contains a normal subgroup isomorphic to $N$ with quotient isomorphic to $G$; such an extension then determines a ``twisting" homomorphism $\phi:G\to \text{Aut}(N)$. If, on the other hand, we are given groups $N$ and $G$, and a homomorphism $\phi:G\to\text{Aut... More
Prof. Andrey Vasilyev, Sobolev Institute of Mathematics
A sufficient condition for a homogeneous coherent configuration (or simply a scheme) to have the (combinatorial) base of size $2$ is proved. This result is applied to the Cartan scheme of a finite simple group $G$ with BN-pair; by definition, it is the coherent configuration associated with the action of $G$ on the... More
A design over the finite field $\mathbb{F}_q$ with parameters $t$-$(v,k,\lambda)_q$ is a pair $(\mathcal{V}, \mathcal{B})$ where $\mathcal{V}$ is the $v$-dimensional vector space over $\mathbb{F}_q$ and $\mathcal{B}$ is a collection of $k$-dimensional subspaces of $\mathcal{V}$, such that each $t$-dimensional subspa... More
Prof. Egon Schulte, Northeastern University
Highly symmetric polyhedra-like structures in ordinary euclidean 3-space have a long history of study tracing back to the early days of geometry. With the passage of time, various notions of polyhedra have brought to light new exciting figures intimately related to finite or infinite groups of isometries. In the 197... More
Dr. Sanja Rukavina, Department of Mathematics, University of Rijeka
Graphs in which each pair of nonadjacent vertices has at most $k$ paths of minimum length between them are called $k$-geodetic graphs. We will discuss some properties of $k$-geodetic graphs constructed from block designs. LDPC codes based on the adjacency matrix of $k$-geodetic graphs obtained from block designs wi... More
In this talk, we will consider some regular Cayley maps on dihedral groups and their corresponding skew-morphisms. Especially, reflexible regular Cayley maps, reglar Cayley maps having minimum kernel, some properties of skew-morphisms of dihedral groups and some recent related progress will be dealt with. More
Dr. Carmen Hernando, Universitat Politècnica de Catalunya
Let $\Pi$ be a partition of the set of vertices of a graph $G$. We denote by $r(u|\Pi)$ the vector of distances from vertex $u$ to the parts of $\Pi$. The partition $\Pi$ is a \emph{resolving partition} of $G$ if $r(u,\Pi)\neq r(v,\Pi)$ for every pair of distinct vertices $u$, $v$. The \emph{partition dimension} ... More
Dr. Rafał Witkowski, Adam Mickiewicz University
A $k$-ary De Bruijn sequence $B(n,k)$ of order $n$, is a sequence of a given alphabet $A$ with size $k$ for which every subsequence of length $n$ in $A$ appears as a sequence of consecutive characters exactly once. De Bruijn matrix is an array of symbols from an alphabet $A$ of size $k$ that contains every $m$-by-$n... More
Mr. Milan Pokorny, Trnava University, Faculty of Education
A spectrum of a graph is a set of eigenvalues of its adjacency matrix. Similarly, a distance spectrum of a graph is a set of eigenvalues of its distance matrix. A graph is called integral if all eigenvalues of its adjacency matrix are integers. Similarly, a graph is called distance integral if all eigenvalues of its... More
Mrs. Hatice Topcu, Nevsehir Haci Bektas Veli University
Spectral determination of graphs is questioned by Haemers and Van Dam in the paper "Which graphs are determined by their spectrum?" as in a survey. Just after this paper is published, many results are seen in the literature such that they partially answer the question of Haemers and Van Dam. In this talk, we mak... More
Ali Reza Ashrafi, University of Kashan
The power graph $\mathcal{P}(G)$ of a group $G$ is the graph with group elements as vertex set and two elements are adjacent if one is a power of the other [1,3]. Chattopadhyay and Panigrahi [2] studied the Laplacian spectrum of the power graph of cyclic group $Z_n$ and the dihedral group $D_{2n}$, $n \geq 2$ is po... More
Tanja Gologranc, Faculty of Natural Sciences and Mathematics, University of Maribor
The Steiner tree of a (multi)set of vertices $R =\{u_1,\ldots ,u_k\} \subseteq V(G)$ is the smallest tree in $G$ that contains all vertices of $R$. The Steiner distance $d(R)$ of a set $R$ is the number of edges in a Steiner tree $T$ for $R$. The $k$-Steiner interval of a set $R \subseteq V(G)$, $I(R),$ consists o... More
Let $\Gamma$ be a strongly regular graph with parameters $(n,k,\lambda,\mu)$. Let $A$ be its adjacency matrix. if $0 < k < n-1$, then it is well known that, under certain conditions, \begin{itemize} \item the matrix $A$ has three eigenvalues $k,e^+$ and $e^-$; \item the eigenvalue $k$ has multiplicity $1$ an... More
Dr. Rinovia Simanjuntak, Institut Teknologi Bandung
Let $D$ be a strongly connected oriented graph with vertex-set $V$ and arc-set $E$. The distance from a vertex $u$ to another vertex $v$, $d(u,v)$ is the minimum length of oriented paths from $u$ to $v$. Suppose $B=\{b_1,b_2,b_3,...b_k\}$ is a nonempty ordered subset of $V$. The representation of a vertex $v$ with r... More
Prof. Robert Jajcay, Comenius University, Bratislava, and University of Primorska
Vertex-transitive graphs have many regularity properties, and look the same in the neighborhoods of all of their vertices. Consequently, the number of any small induced subgraphs, such as cycles or cliques, containing any fixed vertex of a vertex-transitive graph must be the same for each vertex of the graph. Wh... More
We describe an approach to constructing spherical graph embeddings in which all vertices are of degrees 3, 4, and 5 and all faces are quadrangular, in terms of regions of expansion and contraction. Of particular interest is a useful "diagonal metric." We describe these constructions more explicitly for the cases whe... More
A \emph{cyclic configuration} is a combinatorial configuration in which all the lines (or blocks) of the configuration are formed via a cyclic permutation of an initial block. Moreover, the fact that the block [0,1,3] forms an initial block for a cyclic configuration $\mathcal{C}_3(n)$ for any $n \geq 7$ has been us... More
Dr. Mohsen Ghasemi, Department of mathematics, Urmia university, Urmia
A graph is vertex-transitive if its automorphism group acts transitively on vertices of the graph. A vertex-transitive graph is a Cayley graph if its automorphism group contains a subgroup acting regularly on its vertices. In this present talk, tetravalent vertex-transitive non-Cayley graphs of order $4p^2$ are ... More
Dr. Elizabeth Jane Hartung, Massachusetts College of Liberal Arts
The Fries and Clar number of a fullerene are two parameters related to the stability of the molecule. We introduce ``Fries chains," a decomposition of the edges of a Kekule structure (or perfect matching) of a fullerene. Chains allow us to better understand the structure of these graphs and to find the Fries numb... More
The problem of calculating the distances among all pairs of vertices in a graph has been studied for a long time. The diameter of a graph is found by identifying the pair of vertices which are the furthest apart. In this work, we investigate the diameter of the family of generalized Petersen graphs $GP[n,m]$ where $... More
Ms. Gulnaz Boruzanli, Ege University
For integers $n\geq 3$ and $ 1\leq k < n $, the generalized Petersen graph $GP[n,k]$ has $2n$ vertices $\{u_0, u_1, \ldots, u_{n-1}, v_0, v_1, \ldots, v_{n-1}\}$ and $3n$ edges $\allowbreak\{u_iu_{i+1}, v_iv_{i+k}, u_iv_i | i=0, 1, \ldots, n-1; \textrm{addition} \bmod{n}\}$. We investigate the diameter, that is th... More
The $k$-independence number of $G$, denoted as $\alpha_k(G)$, is the size of a largest $k$-colorable subgraph of $G$. We conjecture that for any graphs $G$ and $H$, $$\alpha_k(G\times H)\leq \alpha_k(G)|V(H)|+\alpha_k(H)|V(G)|-\alpha_k(G)\alpha_k(H)\,.$$ The conjecture is stronger than the Hedetniemi's conjectur... More
Mr. Ngoc Chi Le, Technische Universität Bergakademie Freiberg
The method of augmenting graphs is a general approach to solve the Maximum Independent Set problem. Our objective is to employ this approach to develop polynomial-time algorithms for some so-called Maximum Set problems, i.e. problems which can be stated as follows. Given a (simple, undirected) graph $G$, find a maxi... More
Let $A$ denote an integral square matrix and $R$ the subring of the full matrix ring generated by $A$. Then $R$ is a free $\mathbb{Z}$-module of finite rank, which guarantees that there are only finitely many ideals of $R$ with given finite index. Thus, the formal Dirichlet series $\zeta_A(s)=\sum_{n\geq 1}a_nn^{... More
Mrs. Wei Li, Northwestern Polytechnical University
P\'{o}lya's problem concerns the conversion of the permanent and determinant of a matrix. As a generalization of this problem, this topic focus on the conversion of the permanental polynomial and the characteristic polynomial. Firstly, we provide a sufficient and necessary condition for converting the compu... More
Mr. Thomas William Tucker, Colgate University
The Riemann-Hurwitz equation for a finite group acting on a closed surface $S$ with isolated fixed points is just a simple application of inclusion-exclusion, but it plays the leading role in all study of surface symmetry and, through a remarkable series of coincidences, in my own research. Those instances include,... More
Dr. Ortrud Oellermann, University of Winnipeg
Let $x, y$ and $v$ be vertices of a graph $G$. Then $v$ is said to resolve the pair $x, y$ if $d_G(x,v) \ne d_G(y,v)$. A set $S$ of vertices of $G$ is a metric generator for $G$ if every pair of vertices of $G$ is resolved by some vertex of $S$. A smallest metric generator of $G$ is called a metric basis and its car... More
Prof. Marston Conder, University of Auckland
A {\em hypertope\/} is a generalisation of an abstract polytope, just as hypermaps generalise maps. Formally, a hypertope is a residually connected thin incidence geometry, with elements categorised according to their type. The theory of hypertopes has been developed recently by Fernandes, Leemans and W... More
Dr. Giuseppe Mazzuoccolo, Università di Modena e Reggio Emilia
For some time the Petersen graph was the only known Snark, with circular flow number $5$ (or more, as long as Tutte's $5$-flow Conjecture is in doubt). Although infinitely many such snarks were presented in "Macajova-Raspaud On the Strong Circular 5-Flow Conjecture JGT 52 (2006)", eight years ago, the variety of ... More
Prof. Shmuel Onn, Technion - Israel Institute of Technology
We show that finding minimally intersecting n paths from s to t in a directed graph or n perfect matchings in a bipartite graph can be done in polynomial time. This holds more generally for unimodular set systems. More
Prof. Daniel Pellicer Covarrubias, National University of Mexico
A polyhedron is said to be tight whenever every vertex belongs to every face. Conder and Cunningham determined the type of all tight orientably regular polyhedra. In this talk I present the recent classification of tight non-orientable polyhedra. More
Prof. Min Yan, Hong Kong University of Science and Technology
The classification of the tiling of the sphere by congruent triangles was started in 1922 and completed 80 years later in 2002. We studied the similar problem for the pentagons and obtained the classification for the minimal case of the dodecahedron and some cases where there is enough variety of edge lengths. In co... More
Mrs. Valisoa Razanajatovo Misanantenaina, Stellenbosch University
The distance matrix of a graph is the matrix whose entry in the $i$th row, $j$th column is the distance $d(v_i,v_j)$ between the $i$th vertex $v_i$ and the $j$th vertex $v_j$. A conjecture of Ili\'c and Stevanovi\'c states that among all trees with given order and maximum degree, the so-called Volkmann trees minimis... More
Prof. Michael Henning, University of Johannesburg
The transversal number, $\tau(H)$, of a hypergraph $H$ is the minimum cardinality of a subset of vertices in $H$ that has a nonempty intersection with every edge of $H$. A hypergraph is $k$-uniform if every edge has size~$k$. We present several bounds on the transversal number of uniform hypergraphs and discuss seve... More
Dr. Marien Abreu, Dipartimento di Matematica, Informatica ed Economia - Università degli Studi della Basilicata - Potenza
In this talk, we present an infinite family of snarks which we call \emph{tree-like snarks} and we prove that they have excessive index 5 ($\chi_e'(G)=5$), circular flow number 5 ($\phi_C(G)=5$), and admit a cycle double cover. More
Dr. Eric Ould Dadah Andriantiana, Rhodes University
A subset $X$ of $V(T)$ is called an infima closed set of a rooted tree $T$ if for any $u,v\in X$ the merging vertex of the paths joining the root of $T$ to $u$ and $v$ is also in $X$. We determine the trees with minimum number of infima closed sets among all rooted trees of fixed order. It is observed that minimal ... More
Dr. Tomasz Dzido, University of Gdansk
The Tur{\'a}n number $ex(n, G)$ is the maximum number of edges in any $n$-vertex graph that does not contain a subgraph isomorphic to $G$. A \emph{wheel} $W_k$ is a graph on $k$ vertices obtained from a $C_{k-1}$ by adding one vertex $w$ and making $w$ adjacent to all vertices of the $C_{k-1}$. We obtain exact v... More
Dr. Gordon Ian Williams, University of Alaska Fairbanks
In this talk I will provide a survey of some recent work on the structure of monodromy groups of abstract polytopes, as well as discussing open problems suggested by these investigations. This talk will emphasize families of well understood examples, and the methods used to study them. Particular areas of emphasis w... More
Dr. Merce Mora, Universitat Politecnica de Catalunya
The collection of the minimal dominating sets of a graph is a hypergraph. However, there are hypergraphs $H$ that are not the collection of the vertex dominating sets of any graph. We say that a hypergraph $H$ is a \emph{domination hypergraph} if there is at least a graph $G$ such that the collection of minimal dom... More
Dr. Mario Thüne, Leipzig University
If the adjacency matrices of two graphs are related trough an unitary transformation we call those graphs unitary equivalent. For simple graphs this notion coincides with isospectrality. A construction for unitary equivalent graphs, which generalizes GM switching, will be given. More
Prof. Matjaž Konvalinka, FMF, University of Ljubljana
In this talk, I will present two recent results on the enumeration of double cosets in the symmetric group. \emph{Tanglegrams} are a special class of graphs appearing in applications concerning cospeciation and coevolution in biology and computer science. They are formed by identifying the leaves of two rooted bi... More
Ms. Rojin Kianian, Department of Mathematics and Computer Science, University of Southern Denmark
Sophisticated tools have been developed in order to create new compounds. However, despite the fact that computer-assisted organic synthesis design has been an active research topic for decades, many well-established approaches from theoretical computer science are nearly unused in this context. For insta... More
Marko Jakovac, Faculty of Natural Sciences and Mathematics, University of Maribor
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$. A lower and an upper bound for $\psi_k$ of the rooted product graphs are presented. Two c... More
Dr. Luke Morgan, The University of Western Australia
A graph $\Gamma$ is $G$-locally-transitive, for $G\leqslant \mathrm{Aut}(\Gamma)$, if for each vertex $x$ of $\Gamma$ the vertex-stabiliser $G_x$ acts transitively on the neighbours of $x$ in $\Gamma$. Additionally, $\Gamma$ is weakly locally projective if for each vertex $x$ the stabiliser $G_x$ induces on the set ... More
Dr. Arjana Žitnik, University of Ljubljana and IMFM
Let $X$ be a finite vertex-transitive graph of valency $d$, and let $A$ be the full automorphism group of $X$. Then the {\em arc-type\/} of $X$ is defined in terms of the sizes of the orbits of the action of the stabiliser $A_v$ of a given vertex $v$ on the set of arcs incident with $v$. Specifically, the arc-typ... More
Mr. Alexander Mednykh, Sobolev Institute of Mathematics
In this lecture we describe a few methods to calculate the volumes of polyhedra with symmetries in the spaces of constant curvature. We apply the obtained results to find volume of some knots and links modelled in the hyperbolic, spherical or Euclidean geometries. More
Prof. Janez Žerovnik, University of Ljubljana
Cactus is a graph in which every edge is on at most one cycle. Or, equivalently, each pair of cycles can meet in at most one vertex. A linear algorithm for weighted domination number of (vertex-weighted) cactus graphs is given. Although algorithms for the domination problem on trees and cacti are known for a ... More
Mr. István Estélyi, University of Ljubljana, University of Primorska
Haar graphs are regular covering graphs of dipoles. They can also be constructed in a Cayley graph-like manner, in terms of a group $G$ and its subset $S$. Just like Cayley graphs, these graphs frequently appear in various constructions, due to their pleasant symmetry properties. For example, Haar graphs were used f... More
Prof. Gareth Aneurin Jones, University of Southampton
It has been conjectured that `most' vertex-transitive connected graphs are Cayley graphs. Recently Dobson and Malni\v c, building on earlier work of Godsil on Kneser graphs and of Kantor on permutation groups, have determined which Johnson graphs $J(n,k)$ are Cayley graphs: most are not, although they are all vertex... More
Steve Wilson, Univerza na Primorskem
This talk describes a construction of a semisymmetric graph from a reflexible map. Mysteriously, the construction also yields a semisymmetric graph in a non-trivialnumber of cases when the input map is chiral. No one knows why. More
Tamas Szonyi, ELTE Budapest
Zarankiewicz asked for the minimum number of $1$s in an $m\times n$ $0$-$1$ matrix that assures the existence of an $s\times t$ submatrix containing only $1$s. We consider the following, equivalent formulation. A bipartite graph $G=(A,B;E)$ is \emph{$K_{s,t}$-free} if it does not contain $s$ nodes in $A$ and $t$ nod... More
Dr. Yulia Kempner, Holon Institute of Technology
The pivot operation, i.e., exchanging exactly one element in a basis, is one of the fundamental algorithmic tools in linear algebra. Korte and Lov\'{a}sz introduced a combinatorial analog of this operation for bases of greedoids. Let $X,Y$ be two bases of a greedoid $(U,\mathcal{F})$ such that $\left\vert X-Y\... More