It is shown that the graph Q(7)-c obtained from the 7-cube Q( 7) by deletion of a perfect Hamming code C has a spanning self-complementary subgraph which is edge-transitive but not vertextransitive and also extremal among all the cube subgraphs which are square-blocking and codeavoiding. Our work uses combinatorial techniques involving orientations on the Fano plane and the resulting Steiner triple systems.
In this paper, we study some combinatorial properties of a cubic bipartite graph, that we will denote by W, which is edge-transitive but not vertex-transitive. Bouwer mentioned at the end of his introduction in [2] that R.M. Foster found such a graph that has 112 vertices and whose girth is 10. We will see that W has these characteristics. Moreover, we will also see that if C denotes the perfect Hamming code in the 7-cube Q(7), then W is a spanning self-complementary subgraph of the graph Q(7)-c.
In contrast, Q(7) -C is seen to be both an edge-transitive and a vertextransitive graph. The fact that Wand its complement in Q(7) -C are edge-transitive but not vertex-transitive subgraphs of Q(7) -C, which is both an edge-and vertextransitive subgraph of the 7-cube (itself edge-and vertex-transitive), testifies to the difficulty of the task of studying the symmetrical properties of subgraphs of n-cubes.
The graph W appeared in [3] as the subgraph induced by a subset E' of edges of the 7-cube Q(7). It was shown in [3] that:
(1) E' blocks all the squares of Q( 7).
(2) If C denotes the perfect Hamming code in Q(7) (see e.g. [6]), then no edge of E' has as an endvertex a codeword of C.
(3) The cardinality ]E'] of E' is the smallest known one among the cardinalities of those edge subsets of Q(7) that satisfy (1) and (2).