International Journal of Mathematics and Mathematical Sciences
Volume 2008 (2008), Article ID 468583, 11 pages
doi:10.1155/2008/468583

Bipartite diametrical graphs of diameter 4 and extreme orders

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.