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 -