Graphs and cubes (Q636729)

This book, split into eight chapters, presents an introductory text in graph theory and considers in particular detail partial cubes, defined as the graphs that are isometrically embeddable into hypercubes. The book begins with an introduction to graph theory where all the necessary definitions are introduced, followed by a chapter on bipartite graphs, since all cubic graphs are also bipartite. The third and fourth graphs consider respectively cubes and cubical graphs. These are essential for an understanding of the fifth chapter, partial cubes, which forms the central chapter of this book. In this chapter the structural properties of partial cubes is explored and several characterizations of these graphs are presented. The next two chapters expand the study of partial cubes including applications and the geometric interpretation. The book concludes with a chapter on the application of partial cubes on cubical token systems, a list of useful references and an index.