Bipartite Diametrical Graphs of Diameter 4 and Extreme Orders. (10th December 2007)

• Record Type: Journal Article
• Authors: Al-Addasi, Salah; Al-Ezeh, Hasan
• Other Names: Johnson Peter Academic Editor.
• Is Part Of: International journal of mathematics and mathematical sciences. Volume 2008(2008)
• Publication Date: 2007-12-10
• Subjects: Mathematics -- Periodicals; 510.5
• DOI: 10.1155/2008/468583
• Languages: English
• ISSNs: 0161-1712

Abstract

Abstract : We provide a process to extend any bipartite diametrical graph of diameter 4 to anS -graph of the same diameter and partite sets. For a bipartite diametrical graph of diameter 4 and partite setsU andW, where2 m = | U | ≤ | W |, we prove that2 m is a sharp upper bound of| W | and construct anS -graphG ( 2 m, 2 m ) in which this upper bound is attained, this graph can be viewed as a generalization of the Rhombic Dodecahedron. Then we show that for anym ≥ 2, the graphG ( 2 m, 2 m ) is the unique (up to isomorphism) bipartite diametrical graph of diameter 4 and partite sets of cardinalities2 m and2 m, and hence in particular, form = 3, the graphG ( 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 ofS -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 ofG ( 2 m, 2 m ) form a matroid whose basis graph is the hypercubeQ m . We prove that anyS -graph of diameter 4 is bipartite self complementary, thus in particularG ( 2 m, 2 m ) . Finally, we study some additional properties ofG ( 2 m, 2 m ) concerning the order of its automorphism group, girth, domination number, and when being Eulerian.