Hamiltonicity in (0–1)-polyhedra |
| |
Authors: | DJ Naddef WR Pulleyblank |
| |
Institution: | 1. Laboratoire d''Informatique et de Mathématiques Appliquées, Université Scientifique et Médicale de Grenoble, France;2. Université des Sciences Sociales de Grenoble, France |
| |
Abstract: | The graph G(P) of a polyhedron P has a node corresponding to each vertex of P and two nodes are adjacent in G(P) if and only if the corresponding vertices of P are adjacent on P. We show that if P ? n is a polyhedron, all of whose vertices have (0–1)-valued coordinates, then (i) if G(P) is bipartite, the G(P) is a hypercube; (ii) if G(P) is nonbipartite, then G(P) is hamilton connected. It is shown that if P ? n has (0–1)-valued vertices and is of dimension d (≤n) then there exists a polyhedron P′ ? d having (0–1)-valued vertices such that . Some combinatorial consequences of these results are also discussed. |
| |
Keywords: | |
本文献已被 ScienceDirect 等数据库收录! |
|