A classification of graphs through quadratic embedding constants and clique graph insights

Document Type : Original paper

Authors

1 Combinatorial Mathematics Research Group, Faculty of Mathematics and Natural Sciences, Institut Teknologi Bandung, Jalan Ganesa 10 Bandung, Indonesia

2 Center for Data-driven Science and Artificial Intelligence, Tohoku University, Sendai 980-8576, Japan

Abstract

The quadratic embedding constant (QEC) of a graph $G$ is a new numeric invariant, which is defined in terms of the distance matrix and is denoted by $\mathrm{QEC}(G)$. By observing graph structure of the maximal cliques 
(clique graph), we show that a graph $G$ with $\mathrm{QEC}(G)<-1/2$ admits a ``cactus-like'' structure. We derive a formula for the quadratic embedding constant of a graph consisting of two maximal cliques. As an application we discuss characterization of graphs along the increasing sequence of $\mathrm{QEC}(P_d)$, where $P_d$ is the path on $d$ vertices. In particular, we determine graphs $G$ satisfying $\mathrm{QEC}(G)<\mathrm{QEC}(P_5)$.

Keywords

Main Subjects

References

[1] A.Y. Alfakih, Euclidean Distance Matrices and Their Applications in Rigidity Theory, Springer, Cham, 2018.
[2] M. Aouchiche and P. Hansen, Distance spectra of graphs: A survey, Linear Algebra Appl. 458 (2014), 301–386. https://doi.org/10.1016/j.laa.2014.06.010
[3] R. Balaji and R.B. Bapat, On euclidean distance matrices, Linear Algebra Appl. 424 (2007), no. 1, 108–117. https://doi.org/10.1016/j.laa.2006.05.013
[4] E.T. Baskoro and N. Obata, Determining finite connected graphs along the quadratic embedding constants of paths, Electron. J. Graph Theory Appl. 9 (2021), no. 2, 539–560.  https://dx.doi.org/10.5614/ejgta.2021.9.2.23
[5] P.N. Choudhury and R. Nandi, Quadratic embedding constants of graphs: Bounds and distance spectra, Linear Algebra Appl. 680 (2024), 108–125.  https://doi.org/10.1016/j.laa.2023.09.024
[6] M.M. Deza, M. Laurent, and R. Weismantel, Geometry of Cuts and Metrics, Springer, Verlag Berlin, 1997.
[7] H. Guo and B. Zhou, Graphs for which the second largest distance eigenvalue is less than $\frac{-1}{2}$,  Discrete Math. 347 (2023), no. 9, 114082. https://doi.org/10.1016/j.disc.2024.114082
[8] F. Harary and G.E. Uhlenbeck, On the number of husimi trees: I, Proc. Nat. Acad. Sci. 39 (1953), no. 4, 315–322. https://doi.org/10.1073/pnas.39.4.315
[9] G. Indulal and I. Gutman, On the distance spectra of some graphs, Math. Commun. 13 (2008), 123–131.
[10] G. Indulal and I. Gutman, On euclidean distance matrices of graphs, Electron. J. Linear Algebra 26 (2013), 574–589.
[11] W. Irawan and K.A. Sugeng, Quadratic embedding constants of hairy cycle graphs, Journal of Physics: Conference Series, 1722 (2021), no. 1, Article ID: 012046.
[12] G. Jaklič and J. Modic, Euclidean graph distance matrices of generalizations of the star graph, Appl. Math. Comput. 230 (2014), 650–663.  https://doi.org/10.1016/j.amc.2013.12.158
[13] J.H. Koolen and S.V. Shpectorov, Distance-regular graphs the distance matrix of which has only one positive eigenvalue, European J. Combin. 15 (1994), no. 3, 269–275.  https://doi.org/10.1006/eujc.1994.1030
[14] L. Liberti, C. Lavor, N. Maculan, and A. Mucherino, Euclidean distance geometry and applications, SIAM Rev. 56 (2014), no. 1, 3–69.   https://doi.org/10.1137/120875909
[15] H. Lin, Y. Hong, J. Wang, and J. Shu, On the distance spectrum of graphs, Linear Algebra Appl. 439 (2013), no. 6, 1662–1669.  https://doi.org/10.1016/j.laa.2013.04.019
[16] Z. Lou, N. Obata, and Q. Huang, Quadratic embedding constants of graph joins, Graphs Combin. 38 (2022), no. 5, Article ID: 161.  https://doi.org/10.1007/s00373-022-02569-w
[17] W. Młotkowski, Quadratic embedding constants of path graphs, Linear Algebra Appl. 644 (2022), 95–107.  https://doi.org/10.1016/j.laa.2022.02.037
[18] W. Młotkowski and N. Obata, On quadratic embedding constants of star product graphs, Hokkaido Math. J. 49 (2020), no. 1, 129–163.  https://doi.org/10.14492/hokmj/1591085015
[19] N. Obata, Quadratic embedding constants of wheel graphs, Interdiscip. Inform. Sci. 23 (2017), no. 2, 171–174. https://doi.org/10.4036/iis.2017.S.02
[20] N. Obata, Complete multipartite graphs of non-QE class, Electronic J. Graph Theory Appl. 11 (2023), no. 2, 511–527. http://dx.doi.org/10.5614/ejgta.2023.11.2.14
[21] N. Obata, Primary non-QE graphs on six vertices, Interdiscip. Inform. Sci. 29 (2023), no. 2, 141–156. https://doi.org/10.4036/iis.2023.R.01
[22] N. Obata and A.Y. Zakiyyah, Distance matrices and quadratic embedding of graphs, Electronic J. Graph Theory Appl. 6 (2018), no. 1, 37–60.  http://dx.doi.org/10.5614/ejgta.2018.6.1.4
[23] M. Purwaningsih and K.A. Sugeng, Quadratic embedding constants of squid graph and kite graph, Journal of Physics: Conference Series, vol. 1722, IOP Publishing, 2021, p. Article ID: 012047.
[24] F.S. Roberts and J.H. Spencer, A characterization of clique graphs, J. Comb. Theory Ser. B. 10 (1971), no. 2, 102–108.
https://doi.org/10.1016/0095-8956(71)90070-0
[25] I.J. Schoenberg, Remarks to maurice frechet’s article“sur la definition axiomatique d’une classe d’espace distances vectoriellement applicable sur l’espace de hilbert, Ann. Math. 36 (1935), no. 3, 724–732.
[26] I.J. Schoenberg, Metric spaces and positive definite functions, Trans. Amer. Math. Soc. 44 (1938), no. 3, 522–536.
[27] J.L. Szwarcfiter, A Survey on Clique Graphs, in “Recent Advances in Algorithms and Combinatorics” (B.A. Reed and C.L. Sales, eds.), Springer New York, New York, NY, 2003, pp. 109–136.
Communications in Combinatorics and Optimization
Volume 11, Issue 1
March 2026
Pages 57-77

Files

Share

How to cite

Statistics