Saved in:
| Main Author: | |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2501.15716 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866913666824142848 |
|---|---|
| author | Hasunuma, Toru |
| author_facet | Hasunuma, Toru |
| contents | Motivated by very large-scale communication networks, we newly introduce exponentiation of graphs. Using the exponential operation on graphs, we can construct various graphs of multi-exponential order with logarithmic diameter. We show that every connected exponential graph is maximally connected. For exponential graphs, we also present a necessary and sufficient condition to be super edge-connected and sufficient conditions to be Hamiltonian and to have edge-disjoint Hamiltonian cycles and completely independent spanning trees. Applying our results to previously known networks, we have maximally connected and super edge-connected Hamiltonian graphs of doubly exponential order with logarithmic diameter. We furthermore define iterated exponential graphs which may be of not only practical but also theoretical interest. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2501_15716 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Exponentiation of Graphs Hasunuma, Toru Combinatorics Motivated by very large-scale communication networks, we newly introduce exponentiation of graphs. Using the exponential operation on graphs, we can construct various graphs of multi-exponential order with logarithmic diameter. We show that every connected exponential graph is maximally connected. For exponential graphs, we also present a necessary and sufficient condition to be super edge-connected and sufficient conditions to be Hamiltonian and to have edge-disjoint Hamiltonian cycles and completely independent spanning trees. Applying our results to previously known networks, we have maximally connected and super edge-connected Hamiltonian graphs of doubly exponential order with logarithmic diameter. We furthermore define iterated exponential graphs which may be of not only practical but also theoretical interest. |
| title | Exponentiation of Graphs |
| topic | Combinatorics |
| url | https://arxiv.org/abs/2501.15716 |