# Bipartite Diametrical Graphs of Diameter 4 and Extreme Orders

International Journal of Mathematics and Mathematical Sciences. 2008;2008 DOI 10.1155/2008/468583

**Journal Title**: International Journal of Mathematics and Mathematical Sciences

**ISSN**:
0161-1712 (Print); 1687-0425 (Online)

**Publisher**: Hindawi Publishing Corporation

**LCC Subject Category**:
Science: Mathematics

**Country of publisher**: Egypt

**Language of fulltext**: English

**Full-text formats available**: PDF, HTML, ePUB

**AUTHORS**

*Salah Al-Addasi
(Mathematics Department, Faculty of Science, Hashemite University, Zarqa 150459, Jordan)
*

*Hasan Al-Ezeh
(Mathematics Department, Faculty of Science, University of Jordan, Amman 11942, Jordan)
*

**EDITORIAL INFORMATION**

Time From Submission to Publication: 17 weeks

**
Abstract
| Full Text
**

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 2𝑚=|𝑈|≤|𝑊|, we prove that 2𝑚 is a sharp upper bound of |𝑊| and construct an 𝑆-graph 𝐺(2𝑚,2𝑚) 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 𝑚≥2, the graph 𝐺(2𝑚,2𝑚) is the unique (up to isomorphism) bipartite diametrical graph of diameter 4 and partite sets of cardinalities 2𝑚 and 2𝑚, and hence in particular, for 𝑚=3, the graph 𝐺(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 𝑆-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 𝐺(2𝑚,2𝑚) form a matroid whose basis graph is the hypercube 𝑄𝑚. We prove that any 𝑆-graph of diameter 4 is bipartite self complementary, thus in particular 𝐺(2𝑚,2𝑚). Finally, we study some additional properties of 𝐺(2𝑚,2𝑚) concerning the order of its automorphism group, girth, domination number, and when being Eulerian.