English      Slovensko

Customized Project N1-0038
Graphs and Odd Automorphisms


Project Title: Graphs and Odd Automorphisms.

PI: Dragan Marušič.

Project Code: N1-0038.

Type of the Project: customized project.

Funding Organization: Slovenian Research Agency (ARRS).

Research Field (ARRS): 1.01.00 - Natural Sciences and Mathematics / Mathematics.

Duration: 1. 9. 2015 - 31. 8. 2018.

Project Category: B.

Yearly Range: 1.88 FTE (3198 research hours).

Sicris profile of the project is avaliable here.

Research Organization: University of Primorska, Andrej Marušič Institute.

Project Members:

Hujdurović Ademir (ARRS code: 32518)
Kovacs Istvan (ARRS code: 25997)
Kutnar Klavdija (ARRS code: 24997)
Jajcay Robert (ARRS code: 37724)
Malnič Aleksander (ARRS code: 02507)
Marušič Dragan (PI) (ARRS code: 02887)
Miklavič Štefko (ARRS code: 21656)
Požar Rok (ARRS code: 32026)
Šparl Primož (ARRS code: 23341)



This project focuses on the concept of even/odd automorphisms of graphs, that is, even/odd permutations on the vertex set of the graph preserving the structure of the graph in question. This simple yet novel concept opens up a new research area, of interest in its own right, leading to important progress in many long-standing research problems.

The core research problems: Given a transitive group of even automorphisms H of a graph X, is there a group G containing odd automorphisms of X and H as a subgroup? If yes, what is the minimum index [G:H] among all such groups G? And finally, provided that H admits an H-invariant partition B such that the action of H on the quotient X/B is primitive, is there an “extension” G such that the index [G:H] is minimum and B is not G-invariant?

Seeking for “extensions” of groups via odd automorphisms is also a novel approach to the following fundamental question: Given a transitive group H acting on a combinatorial/geometric object, determine whether H is its full automorphism group or not. When H consists of even automorphisms only, a partial answer could be given provided the structure of the object in question forces existence of odd automorphisms.

Our goal is to build a theory that will allow us to decide whether a given graph, admitting a transitive group action, does or does not have odd automorphisms. The first step in our strategy consists in finding conditions for existence of odd automorphisms for large classes of graphs, admitting a transitive action of a group H, with suitably imposed constraints. In parallel, this theory will be applied to address open questions in algebraic graph theory (involving semiregularity, hamiltonicity, etc.).