A generalization of hypercubes: Complemented graphs
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.
This page was built for publication: A generalization of hypercubes: Complemented graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1808497)
