Layered subgraphs of the hypercube
Authors:
- Natalie BehagueNBNatalie Behague
- Imre LeaderILImre Leader
- Natasha MorrisonNMNatasha Morrison
- Kada WilliamsKWKada Williams
Preprint
Abstract
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.Keywords
All Related Versions
This publication has 3 references indexed in Scilit:
- On Graphs Embeddable in a Layer of a Hypercube and Their Extremal NumbersAnnals of Combinatorics, 2024
- Modern Graph Theory1998
- $B$-valuations of graphsCzechoslovak Mathematical Journal, 1972