Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userAutomorphism Groups of Comparability Graphs
107
0
0.0
(
0
)
Added by
Pavel Klav\\'ik
Publication date
2015
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
Comparability graphs are graphs which have transitive orientations. The dimension of a poset is the least number of linear orders whose intersection gives this poset. The dimension ${rm dim}(X)$ of a comparability graph $X$ is the dimension of any transitive orientation of X, and by $k$-DIM we denote the class of comparability graphs $X$ with ${rm dim}(X) le k$. It is known that the complements of comparability graphs are exactly function graphs and permutation graphs equal 2-DIM. In this paper, we characterize the automorphism groups of permutation graphs similarly to Jordans characterization for trees (1869). For permutation graphs, there is an extra operation, so there are some extra groups not realized by trees. For $k ge 4$, we show that every finite group can be realized as the automorphism group of some graph in $k$-DIM, and testing graph isomorphism for $k$-DIM is GI-complete.
rate research
Read More
A detailed proof is given of a theorem describing the centraliser of a transitive permutation group, with applications to automorphism groups of objects in various categories of maps, hypermaps, dessins, polytopes and covering spaces, where the automorphism group of an object is the centraliser of its monodromy group. An alternative form of the theorem, valid for finite objects, is discussed, with counterexamples based on Baumslag--Solitar groups to show how it fails more generally. The automorphism groups of objects with primitive monodromy groups are described, as are those of non-connected objects.
A graph $G$ is said to be the intersection of graphs $G_1,G_2,ldots,G_k$ if $V(G)=V(G_1)=V(G_2)=cdots=V(G_k)$ and $E(G)=E(G_1)cap E(G_2)capcdotscap E(G_k)$. For a graph $G$, $mathrm{dim}_{COG}(G)$ (resp. $mathrm{dim}_{TH}(G)$) denotes the minimum number of cographs (resp. threshold graphs) whose intersection gives $G$. We present several new bounds on these parameters for general graphs as well as some special classes of graphs. It is shown that for any graph $G$: (a) $mathrm{dim}_{COG}(G)leqmathrm{tw}(G)+2$, (b) $mathrm{dim}_{TH}(G)leqmathrm{pw}(G)+1$, and (c) $mathrm{dim}_{TH}(G)leqchi(G)cdotmathrm{box}(G)$, where $mathrm{tw}(G)$, $mathrm{pw}(G)$, $chi(G)$ and $mathrm{box}(G)$ denote respectively the treewidth, pathwidth, chromatic number and boxicity of the graph $G$. We also derive the exact values for these parameters for cycles and show that every forest is the intersection of two cographs. These results allow us to derive improved bounds on $mathrm{dim}_{COG}(G)$ and $mathrm{dim}_{TH}(G)$ when $G$ belongs to some special graph classes.
The thinness of a graph is a width parameter that generalizes some properties of interval graphs, which are exactly the graphs of thinness one. Many NP-complete problems can be solved in polynomial time for graphs with bounded thinness, given a suitable representation of the graph. In this paper we study the thinness and its variations of graph products. We show that the thinness behaves well in general for products, in the sense that for most of the graph products defined in the literature, the thinness of the product of two graphs is bounded by a function (typically product or sum) of their thinness, or of the thinness of one of them and the size of the other. We also show for some cases the non-existence of such a function.
Building on earlier results for regular maps and for orientably regular chiral maps, we classify the non-abelian finite simple groups arising as automorphism groups of maps in each of the 14 Graver-Watkins classes of edge-transitive maps.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
