Ferdi
2025
Read Ferdi (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2512-17258.txt.
Introduction
Ferdi, Edy Tri Baskoro, Nobuaki Obata, and Aditya Purwa Santika compute a key number for a family of graphs built by gluing two graphs together. The number, called the quadratic embedding constant, comes from the graph's distance table and measures how the graph can sit inside a sphere-like space. The glued shape, a corona graph, hangs a copy of one graph off each point of another.
Their formula finds the constant of the glued graph from the constant of the base graph alone, under stated spectral conditions on the attached graph. When the attached graph is regular and its smallest adjacency value is minus 2, the formula becomes fully explicit. Such closed forms save heavy computation for large network shapes.
Catalog record
| YEAR | 2025 |
|---|---|
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 64 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2512-17258
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Ferdi Abstract Quadratic Embedding Constants of Corona Graphs Edy Tri Baskoro Combinatorial Mathematics Research Group Faculty of Mathematics and Natural Sciences Institut Teknologi Bandung, Indonesia and Center for Research Collaboration on Graph Theory and Combinatorics, Indonesia [email protected] Nobuaki Obata Center for Data-driven Science and Artificial Intelligence Tohoku University Sendai 980-8576 Japan [email protected] Aditya Purwa Santika Combinatorial Mathematics Research Group Faculty of Mathematics and Natural Sciences Institut Teknologi Bandung, Indonesia [email protected] Abstract The quadratic embedding constant (QEC) of a connected graph is defined to be the maximum of the quadratic function associated with its distance matrix on a certain unit sphere of codimension two. In this paper we derive a formula for the QEC of a corona graph G\odot H . It is shown that \mathrm{QEC}(G\odot H)=\psi_{H*}^{-1}(\mathrm{QEC}(G)) holds under some spectral assumptions on H , where \psi_{H*}^{-1} is the inverse function of the most right branch of the analytic function \psi_{H} defined by means of the main eigenvalues of the adjacency matrix of H . Moreover, if H is a regular graph of which the adjacency matrix has the smallest eigenvalue -2 , then the formula is written down explicitly. Keywords quadratic embedding constant, corona graph, main eigenvalue, distance matrix, distance spectra, Euclidean distance geometry. MSC primary:05C50. secondary:05C12, 05C76, 15A63, 51K05. Acknowledgements This work was supported by the International Research Collaboration Program of Institut Teknologi Bandung, the PMDSU Program funded by the Ministry of Higher Education, Science and Technology, Indonesia, and the JSPS Grant-in-Aid for Scientific Research 23K03126, Japan, 1 Introduction Let G=(V,E) be a finite connected graph with |V|=n\geq 2 and D=[d(x,y)]_{x,y\in V} the distance matrix of G , where d(x,y) stands for the standard graph distance between two vertices x,y\in V . A quadratic embedding of G into a Euclidean space \mathcal{H} is a map \varphi:V\to\mathcal{H} such that \|\varphi(x)-\varphi(y)\|^{2}=d(x,y),\quad x,y\in V. In general, a given graph does not necessarily admit a quadratic embedding; when it does, it is said to be of QE class . In the terminology of Euclidean distance geometry, a graph is of QE class if and only if the distance matrix D is a Euclidean distance matrix [ 1 , 2 , 15 , 16 , 17 ] . It is known from the celebrated Schoenberg’s theorem [ 28 , 29 , 30 , 31 ] that a connected graph G is of QE class if and only if its distance matrix D is conditionally negative definite. To identify this condition, it is natural to consider the quadratic embedding constant (QEC) defined by \mathrm{QEC}(G)=\max\{\langle f,Df\rangle\,;\,f\in C(V),\,\langle f,f\rangle=1,\,\langle{\bm{1}},f\rangle=0\}, where C(V) is the space of real column vectors f=[f_{x}]_{x\in V} with the canonical inner product \langle\cdot,\cdot\rangle , and \bm{1}\in C(V) is the column vector whose entries are all one. In fact, a connected graph G is of QE class if and only if \mathrm{QEC}(G)\leq 0 . Since the QEC was first introduced by Obata and Zakiyyah [ 26 ] , interest has grown in characterization and classification of graphs using the QEC as a new numeric invariant of connected graphs. The QECs of graphs of some particular classes are determined explicitly, including complete graphs and cycles [ 26 ] , paths [ 19 ] , complete multipartite graphs [ 25 ] , fan graphs [ 21 , 22 ] , wheels [ 23 ] , squid and kite graphs [ 27 ] , hairy cycle graphs [ 14 ] , double star graphs [ 8 ] . It is also interesting to obtain explicit formulas and estimates of QEC along with various graph operations, for example, the Cartesian product [ 26 ] , star product [ 4 , 20 , 26 ] , lexicographic product [ 18 ] , graph join [ 18 , 21 ] , and comb graphs (cluster graphs) [ 8 ] . Moreover, an effort was initiated to characterize particular block graphs [ 5 ] and to construct primary non-QE graphs [ 24 , 25 ] . In this paper, along the line of research on QEC in relation to various graph operations, we focus on the corona of two graphs G and H , denoted by G\odot H , for definition see Section 2.1 . Since the corona graph was first discussed by Frucht and Harary [ 12 ] in relation to automorphism groups, it has been actively studied as a benchmark class of graphs along with chemical graph theory, graph coloring, graph labeling, network models, and so on. For relevant spectral results we refer to [ 3 ] for the adjacency spectra and [ 13 ] for the distance spectra. The main purpose of this paper is to derive a formula for \mathrm{QEC}(G\odot H) , where G is a connected graph on two or more vertices, H an arbitrary graph and G\odot H their corona graph. To describe \mathrm{QEC}(G\odot H) we need a special analytic function associated with H . Let A_{H} be the adjacency matrix of H , \mathrm{ev}(A_{H}) the set of distinct eigenvalues of A_{H} , and \mathrm{ev}_{M}(A_{H}) the subset of main ones. Let \omega_{H}(\lambda) be the unique real analytic function with maximal domain satisfying \omega_{H}(\lambda)=1+\lambda\langle\mathbf{1},(A_{H}+2+\lambda)^{-1}\mathbf{1}\rangle. (1.1) It is shown that \omega_{H}(\lambda) has a simple pole at \lambda=-\alpha-2 for each \alpha\in\mathrm{ev}_{\mathrm{M}}(A_{H})\backslash\{-2\} and, is analytic except those poles. Moreover, \omega_{H}(\lambda) has k_{H}=|\mathrm{ev}_{\mathrm{M}}(A_{H})\backslash\{-2\}|\geq 1 distinct real zeroes. We then introduce a real analytic function \psi_{H}(\lambda) with the maximal domain uniquely specified by \psi_{H}(\lambda)=\frac{\lambda}{\omega_{H}(\lambda)}\,. (1.2) It is shown that \psi_{H}(\lambda) has a simple pole at each zero of \omega_{H}(\lambda) , and is analytic except those poles. Let \lambda_{*} be the largest zero of \omega_{H}(\lambda) . Then \psi_{H*}=\psi_{H}\!\restriction_{(\lambda_{*},+\infty)} becomes an increasing function varying from -\infty to +\infty . Thus, we may define the inverse function \lambda=\psi_{H*}^{-1}(\lambda^{\prime}) for \lambda^{\prime}\in\mathbb{R} , namely, \lambda is the largest solution to the equation \psi_{H}(\lambda)=\lambda^{\prime} . With those notations we will prove that the formula \mathrm{QEC}(G\odot H)=\psi_{H*}^{-1}(\mathrm{QEC}(G)) (1.3) holds under some spectral assumptions, for the precise statements see Sections 4.3 and 4.4 . It is also interesting to note that if H is a regular graph with \min\mathrm{ev}(A_{H})=-2 , formula ( 1.3 ) holds for \mathrm{QEC}(G)>0 , and \mathrm{QEC}(G\odot H)=0 for any G with \mathrm{QEC}(G)\leq 0 . We thus expect further profound relation to the graphs H with \min\mathrm{ev}(A_{H})=-2 , which have been extensively studied so far, see e.g., the celebrated books [ 6 , 10 , 11 ] . The paper is organized as follows. In Section 2 we obtain a useful expression of the distance matrix of a corona graph and derive the set of basic equations from which \mathrm{QEC}(G\odot H) is determined. In Section 3 we develop a general theory on two key functions in ( 1.1 ) and ( 1.2 ). In Section 4 we obtain an intermediate expression for \mathrm{QEC}(G\odot H) as the greater or equal of \psi_{H*}^{-1}(\mathrm{QEC}(G)) and a certain constant \gamma_{3} determined by \mathrm{ev}(A_{H}) , see Proposition 4.7 ; and then specify several spectral conditions under which formula ( 1.3 ) holds, see Theorems 4.9 – 4.11 . Moreover, if H is a regular graph the formula becomes simpler, see Theorem 4.14 . For a regular graph H with \min\mathrm{ev}(A_{H})=-2 , that formula ( 1.3 ) holds for \mathrm{QEC}(G)>0 and \mathrm{QEC}(G\odot H)=0 otherwise, see Theorem 4.17 . In Section 5 we present