SEMINAR: Groups and Combinatorics Seminar: Construction of Large Graphs: Few Results and a Wealth of Open Problems
|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
Maths Lecture Room 2
Mon, 25 Jan 2010 11:00
Mon, 25 Jan 2010 11:45
Michael Giudici <[email protected]>
Tue, 19 Jan 2010 10:35
- Locations of venues on the Crawley and Nedlands campuses are
available via the Campus Maps website.
- Download this event as:
Mail this event: