k-Dismantlability in Graphs
Résumé
Given a finite undirected graph $X$, a vertex is $0$-dismantlable if its open neighborhood 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 neighborhood is $k$-dismantlable and a graph is $k$-dismantlable if it is reducible to a single vertex by successive deletions of $k$-dismantlable vertices. Within the class of graphs whose clique complex is collapsible, the family of $k$-dismantlable graphs form a strict hierarchy in the sub-class of graphs whose clique complex is non-evasive. We introduce special graphs to study higher $k$-dismantlabilities. We point out how $k$-dismantlability is related to the derivability of graphs defined by Mazurkievicz and we get a new characterization of the class of closed graphs that he defined. By generalizing the notion of vertex transitivity, we replace $k$-dismantlability in its link with the evasiveness conjecture.