Name
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 Jordanu0027s 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. |
Year | Venue | Field |
|---|---|---|
2015 | arXiv: Discrete Mathematics | Graph automorphism,Permutation graph,Discrete mathematics,Modular decomposition,Comparability graph,Indifference graph,Combinatorics,Interval graph,Chordal graph,Cograph,Mathematics |
DocType | Volume | Citations |
Journal | abs/1506.05064 | 1 |
PageRank | References | Authors |
0.35 | 8 | 2 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Pavel Klavík | 1 | 95 | 10.63 |
| Peter Zeman | 2 | 6 | 3.14 |