betaFeedback

WorksMathematics

Quadratic Embedding Constants of Block Graphs and Characterization of Cactus-like Graphs

Abstract

A (finite or infinite) connected graph is called cactus-like if every pair of distinct maximal cliques has at most one vertex in common and its clique graph is a tree. Equivalently, a cactus-like graph is a block graph whose clique graph is a tree. We prove that a finite connected graph GG with at least two vertices is cactus-like if and only if its quadratic embedding constant satisfies QEC(G)<−1/2\mathrm{QEC}(G)<-1/2. Moreover, we establish upper and lower bounds for QEC(G)\mathrm{QEC}(G) in terms of the clique degree of a block graph GG. For the proofs, we develop a method for constructing a conditionally negative definite kernel on a block graph by concatenating local kernels along geodesics in the block graph. Concrete examples include free products of complete graphs and trees.

Introduction

For a (finite or infinite) connected graph G=(V,E)G = (V, E) with ∣V∣≥2|V| \ge2 the quadratic embedding constant (QEC for short), denoted by QEC⁡(G)\operatorname{QEC}(G), is defined to be the conditional supremum of the canonical quadratic function:

⟨f,Df⟩=∑x,y∈VdG(x,y)f(x)f(y),f∈C0(V),\langle f, Df\rangle= \sum_{x,y \in V} d_G(x,y)f(x)f(y), \qquad f \in C_0(V),

associated with the distance matrix D=[dG(x,y)]D = [d_G(x,y)] of GG subject to

⟨f,f⟩=1,⟨1,f⟩=0,f∈C0(V),\langle f,f\rangle= 1,\qquad\langle\mathbf{1},f\rangle= 0,\qquad f \in C_0(V),

where C0(V)C_0(V) is the space of real column vectors f=[f(x)]x∈Vf = [f(x)]_{x\in V} with finite supports, 1∈C(V)\mathbf{1} \in C(V) is the all-one column vector, and ⟨⋅,⋅⟩\langle\cdot,\cdot\rangle the canonical inner product. If GG is finite, the conditional supremum is attained at some f∈C(V)=C0(V)f \in C(V) = C_0(V) so that we may write

QEC⁡(G)=max⁡{⟨f,Df⟩; f∈C(V), ⟨f,f⟩=1, ⟨1,f⟩=0}.(1)\operatorname{QEC}(G) = \max\{\langle f,Df\rangle;\ f\in C(V),\ \langle f,f\rangle= 1,\ \langle\mathbf{1},f\rangle= 0\}. \tag*{(1)}

The QEC becomes a numeric invariant of connected graphs on two or more vertices, and takes values in [−1,+∞)[-1,+\infty).

Since the QEC was introduced in [35], research interest in it has steadily increased, with most studies focusing on finite graphs; see [34] for a comprehensive survey of recent results. Concrete values of QEC are known for some special classes of graphs, e.g., paths [25], fan graphs [27, 28], theta graphs [29, 42], wheels [31] and others [17, 37]. Formulas and estimates for QEC under various graph operations have also been investigated, e.g., for cluster graphs [10], corona graphs [13], graph joins [21], star products [26], lexicographic products [30], and so on. The investigation of graphs with a positive QEC has only recently begun [29, 32, 33]. The classification of graphs in terms of QEC remains a central open problem, though progress has been limited so far, see [4, 5]. In this paper we present a result that is expected to constitute an important step toward this goal.

The most fundamental fact that motivated the introduction of the QEC comes from the famous works of Schoenberg [40, 41]. Let G=(V,E)G = (V,E) be a (finite or infinite) connected graph and H\mathcal{H} a Hilbert space. A map φ:V→H\varphi: V \to\mathcal{H} is called a quadratic embedding of GG if

∥φ(x)−φ(y)∥2=dG(x,y),x,y∈V,\lVert\varphi(x)-\varphi(y)\rVert^2 = d_G(x,y),\qquad x,y\in V,

where ∥⋅∥\lVert\cdot\rVert stands for the norm of H\mathcal{H}. The concept of quadratic embedding has been developed into a central one along with the Euclidean distance geometry [1, 3, 18, 19, 20]. In our terminology we recall the following

Theorem 1.1 (Schoenberg). For a (finite or infinite) connected graph G=(V,E)G = (V,E) with ∣V∣≥2|V| \ge2 the following three conditions are equivalent:

  1. GG admits a quadratic embedding;

  2. the distance matrix DD of GG is conditionally negative definite, i.e., ⟨f,Df⟩≤0\langle f,Df\rangle\le0 for any f∈C0(V)f \in C_0(V) with ⟨1,f⟩=0\langle\mathbf{1},f\rangle= 0;

  3. QEC⁡(G)≤0\operatorname{QEC}(G) \le0.

The essential point lies in the equivalence (i) ⇔\Leftrightarrow (ii), which was first proved in the seminal works of Schoenberg [40, 41], while the equivalence (ii) ⇔\Leftrightarrow (iii) is verified easily from the definition of the QEC. As a result, the QEC allows us to determine numerically whether a connected graph admits a quadratic embedding. In this context, we will determine the class of graphs with QEC⁡(G)<−1/2\operatorname{QEC}(G) < -1/2, which represents the first non-trivial achievement after Schoenberg’s result (Theorem 1.1). We will prove the following

Theorem 1.2. Let G=(V,E)G = (V,E) be a finite connected graph with ∣V∣≥2|V| \ge2. Then the following conditions are equivalent:

(i) GG is cactus-like, that is, every pair of distinct maximal cliques has at most one vertex in common and the clique graph Γ(G)\Gamma(G) is a tree;

(ii) GG is a block graph whose clique graph Γ(G)\Gamma(G) is a tree;

(iii) QEC⁡(G)<−1/2\operatorname{QEC}(G) < -1/2.

A cactus-like graph was introduced in the recent paper [5], where the implication (iii) ⇒\Rightarrow (i) was proved. The main contribution of this paper is the converse (i) ⇒\Rightarrow (iii), which has been left open. Meanwhile, the equivalence (i) ⇔\Leftrightarrow (ii), which can be verified directly by definition, provides a clear structural characterization of cactus-like graphs. To gain an intuitive understanding of a cactus-like graph, an example is given in Figure 1.

Figure 1. Cactus-like graph GG and its clique graph Γ(G)\Gamma(G)

In the proof of the implication (i) ⇒\Rightarrow (iii), two results play a key role. One is a generalization of a result on the length function of trees or of free product groups studied within harmonic analysis [22, 23, 24, 44]. The other is a technical estimate of QEC of star products obtained in [4]. Thus, our study of QEC of block graphs led us to a link of harmonic analysis on free products. Moreover, determining the infinite connected graphs that satisfy QEC⁡(G)<−1/2\operatorname{QEC}(G) < -1/2 is an interesting open question and the subject of ongoing research.

This paper is organized as follows. In § 2 we recall some notions and notations of graphs in relation to QEC, and assemble some known results necessary for our goal. In § 3 we describe some properties of block graphs and introduce cactus-like graphs in this context. In particular, we obtain equivalent conditions for a graph to be cactus-like (Proposition 3.14), from which we see that two conditions (i) and (ii) in Theorem 1.2 are equivalent. In § 4 we derive upper and lower bounds for QEC of a block graph and complete the proof of Theorem 1.2. The upper bound of QEC of a finite block graph with two or more maximal cliques is also noteworthy (Theorem 4.4). In § 5 we prove the key result on conditionally negative definite matrices on a block graph (Theorem 4.1), which plays an essential role in the proof of the main result. The proof proceeds by constructing a conditionally negative definite kernel by concatenating local ones along geodesics in a block graph. This method is an extension of a similar idea established for trees and Cayley graphs of free product groups [24]. In Section 6 we discuss trees and free products of complete graphs as special cases and make some comments. In Appendix we review the formula for QEC of a star product of complete graphs, which is used for the lower bound for QEC of a block graph.

Preliminaries

Graphs and Subgraphs

A graph is a pair G=(V,E)G=(V,E) consisting of a non-empty set VV and a subset of the two-element subsets of VV. An element of VV is called a vertex and an element of EE an edge. A graph G=(V,E)G=(V,E) is called finite if VV is a (non-empty) finite set, and infinite otherwise. In this paper we deal with both finite and infinite graphs.

Let G=(V,E)G=(V,E) be a graph. Two vertices x,y∈Vx,y\in V are called adjacent if {x,y}∈E\{x,y\}\in E. In that case, we write x∼yx\sim y as usual. Note that this definition of a graph precludes loops, that is, x≁xx\not\sim x. For any x,y∈Vx,y\in V a finite sequence of vertices x0,x1,…,xm∈Vx_0,x_1,\ldots,x_m\in V such that

x=x0∼x1∼⋯∼xm=y,(2)x=x_0\sim x_1\sim\cdots\sim x_m=y, \tag*{(2)}

where m≥0m\ge0 and some of x0,x1,…,xmx_0,x_1,\ldots,x_m may coincide, is called a walk of length mm connecting xx and $y. If x0,x1,…,xmx_0,x_1,\ldots,x_m are mutually distinct, the walk in (2) is called a path of length mm. If m≥3m\ge3, x=yx=y, and x0,x1,…,xm−1x_0,x_1,\ldots,x_{m-1} are mutually distinct, then the walk in (2) is called a cycle of length mm.

A graph G=(V,E)G=(V,E) is called connected if any two vertices x,y∈Vx,y\in V are connected by a walk. In that case, the length of a shortest walk (equivalently, a shortest path) connecting xx and yy is called the graph distance between xx and yy, and is denoted by dG(x,y)d_G(x,y) or simply by d(x,y)d(x,y) when there is no risk of confusion.

Let G=(V,E)G=(V,E) and H=(W,F)H=(W,F) be two graphs. We say that HH is a subgraph of GG and write H⊂GH\subset G if W⊂VW\subset V and F⊂EF\subset E. A subgraph H=(W,F)H=(W,F) of G=(V,E)G=(V,E) is called an induced subgraph if F=E↾WF=E\mathord{\upharpoonright}_W holds, that is, for any x,y∈Wx,y\in W we have {x,y}∈F⟺{x,y}∈E\{x,y\}\in F\Longleftrightarrow\{x,y\}\in E. In that case we also say that HH is the subgraph induced by WW, and write H=⟨W⟩H=\langle W\rangle.

Let G=(V,E)G=(V,E) be a connected graph and H=(W,F)H=(W,F) a connected subgraph of GG. Let dGd_G and dHd_H be the graph distances of GG and HH, respectively. We say that HH is an isometric subgraph of GG if

dH(x,y)=dG(x,y),x,y∈W.(3)d_H(x,y)=d_G(x,y),\qquad x,y\in W. \tag*{(3)}

An isometric subgraph is necessarily an induced subgraph, but the converse is false.

Quadratic Embedding Constant

Let G=(V,E)G=(V,E) be a connected graph with ∣V∣≥2|V|\ge2 and d(x,y)d(x,y) the graph distance between two vertices xx and yy in VV. Recall that GG may be finite or infinite. Let C(V)C(V) be the space of real column vectors f=[f(x)]x∈Vf=[f(x)]_{x\in V} and C0(V)C_0(V) its subspace of those with finite supports, that is, those f=[f(x)]f=[f(x)] with f(x)=0f(x)=0 except finitely many x∈Vx\in V.

The canonical quadratic function associated to the distance matrix D=[d(x,y)]x,y∈VD=[d(x,y)]_{x,y\in V} of GG is defined by

⟨f,Df⟩=∑x,y∈Vd(x,y)f(x)f(y),f∈C0(V),(4)\langle f,Df\rangle=\sum_{x,y\in V}d(x,y)f(x)f(y),\qquad f\in C_0(V), \tag*{(4)}

where ⟨⋅,⋅⟩\langle\cdot,\cdot\rangle stands for the canonical inner product on C0(V)C_0(V). The quadratic embedding constant (QEC for short) of GG is the conditional supremum of ⟨f,Df⟩\langle f,Df\rangle defined by

QEC⁡(G)=sup⁡{⟨f,Df⟩; f∈C0(V), ⟨f,f⟩=1, ⟨1,f⟩=0},(5)\operatorname{QEC}(G)=\sup\{\langle f,Df\rangle;\ f\in C_0(V),\ \langle f,f\rangle=1,\ \langle\mathbf{1},f\rangle=0\}, \tag*{(5)}

where 1∈C(V)\mathbf{1}\in C(V) is the column vector whose entries are all one and ⟨1,f⟩\langle\mathbf{1},f\rangle is understood as a natural extension of the inner product on C0(V)C_0(V). If G=(V,E)G=(V,E) is a finite connected graph with ∣V∣=n≥2|V|=n\ge2, we have C(V)=C0(V)≅RnC(V)=C_0(V)\cong\mathbb{R}^{n} and QEC⁡(G)\operatorname{QEC}(G) is attained at some f∈C(V)f\in C(V) satisfying ⟨f,f⟩=1\langle f,f\rangle=1 and ⟨1,f⟩=0\langle\mathbf{1},f\rangle=0. Hence, (2.4) becomes

QEC⁡(G)=max⁡{⟨f,Df⟩; f∈C(V), ⟨f,f⟩=1, ⟨1,f⟩=0},(6)\operatorname{QEC}(G)=\max\{\langle f,Df\rangle;\ f\in C(V),\ \langle f,f\rangle=1,\ \langle\mathbf{1},f\rangle=0\}, \tag*{(6)}

as stated in Introduction. The QEC is a numeric invariant of connected graphs on two or more vertices.

The following result, the proof of which is straightforward from definition, will be used freely without further comment.

Proposition 2.1 ([35]). Let G=(V,E)G=(V,E) be a connected graph and H=(W,F)H=(W,F) its isometric subgraph with ∣W∣≥2|W|\ge2. Then we have QEC⁡(H)≤QEC⁡(G)\operatorname{QEC}(H)\le\operatorname{QEC}(G).

The set of integers Z={…,−2,−1,0,1,2,…}\mathbb{Z}=\{\ldots,-2,-1,0,1,2,\ldots\} equipped with the natural adjacency relation i∼i+1i\sim i+1 becomes an (infinite) graph called the two-sided infinite path and is denoted by Z\mathbb{Z} for simplicity. The subgraph induced by {0,1,2,…}\{0,1,2,\ldots\} is called the one-sided infinite path and denoted by Z+\mathbb{Z}_+.

References

  1. [1]A. Y. Alfakih: “Euclidean Distance Matrices and Their Applications in Rigidity Theory,” Springer, Cham, 2018.DOI
  2. [2]R. Balakrishnan and K. Ranganathan: “A Textbook of Graph Theory (2nd Ed.),” Springer, New York, 2012.
  3. [3]R. Balaji and R. B. Bapat: On Euclidean distance matrices, Linear Algebra Appl. 424 (2007), 108–117.DOI
  4. [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), 539–560.DOI
  5. [5]E. T. Baskoro and N. Obata: A classification of graphs through quadratic embedding constants and clique graph insights, Communications in Combinatorics and Optimization 11 (2026): 57–77. doi.org/10.22049/CCO.2024.29159.1869
  6. [6]A. Behtoei, M. Jannesari and B. Taeri: A characterization of block graphs, Discrete Appl. Math. 158 (2010), 219–221.DOI
  7. [7]C. Berg, J. P. R. Christensen and P. Ressel: “Harmonic Analysis on Semigroups,” Springer-Verlag, New York, 1984.
  8. [8]J. A. Bondy and U. S. R. Murty: “Graph Theory,” Springer, New York, 2008.
  9. [9]M. Carter, S. Tornier and G. Willis: On free products of graphs, Australas. J. Combin. 78 (2020), 154–176.arxiv.org/abs/2002.10639
  10. [10]P. N. Choudhury and R. Nandi: Quadratic embedding constants of graphs: bounds and distance spectra, Linear Algebra Appl. 680 (2024), 108–125.arxiv.org/abs/2306.15589
  11. [11]A. Dobrynin and I. Gutman: On a graph invariant related to the sum of all distances in a graph, Publ. Inst. Math. (Beograd) (N.S.) 56 (1994), 18–22.
  12. [12]R. D. Dutton and R. C. Brigham: On the radius and diameter of the clique graph, Discrete Math. 147 (1995), 293–295.DOI
  13. [13]Ferdi, E. T. Baskoro, N. Obata and A. P. Santika: Quadratic embedding constants of corona graphs, Linear Algebra Appl. 741 (2026), 97–125.
  14. [14]R. C. Hamelink: A partial characterization of clique graphs, J. Combinatorial Theory 5 (1968), 192–197.DOI
  15. [15]F. Harary: A characterization of block-graphs, Canad. Math. Bull. 6 (1963), 1–6.DOI
  16. [16]E. Howorka: On metric properties of certain clique graphs, J. Combin. Theory Ser. B 27 (1979), 67–74.DOI
  17. [17]W. Irawan and K. A. Sugeng: Quadratic embedding constants of hairy cycle graphs, J. Phys.: Conf. Ser. 1722 (2021) 012046.DOI
  18. [18]G. Jaklič and J. Modic: On Euclidean distance matrices of graphs, Electron. J. Linear Algebra 26 (2013), 574–589.DOI
  19. [19]G. Jaklič and J. Modic: Euclidean graph distance matrices of generalizations of the star graph, Appl. Math. Comput. 230 (2014), 650–663.DOI
  20. [20]L. Liberti, G. Lavor, N. Maculan and A. Mucherino: Euclidean distance geometry and applications, SIAM Rev. 56 (2014), 3–69.arxiv.org/abs/1205.0349
  21. [21]Z. Z. Lou, N. Obata and Q. X. Huang: Quadratic embedding constants of graph joins, Graphs and Combinatorics 38 (2022), 161 (22 pages).DOI
  22. [22]W. Młotkowski: Positive definite radial functions on free product of groups, Boll. Un. Mat. Ital. B (7) 2 (1988), 53–66.
  23. [23]W. Młotkowski: Positive definite functions on free product of groups Boll. Un. Mat. Ital. B (7) 3 (1989), 343–355.
  24. [24]W. Młotkowski: Positive and negative definite kernels on trees, in “Harmonic Analysis and Discrete Potential Theory (M. A. Picardello, Ed.),” pp. 107–110, Plenum Press, New York, 1992.DOI
  25. [25]W. Młotkowski: Quadratic embedding constants of path graphs, Linear Algebra Appl. 644 (2022), 95–107.arxiv.org/abs/2201.01351
  26. [26]W. Młotkowski and N. Obata, On quadratic embedding constants of star product graphs, Hokkaido Math. J. 49 (2020), no. 1, 129–163.arxiv.org/abs/1802.01214
  27. [27]W. Młotkowski and N. Obata: Quadratic embedding constants of fan graphs and graph joins, Linear Algebra Appl. 709 (2025), 58–91.DOI
  28. [28]W. Młotkowski and N. Obata: Partial Chebyshev polynomials and fan graphs, Phil. Trans. R. Soc. A 383 (2025): 20240417.DOI
  29. [29]W. Młotkowski, M. Skrzypczyk, M. Wojtylak: On quadratic embeddability of bipartite graphs and theta graphs, Linear Algebra Appl. 734 (2026), 89–115.arxiv.org/abs/2409.17662
  30. [30]Guiqiang Mou: Quadratic embedding constants of lexicographic product graphs, Linear Algebra Appl. 746 (2026), 1–17.DOI
  31. [31]N. Obata: Quadratic embedding constants of wheel graphs, Interdiscip. Inform. Sci. 23 (2017), 171–174.DOI
  32. [32]N. Obata: Primary non-QE graphs on six vertices, Interdiscip. Inform. Sci. 29 (2023), 141–156.DOI
  33. [33]N. Obata: Complete multipartite graphs of non-QE class, Electron. J. Graph Theory Appl. 11 (2023), 511–527.DOI
  34. [34]N. Obata: “Quadratic Embedding of Graphs,” World Scientific, 2026.DOI
  35. [35]N. Obata and A. Y. Zakiyyah: Distance matrices and quadratic embedding of graphs, Electron. J. Graph Theory Appl. 6 (2018), 37–60.DOI
  36. [36]K. R. Parthasarathy and K. Schmidt: “Positive Definite Kernels, Continuous Tensor Products, and Central Limit Theorems of Probability Theory,” Lecture Notes in Math., Vol. 272 Springer-Verlag, Berlin-New York, 1972.DOI
  37. [37]M. Purwaningsih and K. A. Sugeng: Quadratic embedding constants of squid graph and kite graph, J. Phys.: Conf. Ser. 1722 (2021) 012047.DOI
  38. [38]G. Quenell: Combinatorics of free product graphs, Contemp. Math., 173 (1994), 257–281.DOI
  39. [39]F. S. Roberts and J. H. Spencer: A characterization of clique graphs, J. Combinat. Theory B 10 (1971), 102–108.
  40. [40]I. J. Schoenberg: Remarks to Maurice Fréchet’s article “Sur la définition ax-iomatique d’une classe d’espace distancié vectoriellement applicable sur l’espace de Hilbert”, Ann. of Math. 36 (1935), 724–732.
  41. [41]I. J. Schoenberg: Metric spaces and positive definite functions, Trans. Amer. Math. Soc. 44 (1938), 522–536.
  42. [42]M. Skrzypczyk: Quadratic embedding of theta graphs via reproducing kernel Hilbert spaces, Complex Analysis and Operator Theory 20 (2026), 188 (23 pages).
  43. [43]J. L. Szwarcifter: A survey on clique graphs, in “Recent Advances in Algorithms and Combinatorics (B. A. Reed and C. L. Sales, Eds.),” pp.109–136, CMS Books in Mathematics, Springer, 2003.
  44. [44]A. Valette: Negative definite kernels on trees, in “Harmonic Analysis and Discrete Potential Theory (M. A. Picardello, Ed.),” pp. 99–105, Plenum Press, New York, 1992.DOI
  45. [45]D. V. Znoĭko: Free products of nets and free symmetrizers of graphs, Math. USSR-Sbornik 27 (1975), 463–480.DOI

Paper details

vlnc:W_wcd3cm3s
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 0

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Mathematics

Not recorded for this paper

View statement
Looking for related papers…
Contents