Bipartite Diametrical Graphs of Diameter 4 and Extreme Orders
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𝑚...
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Wiley
2008-01-01
|
| Series: | International Journal of Mathematics and Mathematical Sciences |
| Online Access: | http://dx.doi.org/10.1155/2008/468583 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1832566728488386560 |
|---|---|
| author | Salah Al-Addasi Hasan Al-Ezeh |
| author_facet | Salah Al-Addasi Hasan Al-Ezeh |
| author_sort | Salah Al-Addasi |
| collection | DOAJ |
| description | 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. |
| format | Article |
| id | doaj-art-007181f3bf144b82875a26afa9c5cd6a |
| institution | Kabale University |
| issn | 0161-1712 1687-0425 |
| language | English |
| publishDate | 2008-01-01 |
| publisher | Wiley |
| record_format | Article |
| series | International Journal of Mathematics and Mathematical Sciences |
| spelling | doaj-art-007181f3bf144b82875a26afa9c5cd6a2025-02-03T01:03:22ZengWileyInternational Journal of Mathematics and Mathematical Sciences0161-17121687-04252008-01-01200810.1155/2008/468583468583Bipartite Diametrical Graphs of Diameter 4 and Extreme OrdersSalah Al-Addasi0Hasan Al-Ezeh1Mathematics Department, Faculty of Science, Hashemite University, Zarqa 150459, JordanMathematics Department, Faculty of Science, University of Jordan, Amman 11942, JordanWe 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.http://dx.doi.org/10.1155/2008/468583 |
| spellingShingle | Salah Al-Addasi Hasan Al-Ezeh Bipartite Diametrical Graphs of Diameter 4 and Extreme Orders International Journal of Mathematics and Mathematical Sciences |
| title | Bipartite Diametrical Graphs of Diameter 4 and Extreme Orders |
| title_full | Bipartite Diametrical Graphs of Diameter 4 and Extreme Orders |
| title_fullStr | Bipartite Diametrical Graphs of Diameter 4 and Extreme Orders |
| title_full_unstemmed | Bipartite Diametrical Graphs of Diameter 4 and Extreme Orders |
| title_short | Bipartite Diametrical Graphs of Diameter 4 and Extreme Orders |
| title_sort | bipartite diametrical graphs of diameter 4 and extreme orders |
| url | http://dx.doi.org/10.1155/2008/468583 |
| work_keys_str_mv | AT salahaladdasi bipartitediametricalgraphsofdiameter4andextremeorders AT hasanalezeh bipartitediametricalgraphsofdiameter4andextremeorders |