# Graphs, groups, and more: celebrating Brian Alspach’s 80th and Dragan Marušič’s 65th birthdays

from 28 May 2018 to 1 June 2018
Koper
UTC timezone
Home > Contribution List

## Contribution List

Displaying 50 contributions out of 50
Much of this meeting centres around Cayley graphs. But who was Cayley? What contributions did he make to combinatorics? And what were his connections with graphs and groups?
Presented by Prof. Robin WILSON
For a fixed integer $k$, a set of vertices $B$ of a graph $G$ is a *$k$-limited packing* of $G$ provided that the closed neighourhood of any vertex in G contains at most $k$ elements of $B$. The size of a largest possible $k$-limited packing in $G$ is denoted $L_k(G)$ and is the $k$-limited packing number of $G$. In this talk, we investigate the 2-limited packing number of box products of paths. W ... More
Presented by Dr. Nancy E. CLARKE
This talk will discuss configurations and their history from a Slavonian, from a Slovenian, and from the author's point of view. Configurations are linear regular uniform hypergraphs, but investigated in a geometric language since 1876. Slavonia is a region in the east of Croatia, not to mix up with Slovenia, an independent state since 1991/1992. There are two recent books on configurations by the ... More
Presented by Harald GROPP
A major topic of research in symmetries of graphs is that of finding graphs that admit specific sorts of automorphisms, but do not admit other automorphisms. The study of regular representations is an example of this. Another way to approach this topic is to ask what constraints we can impose on a highly symmetric graph if we want to limit the automorphisms. It is with this approach in mind that w ... More
Presented by Joy MORRIS
If we denote by $n(k, d)$ the order of the largest undirected graphs of maximum degree $k$ and diameter $d$, and let $M(k,d)$ denote the corresponding Moore bound, then $n(k,d) \leq M(k,d)$, for all $k \geq 3, d \geq 2$. While the inequality has been proven strict for all but very few pairs $k$ and $d$, the exact relation between the values $n(k,d)$ and $M(k,d)$ is unknown, and the uncertainty ... More
Presented by Prof. Robert JAJCAY
The Cayley graph relative to a union of conjugacy classes of a finite group will be discussed: properties, results and open questions.
Presented by Dr. Boris ZGRABLIC
The family of generalized Petersen graphs $G(n,k)$, introduced by Coxeter et al. [4] and named by Mark Watkins (1969), is a family of cubic graphs formed by connecting the vertices of a regular polygon to the corresponding vertices of a star polygon. The Kronecker cover $\mathrm{KC}(G)$ of a simple undirected graph $G$ is a a special type of bipartite covering graph of $G$, isomorphic to the ... More
Presented by Matjaž KRNC
In the mid-1990s, two groups of authors independently obtained classifications of vertex-transitive graphs whose order is a product of two distinct primes. In the intervening years it has become clear that there is additional information concerning these graphs that would be useful, as well as making explicit the extensions of these results to digraphs. Additionally, there are several small erro ... More
Presented by Prof. Ted DOBSON
A geometric con figuration of type (p_q,n_k) is an incidence structure consisting of p points and n "blocks" such that each point is incident with q blocks and each block is incident with k points. The "blocks" can be different geometric figures such as lines, circles, conics, etc. The first known geometric confi gurations originate from classical incidence theorems such as the theorems of P ... More
Presented by Gábor GÉVAY
Two related enumeration problems on vertex labeled graphs will be discussed. Given a graph $G$, we introduce and investigate the number $C(G)$ of connected subsets of the vertex set and the number $P(G)$ of connected partitions of the vertex set. By {\it connected} we mean that the induced subgraphs are connected. The numbers $C(G)$ and $P(G)$ can be regarded as the graph analogs of the number ... More
Presented by Prof. Andrew VINCE
In 1979 Tarsi showed that an edge decomposition of a complete multigraph into stars of size $k$ exists whenever the obvious necessary conditions hold. In 1996 Lin and Shyu gave necessary and sufficient conditions for the existence of an edge decomposition of a (simple) complete graph into stars of sizes $m_1,\ldots,m_t$. I will discuss the common generalisation of these problems: when does a c ... More
Presented by Dr. Daniel HORSLEY
Let $\Gamma$ be a signed graph. A cluster in $\Gamma$ of order $c$ and degree $s$, is a pair of vertex subset $(C,S)$, where $C$ is a set of cardinality $c \geq 2$ of pairwise co-neighbor vertices sharing the same set of $s$ neighbors and all edges connecting a fixed vertex in $C$ are equallly signed. We consider the graph $\Gamma(H)$ which is obtained from $G$ by identifying $V(H)$ with $C$ and s ... More
Presented by Dr. Maurizio BRUNETTI
Let χ'(G) denote the chromatic index of G and denote by G-e the graph obtained by removing an edge e from G. The graph G is said to be Δ-critical if χ'(G)=Δ+1 and χ'(G-e)=Δ for any edge e in E(G). We are interested in critical graphs of even order. It has been proved that there are no critical graphs of even order n≤ 10 and that there are no 3-critical graphs of order 12 and 14 (see [ ... More
Presented by Dr. Simona BONVICINI
Let $(\Gamma,+)$ be a finite group. An $m$-composition over $\Gamma$ is an $m$-tuple $(g_1,g_2,\ldots,g_m)$ over $\Gamma$. It is called an $m$-composition of $g$ if $\sum_{j=1}^m g_j = g$. A composition $(g_j)$ over $\Gamma$ is called locally restricted if there is a positive integer $\sigma$ such that any subsequence of $(g_j)$ of length $\sigma$ satisfies certain restrictions. Locally restri ... More
Presented by Prof. zhicheng GAO
There is discussed the recovery conditions of continuous mapping from a discrete representation. The mapping is presented in a network of model elements located on a differentiable manifold. Motivation for this material: a.) The applied models in geomechanics are characterized by large errors of the parameters and uncertainty in results. However, these models are presented by continuous depende ... More
Presented by Dr. Julian DIMITROV
Edge searching is a combinatorial game where a team of searchers are following a strategy to capture a hidden intruder. It is played on the edges and vertices of a graph. When a fixed number of searchers are available, there is a finite number of forbidden minors, exclusion of which will guarantee that the graph will be intruder free. In this talk, we give the set of forbidden minors for 4-search ... More
Presented by Dr. Oznur Yasar DINER
Proteins interact with other molecules through their protein binding sites, which are functionally important regions on the protein surface. Each binding site usually binds one or a few specific molecules, the ligands. Detection of binding sites gives insight in protein functionality and is hence essential for drug design. Sequence variants that occur in coding regions of genes may alter protein's ... More
Presented by Prof. Dušanka JANEŽIČ
\titleoftalk{Graphs with small distinguishing index} \speaker{{Monika} {Pil\'sniak}} \university{Department of~Discrete Mathematics\\AGH University, Krakow, Poland} \email{pilsniak@agh.edu.pl} \ \begin{abstract}The distinguishing index of~a graph $G$, denoted by $D'(G)$, is the~least number of~colours in a general edge colouring of~$G$ not preserved by any non-trivial automor ... More
Presented by Monika PILSNIAK
I will talk about Hamilton decompositions of graphs, focussing on a number of results from the last few years. In particular I will discuss problems relating to Hamilton decompositions of vertex-transitive graphs and line graphs.
Presented by Prof. Darryn BRYANT
A path (cycle) containing every vertex in a graph is called a Hamilton path (Hamilton cycle, respectively). A graph is called vertex-transitive if for any pair of vertices $u$ and $v$ there exists an automorphism mapping $u$ to $v$. In 1969, Lovasz asked whether every finite connected vertex-transitive graph has a Hamilton path. With the exception of the complete graph on two vertices, only f ... More
Presented by Klavdija KUTNAR
In 1969 Lov\' asz conjectured that a vertex transitive graph admits a hamilton path. In fact, only $5$ non-hamiltonian vertex transitive graphs are known, namely $K_2$, the Petersen and the Coxeter graphs and their truncations. This motivates a folklore conjecture stating that every Cayley graph is hamiltonian. Moreover, four of the five examples are cubic graphs, therefore it is natural to inve ... More
Presented by Roman NEDELA
In 1984, Alspach asked whether every Cayley graph of a finite Abelian group admits a Hamilton decomposition. The conjectured answer is yes, but except in some special cases the question remains wide open. In this talk we study an analogous question for infinite, finitely generated groups, using spanning double rays as an infinite analogue of Hamilton cycles. We show that if $G$ is a one-en ... More
Presented by Florian LEHNER
This is a survey talk about Tutte's integer flows in Cayley graphs. Alspach conjectured that every connected Cayley graph contains a Hamilton cycle. After almost five decades, Alspach's conjecture remains widely open. Note that every Hamiltonian graph admits a nowhere-zero $4$-flow. The following is a weaker version of Alspach's conjecture (by Alspach, Liu and Z) that every Cayley graph admits a ... More
Presented by Prof. Cun-Quan ZHANG
Two elements $x,y$ *invariantly generate* a group $G$ if any conjugate $x$ together with any conjugate of $y$ generates $G$. Invariant generation of a group $G$ by prime or prime-power elements has consequences for fixed-point-free actions on certain geometries with $G$ actions. In previous work, John Shareshian and I have shown that, assuming the Riemann hypothesis, the alternating groups $A_ ... More Presented by Dr. Russ WOODROOFE In this talk I'll give a partial (but possibly complete) answer to a question asked by Pierre-Emmanuel Caprace at the Groups St Andrews conference at Birmingham (UK) in August 2017, and investigated at the Tutte Centenary Retreat in Australia in November 2017. Caprace asked if there exists a 2-transitive permutation group$P$such that only finitely many simple groups act arc-transitivel ... More Presented by Prof. Marston CONDER A vertex coloring of graph satisfies the *majority rule*, if for each vertex$v$at most half of its neighbors receive the same color as$v$. A coloring which satisfies the majority rule is called *majority coloring*. The problem of such colorings was introduced in [1,5] and continued with different variants in [2,4]. We consider its game version. For given graph$G$and color set$C$two players ... More Presented by Gabriel JAKÓBCZAK Delen and Cangul recently defined a new graph invariant in terms of a degree sequence. By means of this invariant, it is possible to classify the realizations of the given degree sequence. Also this new invariant gives a lot of information about the connectedness, the number of components, loops, pendant edges, chords and multiple edges of the realizations. We shall give some new combinatorial and ... More Presented by Prof. Ismail Naci CANGUL The cycle space of a graph$G$is the subspace of the edge space of$G$over the 2-element field that is spanned by the cycles of$G$(considered as edge-sets of$G$). Bondy and Lov\'{a}sz (1981) showed that the cycles through any set of$s-1$vertices in an$s$-connected graph generate its cycle space. But what if these cycles are restricted to be of odd length? In this talk, we consid ... More Presented by Prof. Donovan HARE One of the central questions in the study of graphs admitting a certain degree of symmetry is determining how large their automorphism groups can be. For graphs of fixed valency, this is equivalent with determining possible orders of vertex-stabilizers. The famous Tutte's result from 1948 implies that vertex stabilizer of a cubic arc-transitive graph can have order at most 48. Arc-transitive graph ... More Presented by Dr. Ademir HUJDUROVIĆ A polynomial$f(x) = a_0 + a_1 x + \ldots + a_n x^{n}$over the prime field$\mathbb{Z}_p$, where$p$is odd, is reflexible if there exists$\lambda \in \mathbb{Z}_p^*$such that$\lambda a_{n-i} = a_i$(type 1) or$\lambda a_{n-i} = (-1)^i a_i$(type 2), for all indices$i = 0, 1, \ldots, n$. Such polynomials were instrumental in the classification of quartic arc transitive graphs arising as ... More Presented by Aleksander MALNIC A *loose$m$-cycle* is a 3-uniform hypergraph with vertex set$\{v_1, v_2, \ldots, v_{2m}\}$edge set$\{\{v_1,v_2,v_3\}, \{v_3,v_4,v_5\}, \ldots, \{v_{2m-1},v_{2m},v_1\}\}$. We consider the problem of decomposing$K_{v}^{(3)}$, the complete 3-uniform hypergraph of order$v$, into edge-disjoint loose$m$-cycles. We settle the problem in the case$m=4$. Presented by Prof. Saad EL-ZANATI In authors proposed a formula for computing the spectrum of Cayley graph$\Gamma=Cay(G,S)$with respect to the character table of$G$where$S$is a symmetric normal subset of$G$. Let$q$be a power of prime number$p$. A representation of degree$n$of group$G$is a homomorphism$\alpha: G \to GL(n,q)$, where$\alpha(g)=[g]_{\beta}$for some basis$\beta$. A character table is a matrix w ... More Presented by Dr. Modjtaba GHORBAN **Abstract** Let$G$be a group and$S$be a subset of$G$. Then$BCay(G,S)$, bi-Cayley graph of$G$with respect to$S$, is an undirected graph with vertex-set$G\times\{1,2\}$and edge-set$\{\{(g,1),(sg,2)\}\mid g\in G, s\in S\}$. For$\sigma\in Aut(G)$and$g\in G$, we have$BCay(G,S)\cong BCay(G,gS^\sigma)$. A bi-Cayley graph$BCay(G,S)$is called a$BCI$-graph if for any bi-Cayley graph ... More Presented by Prof. Mohammad A. IRANMANESH White, Pisanski and others have proved a number of results on the existence of quadrilateral embeddings of cartesian products of graphs; in some cases these provide minimum genus embeddings. In a 1992 paper Pisanski posed three questions. First, if$G$and$H$are connected$1$-factorable$r$-regular graphs with$r \ge 2$, does the cartesian product$G \times H$have an orientable quadrilateral ... More Presented by Dr. Mark ELLINGHAM It is known that every Riemann surface of genus$g$can be expressed in the form$\mathbb{U}/\Omega$, where$\mathbb{U}$is the Riemann sphere$\Sigma$, the Euclidean plane$\mathbb{C}$, or the hyperbolic plane$\mathbb{H}$, depending on whether$g$is$0$,$1$or$>1$, respectively, and$\Omega$is a discrete group of isometries of$\mathbb{U}$. A Riemann surface$S=\mathbb{U}/\Omega$... More Presented by Dr. Adnan MELEKOGLU Broadly, there are two classical pursuit-evasion problems in graphs. One is cops and robbers, where cops move along vertices in pursuit of a robber that is slow, visible, and also moving on vertices. The other is edge-searching, or sweeping, where agents pursue a fast, invisible evader who moves on edges and vertices. This talk will talk about some of the history of these two problems, as they rel ... More Presented by Danny DYER A non-trivial automorphism$g$of a graph$\Gamma$is called semiregular if the only power$g^i$fixing a vertex is the identity mapping, and it is called quasi-semiregular if it fixes one vertex and the only power$g^i$fixing another vertex is the identity mapping. In this paper, we prove that$K_4,$the Petersen graph and the Coxeter graph are the only connected cubic arc-transitive graphs ... More Presented by Istvan KOVACS A {\em unital} is defined to be a set of$q^3 + 1$points equipped with a family of subsets, each of size$q + 1$, such that every pair of distinct points are contained in exactly one subset of the family. Such subsets are usually called {\em blocks} so that unitals are block-designs$2-(q^{3}+1,q+1,1)$. Unitals are known to play an important role in many investigations in finite geometry. Comp ... More Presented by Prof. Gabor KORCHMAROS In this talk we will give constructions of self-orthogonal and self-dual codes, with respect to certain scalar products, with the help of orbit matrices of block designs and quotient matrices of symmetric (group) divisible designs (SGDDs) with the dual property. First we will describe constructions from block designs and their extended orbit matrices, where the orbit matrices are induced by the ac ... More Presented by Dr. Nina MOSTARAC In this talk we will show that under certain conditions submatrices of orbit matrices of strongly regular graphs span self-orthogonal codes. We apply this method to construct self-orthogonal binary linear codes from column orbit matrices of the triangular graph$T(2k)$with at most 120 vertices. Moreover, we construct linear codes from row orbit matrices of strongly regular graph with parameters ... More Presented by Dr. Marija MAKSIMOVIĆ Last year marked the$50^{th}$anniversary of the Oberwolfach Problem, which was formulated in 1967 by Gerhard Ringel as follows: At a conference in Oberwolfach,$2k+1$participants are to be seated at$t$round tables for$k$meals so that each participant sits next to every other participant at exactly one meal. Can this be achieved with tables of sizes$m_1, m_2,\ldots, m_t$if$m_1+m_2+ ... More
Presented by Prof. Mateja SAJNA
A $2-(v,k,1)$ design or, also, a Steiner $2$-design is said to be cyclic if it admits an automorphism cyclically permuting all its points. To establish the number NC$(v,k)$ of cyclic $2-(v,k,1)$ designs is in general not feasible and very little is known about this number. By playing'' with $(v,k,1)$ difference families, some lower bounds on NC$(v,k)$ are given. In particular, for primes $p=6n+1 ... More Presented by Dr. Emanuele BRUGNOLI A few topics regarding symmetries of finite graphs that I find interesting, intriguing and worth studying shall be presented. Presented by Mr. Primož POTOČNIK I will survey known results and open problems about the automorphism groups of Steiner triple systems and Kirkman triple systems. Presented by Prof. Marco BURATTI In the generalized graph truncation construction, one replaces each vertex of a$k$-regular graph$\Gamma$with a copy of a graph$\Upsilon$of order$k$. In this talk, which is based on joint work with Eduard Eiben and Robert Jajcay, we focus on symmetry properties of generalized truncations, especially in connection to the symmetry properties of the graphs$\Gamma$and$\Upsilon$used in the ... More Presented by Dr. Primož ŠPARL The *distinguishing index*$D'(G)$of a graph$G$is the least number of colours of an edge colouring that is not preserved by any non-trivial automorphism. The following result was proved by Pil\'sniak in [1]. **Theorem.** If$G$is a connected graph, then$(1)D'(G)=\Delta(G)+1$iff$G$is a cycle of length less than$6$,$(2)D'(G)=\Delta(G)$iff$G$is a symmetric or a bisymmetri ... More Presented by Rafal KALINOWSKI The Hamilton-Waterloo problem asks for a decomposition of the complete graph into$r$copies of a 2-factor$F_{1}$and$s$copies of a 2-factor$F_{2}$such that$r+s=\left\lfloor\frac{v-1}{2}\right\rfloor$. If$F_{1}$consists of$m$-cycles and$F_{2}$consists of$n$cycles, then we call such a decomposition a$(m,n)-$HWP$(v;r,s)$. The goal is to find a decomposition for every possible pair$(r ... More
An association scheme is called *metric* if its intersection numbers satisfy the triangle inequality, i.e., $p^h_{ij} \ne 0$ implies $|i-j| \le h \le i+j$ for some ordering of its relations. Dually, an association scheme is called *cometric* if its Krein parameters satisfy the triangle inequality for some ordering of its eigenspaces. Metric association schemes correspond precisely to distan ... More
The *$2$-block intersection graph* ($2$-BIG) of a twofold triple system is the graph whose vertex set is the blocks of the $TTS$ and two vertices are joined by an edge if they intersect in exactly two elements. A Hamilton cycle in a $2$-BIG is equivalent to a cyclic Gray code, so an interesting problem is to classify which $TTS$s have Hamiltonian $2$-BIGs. The $2$-BIGs are themselves interest ... More
A $(k,g)$-graph is a simple undirected $k$-regular graph with girth $g$. A $(k,g)$-cage is a $(k,g)$-graph with the least possible number of vertices. Cages have been studied quite intensively yet for most pairs $(k,g)$ the corresponding cages are still unknown. There is an obvious lower bound on the order of a $(k,g)$-cage, called the Moore bound (i.e., the number of vertices needed for a \$( ... More