Clumps, minimal asymmetric graphs, and involutions (Q1262321): Difference between revisions

A graph is minimal asymmetric if it is asymmetric (i.e., has no non- trivial automorphism) and contains no proper non-trivial asymmetric induced subgraph. The induced length of a graph is the length of a longest induced path. We show that there exist seven minimal asymmetric graphs \(M_ 1,...,M_ 7\) such that for any connected graph G of induced length \(n\geq 5\) the following holds: G contains an \(M_ i\) as an induced subgraph, or G has a non-trivial clump (i.e., a set S of vertices all of whose members have the same neighbours outside S), or G has an involution (automorphism of order 2). More precise forms of this statment can be given depending on the value of n. This is used to show that (i) there are no minimal asymmetric graphs of induced length greater than 5, and (ii) there are exactly two such graphs of induced length 5. These are the asymmetric tree of 7 vertices, and the graph consisting of two 4-cycles C, D having exactly one common edge, with a pendant edge attached to one of the vertices not in \(C\cap D\). The same statements hold if ``minimal asymmetric'' is replaced by ``minimal involution-free''.