Intersection graphs of maximal hypercubes
type: Item
instance of: scholarly article
title: Intersection graphs of maximal hypercubes
zbMATH Open document ID: 1018.05091
DOI: 10.1016/S0195-6698(02)00142-7
author: Boštjan Brešar
published in: European Journal of Combinatorics
publication date: 2003-04-02T00:00:00Z
review text: A hypercube \(Q_k\) is the graph with vertex set \(\{0,1\}^k\) where two vertices are adjacent whenever they differ in exactly one position. The cube graph \(Q(G)\) of a graph \(G\) is the intersection graph of maximal (induced) hypercubes of \(G\): The vertices of \(Q(G)\) correspond to the maximal hypercubes of \(G\), and two vertices are adjacent if the corresponding hypercubes are nondisjoint. The author investiges the cube graphs of several particular graph classes. Among other results, he proves that any graph is a cube graph of a bipartite graph, and that dually chordal graphs are exactly the cube graphs of graphs of acyclic cubical complexes.
reviewed by: Van Bang Le
Mathematics Subject Classification ID: 05C75
zbMATH DE Number: 1891298
zbMATH Keywords: dually chordal graph
zbMATH Keywords: acyclic cubical complex
zbMATH Keywords: simplicial complex
zbMATH Keywords: intersection graph
zbMATH Keywords: hypercube
zbMATH Keywords: median graph
zbMATH Keywords: expansion
MaRDI profile type: Publication
cites work: Graphs of acyclic cubical complexes
cites work: Clique graphs and Helly graphs
cites work: Superextensions and the depth of median graphs
cites work: Q3993087
cites work: Dually Chordal Graphs
cites work: Graph Classes: A Survey
cites work: Partial Hamming graphs and expansion procedures
cites work: Isometric subgraphs of Hamming graphs and d-convexity
cites work: Distance-preserving subgraphs of hypercubes
cites work: Q3328583
cites work: A convexity lemma and expansion procedures for bipartite graphs
cites work: Q4523707
cites work: Q4264556
cites work: Topics in Intersection Graph Theory
cites work: Doubly chordal graphs, steiner trees, and connected domination
cites work: The structure of median graphs
cites work: n‐cubes and median graphs
cites work: Q3972522
cites work: A characterization of clique graphs
cites work: Clique Graphs of Chordal and Path Graphs
cites work: Q3141898
cites work: Isometric embedding in products of complete graphs
full work available at URL: s0195-6698(02)00142-7
OpenAlex ID: W2008957319
description: scientific article; zbMATH DE number 1891298