Two characterizations of generalized hypercube (Q1182875): Difference between revisions

In the present paper the Hamming graph is investigated which is a generalization of the hypercube. At first there is given a short survey of already known characterizations of these graphs and the author gets two further new statements to the effect that a simple connected graph \(G\) is a Hamming graph. In Theorem 1 structural properties for \(G\) are given which characterize Hamming graphs analogous to the characterization of hypercubes as (0,2) graphs of maximal order. In Theorem 2 the characterization occurs by applying the notion of quasi-interval and it is shown that in the case all quasi-intervals in \(G\) are quasi-convex and closed and \(G\) contains a 3-star as induced subgraph, \(G\) is a Hamming graph. Both theorems are proved by using numerous propositions.