The Cost of Symmetry for Tailed Stars
Abstract
It is known that if, in a connected graph $$\Gamma$$ , one can eliminate $$n$$ vertices so that there remain no subgraphs isomorphic to a graph $$K$$ , then one can remove at most $$|V(K)|\cdot n$$ vertices that form a set invariant under all automorphisms of the graph $$\Gamma$$ so that there remain no subgraphs isomorphic to the graph $$K$$ . We construct an infinite family of (connected) graphs $$K$$ , for which this estimate is not sharp.
Fields of Study & Subjects
History and Developments in Astronomy
Economic Growth and Productivity
Publication details
- Journal / source
- Mathematical Notes
- Publisher
- Pleiades Publishing Ltd
- Volume
- 119
- Issue
- 5-6
- Pages
- 976–983
- Publication date
- 1 May 2026
- Language
- EN