• Title of article

    Intersection graphs of maximal hypercubes

  • Author/Authors

    Bresar M.، نويسنده , , Bo?tjan، نويسنده ,

  • Issue Information
    روزنامه با شماره پیاپی سال 2003
  • Pages
    15
  • From page
    195
  • To page
    209
  • Abstract
    In this paper we consider cube graphs, that is intersection graphs of maximal hypercubes of graphs. In contrast to the related concepts of line graphs and clique graphs, we show that any graph is a cube graph of a (bipartite) graph. We answer a question of Bandelt and Chepoi (European J. Combin. 17 (1996) 113) by showing that dually chordal graphs are precisely cube graphs of graphs of acyclic cubical complexes. Similarly, we characterize classes of chordal graphs, Helly chordal graphs and doubly chordal graphs as cube graphs of certain subclasses of isometric subgraphs of hypercubes.
  • Keywords
    graph , dually chordal , Acyclic cubical complex , Chordal , Intersection graph , median , Hypercube , Simplicial complex , EXPANSION
  • Journal title
    European Journal of Combinatorics
  • Serial Year
    2003
  • Journal title
    European Journal of Combinatorics
  • Record number

    1546935