You are given a graph and you have to decide if it is a halved cube graph which is a subgraph of hypercube graph formed by connecting pairs of verices at distance exactly two from each other in the hypercube. This connectivity pattern produces two isomorphic graphs, disconnected from each other, each of which is the halved cube graph.
Let Qd be a hypercube of order d and let Hd be a halved cube of order d.
Let’s consider a hypercube graph Qd first. Qd has n = 2^d vertices and there is a very handful way of defining it. Let vertices of Qd be the set of all binary strings of length d. We connect two vertices if and only if their corresponding binary strings differ by exactly one bit. Based on this definition, it is easy to see that Qd is a d-regular graph with 2^d-1 * d edges and diameter d.
Let’s consier a vertex v of Qd. In order to know how to form a halved cube, we want to know how many vertices are at distance exactly two from v. Our handful definition shows that there are binomial(d, 2) vertices at distance two from v, because there are binomial(d, 2) binary strings different on exactly two bits from the string assigned to v.
You can try to construct one such graph it by hand. For example H3 is a complete graph over 4 vertices.
You can implement the algorithm described in this paper.
All fact below are based on the paper. I don’t give here a complete solution, because it is well presented in the paper.
You can assume that d >= 5, because we can recognize every Hd for d < 5 which is really easy.
It is known than Hd has 2^(d-1) cliques of size d.
Here is a sketch of the algorithm:
The algorithm works in steps:
Input: graph G on n vertices
- We identify all cliques of size d in G
- We construct a new graph G’ in the following way. For any cluque C found in step 1, we add a new vertex and join it to every vertex of C. The edges added in this process are all edges of G` - we remove all old edges of G at the end.
- We check if G` is a hypercube. If it is, G is a halved cube, otherwise G is not a halved cube.
Paper describes every step with all details. In order to understand the logic behind the construction in step 2 let’s consider any clique C. If G is a halved cube graph, then all pairs of vertices in C are at distance 2 in the corresponding hypercube graph. Based on this fact, it is easy to see that in there must be a vertex u in Qn such that u is as distance 1 from any of vertices in C. Please check the paper for more details.
AUTHOR’S AND TESTER’S SOLUTIONS:
To be uploaded soon.
To be uploaded soon.