A generalization of hypercubes: Complemented graphs (Q1808497)

Let \(G=(V,X)\) be a simple graph. A nonempty subset \(A\) of \(V\) is called a convex if \(A\) contains every vertex on any shortest \(a\)-\(b\) path with \(a,b\in A\). The least convex containing a set \(B\) is denoted by \([B]\). A graph \(G=(V,X)\) is complemented if it is connected, has at least two vertices, and the following conditions are satisfied: (i) For every vertex \(v\) of \(G\), there exists a unique vertex \(v'\) such that \(d(v,v')=\text{diam} (G)\). (ii) For every vertex \(w\in N(v)\) (the neighbourhood of \(v\)), the vertex \(w'\) also belongs to \(N(v)\). (iii) Let \(A\) be a convex of \(G\). If \([A\cup \{ v\} ]=V\), then \(v'\in A\), and if \(v'\in B\), then \([[B]\cup \{ v\} ]=V\). A nonempty convex \(P\) of \(G\) is a prime convex if the set \(V\setminus P\) is also a convex of \(G\). The graph \(G\) is a prime convex intersection graph if every convex of \(G\) different from \(V\) is the intersection of prime convexes of \(G\). In the paper several properties of complemented graphs are proved. Furthermore, the authors provide necessary and sufficient conditions for (connected) prime convex intersection graphs to be hypercubes in terms of complemented graphs.