A hierarchy of dismantlings in Graphs

Autor: Bertrand Jouve, Etienne Fieux
Přispěvatelé: Institut de Mathématiques de Toulouse UMR5219 (IMT), Institut National des Sciences Appliquées - Toulouse (INSA Toulouse), Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Université Toulouse 1 Capitole (UT1), Université Fédérale Toulouse Midi-Pyrénées-Université Fédérale Toulouse Midi-Pyrénées-Université Toulouse - Jean Jaurès (UT2J)-Université Toulouse III - Paul Sabatier (UT3), Université Fédérale Toulouse Midi-Pyrénées-Centre National de la Recherche Scientifique (CNRS), Laboratoire Interdisciplinaire Solidarités, Sociétés, Territoires (LISST), École des hautes études en sciences sociales (EHESS)-Université Toulouse - Jean Jaurès (UT2J)-École Nationale Supérieure de Formation de l'Enseignement Agricole de Toulouse-Auzeville (ENSFEA)-Centre National de la Recherche Scientifique (CNRS), Université Toulouse Capitole (UT Capitole), Université de Toulouse (UT)-Université de Toulouse (UT)-Institut National des Sciences Appliquées - Toulouse (INSA Toulouse), Institut National des Sciences Appliquées (INSA)-Université de Toulouse (UT)-Institut National des Sciences Appliquées (INSA)-Université Toulouse - Jean Jaurès (UT2J), Université de Toulouse (UT)-Université Toulouse III - Paul Sabatier (UT3), Université de Toulouse (UT)-Centre National de la Recherche Scientifique (CNRS), École des hautes études en sciences sociales (EHESS)-Université Toulouse - Jean Jaurès (UT2J), Université de Toulouse (UT)-Université de Toulouse (UT)-École Nationale Supérieure de Formation de l'Enseignement Agricole de Toulouse-Auzeville (ENSFEA)-Centre National de la Recherche Scientifique (CNRS)
Rok vydání: 2019
Předmět:
0102 computer and information sciences
02 engineering and technology
[INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM]
01 natural sciences
Theoretical Computer Science
Combinatorics
0202 electrical engineering
electronic engineering
information engineering
FOS: Mathematics
Mathematics - Combinatorics
Discrete Mathematics and Combinatorics
Algebraic Topology (math.AT)
Mathematics - Algebraic Topology
Undirected graph
Mathematics
Discrete mathematics
Iterative and incremental development
Transitive relation
Aanderaa–Karp–Rosenberg conjecture
Neighbourhood (graph theory)
020206 networking & telecommunications
flag complexes
evasiveness
Graph
Vertex (geometry)
010201 computation theory & mathematics
graph derivability
collapses
Combinatorics (math.CO)
dismantlability
Clique complex
Zdroj: Discrete Mathematics
Discrete Mathematics, Elsevier, In press, 343 (8)
Discrete Mathematics, 2020, 343 (8), ⟨10.1016/j.disc.2020.111914⟩
ISSN: 0012-365X
DOI: 10.48550/arxiv.1902.04508
Popis: 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.
Comment: 17 pages, 9 figures
Databáze: OpenAIRE
Externí odkaz: