Layered Subgraphs of the Hypercube
A subgraph of the $n$-dimensional hypercube is called 'layered' if it is a subgraph of a layer of some hypercube. In this paper we show that there exist subgraphs of the cube of arbitrarily large girth that are not layered. This answers a question of Axenovich, Martin and Winter. Perhaps surprisingly, these subgraphs may even be taken to be induced.
Authors
- Natalie Behague (ORCID: https://orcid.org/0000-0001-6616-1606)
- Imre Leader
- Kada Williams
- Natasha Morrison
Institutions
- University of Cambridge (GB)
- University of Warwick (GB)
Publication Details
- Journal
- The Electronic Journal of Combinatorics
- Published
- 2024-10-18
- DOI
- https://doi.org/10.37236/12980
- Citations
- 1
- Primary Topic
- Interconnection Networks and Systems
- Type
- article
- Field-Weighted Citation Impact
- 0.35
Funders
- Natural Sciences and Engineering Research Council of Canada