Nobuaki Obataa,b

^aCenter for Data-driven Science and Artificial Intelligence,

Tohoku University, Sendai 980-8576, Japan

^bCombinatorial Mathematics Research Group,

Faculty of Mathematics and Natural Sciences,

Institut Teknologi Bandung, Jalan Ganesa 10 Bandung, Indonesia

obata@tohoku.ac.jp

We derive a formula for the QE constant of a complete multipartite graph and determine the complete multipartite graphs of non-QE class, namely, those which do not admit quadratic embeddings in Euclidean spaces. Moreover, we prove that there are exactly four primary non-QE graphs among the complete multipartite graphs.

Keywords: distance matrix, quadratic embedding, quadratic embedding constant (QEC), primary non-QE graph Mathematics Subject Classification : 05C50, 05C12, 05C76

DOI: 10.5614/ejgta.2023.11.2.14

1. Introduction

Realization of a graph G = (V, E) in a Euclidean space R ^N is of fundamental interest. In this paper, we focus on a particular realization called quadratic embedding, which traces back to the early works of Schoenberg [20, 21] and has been studied along with Euclidean distance geometry, see e.g., [1, 3, 6, 7, 10].

Let G = (V, E) be a graph, which is always assumed to be finite and connected. A map φ : V → R ^N is called a quadratic embedding of G if

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

Received: 13 June 2022, Revised: 25 September 2023, Accepted: 14 October 2023.

where the left-hand side is the square of the Euclidean distance and the right-hand side is the graph distance. A graph G is called of QE class or of non-QE class according as it admits a quadratic embedding or not. It follows from Schoenberg [20, 21] that a graph G admits a quadratic embedding if and only if the distance matrix D = [dG(x, y)] is conditionally negative definite, i.e., ⟨f, Df⟩ ≤ 0 for all real column vectors f indexed by V with ⟨1, f⟩ = 0, where 1 denotes the column vector of which entries are all one and ⟨·, ·⟩ is the canonical inner product. In this connection, a new numeric invariant of a graph was proposed in the recent papers [16, 18]. The quadratic embedding constant (QE constant for short) of a graph G is defined by

\[QEC(G) = \max\{\langle f, Df \rangle; \langle f, f \rangle = 1, \langle \mathbf{1}, f \rangle = 0\}, \tag{1}\]

where the right-hand side stands for the conditional maximum of the quadratic function ⟨f, Df⟩ with f running over a unit sphere determined by ⟨f, f⟩ = 1 and ⟨1, f⟩ = 0. By definition, a graph G is of QE class if and only if QEC(G) ≤ 0. An advantage of the QE constant is that (1) is determined explicitly or estimated finely by means of the method of Lagrange's multipliers. The QE constants are explicitly known for some special series of graphs, see also [4, 5, 12, 14, 15, 17, 19].

There are interesting questions both on graphs of QE class and on those of non-QE class. One of the important questions on non-QE graphs is to obtain a sufficiently rich list of non-QE graphs. The main purpose of this paper is to determine all complete multipartite graphs of non-QE class. In this paper we first derive a general formula for the QE constant of a complete multipartite graph.

Theorem 1.1 (Theorem 3.1). Let k ≥ 2 and m¹ ≥ m² ≥ · · · ≥ m^k ≥ 1. The QE constant of the complete k-partite graph K^m1,m2,...,m^k is given as follows.

(1) If m¹ = m2, we have

\[QEC(K_{m_1,m_2,...,m_k}) = -2 + m_1.\]

(2) If m¹ > m2, we have

\[QEC(K_{m_1,m_2,...,m_k}) = -2 - \alpha^*,\]

where α ∗ is the minimal solution to the equation

\[\sum_{i=1}^{k} \frac{m_i}{\alpha + m_i} = 0.\]

Moreover, −m¹ < α^∗ < −m2.

Using the above explicit formula, we determine all complete multipartite graphs with positive QE constants, that is, of non-QE class.

Theorem 1.2 (Theorem 4.1). Let k ≥ 2 and m¹ ≥ m² ≥ · · · ≥ m^k ≥ 1. Then the complete k-partite graph K^m1,m2,...,m^k is of non-QE class if and only if one of the following conditions is satisfied:

• (i) m¹ ≥ 3 and m² ≥ 2,
• (ii) k ≥ 3, m¹ ≥ 5 and m² = · · · = m^k = 1,

(iii) \[k \ge 4\], \(m_1 = 4\) and \(m_2 = \cdots = m_k = 1\),
(iv) \(k \ge 5\), \(m_1 = 3\) and \(m_2 = \cdots = m_k = 1\).

If a graph H is isometrically embedded in a graph G, we have QEC(H) ≤ QEC(G). Hence, if G contains a non-QE subgraph H isometrically, then G is of non-QE class too. Thus, upon classifying graphs of non-QE class it is important to specify a primary non-QE graph, that is, a non-QE graph G which does not contain a non-QE graph H as an isometrically embedded proper subgraph.

By Theorem 1.2 there are four families of complete multipartite graphs of non-QE class. From each family a primary one is specified as follows.

Theorem 1.3 (Theorem 4.2). Among the complete multipartite graphs there are four primary non-QE graphs which are listed with their QE constants as follows:

QEC\[(K_{3,2}) = 2/5\],
QEC\((K_{5,1,1}) = 1/7\),
QEC\((K_{4,1,1,1}) = 2/7\),
QEC\((K_{3,1,1,1,1}) = 1/7\).

Moreover, any complete multipartite graph of non-QE class contains at least one of the above four primary non-QE graphs as an isometrically embedded subgraph.

This paper is organized as follows. In Section 2 we prepare basic notions and notations, for more details see [15, 18]. In Section 3 we prove the main formula for the QE constants of complete multipartite graphs (Theorem 1.1) and show some examples. In Section 4 we determine all complete multipartite graphs of non-QE class (Theorem 1.2) and specify primary ones (Theorem 1.3). All primary non-QE graphs on six or fewer vertices are already determined [17]. As a result, we find three new primary non-QE graphs on seven vertices.

The QE constant is not only useful for judging whether nor not a graph G is of QE-class but also interesting as a possible scale of classifying graphs [4]. Moreover, the QE constant is interesting from the point of view of spectral analysis of distance matrices, for distance spectra see e.g., [2, 8, 9]. In fact, QEC(G) lies between the largest and the second largest eigenvalues of the distance matrix D in such a way that λ2(D) ≤ QEC(G) < λ1(D). In this line, an interesting question is to characterize graphs such that λ2(D) = QEC(G). The work is now in progress.

2. Quadratic embedding of graphs

2.1. Distance matrices

A graph G = (V, E) is a pair of a non-empty set V of vertices and a set E of edges, where V is assumed to be a finite set throughout the paper. For x, y ∈ V we write x ∼ y if {x, y} ∈ E. A graph is called connected if any pair of vertices x, y ∈ V there exists a finite sequence of vertices x0, x1, . . . , x^m ∈ V such that x = x⁰ ∼ x¹ ∼ · · · ∼ x^m = y. In that case the sequence of vertices is called a walk from x to y of length m. Unless otherwise stated, by a graph we mean a finite connected graph throughout this paper.

Let G = (V, E) be a graph. For x, y ∈ V with x ̸= y let dG(x, y) denote the length of a shortest walk connecting x and y. By definition we set dG(x, x) = 0. Then dG(x, y) becomes a metric on V , which we call the graph distance. The distance matrix of G is defined by

\[D = [d_G(x, y)]_{x, y \in V},\]

which is a matrix with index set V × V . For notational simplicity we sometimes write d(x, y) for dG(x, y) when there is no danger of confusion.

Let C(V ) be the linear space of R-valued functions f on V . We always identify f ∈ C(V ) with a column vector [fx]x∈^V through f^x = f(x). The canonical inner product on C(V ) is defined

\[\langle f, g \rangle = \sum_{x \in V} f(x)g(x), \qquad f, g \in C(V).\]

The distance matrix D induces a linear transformation on C(V ) by matrix multiplication as usual. Since D is symmetric, we have ⟨f, Dg⟩ = ⟨Df, g⟩.

2.2. Quadratic embedding

A quadratic embedding of a graph G = (V, E) in a Euclidean space R ^N is a map φ : V → R N satisfying

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

where the left-hand side is the square of the Euclidean distance. A graph G is called of QE class or of non-QE class according as it admits a quadratic embedding or not.

A graph H = (V ′ , E′ ) is called a subgraph of G = (V, E) if V ′ ⊂ V and E ′ ⊂ E. By our convention both G and H are assumed to be connected and hence admit graph distances of their own. We say that H is isometrically embedded in G if

\[d_H(x,y) = d_G(x,y), \qquad x,y \in V'.\]

In that case we write H ,→ G.

Lemma 2.1. Let G = (V, E) and H = (V ′ , E′ ) be graphs and assume that H is isometrically embedded in G, that is, H ,→ G.

• (1) If G is of QE class, so is H.
• (2) If H is of non-QE class, so is G.

Proof. Obvious by definition.

We say that a graph of non-QE class is primary if it contains no isometrically embedded proper subgraphs of non-QE class. In view of Lemma 2.1, for classifying graphs of non-QE class it is essential to explore primary non-QE graphs.

We mention a simple and useful criterion for isometric embedding. Recall that the diameter of a graph G = (V, E) is defined by

\[diam(G) = \max\{d_G(x, y); x, y \in V\}.\]

Lemma 2.2. Let G = (V, E) be a graph and H = (V ′ , E′ ) a subgraph.

• (1) If H is isometrically embedded in G, then H is an induced subgraph of G.
• (2) If H is an induced subgraph of G and diam (H) ≤ 2, then H is isometrically embedded in G.
• Proof. (1) By assumption dH(x, y) = dG(x, y) for all x, y ∈ V ′ . In particular, for x, y ∈ V ′ dH(x, y) = 1 if and only if dG(x, y)=1. Therefore, if two vertices x, y ∈ V ′ are adjacent in G, so are in H. This means that H is an induced subgraph of G.
• (2) We will prove that dH(x, y) = dG(x, y) for all x, y ∈ V ′ . As dH(x, y) ≤ 2 for x, y ∈ V ′ by assumption, we consider three cases. If dH(x, y) = 0, obviously dG(x, y) = 0. Suppose that dH(x, y) = 1. Then x and y are adjacent in H, so are in G and dG(x, y) = 1. Suppose that dH(x, y) = 2. Since H is a subgraph of G, we have dG(x, y) ≤ dH(x, y) ≤ 2. If dG(x, y) = 0, we have x = y and dH(x, y) = 0, which is contradiction. If dG(x, y) = 1, then x and y are adjacent in G, so are in H since H is an induced subgraph of G. We then obtain dH(x, y) = 1, which is again contradiction. Therefore, we have dG(x, y) = 2 and dH(x, y) = dG(x, y) holds.

2.3. Quadratic embedding constants

Let G = (V, E) be a graph with |V | ≥ 2. The quadratic embedding constant (QE constant for short) of G is defined by

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

where 1 ∈ C(V ) is defined by 1(x) = 1 for all x ∈ V .

It follows from Schoenberg [20, 21] that a graph G admits a quadratic embedding if and only if the distance matrix D = [dG(x, y)] is conditionally negative definite, i.e., ⟨f, Df⟩ ≤ 0 for all f ∈ C(V ) with ⟨1, f⟩ = 0. Hence a graph G is of QE class (resp. of non-QE class) if and only if QEC(G) ≤ 0 (resp. QEC(G) > 0). The idea of QE constant was proposed in [18], where a standard method of computing the QE constants is established on the basis of Lagrange's multipliers.

Lemma 2.3. Let G = (V, E) and H = (V ′ , E′ ) be two graphs with |V | ≥ 2 and |V ′ | ≥ 2. If H is isometrically embedded in G, we have

\[QEC(H) \leq QEC(G)\].

As the distance matrix of H becomes a principal submatrix of the distance matrix of G, the proof is straightforward, see also [18]. Note also that Lemma 2.1 follows immediately from Lemma 2.3.

For later reference we recall some concrete values of the QE constants. Further examples are found in [5, 12, 15, 16, 19].

Example 2.1 ([18]). For the complete graph Kⁿ with n ≥ 2 we have

\[QEC(K_n) = -1.\]

Conversely, any graph G with QEC(G) = −1 is necessarily a complete graph [4]. Moreover, for any graph G on two or more vertices we have QEC(G) ≥ −1.

Example 2.2 ([18]). For the cycles on odd number of vertices we have

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

and for those on even number of vertices we have

\[QEC(C_{2n}) = 0, \qquad n \ge 2.\]

Example 2.3 ([14]). For the paths Pⁿ with n ≥ 2 we have

\[QEC(P_n) = -\left(1 + \cos\frac{\pi}{n}\right)^{-1}.\]

Example 2.4 ([18]). For the complete bipartite graph Km,n with m ≥ 1 and n ≥ 1 we have

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

The above formula will be generalized to the complete multipartite graphs in Subsection 3.2, see Theorem 3.1.

Example 2.5 ([12]). For m ≥ 1 and n ≥ 1 the graph join K¯^m + Kⁿ is called the complete split graph. We have

QEC\[(\bar{K}_m + K_n) = \frac{(m-2)(n-1)-2}{m+n}\].

For a more general result on the graph join of regular graphs, see [12].

Example 2.6. A table of the QE constants of graphs on n ≤ 5 vertices is available [18]. We see directly from the table that all graphs on n ≤ 4 vertices are of QE-class, and that there are 21 graphs on five vertices among which two are of non-QE class. Those graphs are shown in Figure 1, where Gn-x stands for the graph on n vertices with number x in the list of small graphs due to McKay [13]. Their QE constants are given by

QEC(G5-10) = \[\frac{2}{5}\], QEC(G5-17) = \(\frac{4}{11 + \sqrt{161}} \approx 0.1689\).

Both are primary non-QE graphs since all graphs on four vertices are of QE class. Note that G5-10 is the complete bipartite graph K3,2.

3. Complete multipartite graphs

3.1. Definition and basic properties

For k ≥ 2 let V1, V2, . . . V^k be mutually disjoint non-empty finite sets. Setting

\[V = \bigcup_{i=1}^{k} V_i, \qquad E = \bigcup_{i \neq j} \{ \{x, y\} ; x \in V_i, y \in V_j \},\]

Complete multipartite graphs of non-QE class | Nobuaki Obata

Figure 1. Non-QE graphs: G5-10 (left) and G5-17 (right)

we obtain a graph G = (V, E), which is called a complete k-partite graph with parts V1, V2, . . . , V^k and is denoted by KM(V1, V2, . . . , Vk). A complete multipartite graph is a complete k-partite graph for some k ≥ 2.

For k ≥ 2 a complete k-partite graph is determined (up to graph isomorphisms) by the sequence m1, m2, . . . , m^k defined by mⁱ = |Vⁱ | and is denoted by

\[K_{m_1, m_2, \dots, m_k} = KM(V_1, V_2, \dots, V_k).\] (2)

Without loss of generality we may assume that m¹ ≥ m² ≥ · · · ≥ m^k ≥ 1. For simplicity we write K1(k) for K1,1,...,¹ ("1" appears k times). Obviously,

\[K_{1(k)} = K_{1,1,\dots,1} = K_k\]

which is nothing else but the complete graph on k vertices. Overusing our notation for the case of k = 1 we understand that KM(V1) is the empty graph on V1, that is the complement to the complete graph K^m1 so that

\[KM(V_1) = \bar{K}_{m_1}. (3)\]

We note that (2) is not valid for k = 1.

For later use we list some basic properties of complete multipartite graphs, of which verification is straightforward and is omitted.

Lemma 3.1. Let k ≥ 2 and m¹ ≥ m² ≥ · · · ≥ m^k ≥ 1. Then diam(K^m1,m2,...,m^k ) = 2 unless m¹ = m² = · · · = m^k = 1.

Lemma 3.2. Let k ≥ 2 and let V1, V2, . . . , V^k be mutually disjoint non-empty finite sets. Consider an arbitrary partition:

\[\{V_1, V_2, \dots V_k\} = \{U_1, \dots, U_p\} \cup \{U'_1, \dots, U'_q\},\\]

where p ≥ 1, q ≥ 1 and p + q = k. Then we have

\[KM(V_1, V_2, \dots V_k) = KM(U_1, U_2, \dots U_p) + KM(U'_1, U'_2, \dots U'_q),\]

where the right-hand side is the graph join.

For example, we have

\[\begin{split} K_{m_1,m_2} &= \bar{K}_{m_1} + \bar{K}_{m_2}, \\ K_{m_1,m_2,m_3} &= \bar{K}_{m_2} + K_{m_1,m_3}, \\ K_{m_1,m_2,m_3,m_4} &= K_{m_1,m_3} + K_{m_2,m_4}, \quad \text{etc.,} \end{split}\]

where (3) is taken into account.

Next we study a subgraph of \(KM(V_1,V_2,\ldots V_k)\). For \(2\leq p\leq k\) let \(U_1,U_2,\ldots,U_p\) be p parts chosen from \(V_1,V_2,\ldots V_k\). For each \(1\leq i\leq p\) let \(U_i'\subset U_i\) be a non-empty subset. It is then easy to see that

\[KM(U'_1, U'_2, \dots U'_p) \hookrightarrow KM(V_1, V_2, \dots V_k).\]

This isometric embedding is stated as follows.

Lemma 3.3. Let \(m_1 \ge m_2 \ge \cdots \ge m_k \ge 1\) and \(n_1 \ge n_2 \ge \cdots \ge n_p \ge 1\) be two sequences with \(k \ge 2\) and \(p \ge 2\). If there exist \(1 \le i_1 < i_2 < \cdots < i_p \le k\) such that

\[n_1 \leq m_{i_1}, \quad n_2 \leq m_{i_2}, \quad \dots, \quad n_p \leq m_{i_p},\]

then we have

\[K_{n_1,n_2,\ldots,n_p} \hookrightarrow K_{m_1,m_2,\ldots,m_k}.\]

Obviously, any induced subgraph of \(KM(V_1, V_2, \dots V_k)\) is of the form \(KM(U_1', U_2', \dots U_p')\) as mentioned above. With the help of Lemma 2.2 we come to the following

Lemma 3.4. Let H be a subgraph of a complete k-partite graph \(K_{m_1,m_2,...,m_k}\). If H is a graph on two or more vertices and is isometrically embedded in \(K_{m_1,m_2,...,m_k}\), then H is a complete p-partite graph \(K_{n_1,n_2,...,n_p}\) of the form as in Lemma 3.3.

3.2. Calculating QE constants

Throughout this subsection, letting \(k \geq 2\) and \(m_1 \geq m_2 \geq \cdots \geq m_k \geq 1\) be fixed, we set

\[G=K_{m_1,m_2,\ldots,m_k}\].

Our goal is to obtain an explicit formula for QEC(G). Since \(1 \leq diam(G) \leq 2\) the following general result is useful.

Proposition 3.1. [16, Proposition 2.1] Let G be a graph with \(1 \leq \operatorname{diam}(G) \leq 2\). Let A be the adjacency matrix of G and set

\[\alpha_{\min} = \min\{\langle f, Af \rangle \; ; \; \langle f, f \rangle = 1, \; \langle \mathbf{1}, f \rangle = 0\}.\] (4)

Then we have

\[QEC(G) = -2 - \alpha_{\min}.\]

Now let A be the adjacency matrix of \(G = K_{m_1, m_2, \dots, m_k}\). Then A is written in a block matrix form:

\[A = \begin{bmatrix} 0 & J & J & \dots & J \\ J & 0 & J & \dots & J \\ \vdots & \vdots & \ddots & & \vdots \\ J & J & \dots & 0 & J \\ J & J & \dots & J & 0 \end{bmatrix} = J - \begin{bmatrix} J & 0 & 0 & \dots & 0 \\ 0 & J & 0 & \dots & 0 \\ \vdots & \vdots & \ddots & & \vdots \\ 0 & 0 & \dots & J & 0 \\ 0 & 0 & \dots & 0 & J \end{bmatrix},\] (5)

where J is a matrix of which entries are all one and the size is understood in the context. For example, in the last block matrix in (5) J's appear as diagonal entries. We understand naturally that their sizes are \(m_1 \times m_1, \ldots, m_k \times m_k\) from left top to right bottom.

We will find the conditional minimum \(\alpha_{\min}\) in (4). According to the block matrix form of the adjacency matrix A in (5), any \(f \in C(V) \cong \mathbb{R}^{m_1 + \dots + m_k}\) is written as

\[f = \begin{bmatrix} f_1 \\ f_2 \\ \vdots \\ f_k \end{bmatrix}, \qquad f_i = \begin{bmatrix} f_{i1} \\ f_{i2} \\ \vdots \\ f_{im_i} \end{bmatrix} \in \mathbb{R}^{m_i}, \qquad 1 \le i \le k.\]

Then we have

\[\langle f, Af \rangle = \langle f, Jf \rangle - \sum_{i=1}^{k} \langle f_i, Jf_i \rangle = \langle \mathbf{1}, f \rangle^2 - \sum_{i=1}^{k} \langle \mathbf{1}, f_i \rangle^2.\] (6)

Upon applying the method of Lagrange's multiplier we set

\[\varphi(f, \alpha, \beta) = \langle f, Af \rangle - \alpha(\langle f, f \rangle - 1) - \beta \langle \mathbf{1}, f \rangle.\]

By general theory we know that the conditional minimum (4) is attained at a certain stationary point. Let S be the set of all stationary points \((f, \alpha, \beta)\), that is, the set of solutions to

\[\frac{\partial \varphi}{\partial f_{ij}} = \frac{\partial \varphi}{\partial \alpha} = \frac{\partial \varphi}{\partial \beta} = 0, \qquad 1 \le i \le k, \quad 1 \le j \le m_i. \tag{7}\]

After simple calculus (7) becomes the following system of equations:

\[(J+\alpha)f_i = -\frac{\beta}{2}\mathbf{1}, \qquad 1 \le i \le k, \tag{8}\]

\[\langle f, f \rangle = \sum_{i=1}^{k} \langle f_i, f_i \rangle = 1,\] (9)

\[\langle \mathbf{1}, f \rangle = \sum_{i=1}^{k} \langle \mathbf{1}, f_i \rangle = 0.\] (10)

For \(1 \le s \le m_i\) the sth entry of the left-hand side of (8) is given by

\[((J+\alpha)f_i)_s = \sum_{t=1}^{m_i} ((J)_{st} + \alpha \delta_{st}) f_{it} = \langle \mathbf{1}, f_i \rangle + \alpha f_{is}.\]

Thus (8) is equivalent to

\[\langle \mathbf{1}, f_i \rangle + \alpha f_{is} = -\frac{\beta}{2}, \qquad 1 \le s \le m_i, \quad 1 \le i \le k.\] (11)

As a result, S is the set of all solutions \((f = [f_i], \alpha, \beta)\) to the equations (11), (9) and (10). For convenience we denote by \(S_A\) the set of all \(\alpha \in \mathbb{R}\) appearing in S, that is, \((f, \alpha, \beta) \in S\) for some f and g.

Lemma 3.5. For any \((f, \alpha, \beta) \in \mathcal{S}\) we have \(\langle f, Af \rangle = \alpha\). Therefore,

\[\alpha_{\min} = \min \mathcal{S}_A\].

Proof. Let \((f = [f_i], \alpha, \beta) \in \mathcal{S}\). Noting that the equations (8)–(10) are fulfilled, we have

\[\langle f_i, Jf_i \rangle = \left\langle f_i, -\alpha f_i - \frac{\beta}{2} \mathbf{1} \right\rangle = -\alpha \langle f_i, f_i \rangle - \frac{\beta}{2} \langle \mathbf{1}, f_i \rangle\]

and hence

\[\sum_{i=1}^{k} \langle f_i, J f_i \rangle = -\alpha \sum_{i=1}^{k} \langle f_i, f_i \rangle - \frac{\beta}{2} \sum_{i=1}^{k} \langle \mathbf{1}, f_i \rangle = -\alpha.\]

On the other hand, by (10) we have

\[\langle f, Jf \rangle = \langle \mathbf{1}, f \rangle^2 = 0.\]

Consequently, we see from (6) that

\[\langle f, Af \rangle = \langle f, Jf \rangle - \sum_{i=1}^{k} \langle f_i, Jf_i \rangle = 0 - (-\alpha) = \alpha,\]

as desired. The assertion in the second half is then apparent.

In order to study \(S_A\) we come back to the equations (8)–(10), where (8) is equivalent to (11).

Lemma 3.6. If \((\xi_1, \dots, \xi_k, \alpha, \beta) \in \mathbb{R}^k \times \mathbb{R} \times \mathbb{R}\) satisfies

\[(m_i + \alpha)\xi_i = -\frac{\beta}{2}, \qquad 1 \le i \le k, \tag{12}\]

\[\sum_{i=1}^{k} m_i \xi_i^2 = 1,\tag{13}\]

\[\sum_{i=1}^{k} m_i \xi_i = 0, \tag{14}\]

then, setting \(f_i = \xi_i \mathbf{1}\), we have \((f = [f_i], \alpha, \beta) \in \mathcal{S}\). Conversely, for any \((f = [f_i], \alpha, \beta) \in \mathcal{S}\) with \(\alpha \neq 0\) there exist \(\xi_1, \ldots, \xi_k \in \mathbb{R}\) such that \(f_i = \xi_i \mathbf{1}\) and (12)–(14) are satisfied.

Proof. It is straightforward to show that \((f = [f_i], \alpha, \beta)\) with \(f_i = \xi_i \mathbf{1}\) satisfies (11), (9) and (10) under conditions (12)–(14). We prove the converse. Suppose that \(\alpha \neq 0\) and \((f = [f_i], \alpha, \beta)\) is a solution to (11), (9) and (10). In view of \(\alpha \neq 0\) we see from (11) that \(f_{is}\) is constant independently of \(1 \leq s \leq m_i\). In other words, \(f_i\) is a constant multiple of \(\mathbf{1}\), say \(f_i = \xi_i \mathbf{1}\) with \(\xi_i \in \mathbb{R}\). Then equations (11), (9) and (10) are reduced to the equations (12), (13) and (14), respectively.

Lemma 3.7. If α ∈ S^A and α ̸∈ {0, −m1, −m2, . . . , −mk}, then α satisfies

\[\sum_{i=1}^{k} \frac{m_i}{\alpha + m_i} = 0. {15}\]

Conversely, if α ∈ R satisfies (15), then α ∈ SA.

Proof. Let α ∈ S^A with α ̸∈ {0, −m1, −m2, . . . , −mk}. Then (f, α, β) ∈ S for some f and β so that the equations (11), (9) and (10) are satisfied. By Lemma 3.6 there exist ξ1, . . . , ξ^k ∈ R such that fⁱ = ξi1 such that (f = [fⁱ ], α, β) fulfills (12)–(14). From (12) we have

\[\xi_i = -\frac{\beta}{2} \frac{1}{\alpha + m_i}, \qquad 1 \le i \le k. \tag{16}\]

Then (13) and (14) become

\[\frac{\beta^2}{4} \sum_{i=1}^k \frac{m_i}{(\alpha + m_i)^2} = 1,\tag{17}\]

\[-\frac{\beta}{2} \sum_{i=1}^{k} \frac{m_i}{\alpha + m_i} = 0, \tag{18}\]

respectively. We see from (17) that β ̸= 0 and then from (18) we obtain (15).

For the converse assertion let α be a solution to (15). Noting that α ̸∈ {−m1, −m2, . . . , −mk}, we define ξⁱ by (16) and set fⁱ = ξi1. Choosing β satisfying (17), we see that (f = [fⁱ ], α, β) ∈ S and hence α ∈ SA.

Lemma 3.8. If m¹ = m2, then −m¹ ∈ SA.

Proof. It is straightforward to see that equations (12)–(14) are fulfilled by

\[\xi_1 = \frac{1}{\sqrt{2m_1}}, \qquad \xi_2 = -\frac{1}{\sqrt{2m_1}}, \qquad \xi_i = 0, \quad 3 \le i \le k,\] \[\alpha = -m_1, \qquad \beta = 0.\]

It then follows from Lemma 3.6 that (f = [fⁱ ], α, β) with fⁱ = ξi1, α = −m¹ and β = 0 belongs to S. Hence −m¹ ∈ SA.

Lemma 3.9. If m¹ > m2, then −m¹ ̸∈ SA.

Proof. Suppose that −m¹ ∈ SA. Then (f, −m1, β) ∈ S for some f and β. Since α = −m¹ ̸= 0, by Lemma 3.6 there exist ξ1, . . . , ξ^k ∈ R satisfying (12)–(14). Note that (12) becomes

\[(m_i - m_1)\xi_i = -\frac{\beta}{2}, \qquad 1 \le i \le k.\] (19)

Putting i = 1, we obtain β = 0 and (19) becomes

\[(m_i - m_1)\xi_i = 0, \qquad 1 \le i \le k.\] (20)

Since m¹ > m² ≥ m³ ≥ · · · ≥ m^k ≥ 1 by assumption, we see from (20) that ξⁱ = 0 for 2 ≤ i ≤ k. It then follows from (14) that ξ¹ = 0 too. Thus we obtain ξⁱ = 0 for all 1 ≤ i ≤ k, which contradicts (13). Consequently, −m¹ ̸∈ SA.

We are now in a position to sum up the above argument.

Proposition 3.2. Let k ≥ 2 and m¹ ≥ m² ≥ · · · ≥ m^k ≥ 1. Let A be the adjacency matrix of the complete k-partite graph K^m1,m2,...,m^k and set

\[\alpha_{\min} = \min\{\langle f, Af \rangle \; ; \; \langle f, f \rangle = 1, \; \langle \mathbf{1}, f \rangle = 0\}.\]

• (1) If m¹ = m2, then αmin = −m1.
• (2) If m¹ > m2, then αmin = α ∗ , where α ∗ is the minimal solution to

\[\sum_{i=1}^{k} \frac{m_i}{\alpha + m_i} = 0. {(21)}\]

Moreover, −m¹ < α^∗ < −m2.

Proof. We set

\[\psi(\alpha) = \sum_{i=1}^{k} \frac{m_i}{\alpha + m_i} \,.\]

It follows from Lemma 3.7 that

\[S_A \subset \{0, -m_1, \dots, -m_k\} \cup \{\alpha \in \mathbb{R} ; \psi(\alpha) = 0\}, \tag{22}\]

where {α ∈ R ; ψ(α) = 0} = ∅ may occur. Since ψ(α) < 0 for all α < −m1, we have {α ∈ R ; ψ(α) = 0} ⊂ (−m1, +∞). Therefore, the minimum of the right-hand side of (22) is −m1.

• (1) By Lemma 3.8 we know that −m¹ ∈ SA. We then see from (22) that min S^A = −m¹ so that αmin = −m1.
• (2) We first note from m¹ > m² that ψ(α) = 0 has a solution. Hence the minimal solution α ∗ certainly exists and, as is easily verified by simple calculus, we have −m¹ < α^∗ < −m2. Moreover, α ^∗ ∈ S^A by Lemma 3.8. On the other hand, −m¹ ̸∈ S^A by Lemma 3.9. Therefore, min S^A = α ∗ so that αmin = α ∗ .

We now come to the first main result.

Theorem 3.1 (Theorem 1.1). Let k ≥ 2 and m¹ ≥ m² ≥ · · · ≥ m^k ≥ 1.

• (1) If m¹ = m2, we have QEC(K^m1,m2,...,m^k ) = −2 + m1.
• (2) If m¹ > m2, we have QEC(K^m1,m2,...,m^k ) = −2 − α ∗ , where α ∗ is the minimal solution to (21). Moreover, −m¹ < α^∗ < −m2.

Proof. Straightforward from Propositions 3.1 and 3.2.

3.3. Some special cases

We apply Theorem 3.1 to some special cases.

Example 3.1 (See Example 2.4). The QE constant of a bipartite graph Km,n is obtained by simple algebra. If m = n ≥ 1, we have

\[QEC(K_{m,m}) = -2 + m. (23)\]

If m > n, we have

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

The former formula (23) is reproduced by setting m = n in the latter (24). Moreover, since the right-hand side of (24) is symmetric in m and n, we see that (24) is valid for any m ≥ 1 and n ≥ 1. Example 3.2. The QE constant of a tripartite graph Kl,m,n is obtained by simple algebra. If l = m ≥ n ≥ 1, we have

\[QEC(K_{l,l,n}) = -2 + l. (25)\]

Consider the case of l > m ≥ n ≥ 1. The equation (21) becomes

\[\frac{l}{\alpha+l} + \frac{m}{\alpha+m} + \frac{n}{\alpha+n} = 0\]

and the minimal solution is given by

\[\alpha^* = -\frac{lm + mn + nl + \sqrt{(lm + mn + nl)^2 - 3lmn(l + m + n)}}{l + m + n}.\]

Then we have

QEC\[(K_{l,m,n}) = -2 + \frac{lm + mn + nl + \sqrt{(lm + mn + nl)^2 - 3lmn(l + m + n)}}{l + m + n}\]. (26)

By simple algebra we see that (25) is reproduced from (26) by setting l = m. Moreover, since the right-hand side of (26) is symmetric in l, m and n, we conclude that the formula (26) is valid for any l ≥ 1, m ≥ 1 and n ≥ 1.

Example 3.3 (see Example 2.5). Let m ≥ 1 and n ≥ 1. The (n+1)-partite graph Km,1(n) coincides with the graph join K¯^m + Kn, which is known as a complete split graph. The QE constant is obtained by simple algebra. If m = 1, we have

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

In fact, K1,1(n) = Kn+1 is the complete graph and the result is mentioned also in Example 2.1. Assume that m > 1. The minimal solution to

\[\frac{m}{\alpha+m} + \frac{n}{\alpha+1} = 0\]

is given by α ^∗ = −m(n + 1)/(m + n) and we then come to

QEC\[(K_{m,1(n)}) = -2 - \alpha^* = -2 + \frac{m(n+1)}{m+n} = \frac{(m-2)(n-1)-2}{m+n}\]. (28)

Note that (27) is reproduced from (28) by setting m = 1. Hence the formula (28) is valid for any m ≥ 1 and n ≥ 1.

Example 3.4. For n ≥ 2 the complete multipartite graph K2(n) is called a cocktail party graph or a hyperoctahedral graph. A straightforward application of Theorem 3.1 yields

\[QEC(K_{2(n)}) = 0.\]

Note that K2(n) is obtained by deleting n disjoint edges from the complete graph K2n. It is known [18] that the QE constant of a graph obtained by deleting two or more disjoint edges from a complete graph is zero.

4. Primary non-QE graphs

4.1. Complete multipartite graphs of non-QE class

With the help of Theorem 3.1 (Theorem 1.1 in Introduction) all complete multipartite graphs of non-QE class are determined.

Let k ≥ 2 and m¹ ≥ m² ≥ · · · ≥ m^k ≥ 1. If m¹ ≥ 3 and m² ≥ 2, then K^m1,m2,...,m^k is of non-QE class because K3,² ,→ K^m1,m2,...,m^k and K3,² is of non-QE class. We will examine the rest cases.

(Case 1) m¹ ≥ 3 and m² = 1. In that case we have m¹ > m² = · · · = m^k = 1 so that K^m1,m2,...,m^k = K^m1,1(k−1) becomes a complete split graph. Using the formula (28) in Example 3.3, we obtain

QEC\[(K_{m_1,1(k-1)}) = \frac{(m_1 - 2)(k - 2) - 2}{m_1 + k - 1}\].

Hence QEC(K^m1,1(k−1)) > 0 if and only if one of the following three conditions are fulfilled: (i) k ≥ 3 and m¹ ≥ 5; (ii) k ≥ 4 and m¹ ≥ 4; (iii) k ≥ 5 and m¹ ≥ 3.

(Case 2) m¹ = 2. If m¹ = m2, we see from Theorem 3.1 that

\[QEC(K_{2,2,m_3,...,m_k}) = -2 + m_1 = 0.\]

If m¹ > m2, we have m² = · · · = m^k = 1. Applying the formula (28), we have

\[QEC(K_{2,1(k-1)}) = -\frac{2}{k+1} < 0.\]

(Case 3) m¹ = 1. In that case we have m² = · · · = m^k = 1 so that K1(k) = K^k becomes a complete graph. We know that QEC(K1(k)) = −1.

Thus, there are no non-QE graphs in Cases 2 and 3. Summing up the above argument, we claim the following

Theorem 4.1 (Theorem 1.2). Let \(m_1 \ge m_2 \ge \cdots \ge m_k \ge 1\) with \(k \ge 2\). Then the complete k-partite graph \(K_{m_1,m_2,\ldots,m_k}\) is of non-QE class if and only if one of the following conditions is satisfied:

• (i) \(m_1 \ge 3\) and \(m_2 \ge 2\),
• (ii) \(k \ge 3\), \(m_1 \ge 5\) and \(m_2 = \cdots = m_k = 1\),
• (iii) \(k \ge 4\), \(m_1 = 4\) and \(m_2 = \cdots = m_k = 1\),
• (iv) \(k \ge 5\), \(m_1 = 3\) and \(m_2 = \cdots = m_k = 1\).

The four families of complete multipartite graphs in Theorem 4.1 are mutually exclusive. With the help of Lemma 3.4, from each family we find a primary non-QE graph. The result is stated in the following

Theorem 4.2 (Theorem 1.3). Among the complete multipartite graphs there are four primary non-QE graphs, which are listed with their QE constants as follows:

QEC\[(K_{3,2}) = 2/5\],
QEC\((K_{5,1,1}) = 1/7\),
QEC\((K_{4,1,1,1}) = 2/7\),
QEC\((K_{3,1,1,1,1}) = 1/7\).

Moreover, any complete multipartite graph of non-QE class contains at least one of the above four primary non-QE graphs as an isometrically embedded subgraph.

4.2. Exploring primary non-QE graphs

In Theorem 4.2 we find three primary non-QE graphs on seven vertices. Note also that they are all complete split graphs:

\[K_{5,1,1} = \bar{K}_5 + K_2 = \text{G7-351},\]
\(K_{4,1,1,1} = \bar{K}_4 + K_3 = \text{G7-774},\)
\(K_{3,1,1,1,1} = \bar{K}_3 + K_4 = \text{G7-845},\)

where Gn-x stands for the graph on n vertices with number x in the list of small graphs due to McKay [13].

On the other hand, as is mentioned in Example 2.6, there are exactly two primary non-QE graphs on five vertices. Moreover, it is proved [17] that there are exactly three primary non-QE graphs on six vertices. They are the graphs G6-30, G6-60 and G6-84, see Figure 2. For the readers' convenience, we record their QE constants:

\[\begin{aligned} &\text{QEC}(\text{G6-30}) = \frac{-4 + \sqrt{19}}{3} \approx 0.1196, \\ &\text{QEC}(\text{G6-60}) = \lambda_{60}^* \approx 0.2034, \\ &\text{QEC}(\text{G6-84}) = \lambda_{84}^* \approx 0.1313, \end{aligned}\]

where \(\lambda_{60}^*\) is the unique positive root of \(5\lambda^3 + 26\lambda^2 + 24\lambda - 6 = 0\), and \(\lambda_{84}^*\) is the unique positive root of \(3\lambda^4 + 14\lambda^3 + 18\lambda^2 + 5\lambda - 1 = 0\).

In this line an interesting question is to systematically construct primary non-QE graphs and to study the distribution of their QE constants.

Figure 2. Primary non-QE graphs: G6-30, G6-60 and G6-84 (from left to right)

Acknowledgement

This work was carried out during the author's stay as an adjunct professor at Institut Teknologi Bandung (ITB) in 2023–2024, and he expresses heartfelt gratitude to Professor E. T. Baskoro for his gracious hospitality. This work is also supported in part by JSPS Grant-in-Aid for Scientific Research No. 19H01789 and No. 23K03126. Appreciation is extended to the referees for their valuable comments which improved the paper.

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.
• [3] R. Balaji and R.B. Bapat, On Euclidean distance matrices, Linear Algebra Appl. 424 (2007), 108–117.
• [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.
• [5] W. Irawan and K.A. Sugeng, Quadratic embedding constants of hairy cycle graphs, Journal of Physics: Conference Series 1722 (2021) 012046.
• [6] G. Jaklic and J. Modic, On Euclidean distance matrices of graphs, ˇ Electron. J. Linear Algebra 26 (2013), 574–589.
• [7] G. Jaklic and J. Modic, Euclidean graph distance matrices of generalizations of the star graph, ˇ Appl. Math. Comput. 230 (2014), 650–663.
• [8] Y.L. Jin and X.D. Zhang, Complete multipartite graphs are determined by their distance spectra, Linear Algebra Appl. 448 (2014), 285–291.
• [9] H. Lin, Y. Hong, J. Wang, and J. Shub, On the distance spectrum of graphs, Linear Algebra Appl. 439 (2013), 1662–1669.

• [10] L. Liberti, G. Lavor, N. Maculan, and A. Mucherino, Euclidean distance geometry and applications, SIAM Rev. 56 (2014), 3–69.
• [11] R. Liu, J. Xue, and L. Guo. On the second largest distance eigenvalue of a graph, arXiv:1504.04225v1, 2015.
• [12] Z. Z. Lou, N. Obata, and Q. X. Huang, Quadratic embedding constants of graph joins, Graphs and Combinatorics 38 (2022), 161.
• [13] B. McKay, All small connected graphs, http://www.cadaeic.net/graphpics.htm (online 2022.06.10)
• [14] W. Młotkowski, Quadratic embedding constants of path graphs, Linear Algebra Appl. 644 (2022), 95–107.
• [15] W. Młotkowski and N. Obata, On quadratic embedding constants of star product graphs, Hokkaido Math. J. 49 (2020), 129–163.
• [16] N. Obata, Quadratic embedding constants of wheel graphs, Interdiscip. Inform. Sci. 23 (2017), 171–174.
• [17] N. Obata: Primary non-QE graphs on six vertices, Interdiscip. Inform. Sci. 29 (2023), 141– 156.
• [18] N. Obata and A.Y. Zakiyyah, Distance matrices and quadratic embedding of graphs, Electronic J. Graph Theory Appl. 6 (2018), 37–60.
• [19] M. Purwaningsih and K.A. Sugeng, Quadratic embedding constants of squid graph and kite graph, Journal of Physics: Conference Series 1722 (2021) 012047.
• [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, Metric spaces and positive definite functions, Trans. Amer. Math. Soc. 44 (1938), 522–536.