Determining finite connected graphs along the quadratic embedding constants of paths
| Main Authors: | Baskoro, Edy Tri; Combinatorial Mathematics Research Group Faculty of Mathematics and Natural Sciences Institut Teknologi Bandung Indonesia, Obata, Nobuaki; Graduate School of Information Sciences Tohoku University Sendai 980-8579 Japan |
|---|---|
| Other Authors: | JSPS Open Partnership Joint Research Project |
| Format: | Article info application/pdf eJournal |
| Bahasa: | eng |
| Terbitan: |
GTA Research Group, Univ. Newcastle, Indonesian Combinatorics Society and ITB
, 2021
|
| Subjects: | |
| Online Access: |
https://www.ejgta.org/index.php/ejgta/article/view/1401 https://www.ejgta.org/index.php/ejgta/article/view/1401/pdf_198 |
Daftar Isi:
- The QE constant of a finite connected graph G, denoted by QEC(G), is by definition the maximum of the quadratic function associated to the distance matrix on a certain sphere of codimension two. We prove that the QE constants of paths Pn form a strictly increasing sequence converging to −1/2. Then we formulate the problem of determining all the graphs G satisfying QEC(Pn)≤QEC(G)<QEC(Pn + 1). The answer is given for n = 2 and n = 3 by exploiting forbidden subgraphs for QEC(G)< − 1/2 and the explicit QE constants of star products of the complete graphs.