Raziskovalni matematični seminar - Arhiv

The concepts of adjacency and distance are two of the most basic terms in graph theory. A natural generalization leads to the notion of distance degree which tells us the number of vertices at some distance from the chosen vertex, thereby defining the term of growth in a graph.When studying growth we often limit ourselves to the so called distance degree regular graphs, where all the distance degrees for all the vertices are the same, and self-median graphs, where the sum of distances from a chosen vertex to all the other vertices is independent of the selected vertex. It was shown that the former graphs correspond to strongly distance-balanced graphs while the latter correspond to distance-balanced graphs.The talk will focus on the properties and known families of the mentioned types of graphs, the complexity of obtaining them and their use in practical applications. It will present an overview of the known results and pose some still unanswered questions.

Download the abstract.

The thesis contains number of different topics in algebraic graph theory, touching and resolving some open problems that have been a center of research interest over the last decade or so. More precisely, the following open problems are considered in the thesis:

(i) Which graphs are (strongly) quasi $m$-Cayley graphs?
(ii) Which bicirculants are arc-transitive graphs?
(iii) Are there generalized Cayley graphs which are not Cayley graphs, but are vertex-transitive?
(iv) Are there snarks amongst Cayley graphs?
(v) Are there graphs admitting half-arc-transitive group actions with small number of alternets with respect to which they are not tightly attached?

Problem (i) is solved for circulants and $m\in \{2,3,4\}$. Problem (ii) is completely solved for pentavalent bicirculants. Problem (iii) is answered in the affirmative by constructing two infinite families of vertex-transitive non-Cayley generalized Cayley graphs. The graphs in the families are all bicirculants. Problem (iv) is solved for those $(2,s,t)$-Cayley graphs whose corresponding $2t$-gonal graphs are prime-valent arc-transitive bicirculants. The main step in obtaining this solution is the proof that the chromatic number of any prime-valent arc-transitive bicirculant admitting a subgroup of automorphisms acting $1$-regularly, with the exception of the complete graph $K_4$, is at most $3$. Problem (v) is solved for graphs admitting half-arc-transitive group actions with less than six alternets by showing that there exist graphs admitting half-arc-transitive group actions with four or five alternets with respect to which they are not tightly attached, whereas graphs admitting half-arc-transitive group actions with less that four alternets are all tightly attached with respect to such actions.

The thesis is prepared under supervision of Prof. Dragan Marušič and co-supervison of Assoc. Prof. Klavdija Kutnar.

 The polynomial method has many applications in finite geometry, for example for (multiple) blocking sets, arcs, caps, (k,n)-arcs, and other substructures of finite affine or projective spaces. In this talk a small part of the applications is selected: applications of fully reducible lacunary polynomials over finite fields. Such polynomials were Introduced by Laszlo Redei in the 70's and he applied them to the problem of directions determined by a set of $q$ points in a Desarguesian affine plane. In this talk we briefly survey the main theorems of Redei's book and some more recent applications of fully reducible lacinary polynomials in finite geometry. These results are mostly related to generalizations of the above mentioned direction problem and blocking sets. 

 In 2011 K. Kutnar, A. Malnič, L. Martinez and D. Marušič introduced the concept of the quasi m-Cayley graph for a positive integer m as follows. A finite simple graph X=(V,E) is quasi m-Cayley if there is a group G of automorphisms of X with the following properties: G has m+1 orbits on V, one of these orbits consists of a single vertex v, and G is semiregular on the set V\{v}. In this talk I report some results on vertex transitive quasi 2-Cayley graphs. This is a joint work with A. Hujdurović and K. Kutnar.

Extension of finite field F can be considered as a vector space over F and it has a many basis. Normal basis are of the special importance since multiplication of the elements of finite field can be realized in much easier way that in other basis. These are the reasons why normal basis are used in hardware realisation, cryptography and coding theory. Here we will give the definition, characterization and the number of normal basis and introduce some special cases as optimal normal basis with the best possible performance.

Download slides!

A graph is a core if any its endomorphism is an automorphism. In the talk I will describe some cores that are formed by particular sets of matrices. A relation with adjacency preservers will be presented. If the time will permit, few techniques that involve spectral graph theory and a connection with special relativity will be shown.