Salah Al-Addasi¹ and Hasan Al-Ezeh²

Copyright © 2008 Salah Al-Addasi and Hasan Al-Ezeh. This is an open access article distributed under the Creative Commons Attribution License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.

Abstract

We provide a process to extend any bipartite diametrical graph of diameter 4 to an S-graph of the same diameter and partite sets. For a bipartite diametrical graph of diameter 4 and partite sets U and W, where 2m=|U|≤|W|, we prove that 2m is a sharp upper bound of |W| and construct an S-graph G(2m,2m) in which this upper bound is attained, this graph can be viewed as a generalization of the Rhombic Dodecahedron. Then we show that for any m≥2, the graph G(2m,2m) is the unique (up to isomorphism) bipartite diametrical graph of diameter 4 and partite sets of cardinalities 2m and 2m, and hence in particular, for m=3, the graph G(6,8) which is just the Rhombic Dodecahedron is the unique (up to isomorphism) bipartite diametrical graph of such a diameter and cardinalities of partite sets. Thus we complete a characterization of S-graphs of diameter 4 and cardinality of the smaller partite set not exceeding 6. We prove that the neighborhoods of vertices of the larger partite set of G(2m,2m) form a matroid whose basis graph is the hypercube Qm. We prove that any S-graph of diameter 4 is bipartite self complementary, thus in particular G(2m,2m). Finally, we study some additional properties of G(2m,2m) concerning the order of its automorphism group, girth, domination number, and when being Eulerian.