Bipartite diametrical graphs of diameter 4 and extreme orders
type: Item
instance of: scholarly article
title: Bipartite diametrical graphs of diameter 4 and extreme orders
zbMATH Open document ID: 1161.05316
DOI: 10.1155/2008/468583
author: S. Al-Addasi
author: H. Al-Ezeh
published in: International Journal of Mathematics and Mathematical Sciences
publication date: 2008-08-19T00:00:00Z
full work available at URL: https://eudml.org/doc/55353
review text: Summary: 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| \leq |W|\), we prove that \(2^{m}\) is a sharp upper bound of \(|W|\) and construct an \(S\)-graph \(G(2m,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 any \(m \geq 2\), the graph \(G(2m,2^{m})\) is the unique (up to isomorphism) bipartite diametrical graph of diameter 4 and partite sets of cardinalities \(2m\) and \(2^{m}\), 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,2^{m})\) form a matroid whose basis graph is the hypercube \(Q_{m}\). We prove that any \(S\)-graph of diameter 4 is bipartite self complementary, thus in particular \(G(2m,2^{m})\). Finally, we study some additional properties of \(G(2m,2^{m})\) concerning the order of its automorphism group, girth, domination number, and when being Eulerian.
Mathematics Subject Classification ID: 05C12
Mathematics Subject Classification ID: 05C75
Mathematics Subject Classification ID: 05C25
Mathematics Subject Classification ID: 05C35
Mathematics Subject Classification ID: 05C69
Mathematics Subject Classification ID: 05C45
zbMATH DE Number: 5313270
zbMATH Keywords: bipartite diametrical graph
zbMATH Keywords: S-graph
zbMATH Keywords: partite sets
zbMATH Keywords: rhombic dodecahedron
zbMATH Keywords: matroid
zbMATH Keywords: bipartite self complementary graph
MaRDI profile type: Publication
OpenAlex ID: W1999809183
Wikidata QID: Q58644774
cites work: Cross-cloning and antipodal graphs
cites work: Even graphs
cites work: On \(k\)-pairable graphs
cites work: n‐cubes and median graphs
cites work: Q3890733
cites work: Unique eccentric point graphs
cites work: Q4653767
cites work: Characterizing symmetric diametrical graphs of order 12 and diameter 4
cites work: Basis graphs of even delta-matroids
cites work: On the structure of the tight-span of a totally split-decomposable metric
cites work: r-partite self-complementary graphs-diameters
cites work: Quasi‐median graphs and algebras
description: scientific article; zbMATH DE number 5313270