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

Bipartite Diametrical Graphs of Diameter 4 and Extreme Orders

Salah Al-Addasi1 and Hasan Al-Ezeh2

1Mathematics Department, Faculty of Science, Hashemite University, Zarqa 150459, Jordan
2Mathematics Department, Faculty of Science, University of Jordan, Amman 11942, Jordan

Received 9 July 2007; Accepted 5 December 2007

Academic Editor: Peter Johnson

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 m2, 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.