ﻻ يوجد ملخص باللغة العربية
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.
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 autom
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 num
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 suita
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.