Bipartite Diametrical Graphs of Diameter 4 and Extreme Orders

Salah Al-Addasi and Hasan Al-Ezeh

International Journal of Mathematics and Mathematical Sciences, 2008, vol. 2008, 1-11

Abstract:

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.

Date: 2008
References: View complete reference list from CitEc
Citations:

Downloads: (external link)
http://downloads.hindawi.com/journals/IJMMS/2008/468583.pdf (application/pdf)
http://downloads.hindawi.com/journals/IJMMS/2008/468583.xml (text/xml)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:hin:jijmms:468583

DOI: 10.1155/2008/468583

Access Statistics for this article

More articles in International Journal of Mathematics and Mathematical Sciences from Hindawi
Bibliographic data for series maintained by Mohamed Abdelhakeem ().