Embedding and the first Laplace eigenvalue of a finite graph

Takumi Gomyou (), Toshimasa Kobayashi (), Takefumi Kondo () and Shin Nayatani ()
Additional contact information
Takumi Gomyou: Osaka University
Toshimasa Kobayashi: Setsunan University
Takefumi Kondo: Kagoshima University
Shin Nayatani: Nagoya University

Journal of Combinatorial Optimization, 2024, vol. 48, issue 1, No 1, 24 pages

Abstract: Abstract Göring–Helmberg–Wappler introduced optimization problems regarding embeddings of a graph into a Euclidean space and the first nonzero eigenvalue of the Laplacian of a graph, which are dual to each other in the framework of semidefinite programming. In this paper, we introduce a new graph-embedding optimization problem, and discuss its relation to Göring–Helmberg–Wappler’s problems. We also identify the dual problem to our embedding optimization problem. We solve the optimization problems for distance-regular graphs and the one-skeleton graphs of the $$\textrm{C}_{60}$$ C 60 fullerene and some other Archimedian solids.

Keywords: Embedding; Laplacian; Eigenvalue; Duality; Distance-regular; Archimedean solid (search for similar items in EconPapers)
Date: 2024
References: View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10878-024-01191-1 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jcomop:v:48:y:2024:i:1:d:10.1007_s10878-024-01191-1

Ordering information: This journal article can be ordered from
https://www.springer.com/journal/10878

DOI: 10.1007/s10878-024-01191-1

Access Statistics for this article

Journal of Combinatorial Optimization is currently edited by Thai, My T.

More articles in Journal of Combinatorial Optimization from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().