Previous |  Up |  Next


asymmetric diagraphs
A digraph is a symmetric cycle if it is symmetric and its underlying graph is a cycle. It is proved that if $D$ is an asymmetric digraph not containing a symmetric cycle, then $D$ remains asymmetric after removing some vertex. It is also showed that each digraph $D$ without a symmetric cycle, whose underlying graph is connected, contains a vertex which is a common fixed point of all automorphisms of $D$.
[1] Nešetřil J.: A congruence theorem for asymmetric trees. Pacific J. Math. 37 (1971), 771-778. MR 0307955
[2] Nešetřil J., Sabidussi G.: Minimal asymmetric graphs of induced length 4. Graphs and Combinatorics 8.4 (1992), 343-359. MR 1204119
[3] Sabidussi G.: Clumps, minimal asymmetric graphs, and involutions. J. Combin. Th. Ser. B 53.1 (1991), 40-79. MR 1122296 | Zbl 0686.05028
Partner of
EuDML logo