Automorphism groups of geometrically represented graphs

DOI10.4230/LIPICS.STACS.2015.540MaRDI QIDQ2955022zbMATH OpenFDO

Authors Pavel Klavík, Peter Zeman

Publication date 24 January 2017

Full work available at URL https://arxiv.org/abs/1407.2136

zbMATH Keywords

automorphism groupcircle graphgeometric intersection graphinterval graph

Mathematics Subject Classification ID

Graphs and abstract algebra (groups, rings, fields, etc.) (05C25) Graph representations (geometric and intersection representations, etc.) (05C62) Graph algorithms (graph-theoretic aspects) (05C85) Finite automorphism groups of algebraic, geometric, or combinatorial structures (20B25)

Abstract: We describe a technique to determine the automorphism group of a geometrically represented graph, by understanding the structure of the induced action on all geometric representations. Using this, we characterize automorphism groups of interval, permutation and circle graphs. We combine techniques from group theory (products, homomorphisms, actions) with data structures from computer science (PQ-trees, split trees, modular trees) that encode all geometric representations. We prove that interval graphs have the same automorphism groups as trees, and for a given interval graph, we construct a tree with the same automorphism group which answers a question of Hanlon [Trans. Amer. Math. Soc 272(2), 1982]. For permutation and circle graphs, we give an inductive characterization by semidirect and wreath products. We also prove that every abstract group can be realized by the automorphism group of a comparability graph/poset of the dimension at most four.

Recommendations

• Geometric automorphism groups of graphs
• Sufficient conditions for properly colored \(C_3\)'s and \(C_4\)'s in edge-colored complete graphs
• scientific article; zbMATH DE number 3853103
• scientific article; zbMATH DE number 7681424
• Cyclic automorphism groups of graphs and edge-colored graphs

Cited in

(9)

• Automorphism groups of comparability and covering graphs
• Automorphism groups of graph covers and uniform subset graphs
• Sufficient conditions for properly colored \(C_3\)'s and \(C_4\)'s in edge-colored complete graphs
• Geometric automorphism groups of graphs
• Jordan-like characterization of automorphism groups of planar graphs
• Automorphism groups of the Pancake graphs
• Labelled well-quasi-order for permutation classes
• Graph isomorphism restricted by lists
• On endomorphism universality of sparse graph classes

This page was built for publication: Automorphism groups of geometrically represented graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2955022)