Symmetries of a graph are described by its automorphism group, consisting of all permutations of vertices preserving adjacencies and non-adjacencies called an automorphisms. Automorphism groups are closely related to the famous graph isomorphism problem which asks whether two graphs are the same up to a relabeling of vertices called an isomorphism.
For more information and detailed description of our results, see my PhD thesis Extension Properties of Graphs and Structures.
In 1869, Jordan pioneered the study of automorphism groups of trees. Very nice inductive description of these groups was stated by Babai (1991) as the class of groups closed under the direct product and the semidirect product with symmetric groups. We call such inductive characterizations as Jordan-like. By Frucht's theorem, every abstract group is isomorphic to the automorphism group of some graph. A graph class is called universal if for every abstract finite group, there exists a graph from the class having the isomorphic automorphism group, and non-universal otherwise.
In [1], we have described Jordan-like inductive characterizations for the automorphism groups of interval graphs, permutation graphs, and circle graphs. We develop a general technique interpreting automorphisms of geometrically represented graphs as morphisms of these representations. Therefore, the automorphism group Aut(G) can be studied by its induced action on the set of all geometric representations of G. When the structure of all geometric representations is captured by a tree data structure, we can use it to characterize the automorphism groups. This approach is closely related to the research project Geometric Representations of Graphs.
Babai (1972) described a non-inductive characterization of the automorphism groups of planar graphs. In [2], we give the first inductive characterization of these groups based on the aforementioned technique. First, we prove that stabilizers of vertices in connected planar graphs are precisely the class of groups closed under several group products with symmetric, cyclic, and dihedral groups. Next, we describe the automorphism groups of connected planar graphs by direct products of a spherical group with these stabilizers. For more detail, see Chapter 8 of my PhD thesis.
Lubiw (1981) introduced the list-restricted graph isomorphism problem. The input gives two graphs G and H and a list L(u) of admissible images of each vertex u of G. We ask whether there exists a list-compatible isomorphism from G to H such that each vertex u of G is mapped to one of the admissible vertices of H. Surprisingly, Lubiw proved that this problem is NP-complete.
In [3], we revive the study of this problem for restricted graph classes and graph parameters. The goal is to find out which techniques used for graph isomorphism translate to the list restricted version. We prove the following results:
Metatheorem: [3] Polynomial-time reductions for GraphIso using vertex gadgets can be modified to polynomial-time reductions for ListIso. Therefore, GI-completeness results for GraphIso using such reductions imply NP-completeness of ListIso.
Theorem: [3] The problem ListIso can be solved in polynomial time for trees, planar graphs, interval graphs, circle graphs, permutation graphs, bounded genus graphs and bounded treewidth graphs.
Theorem: [3] The problem ListIso remains NP-complete for 3-regular colored graphs with all color classes of size at most 8 and with all lists of size at most 3.
Graph covering is a topological notion of similarity of graphs. A big graph G covers a small graph H if and only if there exists a covering projection p from G to H which is a locally bijective homomorphism. This means that when u is mapped to p(u), then N[u] is mapped bijectively to N[p(u)], so the neighborhoods of u and p(u) look locally the same. Graph coverings are an important technique of algebraic graph theory since many graph properties and results for one of these graph automatically translate to the other one.
A covering projection is called regular if it can be described using certain symmetries of the big graph G. More precisely, if there exists a semiregular subgroup Γ of Aut(G) such that G / Γ ≅ H where the quotient graph G / Γ is created from vertex- and edge-orbits of the action of Γ. For instance, the above covering projection is regular where Γ is generated by the antipodal involution. In [4,5,6], we have pioneered the study of the computational complexity of regular covering testing.
In [4,5], we study structural properties of regular graph covering with respect to 1-cuts and 2-cuts in G. We show that our 3-connected reduction, described in research project Geometric Representations of Graphs, behaves well with respect to regular graph covers: by combining different possible regular quotients of 3-connected component, we obtain all regular quotients of the original graph. Since all quotients of 3-connected planar graphs can be easily understood from the geometry, we describe all possible quotients of all connected planar graphs. As a consequence, we give a new direct proof of Negami's Theorem:
Theorem: (Negami) For a connected planar graph G, every regular quotient of G is planar or projectively planar.
Also, our structural results are applied in [4,6] to construct the following involved algorithm for regular covering testing:
Theorem: [4,6] Let G and H be input graphs such that G is a planar graph. We can test whether G regularly covers H in time O(v(G)^{c} 2^{e(H)/2}) for some constant c where v(G) is the number of vertices of G and e(H) is the number of edges of H.
In other words, regular covering testing of planar graphs is in FPT when parameterized by the size of the small graph. In particular, we get a polynomial-time algorithm for every fixed graph H. This sharply contrast with our result [7] that general covering testing is NP-complete for planar graphs G even for several small fixed graph H. For a detailed description of these results, see Chapters 10 and 11 of my PhD thesis.