Design and Analysis of a Symmetric Log Star Graph with a Smaller Network Cost Than Star Graphs
Graphs are used as models to solve problems in fields such as mathematics, computer science, physics, and chemistry. In particular, torus, hypercube, and star graphs are popular when modeling the connection structure of processors in parallel computing because they are symmetric and have a low netwo...
| Main Authors: | , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
MDPI AG
2021-04-01
|
| Series: | Electronics |
| Subjects: | |
| Online Access: | https://www.mdpi.com/2079-9292/10/8/981 |
| _version_ | 1797537027002990592 |
|---|---|
| author | Jung-Hyun Seo Hyeong-Ok Lee |
| author_facet | Jung-Hyun Seo Hyeong-Ok Lee |
| author_sort | Jung-Hyun Seo |
| collection | DOAJ |
| description | Graphs are used as models to solve problems in fields such as mathematics, computer science, physics, and chemistry. In particular, torus, hypercube, and star graphs are popular when modeling the connection structure of processors in parallel computing because they are symmetric and have a low network cost. Whereas a hypercube has a substantially smaller diameter than a torus, star graphs have been presented as an alternative to hypercubes because of their lower network cost. We propose a novel log star (LS) that is symmetric and has a lower network cost than a star graph. The LS is an undirected, recursive, and regular graph. In LS<i><sub>n</sub></i>, the number of nodes is <i>n</i>! while the degree is 2log<sub>2</sub><i>n</i> − 1 and the diameter is 0.5<i>n</i>(log<sub>2</sub><i>n</i>)<sup>2</sup> + 0.75<i>n</i>log<sub>2</sub><i>n</i>. In this study, we analyze the basic topological properties of LS. We prove that LS<i><sub>n</sub></i> is a symmetrical connected graph and analyzed its subgraph characteristics. Then, we propose a routing algorithm and derive the diameter and network cost. Finally, the network costs of the LS and star graph-like networks are compared. |
| first_indexed | 2024-03-10T12:09:16Z |
| format | Article |
| id | doaj.art-074ab7a6157f4001929919cf0641c30e |
| institution | Directory Open Access Journal |
| issn | 2079-9292 |
| language | English |
| last_indexed | 2024-03-10T12:09:16Z |
| publishDate | 2021-04-01 |
| publisher | MDPI AG |
| record_format | Article |
| series | Electronics |
| spelling | doaj.art-074ab7a6157f4001929919cf0641c30e2023-11-21T16:18:47ZengMDPI AGElectronics2079-92922021-04-0110898110.3390/electronics10080981Design and Analysis of a Symmetric Log Star Graph with a Smaller Network Cost Than Star GraphsJung-Hyun Seo0Hyeong-Ok Lee1Department of Multimedia Engineering, National University of Chonnam, Yeosu 59626, KoreaDepartment of Computer Education, National University of Sunchon, Sunchon 315, KoreaGraphs are used as models to solve problems in fields such as mathematics, computer science, physics, and chemistry. In particular, torus, hypercube, and star graphs are popular when modeling the connection structure of processors in parallel computing because they are symmetric and have a low network cost. Whereas a hypercube has a substantially smaller diameter than a torus, star graphs have been presented as an alternative to hypercubes because of their lower network cost. We propose a novel log star (LS) that is symmetric and has a lower network cost than a star graph. The LS is an undirected, recursive, and regular graph. In LS<i><sub>n</sub></i>, the number of nodes is <i>n</i>! while the degree is 2log<sub>2</sub><i>n</i> − 1 and the diameter is 0.5<i>n</i>(log<sub>2</sub><i>n</i>)<sup>2</sup> + 0.75<i>n</i>log<sub>2</sub><i>n</i>. In this study, we analyze the basic topological properties of LS. We prove that LS<i><sub>n</sub></i> is a symmetrical connected graph and analyzed its subgraph characteristics. Then, we propose a routing algorithm and derive the diameter and network cost. Finally, the network costs of the LS and star graph-like networks are compared.https://www.mdpi.com/2079-9292/10/8/981star graphsnetwork costrouting algorithmlog starsymmetric |
| spellingShingle | Jung-Hyun Seo Hyeong-Ok Lee Design and Analysis of a Symmetric Log Star Graph with a Smaller Network Cost Than Star Graphs Electronics star graphs network cost routing algorithm log star symmetric |
| title | Design and Analysis of a Symmetric Log Star Graph with a Smaller Network Cost Than Star Graphs |
| title_full | Design and Analysis of a Symmetric Log Star Graph with a Smaller Network Cost Than Star Graphs |
| title_fullStr | Design and Analysis of a Symmetric Log Star Graph with a Smaller Network Cost Than Star Graphs |
| title_full_unstemmed | Design and Analysis of a Symmetric Log Star Graph with a Smaller Network Cost Than Star Graphs |
| title_short | Design and Analysis of a Symmetric Log Star Graph with a Smaller Network Cost Than Star Graphs |
| title_sort | design and analysis of a symmetric log star graph with a smaller network cost than star graphs |
| topic | star graphs network cost routing algorithm log star symmetric |
| url | https://www.mdpi.com/2079-9292/10/8/981 |
| work_keys_str_mv | AT junghyunseo designandanalysisofasymmetriclogstargraphwithasmallernetworkcostthanstargraphs AT hyeongoklee designandanalysisofasymmetriclogstargraphwithasmallernetworkcostthanstargraphs |