Complete multipartite graphs of non-QE class

Nobuaki Obata


We derive a formula for the QE constant of a complete multipartite graph and determine the complete multipartite graphs of non-QE class, namely, those which do not admit quadratic embeddings in Euclidean spaces. Moreover, we prove that there are exactly four primary non-QE graphs among the complete multipartite graphs.


distance matrix, quadratic embedding, quadratic embedding constant (QEC), primary non-QE graph

Full Text:




A.Y. Alfakih, Euclidean Distance Matrices and Their Applications in Rigidity Theory, Springer, Cham, 2018.

M. Aouchiche and P. Hansen, Distance spectra of graphs: a survey, Linear Algebra Appl. 458 (2014), 301–386.

R. Balaji and R.B. Bapat, On Euclidean distance matrices, Linear Algebra Appl. 424 (2007), 108–117.

E.T. Baskoro and N. Obata, Determining finite connected graphs along the quadratic embedding constants of paths, Electron. J. Graph Theory Appl. 9 (2021), 539–560.

W. Irawan and K.A. Sugeng, Quadratic embedding constants of hairy cycle graphs, Journal of Physics: Conference Series 1722 (2021) 012046.

G. Jaklič and J. Modic, On Euclidean distance matrices of graphs, Electron. J. Linear Algebra 26 (2013), 574–589.

G. Jaklič and J. Modic, Euclidean graph distance matrices of generalizations of the star graph, Appl. Math. Comput. 230 (2014), 650–663.

Y.-L. Jin and X.D. Zhang, Complete multipartite graphs are determined by their distance spectra, Linear Algebra Appl. 448 (2014), 285–291.

H. Lin, Y. Hong, J. Wang, and J. Shub, On the distance spectrum of graphs, Linear Algebra Appl. 439 (2013), 1662–1669.

L. Liberti, G. Lavor, N. Maculan, and A. Mucherino, Euclidean distance geometry and applications, SIAM Rev. 56 (2014), 3–69.

R. Liu, J. Xue, and L. Guo. On the second largest distance eigenvalue of a graph, arXiv:1504.04225v1, 2015.

Z.Z. Lou, N. Obata and Q.X. Huang, Quadratic embedding constants of graph joins, Graphs and Combinatorics 38 (2022), 161.

B. McKay, All small connected graphs, (online 2022.06.10)

W. Młotkowski, Quadratic embedding constants of path graphs, Linear Algebra Appl. 644 (2022), 95–107.

W. Młotkowski and N. Obata, On quadratic embedding constants of star product graphs, Hokkaido Math. J. 49 (2020), 129–163.

N. Obata, Quadratic embedding constants of wheel graphs, Interdiscip. Inform. Sci. 23 (2017), 171–174.

N. Obata: Primary non-QE graphs on six vertices, Interdiscip. Inform. Sci. 29 (2023), 141–156.

N. Obata and A.Y. Zakiyyah, Distance matrices and quadratic embedding of graphs, Electronic J. Graph Theory Appl. 6 (2018), 37–60.

M. Purwaningsih and K.A. Sugeng, Quadratic embedding constants of squid graph and kite graph, Journal of Physics: Conference Series 1722 (2021) 012047.

I.J. Schoenberg, Remarks to Maurice Fréchet’s article “Sur la définition axiomatique d’une classe d’espace distanciś vectoriellement applicable sur l’espace de Hilbert”, Ann. of Math. 36 (1935), 724–732.

I.J. Schoenberg, Metric spaces and positive definite functions, Trans. Amer. Math. Soc. 44 (1938), 522–536.


  • There are currently no refbacks.

ISSN: 2338-2287

Creative Commons License
This work is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.

View EJGTA Stats