Back to Search
Start Over
Long geodesics in subgraphs of the cube.
- Source :
-
Discrete Mathematics . Jul2014, Vol. 326, p29-33. 5p. - Publication Year :
- 2014
-
Abstract
- Abstract: We show that any subgraph of the hypercube of average degree contains a geodesic of length , where by geodesic we mean a shortest path in . This result, which is best possible, strengthens a theorem of Feder and Subi. It is also related to the ‘antipodal colourings’ conjecture of Norine. [Copyright &y& Elsevier]
Details
- Language :
- English
- ISSN :
- 0012365X
- Volume :
- 326
- Database :
- Academic Search Index
- Journal :
- Discrete Mathematics
- Publication Type :
- Academic Journal
- Accession number :
- 95505294
- Full Text :
- https://doi.org/10.1016/j.disc.2014.02.013