how to create your own web page

v1.0 © Copyright 2018 by webStone - All Rights Reserved


Abstracts are listed alphabetically with respect to Presenting Author.

Unique maximum packing of graphs
Dragana Božović, Iztok Peterin
Let G be a graph. A packing in G is a subset P of vertices V (G) such that the distance between any two distinct vertices from P is greater than 2. A graph G has a unique maximum packing if there exists exactly one packing of the maximum cardinality.
We present some general properties of graphs with the unique maximum packing. Additionally we concentrate on the unique maximum packing of trees and present two characterizations of trees with the unique maximum packing, one inductive and the other one structural.

On the non-existence of antipodal cages of even girth
Slobodan Filipovski
The Moore bound M(k, g) is a lower bound on the order of k-regular graphs of girth g (denoted (k, g)-graphs). The excess e of a (k, g)-graph of order n is
the diff e = n − M(k, g). A (k, g)-cage is a (k, g)-graph with the fewest possible number of vertices. A graph of diameter d is said to be antipodal if, for any vertices u, v, w such that d(u, v) = d and d(u, w) = d, it follows that d(v, w) = d or v = w. Biggs and Ito proved that any (k, g)-cage of even
girth g = 2d ≥ 6 and excess e ≤ k − 2 is a bipartite graph of diameter d + 1. In this paper we treat (k, g)-cages of even girth and excess e ≤ k − 2. Based on spectral analysis we give a relation between the eigenvalues of the
adjacency matrix A and the distance matrix Ad+1 of such cages. Applying matrix theory, we prove the non-existence of antipodal (k, g)-cages of excess e, for k ≥ e + 2 ≥ 4 and g = 2d ≥ 14.


Double Covers, Cancellation and Automorphisms
Wilfried Imrich
The motivation for this talk are the similarities of results on automorphisms of double covers with those on the cancellation of graphs with respect to the direct product. The double cover of a graph G is the direct product of G by K2, and G is unstable if the automorphism group of its double cover is larger
than Aut(G)×Z2. G is called nontrivially unstable, if it is non-bipartite and if any two distinct vertices have diff t neighborhoods, in other words, if G is non-bipartite and thin. 1989 Marušic, Scapellato and Zagaglia Salvi proved that to any nontrivially unstable graph G there always exists a permutation matrix P such that the product AP , where A is the adjacency matrix of G, is the adjacency matrix of some graph. They asked when the converse holds.
Translated into the language of matrices the answer of Mizzi and Scapel- lato form 2013 is that G is nontrivially unstable if and only if there exists a permutation matrix P of order > 2 such that PAP = A. We give a proof us- ing aresult of Richard Hammack aboutantiautomorphisms and cancellation properties of direct products.
The talk also presents the background and discusses related results and prob- lems about direct products.

The Annihilaton Number and Domination Invariants
Csilla Bujtás, Marko Jakovac
The annihilation number a(G) of G is the largest integer k such that there exist k diff t vertices in G with degree sum of at most |E(G)|. It is conjectured that γt(G) ≤ a(G) + 1 and γ2(G) ≤ a(G) + 1 hold for every nontrivial connectedgraph G, where γt(G) andγ2(G) denote thetotal domination num-
ber and the 2-domination number, respectively. In this talk some results on these two conjectures will be presented

Domination game and minimal edge cuts
Sandi Klavžar
Ljubljana, Maribor
The domination game is played on a graph G by Dominator and Staller. They take turns choosing a vertex from G such that at least one previously undominated vertex becomes dominated. The game is over when G becomes dominated. Dominatorwants tominimize the number ofvertices played, and Staller wishes to maximize it. If Dominator starts the game and both players play optimally, then the number of moves played is the game domination number γg(G) of G. In this talk a relationship between the domination game and minimal edge cuts will be presented. In particular, if C a minimum edge cut of a connected graph G, then γg(G) ≤ γg(G \ C) + 2κ'(G). Double- Staller graphs will be introduced in order to show that this upper bound can 
be attained for graphs with a bridge. The family of known traceable graphs whose game domination numbers are at most one-half their order will be extended.
This is a joint work with Douglas F. Rall, Department of Mathematics, Fur- man University, Greenville, SC, USA.

The Connective Constant of the Grandparent Graph
The connective constant of a quasi-transitive infi graph is a measure for the asymptotic growth rate of the number of self-avoiding walks of length n from a given starting vertex. It is the reciprocal of the radius of convergence of the generating function counting self-avoiding walks. The decomposition of a 2-connected graph into 3-blocks and the corresponding 3-block tree can be used to get a system of equations having as a solution the generating function of self-avoiding walks on this graph and allowing to compute its connective constant. In this talk the Grandparent Graph will be used to illustrate this procedure.

On the Terwilliger algebra of bipartite distance-regular graphs
with Γi-1,i-1,1(x, y, z) = ai + ßiΓ1,1,i-1(x, y, z)
Safet Penjić
Let Γ denote a bipartite distance-regular graph with diameter D ≥ 4 and valency k ≥ 3. Let X denote the vertex set of Γ, and let Ai denote the distance-i matrix of Γ. For x ∈ X and for 0 ≤ i ≤ D, let Γi(x) denote the set of vertices in X that are distance i from vertex x.
For x ∈ X let T = T (x) denote the subalgebra of MatX (C) generated by  A, E∗, E∗,..., E∗ , where for 0 ≤ i ≤ D, E∗ represents the projection onto  0 1 D i the ith subconstituent of Γ with respect to x. We refer to T as the Terwilliger algebra of Γ with respect to x. By the endpoint of an irreducible T -module W we mean min{i | E∗W /= 0}. 
Inthis talk we present some results about structureof irreducible T-modules of endpoint 2 for graphs Γ for which the following property (Q1) holds.

(Q1) For 2 ≤ i ≤ D − 1, there exist complex scalars αi, βi such that for all x, y, z ∈ X with path-length distance ∂(x, y) = 2, ∂(x, z) = i, ∂(y, z) = i, we have  

αi + βi|Γ1(x) ∩ Γ1(y) ∩ Γi−1(z)| = |Γi−1(x) ∩ Γi−1(y) ∩ Γ1(z)|.

(we are motivated by the fact that (Q1) above holds if Γ is Q-polynomial). 

Efficient closed domination in product of digraphs
Iztok Peterin and Ismael G. Yero
A digraph D is an efficient open domination digraph if there exists a subset S of V (D) for which the closed outer neighborhoods centered in vertices of S form a partition of V (G). We completely describe efficient closed domination graphs among lexicographic and strong products of digraphs. We characterize which direct products of either cycles or paths are efficient closed dominated as an analogue to the undirected case. Among Cartesian product of digraphs we settle the case of describing all digraphs F such that either its Cartesian product with a cycle or with a star is an efficient closed dominated digraph.

Fixicity of graphs
Florian Lehner, Primož Potocnik, Pablo Spiga
Fixicity of a graph is the largest number of fi points that the automorphisms of a graph have. I will present some results about graphs with large fi y and I will be particularly interested in cubic vertex-transitive graphs.

New structural results on tetravalent half-arc-transitive graphs
Alejandra Ramos Rivera, Primož Šparl
In this talk we focus on tetravalent graphs admitting a half-arc-transitive group of automorphisms, that is a subgroup of the automorphism group acting transitively on its vertices and its edges but not on its arcs. One of the most fruitful approaches for the study of structural properties of such graphs is the well-known concept of alternating cycles and their intersections which was introduced by Marušic 20 years ago.
We introduce a new parameter for such graphs, the alternating jump parameter, giving a further insight into their structure. The obtained results are used to establish a link between two frameworks for a systematic study of all tetravalent graphs admitting a half-arc-transitive subgroup of automorphisms, the one proposed by Marušic and Praeger in 1999, and the much more recent one proposed by Al-bar, Al-kenai, Muthana, Praeger and Spiga which is based on the normal quotients method.
We also present results on the graph of alternating cycles of a tetravalent graph admitting a half-arc-transitive subgroup of automorphisms. A considerable step towards the complete answer to the question of whether the attachment number necessarily divides the radius in tetravalent half-arc- transitive graphs is made.

k-arc transitive digraphs with polynomial growth
Norbert Seifter
In a digraph Γ a k-arc is a sequence (v0, . . . , vk ) of k + 1 vertices such that (vi−1, vi) is an arc for each i, 1 ≤ i ≤ k. A digraph Γ is called k-arc-transitive if Aut(Γ) acts transitively on the set of k-arcs of Γ. Furthermore, Γ is sharply
k-arc-transitive if it is k-arc-transitive but not (k + 1)-arc-transitive. If an
infinit digraph Γ is k-arc-transitive for all integers k ≥ 1 then we say that Γ is highly-arc-transitive.

Concerning k-arc-transitivity, the situation is much more involved for digraphs than for undirected graphs. There exist several constructions for k-arc-transitive digraphs for arbitrarily large k. If digraphs are infinite then they might even be highly-arc-transitive. The investigation of highly-arc- transitive digraphs was initiated in 1993 in a paper of Cameron, Praeger and Wormald. In fact this paper was a rich source of many nice problems which lead toseveral interesting papers.

In a paper by Möller, Potočnik and Seifter (2018) a new construction of sharply k-arc-transitive digraphs is presented, which leads to finite and infinite examples. Among the infinite examples there are digraphs with one, two and infinite many ends. In particular the class of sharply k-arc-transitive infinite digraphs with one end and polynomial growth give rise to another interesting question: It follows from a result of R. Möller that one-ended digraphs with polynomial growth cannot be highly-arc-transitive. On the other hand the known examples of sharply k-arc-transitive one-ended graphs with polynomial growth have growth rate k + 1. So it is nearby to ask, if it is a general property of one-ended k-arc-transitive digraphs with polynomial growth that the growth rate grows with k.

In this talk we present results which are closely related to this question. Whatever we present is the outcome of the collaboration with A. Malnič, R.  Möller, P. Potočnik and P. Šparl. 

Distance balancedness of graphs
Primož Šparl
Let u and v be two vertices of a graph Γ. This pair of vertices is balanced  if the number of vertices closer to u than to v is equal to the number of vertices closer to v than to u. In the last decade the class of distance- balanced graphs in which every pair of adjacent vertices is balanced has been studied quite a lot. Apart from purely graph-theoretical interest in these graphs the balancedness property makes them important also in areas such as mathematical chemistry and communication networks. 
In this talk we present avery natural generalization ofthe concept of distance- balanced graphs to n-distance-balanced graphs, fi introduced by Boštjan Frelih in 2014, in which we insist that every pair of vertices at distance n is balanced. If a graph is n-distance-balanced for all n it is highly distance- balanced. We discuss some basic properties of n-distance-balanced and highly distance-balanced graphs, give several examples of such graphs and present a characterization of such graphs of small diameter. We also discuss the n-distance-balanced property for some well-known families of (cubic) graphs and pose a number of open problems.
This is joint work with Štefko Miklavič.

Polyharmonic functions on finite graphs
Thomas Hirschler, Wolfgang Woess
Let (X, E) be a fi connected, simple graph. We designate a non-empty subset as the boundary of X. The associated normalised graph Laplacian  is P - I, where I is the identity matrix, and P is the normalised adjacency matrix with absorbing boundary points, that is, p(x, y) = 1/deg(x) when x is an interior point and y a neighbour of x, while p(y, y) = 1 if y is in the  boundary. (All other entries are 0.) The involved matrices act on complex functions on the vertex set, to be seen as column vectors. A polyharmonic  function is one for which (P -I)nf = 0, possibly with a modifi induced by a collection of pre-assigned boundary values. We describe those functions, and more generally also λ-polyharmonic functions corresponding to (P -λI)n  for suitable complex λ. 

D. Božovic
S. Filipovski
W. Imrich
M. Jakovac
S. Klavžar
A. Kräuter
C. Lindorfer
A. Malnic
S. Penjic
I. Peterin
P. Potocnik
D. Rall
A. Rivera
N. Seifter
P. Šparl
W. Woess
B. Zgrablic