A hierarchy of dismantlings in Graphs

Etienne Fieux (1) , Bertrand Jouve (2)

1 IMT - Institut de Mathématiques de Toulouse UMR5219
2 LISST - Laboratoire Interdisciplinaire Solidarités, Sociétés, Territoires

Given a finite undirected graph $X$, a vertex is $0$-dismantlable if its open neighbourhood is a cone and $X$ is $0$-dismantlable if it is reducible to a single vertex by successive deletions of $0$-dismantlable vertices. By an iterative process, a vertex is $(k+1)$-dismantlable if its open neighbourhood is $k$-dismantlable and a graph is $k$-dismantlable if it is reducible to a single vertex by successive deletions of $k$-dismantlable vertices. We introduce a graph family, the cubion graphs, in order to prove that $k$-dismantlabilities give a strict hierarchy in the class of graphs whose clique complex is non-evasive. We point out how these higher dismantlabilities are related to the derivability of graphs defined by Mazurkievicz and we get a new characterization of the class of closed graphs he defined. By generalising the notion of vertex transitivity, we consider the issue of higher dismantlabilities in link with the evasiveness conjecture.

Mots clés: dismantlability; flag complexes; collapses; evasiveness; graph derivability

Domaines: Mathématique discrète [cs.DM]

Etienne Fieux, Bertrand Jouve. A hierarchy of dismantlings in Graphs. Discrete Mathematics, 2020, 343 (8), ⟨10.1016/j.disc.2020.111914⟩. ⟨hal-02540557⟩