Graphs of acyclic cubical complexes
type: Item
instance of: scholarly article
title: Graphs of acyclic cubical complexes
zbMATH Open document ID: 0848.05053
author: Hans-Jürgen Bandelt
author: Victor Chepoi
published in: European Journal of Combinatorics
publication date: 1996-10-01T00:00:00Z
review text: A cubical complex is a finite set \({\mathfrak K}\) of cubes of any dimensions which is closed under taking subcubes and non-empty intersections. Its vertices are null-dimensional cubes of \({\mathfrak K}\), and it is said to be conformal if any set of vertices is included in a member of \({\mathfrak K}\) whenever each pair of its vertices is contained in a member of \({\mathfrak K}\). This means that a cubical complex \({\mathfrak K}\) can be regarded as a hypergraph where the edges are the members of \({\mathfrak K}\) and the vertices are the vertices of \({\mathfrak K}\). A conformal \({\mathfrak K}\) which does not contain cycles is called acyclic. In the present paper the class of graphs \(G\) associated with such acyclic cubical complexes is investigated. After the introduction of the concepts of the so-called cube elimination scheme, of the cube contraction scheme, and of the simplicial complex, the first result consists in four equivalent statements for a cubical complex \({\mathfrak K}\) to be acyclic (Proposition 1). Then the graphs \(G\) are characterized among median graphs by forbidden convex subgraphs. A median graph is defined to be a connected graph such that for every triple of vertices \(u,v,w\) there exists a unique vertex which lies on shortest paths between each pair from \(u,v,w\). The authors obtain the result that for the graph \(G\) of a conformal cubical complex \({\mathfrak K}\) the following statements are equivalent: (1) \({\mathfrak K}\) is acyclic; (2) \(G\) is a median graph not containing any convex bipartite wheel; (3) \(G\) is a median graph such that the incompatibility graph of its convex splits is chordal. Further the authors disprove a conjecture of Mulder on star contractions of median graphs \(G\) saying that the equality \(s(G) = h(G)\) holds; the star-contraction number \(s(G)\) denotes the largest number \(n\) for which the star with \(n\) endvertices is a homomorphic image of \(G\) and the hull number \(h(G)\) denotes the…
Mathematics Subject Classification ID: 05C75
Mathematics Subject Classification ID: 05C65
Mathematics Subject Classification ID: 05C38
zbMATH DE Number: 871008
zbMATH Keywords: cubical complex
zbMATH Keywords: hypergraph
zbMATH Keywords: median graph
zbMATH Keywords: star-contraction number
zbMATH Keywords: hull number
zbMATH Keywords: Mulder conjecture
zbMATH Keywords: perfect graphs
reviewed by: Heinz-Joachim Presia
MaRDI profile type: Publication
OpenAlex ID: W2010493552
DOI: 10.1006/EUJC.1996.0010
description: scientific article; zbMATH DE number 871008