zbMATH — the first resource for mathematics

Clumps, minimal asymmetric graphs, and involutions. (English) Zbl 0686.05028
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”.
Reviewer: G.Sabidussi

05C35 Extremal problems in graph theory
Full Text: DOI
[1] Aschbacher, M, A homomorphism theorem for finite graphs, (), 468-470 · Zbl 0319.05115
[2] Blass, A, Graphs with unique maximal clumpings, J. graph theory, 2, 19-24, (1976) · Zbl 0377.05036
[3] Gallai, T, Transitiv orientierbare graphen, Acta math. acad. sci. hungar., 18, 25-66, (1967) · Zbl 0153.26002
[4] Nešetřil, J, A congruence theorem for asymmetric trees, Pacific J. math., 37, 771-778, (1971) · Zbl 0228.05103
[5] \scJ. Nešetřil and G. Sabidussi, Minimal graphs without bilateral symmetry: The case of induced length 4, preprint, No. 88-512, “Forschungsinst. f. Diskrete Mathematik” Bonn University.
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.