International Journal of Mathematics and Mathematical Sciences
Volume 2008 (2008), Article ID 468583, 11 pages
Bipartite Diametrical Graphs of Diameter 4 and Extreme Orders
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.
We provide a process to extend any bipartite diametrical graph of diameter 4 to an -graph of the same diameter and partite sets. For a bipartite diametrical graph of diameter 4 and partite sets
and , where , we prove that
is a sharp upper bound of and construct an -graph
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 , the graph is the unique (up to isomorphism) bipartite diametrical graph of diameter 4 and partite sets of cardinalities
and , and hence in particular, for ,
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 -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
form a matroid whose basis graph is the hypercube . We prove that any -graph of diameter 4 is bipartite self complementary, thus in particular
. Finally, we study some additional properties of concerning the order of its automorphism group, girth, domination number, and when being Eulerian.