TY - JOUR

T1 - Optimal Embedding of Graphs with Nonconcurrent Longest Paths in Archimedean Tessellations

AU - Nadeem, Muhammad Faisal

AU - Shabbir, Ayesha

AU - Imran, Muhammad

N1 - Publisher Copyright:
Copyright © 2023 Muhammad Faisal Nadeem et al.

PY - 2023

Y1 - 2023

N2 - Optimal graph embeddings represent graphs in a lower dimensional space in a way that preserves the structure and properties of the original graph. These techniques have wide applications in fields such as machine learning, data mining, and network analysis. Do we have small (if possible minimal) k -connected graphs with the property that for any j vertices there is a longest path avoiding all of them? This question of Zamfirescu (1972) was the first variant of Gallai’s question (1966): Do all longest paths in a connected graph share a common vertex? Several good examples answering Zamfirescu’s question are known. In 2001, he asked to investigate the family of geometrical lattices with respect to this property. In 2017, Chang and Yuan proved the existence of such graphs in Archimedean tiling. Here, we prove that the graphs presented by Chang and Yuan are not optimal by constructing such graphs of sufficiently smaller orders. The problem of finding nonconcurrent longest paths in Archimedean tessellations refers to finding paths in a lattice such that the paths do not overlap or intersect with each other and are as long as possible. The complexity of embedding graph is still unknown. This problem can be challenging because it requires finding paths that are both long and do not intersect, which can be difficult due to the constraints of the lattice structure.

AB - Optimal graph embeddings represent graphs in a lower dimensional space in a way that preserves the structure and properties of the original graph. These techniques have wide applications in fields such as machine learning, data mining, and network analysis. Do we have small (if possible minimal) k -connected graphs with the property that for any j vertices there is a longest path avoiding all of them? This question of Zamfirescu (1972) was the first variant of Gallai’s question (1966): Do all longest paths in a connected graph share a common vertex? Several good examples answering Zamfirescu’s question are known. In 2001, he asked to investigate the family of geometrical lattices with respect to this property. In 2017, Chang and Yuan proved the existence of such graphs in Archimedean tiling. Here, we prove that the graphs presented by Chang and Yuan are not optimal by constructing such graphs of sufficiently smaller orders. The problem of finding nonconcurrent longest paths in Archimedean tessellations refers to finding paths in a lattice such that the paths do not overlap or intersect with each other and are as long as possible. The complexity of embedding graph is still unknown. This problem can be challenging because it requires finding paths that are both long and do not intersect, which can be difficult due to the constraints of the lattice structure.

UR - http://www.scopus.com/inward/record.url?scp=85165341750&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85165341750&partnerID=8YFLogxK

U2 - 10.1155/2023/3919389

DO - 10.1155/2023/3919389

M3 - Article

AN - SCOPUS:85165341750

SN - 1076-2787

VL - 2023

JO - Complexity

JF - Complexity

M1 - 3919389

ER -