SEMINAR: Groups and Combinatorics Seminar: Construction of Large Graphs: Few Results and a Wealth of Open Problems

Groups and Combinatorics Seminar

Guillermo Pineda-Villavicencio (University of Ballarat)

will speak on

Construction of Large Graphs: Few Results and a Wealth of Open Problems

at 11am in Maths Lecture Room 2 on Monday 25 January

Abstract: In recent work with Eyal Loz we constructed all the new largest known graphs of maximum degree 16< k < 21 and diameter 1< D < 11, using a wide range of techniques and concepts, such as graph compounding, vertex duplication, Kronecker product, polarity graphs and voltage graphs. In this way, we extended the table of largest graphs known at present, which previously only covered graphs of maximum degree 2< k< 17 and diameter 1< D < 11. During the constructing process we arrived at the conclusion that, among all the techniques employed, the notion of voltage graphs is the leading beacon for future directions in the construction of large graphs. However, many of its weaknesses need to be tackle to reach its potential. For instance, (i) There is NO methodology to obtain voltage groups and voltage assignments to generate graphs with specific properties. (ii) The procedure is done "blindly" in some sense; little is known about the classes of graphs that can be lifted.

In our talk we present a number of ideas and open problems that address the previous defects; some of the open problems are related below. Problem 1: Develop a methodology to construct the voltage group and the voltage assignment, given some desired properties for the lift. Problem 2: Given a base graph with a graph property P, provide conditions for a lift to have the property P. (Special case of the previous problem). Problem 3: For what graphs (not necessarily vertex-transitive) G, does Aut(G) contain a subgroup semiregular on V(G)?.

This is joint work with Eyal Loz and Hebert Peerez-Roses

All welcome