Graphs of acyclic cubical complexes (Q1911833)

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 minimum cardinality of subsets the convex hulls of which coincides with \(G\). A counterexample is given by the bipartite 5-wheel. In connection with this, the simplex graph \(G\) of a graph \(F\) is considered and the authors obtain the result (Proposition 2) that six statements for the simplex graph \(G\) of \(F\) are equivalent, for instance: \(F\) is perfect and the Mulder conjecture holds for all convex subgraphs \(G'\) of \(G\). From this result the perfectness of acyclic cubical complexes follows (Corollary 1). Generalizing the results of Proposition 2 to arbitrary median graphs and complexes, median homomorphic images instead of convex subgraphs are considered. So the authors obtain, for the class of median cubical complexes relations to perfect graphs for which also the Mulder conjecture holds true.