Invariant systems of weighted representatives

Abstract: It is known that, if removing some

n

edges from a graph

G a m m a

destroys all subgraphs isomorphic to a given finite graph

K

, then all subgraphs isomorphic to

K

can be destroyed by removing at most

| E (K) | c d o t n

edges, which form a set invariant with respect to all automorphisms of

G a m m a

. We construct the first examples of (connected) graphs

K

for which this estimate is not sharp. Our arguments are based on a ``weighted analogue of an earlier known estimate for the cost of symmetry.

This page was built for publication: Invariant systems of weighted representatives