Distance matrices and quadratic embedding of graphs

Nobuaki Obata^a , Alfi Y. Zakiyyah^b

obata@math.is.tohoku.ac.jp, yusrotis@gmail.com

A connected graph is said to be of QE class if it admits a quadratic embedding in a Hilbert space, or equivalently, if the distance matrix is conditionally negative definite. Several criteria for a graph to be of QE class are derived from the point of view of graph operations. For a quantitative criterion the QE constant is introduced and concrete examples are shown with explicit calculation. If the distance matrix admits a constant row sum, the QE constant coincides with the second largest eigenvalue of the distance matrix. The QE constants are determined for all graphs on n vertices with n ≤ 5, among which two are not of QE class.

Keywords: conditionally negative definite matrix, distance matrix, Euclidean distance matrix quadratic embedding, QE constant Mathematics Subject Classification : 05C50, 05C12, 05C76

DOI: 10.5614/ejgta.2018.6.1.4

1. Introduction

Since Schoenberg [20, 21, 22] introduced essentially the concept of quadratic embedding of a metric space, many relevant works have appeared with wide applications often under the name of Euclidean distance geometry, see e.g., the excellent survey by Liberti et al [15] and references cited therein. In this line, discrete spaces have also attracted much attention from various aspects.

In this paper we focus on quadratic embedding of graphs, being motivated by two lines of researches. First, although less actively considered than the adjacency or Laplacian matrices, distance matrices are also interesting in characterization of graphs. Noteworthy characteristic properties of the distance matrices of trees are derived by Balaji–Bapat [2], see also Bapat [3, Chapter

Received: 22 August 2017, Revised: 9 January 2018, Accepted: 27 January 2018.

^aGraduate School of Information Sciences, Tohoku University, Sendai 980-8579 Japan

^bFaculty of Mathematics and Natural Sciences, Institut Teknologi Bandung, Jalan Ganesa 10 Bandung 40132, Indonesia.

8]. More recently, Jaklic–Modic [11, 12, 13] determine some classes of graphs of QE class (in ˇ our terminology) and their explicit embeddings in Euclidean spaces. Second, the Q-matrix of a graph, the entrywise exponential of the distance matrix, has become important in relation to the q-deformation of spectral distributions of graphs, see e.g., Hora–Obata [9]. In this context it is fundamental to know whether the Q-matrix of a graph is positive definite or not. In fact, this property is closely related to that the graph admits a quadratic embedding, as is discussed by Haagerup [7] for a tree and by Bozejko [5] for an elegant extension in terms of a Markov product. For further ˙ developments, see Obata [17, 18].

Now let G = (V, E) be a connected (finite or infinite) graph and denote by d(x, y) the graph distance between two vertices x, y ∈ V , i.e., the length of a shortest walk (or path) connecting x and y. A map φ from V into a Hilbert space H is called a quadratic embedding of G if

\[\|\varphi(x) - \varphi(y)\|^2 = d(x, y), \qquad x, y \in V,\] (1)

where ∥ · ∥ stands for the norm of H. A graph G is said to be of QE class if it admits a quadratic embedding. A criterion for a graph G = (V, E) to be of QE class is given by a kind of spectral characteristic of the distance matrix D = [d(x, y)]x,y∈^V . In this paper we concentrate on the study of the QE constant of a graph G defined by

\[QEC(G) = \sup\{\langle f, Df \rangle; f \in C_0(V), \langle f, f \rangle = 1, \langle \mathbf{1}, f \rangle = 0\},\] (2)

for notations see Section 2. By definition the distance matrix D is conditionally negative definite if and only if QEC(G) ≤ 0. The crucial fact due to Schoenberg [20, 21] (also Young–Householder [23] for a finite case) says that a graph G admits a quadratic embedding if and only if D is conditionally negative definite. We thus have a quantitative criterion: a graph G is of QE class if and only if QEC(G) ≤ 0. The main purpose of this paper is to derive several criteria for a graph to be of QE class, and provide concrete examples with explicit QE constants. We consider the QE constant itself as an interesting spectral characteristic of a graph.

This paper is organized as follows: In Section 2, after preparation of basic notations and notions, we examine paths Pn, cycles Cn, complete graphs Kn, complete bipartite graphs Km,n, a tri-partite graphs K1,1,n and so on as first examples.

In Section 3 we discuss graph operations preserving the property of being of QE class, in particular, isometric embedding of a subgraph, the Cartesian product, the star product, and deletion of edges. It is noteworthy that QEC(G¹ × G2) = 0 holds whenever both G¹ and G² are graphs of QE class on two or more vertices (Theorem 3.3). The star product preserves the property of being QE class (Theorem 3.5). Deleting edges from the complete graphs, we construct graphs of QE class and of non-QE class.

In Section 4 we provide two methods of calculating the QE constants. As is anticipated from the definition (2), the method of Lagrange multipliers gives rise to a concise formula, but not very practical (Proposition 4.2). The second method uses eigenvalues of the distance matrix. It is shown that QEC(G) coincides with the second largest eigenvalue of D if the distance matrix admits a constant row sum (Theorem 4.7). The second method is restrictive but still covers a wide class of graphs.

In Section 5 we examine all graphs on n vertices with 2 ≤ n ≤ 5 together with their QE constants. As a result, there are two graphs which are not of QE class. It seems that these two

graphs are well-known among experts, but not easily found in literatures. The full list will be useful in the further study of graph operations and non-QE graphs.

2. Graphs of QE class

2.1. Notations

For a non-empty set X let C(X) denote the space of R-valued functions on X, and C0(X) the subspace of ones with finite supports. Obviously, C0(X) = C(X) if X is finite. The canonical inner product and norm on C0(X) are defined by

\[\langle f, g \rangle = \sum_{x \in X} f(x) g(x), \qquad ||f|| = \sqrt{\langle f, f \rangle}, \qquad f, g \in C_0(X),\]

respectively. Let 1 ∈ C(X) be the constant function defined by 1(x) = 1 for all x ∈ X. Overusing the notation, we write

\[\langle \mathbf{1}, f \rangle = \sum_{x \in X} f(x), \qquad f \in C_0(X).\]

A R-valued function K : X × X → R, i.e., K ∈ C(X × X), is called a kernel on X or a matrix with index set X × X, and we write

\[K = [K(x,y)] = [K(x,y)]_{x,y \in X}, \qquad (K)_{xy} = K(x,y).\]

In accordance with usual matrix multiplication, for K ∈ C(X × X) and f ∈ C0(X) we define

\[Kf(x) = \sum_{y \in X} K(x, y) f(y), \qquad x \in X, \quad f \in C_0(X).\]

Then Kf ∈ C(X) but not necessarily Kf ∈ C0(X). Overusing the notation again, we write

\[\langle f, Kg \rangle = \sum_{x,y} K(x,y) f(x) g(x), \qquad f, g \in C_0(X).\]

The canonical basis of C0(X) is denoted by {e^x ; x ∈ X}, where ex(y) = δxy (Kronecker symbol). Obviously, ⟨ex, ey⟩ = δxy. Note the obvious relation:

\[\langle e_x, Ke_y \rangle = K(x, y), \qquad x, y \in X.\]

The transposed matrix is defined by K^T (x, y) = K(y, x). We then have

\[\langle f, Kg \rangle = \langle K^T f, g \rangle, \qquad f, g \in C_0(X).\]

A matrix K is called symmetric if K^T = K.

2.2. Conditionally negative definite matrices and quadratic embedding of a metric space

A symmetric matrix K = [K(x, y)] with index set X × X is called conditionally negative definite if

\[\langle f, Kf \rangle = \sum_{x,y \in X} K(x,y) f(x) f(y) \le 0\]

for all f ∈ C0(X) with ⟨1, f⟩ = 0.

Let (X, d) be a metric space. A map φ from X into a Hilbert space H is called a quadratic embedding of (X, d) if

\[\|\varphi(x) - \varphi(y)\|^2 = d(x, y), \qquad x, y \in X,\]

where ∥ · ∥ is the norm of the Hilbert space H. The following result is due to Schoenberg [21], for relevant results see also Hayden–Reams–Wells [8], Joziak [14], Young–Householder [23]. ´

Theorem 2.1. For a metric space (X, d) the following two conditions are equivalent:

• (i) the metric space (X, d) admits a quadratic embedding;
• (ii) the distance matrix D = [d(x, y)]x,y∈^X is conditionally negative definite.

Remark 2.2. A symmetric matrix K satisfying K(x, x) = 0 for all x ∈ X is called a Schoenberg kernel. A finite symmetric matrix K is called a Euclidean distance matrix if there is a map φ from X into a Euclidean space such that K(x, y) = ∥φ(x) − φ(y)∥ 2 for all x, y ∈ X.

2.3. QE constants of graphs

A graph is a pair G = (V, E), where V is a non-empty set of vertices and E a set of edges, i.e., a subset of {{x, y} ; x, y ∈ V, x ̸= y}. If {x, y} ∈ E, we write x ∼ y for simplicity. A finite sequence of vertices x0, x1, . . . , x^m ∈ V is called an m-step walk if x⁰ ∼ x¹ ∼ · · · ∼ xm. In this case we say that x⁰ and x^m are connected by a walk of length m. A graph is called connected if any pair of vertices are connected by a walk. A graph is called finite if V is a finite set. Throughout this paper by a graph we always mean a (finite or infinite) connected graph.

For x, y ∈ V with x ̸= y let d(x, y) denote the length of a shortest walk (or path) connecting x and y. By definition we set d(x, x) = 0. Then d(x, y) becomes a metric on V , which we call the graph distance. A graph G = (V, E) is called of QE class if the metric space (V, d) admits a quadratic embedding, i.e., there exist a Hilbert space H and a map φ : V → H such that

\[\|\varphi(x) - \varphi(y)\|^2 = d(x, y), \qquad x, y \in V.\]

Such a map φ is called a quadratic embedding of G.

Let D = [d(x, y)]x,y∈^V be the distance matrix of a graph G = (V, E). The QE constant of a graph G is defined by

QEC(G) = sup{\[\langle f, Df \rangle\]; \(f \in C_0(V), ||f|| = 1, \langle \mathbf{1}, f \rangle = 0\)}. (3)

Obviously, QEC(G) is characterized as the infimum among constants C satisfying

\[\langle f, Df \rangle \leq C \|f\|^2\] for all \(f \in C_0(V)\) with \(\langle \mathbf{1}, f \rangle = 0\).

By definition D is conditionally negative definite if and only if QEC(G) ≤ 0. Then, combining Theorem 2.1, we come to the following

Theorem 2.3. Let G = (V, E) be a graph with distance matrix D = [d(x, y)]. Then the following conditions are equivalent:

• (i) G is of QE class;
• (ii) D is conditionally negative definite;
• (iii) QEC(G) ≤ 0.

Remark 2.4. If G is a finite graph, say V = {1, 2, . . . , n}, then through the natural identification of C(V ) with R n the domain

\[\{f \in \mathbb{R}^n \, ; \, ||f|| = 1, \, \langle \mathbf{1}, f \rangle = 0\}\]

is homeomorphic to a sphere of n − 2 dimension. Therefore, QEC(G) is attained by some f ∈ R n with ∥f∥ = 1 and ⟨1, f⟩ = 0, that is,

\[QEC(G) = \max\{\langle f, Df \rangle; f \in C(V), ||f|| = 1, \langle \mathbf{1}, f \rangle = 0\}.\] \[(4)\]

2.4. First examples of graphs of QE class

Theorem 2.5 (Jaklic–Modic [11]) ˇ . For any n ≥ 1 the path Pⁿ on n vertices is of QE class.

Theorem 2.6. For any n ≥ 1 the complete graph Kⁿ on n vertices is of QE class.

In fact, a path along the mutually vertical edges of a hypercube gives rise to a quadratic embedding of Pⁿ into R n−1 . Similarly, a natural realization of Kⁿ as a regular polytope in R n−1 is a quadratic embedding.

The QE constant of Kⁿ is obtained easily. Taking V = {1, 2, . . . , n}, we see that all entries of D are 1 except the zero diagonals. Then for f = [x¹ · · · xn] ^T ∈ R ⁿ we have

\[\langle f, Df \rangle = \sum_{i \neq j} x_i x_j = \sum_{i,j=1}^n x_i x_j - \sum_{i=1}^n x_i^2 = \langle \mathbf{1}, f \rangle^2 - ||f||^2.\]

Obviously, ⟨f, Df⟩ ≤ 0 whenever ⟨1, f⟩ = 0. Moreover, for n ≥ 2 we have

QEC\[(K_n) = \max\{\langle f, Df \rangle ; f \in C(V), ||f|| = 1, \langle \mathbf{1}, f \rangle = 0\} = -1.\]

Note that QEC(K1) = 0 by definition.

Theorem 2.7 (Jaklic–Modic [12]) ˇ . For any n ≥ 3 the cycle Cⁿ is of QE class.

Calculation of QEC(Cn) is postponed, see Example 4.9.

Theorem 2.8. Let 1 ≤ m ≤ n. The complete bipartite graph Km,n is of QE class if and only if

• (i) m = 1 and n ≥ 1, that is, K1,n is a star; or
• (ii) m = n = 2, that is, K2,² ∼= C⁴ is a cycle on 4 vertices.

Proof. The distance matrix is written in the form:

\[D = \begin{bmatrix} A & J \\ J^T & B \end{bmatrix},\]

where A is an m × m matrix with off-diagonal entries being all 2 and diagonal ones all 0, B is an n × n matrix of the same type, and J is an m × n matrix with entries being all 1. For f = [x¹ · · · x^m y¹ · · · yn] ^T ∈ R ^m+ⁿ we have

\[\langle f, Df \rangle = 2 \sum_{1 \le i \ne j \le m} x_i x_j + 2 \sum_{i=1}^m \sum_{j=1}^n x_i y_j + 2 \sum_{1 \le i \ne j \le n} y_i y_j\] \[= 2 \left( \sum_{i,j=1}^m x_i x_j - \sum_{i=1}^m x_i^2 \right) + 2 \sum_{i=1}^m \sum_{j=1}^n x_i y_j + 2 \left( \sum_{i,j=1}^n y_i y_j - \sum_{j=1}^n y_j^2 \right)\] \[= -2 \left( \sum_{i=1}^m x_i^2 + \sum_{j=1}^n y_j^2 \right) + 2 \left( \sum_{i,j=1}^m x_i x_j + \sum_{i=1}^m \sum_{j=1}^n x_i y_j + \sum_{i,j=1}^n y_i y_j \right). \tag{5}\]

It is sufficient to find the maximum of ⟨f, Df⟩, where f ∈ R m+n runs over the domain determined by

\[||f||^2 = \langle f, f \rangle = \sum_{i=1}^m x_i^2 + \sum_{j=1}^n y_j^2 = 1, \quad \langle 1, f \rangle = \sum_{i=1}^m x_i + \sum_{j=1}^n y_j = 0.\] (6)

The above conditions being taken into account, (5) admits a simpler expression:

\[\langle f, Df \rangle = -2 + 2 \left( \sum_{i=1}^{m} x_i \right)^2.\]

The maximum of ⟨f, Df⟩ subject to (6) is computed by elementary calculus (see Appendix No. 1) and we come to

QEC\[(K_{m,n}) = -2 + \frac{2mn}{m+n} = \frac{2}{m+n} \{ (m-1)(n-1) - 1 \},\]

from which the assertion follows immediately.

Theorem 2.9. Let n ≥ 1. A tri-partite graph K1,1,n is of QE class if and only if 1 ≤ n ≤ 4.

Proof. Let V = {1, 2, . . . , n, n + 1, n + 2} and assume that the three components are given by {1, 2, . . . , n}, {n + 1} and {n + 2}. For f = [x¹ · · · xⁿ xn+1 xn+2] ^T ∈ R ⁿ+2, under the conditions ∥f∥ = 1 and ⟨1, f⟩ = 0 we have

\[\langle f, Df \rangle = -\|f\|^2 + \sum_{1 \le i < j \le n} 2x_i x_j,\]

of which the maximum subject to ||f|| = 1 and \(\langle \mathbf{1}, f \rangle = 0\) is the QE constant. By elementary calculus (see Appendix No. 3) we obtain

QEC\[(K_{1,1,n}) = -1 + \frac{(n-1)\{(n+2) - n\}}{n+2} = \frac{n-4}{n+2},\]

which proves the assertion.

Remark 2.10. The tri-partite graph \(K_{1,1,n}\) is also called the n-fold edge-amalgamation of \(K_3\).

Figure 1. \(K_{1,1,n}\): n-fold edge amalgamation of \(K_3\)

3. Graph operations preserving QE class

3.1. Subgraphs

Theorem 3.1. Let G = (V, E) be a subgraph of \(\tilde{G} = (\tilde{V}, \tilde{E})\). Let d and \(\tilde{d}\) be the graph distances of G and \(\tilde{G}\), respectively. If \(d(x, y) = \tilde{d}(x, y)\) for all \(x, y \in V\), i.e., G is isometrically embedded in \(\tilde{G}\), then we have

\[QEC(G) \leq QEC(\tilde{G}).\]

In particular, if \(\tilde{G}\) is of QE class, so is G.

Proof. Let \(\tilde{D}\) and D be the distance matrices of \(\tilde{G}\) and G, respectively. Then \(\tilde{D}\) admits an expression in the form of block matrices:

\[\tilde{D} = \begin{bmatrix} D & C \\ C^T & B \end{bmatrix}.\]

By definition of QEC(G), for any \(\epsilon > 0\) there exists an \(f \in C_0(V)\) with ||f|| = 1 and \(\langle \mathbf{1}, f \rangle = 0\) such that \(\langle f, Df \rangle \geq \mathrm{QEC}(G) - \epsilon\). Define \(\tilde{f} \in C_0(\tilde{V})\) by \(\tilde{f}(x) = f(x)\) for \(x \in V\) and = 0 otherwise. Then, we have \(||\tilde{f}|| = 1\), \(\langle \mathbf{1}, \tilde{f} \rangle = 0\) and

\[\langle \tilde{f}, \tilde{D}\tilde{f} \rangle = \left\langle \begin{bmatrix} f \\ 0 \end{bmatrix}, \begin{bmatrix} D & C \\ C^T & B \end{bmatrix} \begin{bmatrix} f \\ 0 \end{bmatrix} \right\rangle = \langle f, Df \rangle \ge \text{QEC}(G) - \epsilon.\]

Hence \(QEC(\tilde{G}) \ge QEC(G) - \epsilon\). Since \(\epsilon > 0\) is arbitrary, we have \(QEC(\tilde{G}) \ge QEC(G)\).

Theorem 3.1 is useful for constructing a graph of not QE class from a smaller one. For example,

Proposition 3.2. Let G = (V, E) be a graph with \(\operatorname{diam}(G) \leq 2\). Let \(\tilde{G} = (\tilde{V}, \tilde{E})\) be a graph obtained by adding a vertex to G with one or more edges. If G is not of QE class, either is not \(\tilde{G}\).

3.2. Cartesian product

For two graphs G¹ = (V1, E1) and G² = (V2, E2) the Cartesian product G¹ × G² is defined to be a graph on V¹ × V² with the adjacency relation:

\[(x_1, y_1) \sim (x_2, y_2) \iff (i) \begin{cases} x_1 \sim x_2, \\ y_1 = y_2 \end{cases} \text{ or } (ii) \begin{cases} x_1 = x_2, \\ y_1 \sim y_2. \end{cases}\]

Theorem 3.3. If both G¹ and G² are of QE class, so is the Cartesian product G¹ × G2. Moreover, QEC(G¹ × G2) = 0 whenever |V1| ≥ 2 and |V2| ≥ 2.

Proof. For i = 1, 2 let αⁱ : Vⁱ → Hⁱ be a quadratic embedding. Define a map β : V¹ × V² → H¹ ⊕ H² by

\[\beta(x,y) = \alpha_1(x) \oplus \alpha_2(y), \qquad x \in V_1, \quad y \in V_2.\]

We then see that

\[\|\beta(x_1, y_1) - \beta(x_2, y_2)\|^2 = \|\alpha_1(x_1) \oplus \alpha_2(y_1) - \alpha_1(x_2) \oplus \alpha_2(y_2)\|^2\] \[= \|(\alpha_1(x_1) - \alpha_1(x_2)) \oplus (\alpha_2(y_1) - \alpha_2(y_2)\|^2\] \[= \|\alpha_1(x_1) - \alpha_1(x_2)\|^2 + \|\alpha_2(y_1) - \alpha_2(y_2)\|^2.\] (7)

Let d¹ and d² be the graph distances of G¹ and G2, respectively. Since α¹ and α² are quadratic embeddings, (7) becomes

\[\|\beta(x_1, y_1) - \beta(x_2, y_2)\|^2 = d_1(x_1, x_2) + d_2(y_1, y_2).\] (8)

On the other hand, the graph distance d of G = G¹ × G² satisfies

\[d((x_1, y_1), (x_2, y_2)) = d_1(x_1, x_2) + d_2(y_1, y_2).\]

Hence (8) means that β is a quadratic embedding of G into H¹ ⊕ H2. Therefore G is of QE class and QEC(G) ≤ 0.

In order to infer that QEC(G) = 0 it is sufficient to show that ⟨f, Df⟩ = 0 holds for some f ∈ C0(V ) satisfying ⟨1, f⟩ = 0 and f ̸= 0. In fact, for i = 1, 2 choosing gⁱ ∈ C0(Vi) such that ⟨1, gi⟩ = 0 and gⁱ ̸= 0 (this is possible whenever |Vⁱ | ≥ 2), we see easily that f(x, y) = g1(x)g2(y) possesses the desired properties.

Example 3.4. Since C⁴ ∼= K² × K² we have QEC(C4) = 0 by Theorem 3.3. That C⁴ is of QE class follows also from Theorems 2.7 and 2.8.

3.3. Star product

Suppose that two graphs G¹ = (V1, E1) and G² = (V2, E2) are given with distinguished vertices o¹ ∈ V¹ and o² ∈ V2, respectively. The graph obtained by gluing vertices o¹ and o² is called the star product or the vertex amalgamation, and is denoted by G¹ ⋆ G2. It is convenient to write the vertex set of G¹ ⋆ G² as

\[V = (V_1 \setminus \{o_1\}) \cup (V_2 \setminus \{o_2\}) \cup \{o\},\]

where o corresponds to the glued vertices o¹ and o2. Let dⁱ denote the graph distance of Gⁱ for i = 1, 2, and d the graph distance of G¹ ⋆ G2. Then we have

\[d(x,y) = \begin{cases} d_1(x,y), & \text{if } x,y \in V_1, \\ d_1(x,o) + d_2(o,y), & \text{if } x \in V_1 \text{ and } y \in V_2, \\ d_2(x,o) + d_1(o,y), & \text{if } x \in V_2 \text{ and } y \in V_1, \\ d_2(x,y), & \text{if } x,y \in V_2. \end{cases}\]

Theorem 3.5. If both G¹ and G² are of QE class, so is the star product G¹ ⋆ G2.

Proof. For i = 1, 2 let αⁱ : Vⁱ → Hⁱ be a quadratic embedding. We may assume that αi(oi) = 0. Define a map β : V → H¹ ⊕ H² by

\[\beta(x) = \begin{cases} \alpha_1(x) \oplus 0, & \text{if } x \in V_1; \\ 0 \oplus \alpha_2(x), & \text{if } x \in V_2. \end{cases}\]

Note that β(o) = 0 ⊕ 0 follows from α1(o1) = α2(o2) = 0. We will show that

\[\|\beta(x) - \beta(y)\|^2 = d(x, y), \quad x, y \in V.\] (9)

In fact, if x, y ∈ V1, we have

\[\|\beta(x) - \beta(y)\|^2 = \|\alpha_1(x) - \alpha_1(y)\|^2 = d_1(x, y) = d(x, y).\]

Similarly, (9) is verified for x, y ∈ V2. For x ∈ V¹ and y ∈ V² we have

\[\|\beta(x) - \beta(y)\|^2 = \|\alpha_1(x) \oplus 0 - 0 \oplus \alpha_2(y)\|^2 = \|\alpha_1(x)\|^2 + \|\alpha_2(y)\|^2\]\[= \|\alpha_1(x) - \alpha_1(o_1)\|^2 + \|\alpha_2(y) - \alpha_2(o_2)\|^2\]\[= d(x, o_1) + d(y, o_2) = d(x, y).\]

Thus, β is a quadratic embedding and G¹ ⋆ G² is of QE class.

A star product of G and K² ∼= P² is called a segment concatenation of G. Since K² is of QE class, we have the following

Corollary 3.6. If G is a graph of QE class, so is any segment concatenation of G.

Corollary 3.7. Any tree is of QE class.

Remark 3.8. In some literatures, the star product of G¹ and G² is defined to be a graph on V¹ × V² equipped with the adjacency relation defined by

\[(x_1, y_1) \sim (x_2, y_2) \iff (i) \begin{cases} x_1 \sim x_2, \\ y_1 = y_2 = o_2, \end{cases} \text{ or } (ii) \begin{cases} x_1 = x_2 = o_1, \\ y_1 \sim y_2, \end{cases}\]

see e.g., Obata [19]. According to this definition the star product contains many isolated vertices. The connected component containing (o1, o2) coincides with G¹ ⋆ G² defined at the beginning of this subsection.

3.4. Deleting edges from complete graphs

For a graph G=(V,E) and a subset \(E_0\subset E\) we define \(G\backslash E_0=(V,E\backslash E_0)\), which is the graph obtained from the original graph G by deleting edges in \(E_0\). We consider graphs obtained from the complete graph \(K_n\) by deleting edges. The vertex set of \(K_n\) is taken to be \(V=\{1,2,\ldots,n\}\) and \(f\in C(V)\) is identified with a column vector \([x_1\cdots x_n]^T\in \mathbb{R}^n\).

We start with the case of deleting edges which are mutually disjoint.

Theorem 3.9. Let \(r \ge 1\) and \(2r \le n\). The graph obtained from the complete graph \(K_n\) by deleting r mutually disjoint edges, denoted by \(K_n \setminus \{e_1, \ldots, e_r\}\), is of QE class and

QEC\[(K_n \setminus \{e_1\}) = -\frac{2}{n}\],
QEC\((K_n \setminus \{e_1, \dots, e_r\}) = 0\), \(r \ge 2\).

Proof. Without loss of generality we may assume that \(e_1 = \{1, 2\}\), \(e_2 = \{3, 4\}\), ..., \(e_r = \{2r - 1, 2r\}\). Then, under the conditions ||f|| = 1 and \(\langle \mathbf{1}, f \rangle = 0\), we have

\[\langle f, Df \rangle = -\|f\|^2 + 2x_1x_2 + 2x_3x_4 + \dots + 2x_{2r-1}x_{2r}.\]

of which the maximum subject to ||f|| = 1 and \(\langle \mathbf{1}, f \rangle = 0\) is the QE constant of \(K_n \setminus \{e_1, \dots, e_r\}\). First for r = 1 an elementary argument (see Appendix No. 3) shows that

\[\max\{2x_1x_2; \|f\|=1, \langle \mathbf{1}, f\rangle=0\} = \frac{n-2}{n}\]

and hence,

\[QEC(K_n \setminus \{e_1\}) = -1 + \frac{n-2}{n} = -\frac{2}{n}.\]

For \(r \geq 2\) we apply Appendix No. 4 to obtain

\[QEC(K_n \setminus \{e_1, \dots, e_r\}) = -1 + 1 = 0.\]

In particular, \(K_n \setminus \{e_1, \dots, e_r\}\) is of QE class.

Example 3.10. Note that \(C_4 \cong K_4 \setminus \{e_1, e_2\}\), where \(e_1\) and \(e_2\) are mutually disjoint edges. Then \(QEC(C_4) = 0\) follows also from Theorem 3.9.

Let us consider the case of deleting two edges \(e_1\) and \(e_2\) which are connected. We write \(K_n \backslash P_3 = K_n \backslash \{e_1, e_2\}\) for convenience.

Theorem 3.11. Let \(n \geq 4\). We have

QEC\[(K_n \backslash P_3) = \frac{n-10}{n+2+\sqrt{2(n-1)(n-2)}}\].

In particular, \(K_n \backslash P_3\) is of QE class if and only if \(4 \le n \le 10\).

Proof. Without loss of generality we may assume that e¹ = {1, 2} and e² = {1, 3}. Then, under the conditions ∥f∥ = 1 and ⟨1, f⟩ = 0, we have

\[\langle f, Df \rangle = -\|f\|^2 + 2x_1x_2 + 2x_1x_3.\]

With the help of Appendix No. 5 we come to

QEC\[(K_n \backslash P_3) = -1 + \frac{-2 + \sqrt{2(n-1)(n-2)}}{n}\],

from which the assertion follows immediately.

Finally, we consider the case of deleting edges of a clique, i.e., a subgraph isomorphic to a complete graph. To be precise, for 2 ≤ r < n we denote by Kn\K^r the graph obtained from Kⁿ by deleting r(r − 1)/2 edges which constitute a complete graph on r vertices. Note that no vertex is deleted.

Theorem 3.12. For 2 ≤ r < n we have

\[QEC(K_n \backslash K_r) = r - 2 - \frac{r(r-1)}{n}\].

In particular, Kn\K^r is of QE class if and only if one of the following four cases occurs:

• (i) r = 2 and n ≥ 3;
• (ii) r = 3 and n = 4, 5, 6;
• (iii) r = 4 and n = 5, 6;
• (iv) r ≥ 5 and n = r + 1.

Proof. Let {1, 2, . . . , r} be the set of vertices of Kr. Then, under the conditions ∥f∥ = 1 and ⟨1, f⟩ = 0, we have

\[\langle f, Df \rangle = -\|f\|^2 + \sum_{1 \le i < j \le r} 2x_i x_j,\]

of which the maximum subject to ∥f∥ = 1 and ⟨1, f⟩ = 0 is the QE constant of Kn\Kr. With the help of Appendix No. 3 we come to

QEC\[(K_n \setminus K_r) = -1 + \frac{(r-1)(n-r)}{n} = r - 2 - \frac{r(r-1)}{n}\],

as desired. The rest of the assertion follows by a simple algebra.

Remark 3.13. Since the tri-partite graph K1,1,n is obtained as Kn+2\Kn, Theorem 2.9 is a consequence of Theorem 3.12.

4. Calculating QE constants of finite graphs

4.1. Method of Lagrange multipliers

Let G = (V, E) be a graph on V = {1, 2, . . . , n} with n ≥ 3, and D the distance matrix of G as usual. We identify f ∈ C(V ) with a column vector [x¹ . . . xn] ^T ∈ R n . By definition the QE constant is the maximum of ⟨f, Df⟩ subject to

\[||f||^2 = \langle f, f \rangle = \sum_{i=1}^n x_i^2 = 1,\] (10)

\[\langle \mathbf{1}, f \rangle = \sum_{i=1}^{n} x_i = 0. \tag{11}\]

We set

\[F(f,\lambda,\mu) = \langle f, Df \rangle - \lambda(\langle f, f \rangle - 1) - \mu \langle \mathbf{1}, f \rangle. \tag{12}\]

By differentiation we obtain

\[\frac{\partial F}{\partial x_i} = 2\langle e_i, Df \rangle - 2\lambda \langle e_i, f \rangle - \mu \langle \mathbf{1}, e_i \rangle = \langle e_i, 2(D - \lambda)f - \mu \mathbf{1} \rangle,\]

where {ei} is the canonical basis of R n . Hence ∂F /∂xⁱ = 0 for all 1 ≤ i ≤ n is equivalent to 2(D − λ)f − µ1 = 0, that is,

\[(D - \lambda)f = \frac{\mu}{2} \mathbf{1}. \tag{13}\]

Let S(D) be the set of (f = [xⁱ ], λ, µ) satisfying (10), (11) and (13).

Since relations (10) and (11) define a sphere of n−2 dimension, which is smooth and compact, the maximum of ⟨f, Df⟩ is attained at a certain f appearing in S(D). On the other hand, for (f, λ, µ) ∈ S(D) we have

\[\langle f, Df \rangle = \langle f, \lambda f + \frac{\mu}{2} \mathbf{1} \rangle = \lambda \langle f, f \rangle + \frac{\mu}{2} \langle f, \mathbf{1} \rangle = \lambda.\] (14)

Consequently, the maximum to be found coincides with the maximum of λ appearing in S(D). The above argument is summarized in the following

Proposition 4.1. Let D be the distance matrix of a graph G on n vertices with n ≥ 3. Let S(D) be the set of (f = [xⁱ ], λ, µ) satisfying (10), (11) and (13). Then QEC(G) coincides with the maximum of λ appearing in S(D).

We go back to equation (13). Suppose first that λ ̸∈ ev(D), or equivalently det(D − λ) ̸= 0. Then from (13) we obtain

\[f = \frac{\mu}{2} (D - \lambda)^{-1} \mathbf{1}. \tag{15}\]

Moreover, (10) and (11) become

\[\frac{\mu^2}{4} \| (D - \lambda)^{-1} \mathbf{1} \|^2 = 1, \tag{16}\]

\[\frac{\mu}{2}\langle \mathbf{1}, (D-\lambda)^{-1}\mathbf{1}\rangle = 0, \tag{17}\]

respectively. Note that \(\mu \neq 0\) by (16). After solving the equation

\[\langle \mathbf{1}, (D-\lambda)^{-1} \mathbf{1} \rangle = 0, \tag{18}\]

we decide \(\mu\) by (16) and then f by (15). Recall that

\[(D - \lambda)^{-1} = \frac{1}{\det(D - \lambda)} [p_{ij}(\lambda)], \tag{19}\]

where \(p_{ij}(\lambda)\) is the (j,i)-cofactor of \(D-\lambda\), i.e., \((-1)^{i+j}\) times the determinant of the submatrix obtained by deleting jth row and ith column of \(D-\lambda\). We then see that equation (18) is equivalent to an algebraic equation:

\[P(\lambda) = 0,\]

where

\[P(\lambda) = \sum_{i,j=1}^{n} p_{ij}(\lambda).\]

Since \(p_{ij}(\lambda)\) is a polynomial of degree at most n-1, so is \(P(\lambda)\). Taking in mind that the zeros of \(P(\lambda)\) may contain an eigenvalue of D, we set

\[\Lambda_1(D) = \{\lambda \in \mathbb{R} ; P(\lambda) = 0\} \setminus ev(D).\]

Then, for each \(\lambda \in \Lambda_1(D)\) we may construct a solution \((f, \lambda, \mu) \in \mathcal{S}(D)\).

Let \(\Lambda_2(D)\) denote the set of eigenvalues \(\lambda \in \text{ev}(D)\) which generate solutions \((f, \lambda, \mu) \in \mathcal{S}(D)\). Then Proposition 4.1 may be rephrased as follows.

Proposition 4.2. Let D be the distance matrix of a graph G on n vertices with \(n \geq 3\). Let \(\Lambda_1(D)\) and \(\Lambda_2(D)\) be as above. Then,

\[QEC(G) = \max \Lambda_1(D) \cup \Lambda_2(D).\] (20)

Formula (20) looks concise, however, involves many routine calculations and further improvement is necessary for application. The situation is suggested by the examples below.

Example 4.3. Consider \(K_3 \star K_2\) with distance matrix

\[D = \begin{bmatrix} 0 & 1 & 2 & 2 \\ 1 & 0 & 1 & 1 \\ 2 & 1 & 0 & 1 \\ 2 & 1 & 1 & 0 \end{bmatrix}.\]

First we have

\[\det(\lambda - D) = (\lambda + 1)(\lambda^3 - \lambda^2 - 11\lambda - 7),\]

from which we see that D has four distinct real eigenvalues. A direct calculation shows that there is no solution \((f,\lambda,\mu)\in\mathcal{S}\) corresponding to an eigenvalue satisfying \(\lambda^3-\lambda^2-11\lambda-7=0\).

While, for λ = −1 ∈ ev(D) there is a solution in S. Thus we have Λ2(D) = {−1}. On the other hand, by routine calculation we obtain

\[P(\lambda) = 2(\lambda + 1)(2\lambda^2 + 6\lambda + 3)\]

and

\[\Lambda_1(D) = \{P(\lambda) = 0\} \setminus ev(D) = \{2\lambda^2 + 6\lambda + 3 = 0\} = \left\{\frac{-3 \pm \sqrt{3}}{2}\right\}.\]

Consequently,

QEC(G) = \[\max \left\{ -1, \frac{-3 \pm \sqrt{3}}{2} \right\} = \frac{-3 + \sqrt{3}}{2}\].

Example 4.4. Consider the complete graph Kⁿ with n ≥ 3. Then, for the distance matrix D we have

\[\det(\lambda - D) = (\lambda + 1)^{n-1}(\lambda - (n-1))\]

and Λ2(D) = {−1} by direct verification. On the other hand, we obtain

\[P(\lambda) = n(\lambda + 1)^{n-1}\]

and Λ1(D) = ∅. Consequently,

\[QEC(K_n) = \max\{-1\} = -1.\]

4.2. Use of spectra of distance matrices

For convenience we say that a finite graph G is of (CRS) if the distance matrix D = [d(x, y)] admits a constant row sum, i.e.,

\[\delta = \sum_{y \in V} d(x, y) \tag{21}\]

is a constant independent of x ∈ V . In order to avoid a trivial case, we consider a finite graph on two or more vertices.

Lemma 4.5. Let G = (V, E) be a finite graph with |V | ≥ 2, and D the distance matrix. The following two conditions are equivalent:

• (i) G is of (CRS);
• (ii) 1 ∈ C(V ) is an eigenvector of D.

In that case, D1 = δ1 with the constant δ given by (21).

Following Brouwer–Cohen–Neumaier [4, Section 4.1], a connected graph G = (V, E) is called distance degree regular if for any k ≥ 0, the number |{y ∈ V ; d(x, y) = k}| is independent of x ∈ V . Apparently, a distance degree regular graph is of (CRS). Note that a distance-regular graph is distance degree regular, and that a distance degree regular graph is regular.

Lemma 4.6. If the distance matrix D admits a constant row sum δ, then ev(D) ⊂ [−δ, δ]. Moreover, δ ∈ ev(D) and it is a simple eigenvalue.

Proof. In general, every eigenvalue of a complex matrix A = [aij ] lies in the centered disk with radius maxⁱ ∑ j |aij |. Then ev(D) ⊂ [−δ, δ] follows from the fact that every eigenvalue of the distance matrix D is real and the assumption that δ in (21) is independent of x ∈ V . Moreover, from Lemma 4.5 we see that δ ∈ ev(D), that is, δ is the largest eigenvalue of D. Since D is an irreducible matrix, it follows from the Perron-Frobenius theorem (see e.g., Bapat [3, Chapter 6], Horn–Johnson [10, Chapter 8]) that δ is a simple eigenvalue.

Theorem 4.7. Let G = (V, E) be a graph of (CRS). Then QEC(G) coincides with the second largest eigenvalue of D. In particular, if the second largest eigenvalue of D is non-positive, the graph G is of QE class.

Proof. By virtue of Lemma 4.6 we may arrange the eigenvalues of D as follows:

\[\lambda_1 \le \lambda_2 \le \dots \le \lambda_{n-1} < \lambda_n = \delta.\]

Let {fk} be an orthonormal basis of C(V ) such that Df^k = λkf^k and fⁿ = 1/∥1∥. Any f ∈ C(V ) with ⟨1, f⟩ = 0 admits an expression:

\[f = \sum_{k=1}^{n-1} \langle f_k, f \rangle f_k.\]

Then we have

\[\langle f, Df \rangle = \sum_{k=1}^{n-1} \lambda_k \langle f_k, f \rangle^2 \le \lambda_{n-1} \sum_{k=1}^{n-1} \langle f_k, f \rangle^2 = \lambda_{n-1} ||f||^2.\]

Since the equality holds for f = fⁿ−¹, the maximum of ⟨f, Df⟩ subject to ∥f∥ = 1 and ⟨1, f⟩ = 0 is λⁿ−¹. Consequently, QEC(G) = λⁿ−¹.

It is noted that λⁿ−¹ ≤ QEC(G) ≤ λⁿ holds in general. For more on distance spectra, see e.g., an excellent survey by Aouchiche–Hansen [1].

Example 4.8. The complete graph Kⁿ (n ≥ 2) is distance-regular. The eigenvalues of its distance matrix D are n−1 with multiplicity 1 and −1 with multiplicity n−1. It then follows from Theorem 4.7 that QEC(Kn) = −1.

Example 4.9. The cycle Cⁿ (n ≥ 3) is distance-regular. The distance matrix D of Cⁿ is a circular matrix and its eigenvalues are easily calculated, see e.g., Aouchiche–Hansen [1], Graovac–Jashari– Strunje [6]. In fact, for C2n+1 with n ≥ 1 the eigenvalues of D are

\[\lambda_0 = n(n+1), \quad \lambda_k = -\frac{1}{4\cos^2\frac{k\pi}{2n+1}}, \quad k = 1, 2, \dots, n,\]

where λ⁰ is multiplicity free and λ^k appears with multiplicity two for all k = 1, 2, . . . , n. Hence the second largest eigenvalues of D is found in {λ1, . . . , λn} and we come to

QEC(\[C_{2n+1}\]) = \(-\frac{1}{4\cos^2\frac{\pi}{2n+1}}\).

In particular, C2n+1 is of QE class. Similarly, for C2ⁿ with n ≥ 2 the eigenvalues of D are

\[\lambda_0 = n^2\], \(\lambda_2 = \lambda_4 = \dots = \lambda_{2n-2} = 0\), \(\lambda_k = -\frac{1}{\sin^2 \frac{k\pi}{2n}}\), \(k = 1, 3, \dots, 2n - 1\).

Hence the second largest eigenvalues of D is 0 and QEC(C2n) = 0. In particular, C2ⁿ is of QE class too.

Now we give examples of graphs which are not of (CRS).

Proposition 4.10. For i = 1, 2 let Gⁱ = (Vⁱ , Ei) be a finite graph with |Vⁱ | ≥ 2. Then G¹ ⋆ G² is not of (CRS).

Proof. Let m, n be integers such that |V1| = m + 1 and |V2| = n + 1. Without loss of generality we may assume that m ≤ n. We set

\[V_1 = \{o, x_1, x_2, \dots, x_m\}, \qquad V_2 = \{o, y_1, y_2, \dots, y_n\},\]

where o is the common contact point of G¹ ⋆ G2. Then

\[V = \{o, x_1, \dots, x_m, y_1, \dots, y_n\}\]

becomes the set of vertices of G¹ ⋆ G2. Let D1, D² and D be the distance matrices of G1, G² and G¹ ∗ G2, respectively. Now we compare two row sums of D given by

\[S_1 = \sum_{z \in V} (D)_{oz} = \sum_{i=1}^m (D)_{ox_i} + \sum_{j=1}^n (D)_{oy_j},\] (22)

\[S_2 = \sum_{z \in V} (D)_{x_1 z} = (D)_{x_1 o} + \sum_{i=1}^m (D)_{x_1 x_i} + \sum_{j=1}^n (D)_{x_1 y_j}.\] (23)

Since xⁱ ∈ V¹ and y^j ∈ V² we have

\[S_1 = \sum_{i=1}^m d_1(o, x_i) + \sum_{j=1}^n d_2(o, y_j).\]

On the other hand, since (D)^x1y^j = d1(x1, o) + d2(o, y^j ) we have

\[S_2 = d_1(x_1, o) + \sum_{i=1}^m d_1(x_1, x_i) + \sum_{j=1}^n (d_1(x_1, o) + d_2(o, y_j))\]\[= d_1(x_1, o) + \sum_{i=1}^m d_1(x_1, x_i) + nd_1(x_1, o) + \sum_{j=1}^n d_2(o, y_j).\]

Then

\[S_2 - S_1 = nd_1(x_1, o) + \sum_{i=2}^{m} (d_1(x_1, x_i) - d_1(o, x_i)).\]

Since d1(o, xi) ≤ d1(o, x1) + d1(x1, xi) by the triangle inequality, we have

\[S_2 - S_1 \ge nd_1(x_1, o) - \sum_{i=2}^m d_1(o, x_1) = (n - m + 1)d_1(o, x_1) > 0.\]

Hence S¹ < S2, which means that D does not admit a constant row sum.

Proposition 4.11. The complete bipartite graph Km,n is of (CRS) if and only if m = n.

Proposition 4.12. The graphs of (CRS) on n vertices with 1 ≤ n ≤ 5 are Kⁿ and Cn.

The proofs of the above results are straightforward and omitted.

5. The graphs of QE class on n vertices with n ≤ 5

5.1. Graphs on n = 2, 3, 4 vertices

Theorem 5.1. Every graph on n vertices with n = 2, 3, 4 is of QE class.

Proof. For n = 2 we have just one graph, which is K² ∼= P2. For n = 3 we have P³ and K³ ∼= C3. As is readily shown in Subsection 2.4, they are of QE class. For n = 4, the graphs No. 1–3 are the star products of smaller graphs of QE class, so they are also of QE class (Theorem 3.5). The graphs No. 4 (C4) and No. 6 (K4) are readily known to be of QE class. The graph No. 5 (K4\{e}) is of QE class by Theorem 3.9.

The QE constants are shown in the following table, where we employ the list of finite connected graphs by McKay [16]. Calculation is routine and omitted, see also Subsection 5.3.

5.2. Graphs on n = 5 vertices

There are 21 graphs. It is an easy task to list star products of smaller graphs of QE class. They are numbered by No. 1, 2, 3, 4, 5, 6, 7, 9, 11, 12, and 15. Next, we pickup graphs judged by means of general criteria. No. 8 (C5) and No. 21 (K5) are of QE class. No. 14 (K5\K3) and No. 18 (K5\P3) are of QE class by Theorems 3.12 and 3.11, respectively. No. 19 (K5\{e1, e2}) and No. 20 (K5\{e}) are of QE class by Theorems 3.9. We see from Theorem 2.8 that No. 10 (K2,3) is not of QE class. The rest are No. 13, 16, and 17, for which the QE constants are calculated directly from their distance matrices.

No. 13 \[(K_5 \ P_5)\] Under \(||f|| = 1\) and \(\langle \mathbf{1}, f \rangle = 0\), we have \(\langle f, Df \rangle = -||f||^2 + 2x_1x_4 + 2x_1x_5 + 2x_2x_5 + 2x_3x_4\).

Then, using x¹ = −x² − x³ − x⁴ − x5, we obtain

\[2x_1x_4 + 2x_1x_5 + 2x_2x_5 + 2x_3x_4 = -2(x_4 + x_5)^2 - 2x_2x_4 - 2x_3x_5\]
\[\leq -2(x_4 + x_5)^2 + (x_2^2 + x_4^2) + (x_3^2 + x_5^2) = -2(x_4 + x_5)^2 + 1 - x_1^2.\]

Hence, under the conditions ∥f∥ = 1 and ⟨1, f⟩ = 0, we have 2x1x⁴ +2x1x⁵ +2x2x⁵ +2x3x⁴ ≤ 1 and the equality holds for

\[x_1 = 0,\] \(x_2 = x_5 = \pm \frac{1}{2}.\) \(x_3 = x_4 = \mp \frac{1}{2}.\)

Consequently, QEC(K5\P4) = −1 + 1 = 0.

No. 16 (K5\P4) We need to find the maximum of

\[\langle f, Df \rangle = -\|f\|^2 + 2x_2x_4 + 2x_2x_5 + 2x_3x_5\]

subject to ∥f∥ = 1 and ⟨1, f⟩ = 0. Applying the method of Lagrange multipliers, we obtain

\[\max \{2x_2x_4 + 2x_2x_5 + 2x_3x_5; \|f\| = 1, \ \langle \mathbf{1}, f \rangle = 0\} = \frac{\sqrt{5} - 1}{2}.\]

Then,

QEC\[(K_5 \backslash P_4) = -1 + \frac{\sqrt{5} - 1}{2} = -\frac{2}{3 + \sqrt{5}}.\]

No. 17 (K5\{P3, e}) We need to find the maximum of

\[\langle f, Df \rangle = -\|f\|^2 + 2x_1x_4 + 2x_1x_5 + 2x_2x_3\]

subject to ∥f∥ = 1 and ⟨1, f⟩ = 0. After a natural guess, setting

\[x_1 = \frac{2}{\sqrt{14}}\], \(x_2 = x_3 = -\frac{2}{\sqrt{14}}\), \(x_4 = x_5 = \frac{1}{\sqrt{14}}\),

we obtain

\[\langle f, Df \rangle = \frac{1}{7} > 0.\]

Therefore, this graph is not of QE class. The QE constant is calculated with the help of the method of Lagrange multipliers:

\[QEC(K_5 \setminus \{P_3, e\}) = \frac{4}{11 + \sqrt{161}}.\]

Theorem 5.2. Among 21 graphs on 5 vertices there are two graphs which are not of QE class. They are No. 10 and 17.

The above statement should be a folklore. In fact, the graph No. 10 is known as Bozejko's ˙ obstruction, see Hora–Obata [9, Chapter 2].

The following table summarizes the results. The QE constants are found by using the Schwartz inequality, the method of Lagrange multipliers and some elementary consideration, see also Subsection 5.3.

Note: (1) λ ∗ 1 is the maximal real root of 5λ ³ − 2λ ² − 4λ + 2 = 0.

(2) λ ∗ 2 is the maximal real root of 5λ ³ + 3λ ² − 5λ + 1 = 0.

5.3. Appendix

In practical calculation of the QE constant of a graph, we need to find the maximum of a certain quadratic function φ = φ(x1, x2, . . . , xn), f = (x1, x2, . . . , xn), subject to

\[\langle f, f \rangle = ||f||^2 = x_1^2 + x_2^2 + \dots + x_n^2 = 1,\]
\(\langle \mathbf{1}, f \rangle = x_1 + x_2 + \dots + x_n = 0.\)

We record some results used in the previous arguments for convenience. For the proofs we only need to apply the Schwartz inequality and the method of Lagrange multipliers.

Acknowledgements

NO is supported by JSPS KAKENHI 16H03939 and by JSPS Open Partnership Joint Research Project "Extremal graph theory, algebraic graph theory and mathematical approach to network science" (2017–18). AYZ is grateful for kind hospitality at the Graduate School of Information Sciences, Tohoku University and for the support by the Ministry of Research, Technology and Higher Education of the Republic of Indonesia through Sandwich-Like Program.

References

• [1] M. Aouchiche and P. Hansen, Distance spectra of graphs: a survey, Linear Algebra Appl. 458 (2014), 301–386.
• [2] R. Balaji and R.B. Bapat, On Euclidean distance matrices, Linear Algebra Appl. 424 (2007), 108–117.
• [3] R.B. Bapat, Graphs and Matrices, Springer, Hindustan Book Agency, New Delhi, 2010.
• [4] A.E. Brouwer, A.M. Cohen and A. Neumaier, Distance-Regular Graphs, Springer-Verlag, Berlin, 1989.
• [5] M. Bozejko, Positive-definite kernels, length functions on groups and noncommutative von ˙ Neumann inequality, Studia Math. 95 (1989), 107–118.
• [6] A. Gaovac, G. Jashari and M. Strunje, On the distance spectrum of a cycle, Aplikace Matematiky 30 (1985), 286–290.
• [7] U. Haagerup, An example of a nonnuclear C^∗ -algebra which has the metric approximation property, Invent. Math. 50 (1979), 279–293.
• [8] T.L. Hayden, R. Reams and J. Wells, Methods for constructing distance matrices and the inverse eigenvalue problem, Linear Algebra Appl. 295 (1999), 97–112.
• [9] A. Hora and N. Obata, Quantum Probability and Spectral Analysis of Graphs, Springer, 2007.
• [10] R. Horn and C.R. Johnson, Matrix Analysis, (2nd ed.), Cambridge University Press, Cambridge, 2013.
• [11] G. Jaklic and J. Modic, On properties of cell matrices. ˇ Appl. Math. Comput. 216 (2010), 2016–2023.
• [12] G. Jaklic and J. Modic, On Euclidean distance matrices of graphs, ˇ Electron. J. Linear Algebra 26 (2013), 574–589.
• [13] G. Jaklic and J. Modic, Euclidean graph distance matrices of generalizations of the star graph, ˇ Appl. Math. Comput. 230 (2014), 650–663.

• [14] P. Joziak, Conditionally strictly negative definite kernels, ´ Linear Multilinear Algebra 63 (2015), 2406–2418.
• [15] L. Liberti, G. Lavor, N. Maculan and A. Mucherino, Euclidean distance geometry and applications, SIAM Rev. 56 (2014), 3–69.
• [16] B. McKay: All small connected graphs, http://www.cadaeic.net/graphpics.htm
• [17] N. Obata, Positive Q-matrices of graphs, Studia Math. 179 (2007), 81–97.
• [18] N. Obata, Markov product of positive definite kernels and applications to Q-matrices of graph products, Colloq. Math. 122 (2011), 177–184.
• [19] N. Obata, Spectral Analysis of Growing Graphs A Quantum Probability Point of View, SpringerBriefs in Mathematical Physics, Vol. 20, Springer, Singapore, 2017.
• [20] I.J. Schoenberg, Remarks to Maurice Frechet's article, Sur la d ´ efinition axiomatique d'une ´ classe d'espace distancis vectoriellement applicable sur l'espace de Hilbert, ´ Ann. of Math. 36 (1935), 724–732.
• [21] I.J. Schoenberg, On certain metric spaces arising from Euclidean spaces by a change of metric and their imbedding in Hilbert space, Ann. of Math. 38 (1937), 787–793.
• [22] I.J. Schoenberg, Metric spaces and positive definite functions, Trans. Amer. Math. Soc. 44 (1938), 522–536.
• [23] G. Young and A.S. Householder, Discussion of a set of points in terms of their mutual distances, Psychometrika 3 (1938), 1–22.