آمار
| تعداد نشریات | 6 |
| تعداد شمارهها | 118 |
| تعداد مقالات | 1,482 |
| تعداد مشاهده مقاله | 1,594,698 |
| تعداد دریافت فایل اصل مقاله | 1,491,316 |
A classification of graphs through quadratic embedding constants and clique graph insights | ||
| Communications in Combinatorics and Optimization | ||
| مقاله 5، دوره 11، شماره 1، خرداد 2026، صفحه 57-77 اصل مقاله (535.54 K) | ||
| نوع مقاله: Original paper | ||
| شناسه دیجیتال (DOI): 10.22049/cco.2024.29159.1869 | ||
| نویسندگان | ||
| Edy Tri Baskoro1؛ Nobuaki Obata* 2 | ||
| 1Combinatorial Mathematics Research Group, Faculty of Mathematics and Natural Sciences, Institut Teknologi Bandung, Jalan Ganesa 10 Bandung, Indonesia | ||
| 2Center for Data-driven Science and Artificial Intelligence, Tohoku University, Sendai 980-8576, Japan | ||
| چکیده | ||
| 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)$. | ||
| کلیدواژهها | ||
| cactus-like graph؛ clique graph؛ distance matrix؛ quadratic embedding constant | ||
| مراجع | ||
|
[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. | ||
|
آمار تعداد مشاهده مقاله: 334 تعداد دریافت فایل اصل مقاله: 709 |
||