Determining finite connected graphs along the quadratic embedding constants of paths

Edy Tri Baskoro (Combinatorial Mathematics Research Group Faculty of Mathematics and Natural Sciences Institut Teknologi Bandung Indonesia)
Nobuaki Obata (Graduate School of Information Sciences Tohoku University Sendai 980-8579 Japan)

Electronic Journal of Graph Theory and Applications (EJGTA)
Vol 9, No 2 (2021): Electronic Journal of Graph Theory and Applications

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.