A Classification of Graphs through
Quadratic Embedding Constants and Clique Graph Insights

Edy Tri Baskoro

Combinatorial Mathematics Research Group

Faculty of Mathematics and Natural Sciences

Institut Teknologi Bandung Jalan Ganesa 10 Bandung, Indonesia

<EMAIL_ADDRESS>

Nobuaki Obata

Center for Data-driven Science and Artificial Intelligence

Tohoku University

Sendai 980-8576 Japan

and

Combinatorial Mathematics Research Group

Faculty of Mathematics and Natural Sciences

Institut Teknologi Bandung Jalan Ganesa 10 Bandung, Indonesia

<EMAIL_ADDRESS>

> Abstract The quadratic embedding constant (QE constant for short) of a graph
> $G$ is a new numeric invariant, which is defined in terms of the distance
> matrix and is denoted by $\mathrm{QEC}(G)$. By observing graph structure of
> the maximal cliques (clique graph), we show that a graph $G$ with
> $\mathrm{QEC}(G)<-1/2$ admits a “cactus-like” structure. We derive a formula
> for the QE constant of a graph consisting of two maximal cliques. As an
> application we discuss characterization of graphs along the increasing
> sequence of $\mathrm{QEC}(P_{d})$, in particular, graphs $G$ satisfying
> $\mathrm{QEC}(G)<\mathrm{QEC}(P_{5})$.

> Key words cactus-like graph, clique graph, distance matrix, quadratic
> embedding constant,

> MSC primary:05C50 secondary:05C12 05C76

##  1 Introduction

In the recent paper [19] the quadratic embedding constant (QE constant for
short) of a finite connected graph $G=(V,E)$ with $|V|\geq 2$ is defined by

$\mathrm{QEC}(G)=\max\\{\langle f,Df\rangle\,;\,f\in C(V),\,\langle
f,f\rangle=1,\,\langle{\bm{1}},f\rangle=0\\},$ (1.1)

where $C(V)$ is the space of all $\mathbb{R}$-valued functions on $V$,
$\bm{1}\in C(V)$ the constant function taking value 1, and
$\langle\cdot,\cdot\rangle$ the canonical inner product. The QE constant is
profoundly related to the quadratic embedding of a graph in a Euclidean space
[9, 10, 22, 23] or more generally to Euclidean distance geometry [1, 3, 6, 11]
and distance spectra [2, 12]. As the QE constant provides a new numeric
invariant of graphs, we are naturally led to the forward-thinking project of
classifying graphs by means of the QE constants.

In [4] we initiated an attempt to classify graphs along with
$\mathrm{QEC}(P_{d})$, the QE constant of the path $P_{d}$ on $d\geq 2$
vertices, which forms an increasing sequence as

$-1=\mathrm{QEC}(P_{2})<\mathrm{QEC}(P_{3})<\dotsb<\mathrm{QEC}(P_{d})<\dotsb\rightarrow-\frac{1}{2}\,.$
(1.2)

In fact, it is known [14] that

$\mathrm{QEC}(P_{d})=-\left(1+\cos\frac{\pi}{d}\right)^{-1},\qquad d\geq 2.$
(1.3)

In this paper, we study graphs $G=(V,E)$ with $\mathrm{QEC}(G)<-1/2$ by means
of the clique graph $\Gamma(G)$. Here the clique graph is a graph
$\Gamma(G)=(\mathcal{V},\mathcal{E})$, where $\mathcal{V}$ is the set of
maximal cliques of $G$ and $\\{H_{1},H_{2}\\}\in\mathcal{E}$ if and only if
$H_{1}\neq H_{2}$ and $H_{1}\cap H_{2}\neq\emptyset$. A key result is that the
clique graph of a graph $G$ with $\mathrm{QEC}(G)<-1/2$ is a tree. Then,
combining the result on forbidden subgraphs [4], we conclude that a graph $G$
with $\mathrm{QEC}(G)<-1/2$ consists of maximal cliques which form a “cactus-
like” structure, for the precise statement see Theorem 4.5. As an application
we discuss graphs $G$ satisfying $\mathrm{QEC}(G)<\mathrm{QEC}(P_{5})$.

The paper is organized as follows. In Section 2 we assemble some basic
notations for the QE constants. In Section 3 we examine some properties of the
clique graph $\Gamma(G)$ and show a relation between the diameters of $G$ and
$\Gamma(G)$ (Propositions 3.5 and 3.7). In Section 4 we prove the main result
(Theorem 4.5). In Section 5 we determine a graph with exactly two maximal
cliques. In Section 6 we discuss graphs $G$ satisfying
$\mathrm{QEC}(G)<\mathrm{QEC}(P_{5})$. In Appendix we derive a formula for the
QE constant of a graph with exactly two maximal cliques.

##  2 Quadratic Embedding Constants

Throughout the paper a graph $G=(V,E)$ is a pair, where $V$ is a non-empty
finite set and $E$ is a set of two-element subsets $\\{x,y\\}\subset V$. As
usual, elements of $V$ and $E$ are respectively called a vertex and an edge.
Two vertices $x,y\in V$ are called adjacent if $\\{x,y\\}\in E$, and we also
write $x\sim y$. In that case we have $x\neq y$ necessarily.

For $s\geq 0$ a sequence of vertices $x=x_{0},x_{1},\dots,x_{s}=y\in V$ is
called a walk connecting $x$ and $y$ of length $s$ if they are successively
adjacent:

$x=x_{0}\sim x_{1}\sim\dotsb\sim x_{s}=y.$ (2.1)

A graph $G$ is called connected if any pair of vertices are connected by a
walk. In this paper a graph is always assumed to be connected unless otherwise
stated. The length of a shortest walk connecting two vertices $x,y\in V$ is
called the graph distance between $x$ and $y$ in $G$ and is denoted by
$d_{G}(x,y)$. A walk in (2.1) is called a shortest path connecting $x$ and $y$
if $s=d_{G}(x,y)$ holds. In that case $x_{0},x_{1},\dots,x_{s}$ are mutually
distinct.

As is defined in (1.1), the QE constant of a graph $G=(V,E)$, denoted by
$\mathrm{QEC}(G)$, is the conditional maximum of the quadratic function
$\langle f,Df\rangle$ associated to the distance matrix $D=[d_{G}(x,y)]$
subject to two constraints $\langle f,f\rangle=1$ and
$\langle\bm{1},f\rangle=0$.

In this section we assemble some basic results, for more details see e.g., [4,
15, 19]. We first recall a computational formula based on the standard method
of Lagrange’s multipliers.

######  Proposition 2.1 ([19]).

Let $D$ be the distance matrix of a graph $G=(V,E)$ on $n=|V|$ vertices with
$n\geq 3$. Let $\mathcal{S}$ be the set of all stationary points
$(f,\lambda,\mu)$ of

$\varphi(f,\lambda,\mu)=\langle f,Df\rangle-\lambda(\langle
f,f\rangle-1)-\mu\langle{\bm{1}},f\rangle,$ (2.2)

where $f\in C(V)\cong\mathbb{R}^{n}$, $\lambda\in\mathbb{R}$ and
$\mu\in\mathbb{R}$. Then we have

$\mathrm{QEC}(G)=\max\\{\lambda\,;\,(f,\lambda,\mu)\in\mathcal{S}\\}.$

In general, a graph $H=(V^{\prime},E^{\prime})$ is called a subgraph of
$G=(V,E)$ if $V^{\prime}\subset V$ and $E^{\prime}\subset E$. If both $G$ and
$H$ are connected, they have their own graph distances. If they coincide in
such a way that

$d_{H}(x,y)=d_{G}(x,y),\qquad x,y\in V^{\prime},$

we say that $H$ is isometrically embedded in $G$. The next assertions are
immediate from definition but useful.

######  Proposition 2.2 ([17, 18]).

Let $G=(V,E)$ be a graph and $H=(V^{\prime},E^{\prime})$ a subgraph.

  1. (1)

If $H$ is isometrically embedded in $G$, then $H$ is an induced subgraph of
$G$.

  2. (2)

If $H$ is an induced subgraph of $G$ and

$\mathrm{diam\,}(H)=\max\\{d_{H}(x,y)\,;\,x,y\in V^{\prime}\\}\leq 2,$

then $H$ is isometrically embedded in $G$.

######  Proposition 2.3 ([19]).

Let $G=(V,E)$ and $H=(V^{\prime},E^{\prime})$ be two graphs with $|V|\geq 2$
and $|V^{\prime}|\geq 2$. If $H$ is isometrically embedded in $G$, we have

$\mathrm{QEC}(H)\leq\mathrm{QEC}(G).$ (2.3)

In particular, (2.3) holds if $H$ is an induced subgraph of $G$ and
$\mathrm{diam\,}(H)\leq 2$.

Since any graph $G=(V,E)$ with $|V|\geq 2$ contains at least one edge, it has
a subgraph $K_{2}$ isometrically embedded in $G$. It then follows from
Proposition 2.3 that

$\mathrm{QEC}(G)\geq\mathrm{QEC}(K_{2})=-1.$

Moreover, we have the following assertion, see also Proposition 6.2.

######  Proposition 2.4 ([4]).

For a graph $G$ we have $\mathrm{QEC}(G)=-1$ if and only if $G$ is a complete
graph.

Thus, in order to determine $\mathrm{QEC}(G)$ of a graph $G$ which is not a
complete graph, it is sufficient to seek out the stationary points of
$\varphi(f,\lambda,\mu)$ with $\lambda>-1$ and then to specify the maximum of
$\lambda$ appearing therein.

The QE constants of graphs of particular classes are known explicitly, see [5,
8, 14, 16, 19, 20], and the formulas in relation to graph operations are
established in [13, 15]. Moreover, a table of the QE constants of graphs on
$n\leq 5$ vertices is available [19], where the value of the graph No. 12 on
$n=5$ vertices is wrong and the correction is found in [4].

##  3 Clique Graphs

Most of this section follows a standard argument; however, to avoid ambiguity,
we present some basic properties of clique graphs.

Let $G=(V,E)$ be a graph (always assumed to be finite and connected). For a
non-empty subset $H\subset V$, the subgraph induced by $H$ is denoted by
$\langle H\rangle$. By definition the vertex set of $\langle H\rangle$ is $H$
itself and two-element subset $\\{x,y\\}\subset H$ belongs to the edge set of
$\langle H\rangle$ if and only if $\\{x,y\\}\in E$. A non-empty subset
$H\subset V$ is called a clique of $G$ if $\langle H\rangle$ is a complete
graph. A clique is called maximal if it is maximal in the family of cliques
with respect to the inclusion relation. Except for notation, ‘clique’ may also
refer to the subgraph it induces.

Obviously, for a clique $H_{0}$ there exists a maximal clique $H$ such that
$H_{0}\subset H$. In particular, for two vertices $a\sim b$ there exists a
maximal clique containing $\\{a,b\\}$.

######  Lemma 3.1.

Let $H_{1}$ and $H_{2}$ be maximal cliques of a graph $G$ such that $H_{1}\neq
H_{2}$. Then $H_{1}\backslash H_{2}\neq\emptyset$ and $H_{2}\backslash
H_{1}\neq\emptyset$. Moreover, there exist $a\in H_{1}\backslash H_{2}$ and
$b\in H_{2}\backslash H_{1}$ such that $a\not\sim b$.

###### Proof.

Suppose that $H_{1}\backslash H_{2}=\emptyset$ or $H_{2}\backslash
H_{1}=\emptyset$. If the former occurs, we have $H_{1}\subset H_{2}$. Since
both $H_{1}$ and $H_{2}$ are maximal and $H_{1}\neq H_{2}$ by assumption, we
come to a contradiction.

For the second half of the assertion, suppose that any pair of $x\in
H_{1}\backslash H_{2}$ and $y\in H_{2}\backslash H_{1}$ are adjacent. We will
show that $H_{1}\cup H_{2}$ is a clique. In fact, take a pair of distinct
vertices $x,y\in H_{1}\cup H_{2}$. If $x,y\in H_{1}$ or $x,y\in H_{2}$, they
are adjacent since $H_{1}$ and $H_{2}$ are cliques. If otherwise, we have
$x\in H_{1}\backslash H_{2}$ and $y\in H_{2}\backslash H_{1}$ or vice versa,
and hence $x\sim y$ by assumption. Consequently, for any pair of distinct
vertices $x,y\in H_{1}\cup H_{2}$ we have $x\sim y$, namely, $H_{1}\cup H_{2}$
becomes a clique. Since $H_{1}\cup H_{2}$ contains $H_{1}$ and $H_{2}$
properly, we come to a contradiction. ∎

For a graph $G=(V,E)$ let $\mathcal{V}$ be the set of all maximal cliques and
$\mathcal{E}$ the set of two-element subsets
$\\{H_{1},H_{2}\\}\subset\mathcal{V}$ such that $H_{1}\cap
H_{2}\neq\emptyset$. Then $\Gamma(G)=(\mathcal{V},\mathcal{E})$ becomes a (in
fact, connected) graph, which is called the clique graph of $G$. Accordingly,
for two maximal cliques $H_{1}$ and $H_{2}$ of $G$ we write $H_{1}\sim H_{2}$
if $H_{1}\neq H_{2}$ and $H_{1}\cap H_{2}\neq\emptyset$. For more information
on the clique graph, see e.g., [21, 24].

######  Lemma 3.2.

The clique graph $\Gamma(G)$ of a graph $G$ is connected.

###### Proof.

Let $H_{1},H_{2}$ be two maximal cliques such that $H_{1}\neq H_{2}$. By Lemma
3.1 we may choose $a\in H_{1}\backslash H_{2}$ and $b\in H_{2}\backslash
H_{1}$. Since $G$ is connected, there exists a walk connecting $a$ and $b$,
say,

$a=x_{0}\sim x_{1}\sim\dotsb\sim x_{s}=b,$

where $s\geq 1$. For $1\leq i\leq s$ take a maximal clique $J_{i}$ containing
$\\{x_{i-1},x_{i}\\}$. Then $x_{i}\in J_{i}\cap J_{i+1}$ implies that
$J_{i}=J_{i+1}$ or $J_{i}\sim J_{i+1}$. Moreover, it follows from $a=x_{0}\in
H_{1}\cap J_{1}$ that $H_{1}=J_{1}$ or $H_{1}\sim J_{1}$. Similarly,
$H_{2}=J_{s}$ or $H_{2}\sim J_{s}$. In any case, $H_{1}$ and $H_{2}$ are
connected by a walk consisting of $J_{1},J_{2},\dots,J_{s}$. ∎

######  Example 3.3.

For a complete graph $K_{n}$ with $n\geq 1$, a path $P_{n}$ with $n\geq 2$,
and a cycle $C_{n}$ with $n\geq 3$ we have

$\Gamma(K_{n})=K_{1},\qquad\Gamma(P_{n})=P_{n-1},\qquad\Gamma(C_{n})=C_{n}\,.$

For a graph $G$ such that every maximal clique of it is $K_{2}$, the clique
graph $\Gamma(G)$ is nothing else but the line graph of $G$. This is the case
of $G=P_{n}$ and $G=C_{n}$.

######  Lemma 3.4.

For $d\geq 1$ let

$x_{0}\sim x_{1}\sim\dotsb\sim x_{d}\,,$ (3.1)

be a shortest path connecting $x_{0}$ and $x_{d}$, that is,
$d(x_{0},x_{d})=d$. For $1\leq i\leq d$ let $H_{i}$ be a maximal clique
containing $\\{x_{i-1},x_{i}\\}$. Then,

$H_{1}\sim H_{2}\sim\dotsb\sim H_{d}$ (3.2)

and $d(H_{1},H_{d})=d-1$. Hence (3.2) is a shortest path connecting $H_{1}$
and $H_{d}$, and $H_{1},H_{2},\dots,H_{d}$ are mutually distinct.

###### Proof.

For $1\leq i\leq d-1$ we have $x_{i}\in H_{i}\cap H_{i+1}$ by definition, and
hence $H_{i}=H_{i+1}$ or $H_{i}\sim H_{i+1}$. Suppose that $H_{i}=H_{i+1}$
occurs. Then $x_{i-1},x_{i},x_{i+1}\in H_{i}$ and these three vertices are
mutually distinct because (3.1) is a shortest path. Since $H_{i}$ is a clique,
we have $x_{i-1}\sim x_{i+1}$, which contradicts to that (3.1) is a shortest
path. Thus we obtain a walk as in (3.2).

We next prove that (3.2) gives rise to a shortest path. Let $s=d(H_{1},H_{d})$
and take a shortest path

$H_{1}=J_{0}\sim J_{1}\sim\dots\sim J_{s}=H_{d}\,.$

In that case we have

$s\leq d-1$ (3.3)

For $1\leq i\leq s$ we take $y_{i}\in J_{i-1}\cap J_{i}$. Then $y_{1}\sim
y_{2}\sim\dotsb\sim y_{s}$. Moreover, since $x_{0},y_{1}\in H_{1}=J_{0}$ we
have $x_{0}=y_{1}$ or $x_{0}\sim y_{1}$. Similarly, $x_{d}=y_{s}$ or
$x_{d}\sim y_{s}$. Thus we obtain a walk connecting $x_{0}$ and $x_{d}$ of
which length is $s-1$, $s$ or $s+1$. Hence $d=d(x_{0},x_{d})\leq s+1$.
Combining (3.3) we obtain $s=d-1$ and hence $d(H_{1},H_{d})=d-1$ as desired. ∎

######  Proposition 3.5.

Let $G$ be a graph and $\Gamma(G)$ its clique graph. Then

$\operatorname{diam\,}(G)-1\leq\operatorname{diam\,}(\Gamma(G)).$ (3.4)

###### Proof.

It is sufficient to show the assertion for a graph $G$ with
$d=\operatorname{diam\,}(G)\geq 1$. We take a shortest path $x_{0}\sim
x_{1}\sim\dotsb\sim x_{d}$ such that $d(x_{0},x_{d})=d$. Define a sequence of
maximal cliques $H_{1},\dots,H_{d}$ as in Lemma 3.4. Then we have

$d-1=d(H_{1},H_{d})\leq\operatorname{diam\,}(\Gamma(G)),$

which completes the proof of (3.4). ∎

######  Lemma 3.6.

For $d\geq 1$ let

$H_{0}\sim H_{1}\sim\dotsb\sim H_{d}$ (3.5)

be a shortest path connecting $H_{0}$ and $H_{d}$, that is $d(H_{0},H_{d})=d$.
For $1\leq i\leq d$ take a vertex $x_{i}\in H_{i-1}\cap H_{i}$. Then

$x_{1}\sim x_{2}\sim\dotsb\sim x_{d}$ (3.6)

and $d(x_{1},x_{d})=d-1$. Hence (3.6) is a shortest path connecting $x_{1}$
and $x_{d}$, and $x_{1},x_{2},\dots,x_{d}$ are mutually distinct.

###### Proof.

For $1\leq i\leq d-1$ we have $x_{i},x_{i+1}\in H_{i}$ and hence
$x_{i}=x_{i+1}$ or $x_{i}\sim x_{i+1}$. Suppose that $x_{i}=x_{i+1}$ occurs.
Then $x_{i}=x_{i+1}\in H_{i-1}\cap H_{i}\cap H_{i+1}$ and hence $H_{i-1}\cap
H_{i+1}\neq\emptyset$, from which we obtain $H_{i-1}=H_{i+1}$ or $H_{i-1}\sim
H_{i+1}$. In any case we come to a contradiction because (3.5) is a shortest
path. We have thus obtained a walk as in (3.6).

We next prove that (3.6) gives rise to a shortest path. We set
$s=d(x_{1},x_{d})$ and take a shortest path connecting $x_{1}$ and $x_{d}$,
say,

$x_{1}=y_{0}\sim y_{1}\sim\dots\sim y_{s}=x_{d}.$

In that case we have

$s\leq d-1$ (3.7)

For $1\leq i\leq s$ let $J_{i}$ be a maximal clique containing
$\\{y_{i-1},y_{i}\\}$. It then follows from Lemma 3.4 that
$d(J_{1},J_{s})=s-1$. Since $x_{1}=y_{0}\in H_{0}\cap J_{1}$, we have
$H_{0}=J_{1}$ or $H_{0}\sim J_{1}$. Similarly, we have $H_{d}=J_{s}$ or
$H_{d}\sim J_{s}$. Thus, we obtain a walk connecting $H_{0}$ and $H_{d}$ of
which length is $s-1$, $s$ or $s+1$. Hence $d=d(H_{0},H_{d})\leq s+1$.
Combining (3.7), we obtain $s=d-1$ and hence $d(x_{1},x_{d})=d-1$ as desired.
∎

######  Proposition 3.7.

Let $G$ be a graph and $\Gamma(G)$ its clique graph. If $\Gamma(G)$ is a tree,
we have

$\operatorname{diam\,}(G)-1=\operatorname{diam\,}(\Gamma(G)).$ (3.8)

###### Proof.

Set $d=\operatorname{diam\,}(\Gamma(G))$ and take a shortest path

$H_{0}\sim H_{1}\sim\dots\sim H_{d},$ (3.9)

where $d(H_{0},H_{d})=d$. For $1\leq i\leq d$ take $x_{i}\in H_{i-1}\cap
H_{i}$. By Lemma 3.6 we have a shortest path $x_{1}\sim x_{2}\sim\dotsb\sim
x_{d}$. Moreover, we take $x_{0}\in H_{0}\backslash H_{1}$ and $x_{d+1}\in
H_{d}\backslash H_{d-1}$. Thus we obtain a walk

$x_{0}\sim x_{1}\sim x_{2}\sim\dotsb\sim x_{d}\sim x_{d+1}$ (3.10)

of length $d+1$.

We shall prove that (3.10) is a shortest path. Set $s=d(x_{0},x_{d+1})$ and
take a shortest path, say,

$x_{0}=y_{0}\sim y_{1}\sim y_{2}\sim\dotsb\sim y_{s}=x_{d+1}$ (3.11)

For $1\leq i\leq s$ let $J_{i}$ be a maximal clique containing
$\\{y_{i-1},y_{i}\\}$. By Lemma 3.2 we obtain a shortest path
$J_{1}\sim\dotsb\sim J_{s}$, namely,

$d(J_{1},J_{s})=s-1.$ (3.12)

Now note that $x_{0}=y_{0}\in H_{0}\cap J_{1}$. Then we have $H_{0}=J_{1}$ or
$H_{0}\sim J_{1}$. Since $\Gamma(G)$ is a tree, the ends of a diameter (3.9)
are pending vertices. Hence $H_{0}\sim J_{1}$ implies that $J_{1}=H_{1}$. In
that case we have $x_{0}=y_{0}\in H_{0}\cap J_{1}=H_{0}\cap H_{1}$. On the
other hand, we chose $x_{0}\in H_{0}\backslash H_{1}$, which is a
contradiction. Therefore, $H_{0}\sim J_{1}$ does not occur and we have
$H_{0}=J_{1}$. In a similar manner, we see that $H_{d}=J_{s}$. Consequently,
combining (3.12) we come to

$d=d(H_{0},H_{d})=d(J_{1},J_{s})=s-1.$

Thus,

$\operatorname{diam\,}(\Gamma(G))=d=s-1=d(x_{0},x_{d+1})-1\leq\operatorname{diam\,}(G)-1.$

Finally, combining Proposition 3.5, we obtain the equality (3.8). ∎

##  4 Graphs with $\mathrm{QEC}(G)<-1/2$

We need notation. The complete bipartite graph $K_{1,3}$ is called a claw. The
complete tripartite graph $K_{1,1,2}$, which is also obtained by deleting an
edge from the complete graph $K_{4}$, is called a diamond, see Figure 1.

Figure 1: Claw $K_{1,3}$ (left) and diamond $K_{1,1,2}$ (right)

It is essential to note that

$\mathrm{QEC}(K_{1,3})=\mathrm{QEC}(K_{1,1,2})=-\frac{1}{2}\,.$

Since $\operatorname{diam\,}(K_{1,3})=\operatorname{diam\,}(K_{1,1,2})=2$, we
see from Propositions 2.2 and 2.3 that if a graph $G$ contains $K_{1,3}$ or
$K_{1,1,2}$ as an induced subgraph, we have $\mathrm{QEC}(G)\geq-1/2$. Thus,
we come to the following criterion.

######  Proposition 4.1 ([4, Corollary 4.1]).

Any graph $G$ with $\mathrm{QEC}(G)<-1/2$ does not contain a claw $K_{1,3}$
nor a diamond $K_{1,1,2}$ as an induced subgraph. In short, the claw and
diamond are forbidden subgraphs for a graph with $\mathrm{QEC}(G)<-1/2$.

######  Lemma 4.2.

Let $G$ be a graph with $\mathrm{QEC}(G)<-1/2$. If $H_{1}$ and $H_{2}$ are
maximal cliques of $G$ with $H_{1}\neq H_{2}$, then $H_{1}\cap
H_{2}=\emptyset$ or $|H_{1}\cap H_{2}|=1$.

###### Proof.

In order to prove the assertion by contradiction, we suppose $|H_{1}\cap
H_{2}|\geq 2$ and take $x,y\in H_{1}\cap H_{2}$ with $x\neq y$. By Lemma 3.1
there exist $a\in H_{1}\backslash H_{2}$ and $b\in H_{2}\backslash H_{1}$ such
that $a\not\sim b$. Then $\langle x,y,a,b\rangle$ forms a diamond, which is a
forbidden subgraph as stated in Proposition 4.1. ∎

######  Lemma 4.3.

Let $G$ be a graph with $\mathrm{QEC}(G)<-1/2$. If $H_{1},H_{2}$ and $H_{3}$
are mutually distinct maximal cliques of $G$, then $H_{1}\cap H_{2}\cap
H_{3}=\emptyset$.

###### Proof.

In order to prove the assertion by contradiction we suppose that $H_{1}\cap
H_{2}\cap H_{3}\neq\emptyset$. Then $H_{1}\cap H_{2}\neq\emptyset$ and by
Lemma 4.2 we have $H_{1}\cap H_{2}=\\{x\\}$ for some $x\in V$. Hence
$H_{2}\cap H_{3}=H_{3}\cap H_{1}=H_{1}\cap H_{2}\cap H_{3}=\\{x\\}$. On the
other hand, by Lemma 3.1 there exist $a\in H_{1}\backslash H_{2}$ and $b\in
H_{2}\backslash H_{1}$ such that $a\not\sim b$. Note that there exists $c\in
H_{3}\backslash H_{1}$ such that $c\not\sim a$. In fact, if any $c\in
H_{3}\backslash H_{1}$ is adjacent to $a$, then $H_{3}\cup\\{a\\}$ becomes a
clique and we come to a contradiction. Thus, we have chosen four vertices
$x,a,b,c$. There are two cases. In case of $b\not\sim c$, the induced subgraph
$\langle x,a,b,c\rangle$ becomes a claw. In case of $b\sim c$ note that there
exist $c^{\prime}\in H_{3}\backslash H_{2}$ such that $c^{\prime}\not\sim b$.
In fact, if any $c^{\prime}\in H_{3}\backslash H_{2}$ is adjacent to $b$,
$H_{3}\cup\\{b\\}$ becomes a clique and we come to a contradiction. Thus,
taking $c^{\prime}\in H_{3}\backslash H_{2}$ such that $c^{\prime}\not\sim b$,
we see that $\langle x,b,c,c^{\prime}\rangle$ becomes a diamond. In any case
we obtain a forbidden subgraph as stated in Proposition 4.1 and arrive to a
contradiction. ∎

######  Proposition 4.4.

For a graph $G=(V,E)$ with $\mathrm{QEC}(G)<-1/2$ the clique graph $\Gamma(G)$
is a tree.

###### Proof.

Suppose that the clique graph $\Gamma(G)$ is not a tree and take a smallest
cycle, say,

$H_{1}\sim H_{2}\sim\dotsb\sim H_{k}\sim H_{1},\qquad k\geq 3,$ (4.1)

where $H_{i}$ is a maximal clique of $G$ and $H_{i}\cap H_{i+1}\neq\emptyset$
for $1\leq i\leq k$ (understanding $H_{k+1}=H_{1}$). It follows from Lemma 4.2
that there exists a unique vertex $x_{i}$ such that $H_{i}\cap
H_{i+1}=\\{x_{i}\\}$ for $1\leq i\leq k$. Then, obviously

$x_{1}\sim x_{2}\sim\dots\sim x_{k}\sim x_{1}.$

(Case 1) $k=3$. In that case $x_{1},x_{2},x_{3}$ are mutually distinct. We
note that $x_{1},x_{3}\in H_{1}$ and $x_{2}\not\in H_{1}$. If
$H_{1}=\\{x_{1},x_{3}\\}$, namely
$H_{1}\backslash\\{x_{1},x_{3}\\}=\emptyset$, then $H_{1}\cup\\{x_{2}\\}$
becomes a clique containing $H_{1}$ properly and we come to a contradiction.
Hence $H_{1}\backslash\\{x_{1},x_{3}\\}\neq\emptyset$. If any $y\in
H_{1}\backslash\\{x_{1},x_{3}\\}$ is adjacent to $x_{2}$, then
$H_{1}\cup\\{x_{2}\\}$ becomes a clique containing $H_{1}$ properly and we
come to a contradiction again. Therefore, there exists $y\in
H_{1}\backslash\\{x_{1},x_{3}\\}$ such that $y\not\sim x_{2}$. Thus, $\langle
x_{1},x_{2},x_{3},y\rangle$ becomes a diamond, which is a forbidden subgraph
by Proposition 4.1. Consequently, $\Gamma(G)$ does not contain a cycle (4.1)
with $k=3$.

(Case 2) $k\geq 4$. Using the assumption that (4.1) is a smallest cycle, one
can show easily that $x_{1},\dots,x_{k}$ are mutually distinct.

We first prove that the induced subgraph $C=\langle
x_{1},x_{2},\dots,x_{k}\rangle$ becomes a cycle $C_{k}$. In fact, if not,
there exist $1\leq i,j\leq k$ such that $i+1<j$ and $x_{i}\sim x_{j}$. Let $J$
be a maximal clique containing $\\{x_{i},x_{j}\\}$. Then $x_{i}\in H_{i}\cap
H_{i+1}\cap J$ and $x_{j}\in H_{j}\cap H_{j+1}\cap J$. In view of Lemma 4.3 we
obtain $J=H_{i}$ or $J=H_{i+1}$ from the former condition, and similarly
$J=H_{j}$ or $J=H_{j+1}$ from the latter. In any case we come to a
contradiction against that (4.1) is a smallest cycle.

We next show that the cycle $C=\langle x_{1},x_{2},\dots,x_{k}\rangle\cong
C_{k}$ is isometrically embedded in $G$. Suppose otherwise. Then there exist
$1\leq i,j\leq k$ such that

$d_{G}(x_{i},x_{j})<d_{C_{k}}(x_{i},x_{j}),$ (4.2)

where the right-hand side is the distance in the cycle $C_{k}$. Without loss
of generality, we may assume that $1\leq i<j\leq k$. Then, (4.2) becomes

$d_{G}(x_{i},x_{j})<\min\\{j-i,k-(j-i)\\}.$ (4.3)

For $j=i+1$ we have $x_{i}\sim x_{j}$ and (4.3) does not hold. For $j=i+2$ it
follows from (4.3) that $d_{G}(x_{i},x_{j})=1$ and come to a contradiction
against the argument in the previous paragraph. Thus, it is sufficient to
derive a contradiction from (4.3) for some $j\geq i+3$. Now take a shortest
path

$x_{i}\sim y_{0}\sim y_{1}\sim\dots\sim y_{s}=x_{j},\qquad
s=d_{G}(x_{i},x_{j}).$

For $1\leq i\leq s$ take a maximal clique $J_{i}$ such that
$\\{y_{i-1},y_{i}\\}\subset J_{i}$. Since $x_{i}=y_{0}\in H_{i}\cap
H_{i+1}\cap J_{1}$, by Lemma 4.3 we have $J_{1}=H_{i}$ or $J_{1}=H_{i+1}$.
Similarly, we see from $x_{j}=y_{s}\in H_{j}\cap H_{j+1}\cap J_{s}$ that
$J_{s}=H_{j}$ or $J_{s}=H_{j+1}$. Thus, the path $J_{1}\sim J_{2}\sim\dots\sim
J_{s}$, which is a shortest path by Lemma 3.4, gives rise to an alternative
path connecting two verices of $C$, and hence two cyclic walks. We will
consider these two cyclic walks in details.

Consider the case where

$J_{1}=H_{i},\quad\text{and}\quad J_{s}=H_{j}.$ (4.4)

We obtain two cyclic walks:

$H_{1}\sim\dots\sim H_{i}=J_{1}\sim J_{2}\sim\dots\sim J_{s}=H_{j}\sim
H_{j+1}\sim\dots\sim H_{k}\sim H_{1}.$ (4.5)

and

$H_{i}=J_{1}\sim J_{2}\sim\dots\sim J_{s}=H_{j}\sim H_{j-1}\sim\dots\sim
H_{i+1}\sim H_{i}\,.$ (4.6)

The length of these walks are $(i-1)+(s-1)+(k-j)+1=k+s+i-j$ and
$(s-1)+(j-i)=s+j-i-1$, respectively. In view of (4.3) we consider two cases.
First, in case of $s<\min\\{j-i,k-(j-i)\\}=j-i$ we have $k+s+i-j<k$, that is,
the length of (4.5) is less than $k$. This contradicts to the choice of $k$.
Second, in case of $s<\min\\{j-i,k-(j-i)\\}=k-(j-i)$ we have $s+j-i-1<k-1$,
that is, the length of (4.5) is less than $k-1$. This contradicts to the
choice of $k$. Thus (4.4) does not occur.

Other than (4.4) there are three more cases. In each of these cases we may
find in a similar manner a cycle in $\Gamma(G)$ which is smaller than (4.1),
and come to a contradiction. As a result, the cycle $C=\langle
x_{1},x_{2},\dots,x_{k}\rangle\cong C_{k}$ is isometrically embedded in $G$.

We now recall that $\mathrm{QEC}(C_{k})>-1/2$ for any $k\geq 4$. In fact, the
exact value of $\mathrm{QEC}(C_{k})$ is known [19]. As a consequence of (Case
2), we obtain $\mathrm{QEC}(G)\geq\mathrm{QEC}(C_{k})>-1/2$ and come to a
contradiction. Hence, $\Gamma(G)$ does not contain a smallest cycle (4.1) with
$k\geq 4$. This completes the proof. ∎

Summing up the above results, we state the following

######  Theorem 4.5.

Let $G=(V,E)$ be a graph with $\mathrm{QEC}(G)<-1/2$. Then the clique graph
$\Gamma(G)$ is a tree. Any pair of adjacent maximal cliques $H_{1}$ and
$H_{2}$ intersect with a single vertex, i.e., $|H_{1}\cap H_{2}|=1$. Moreover,
mutually distinct three maximal cliques $H_{1},H_{2}$ and $H_{3}$ do not
intersect, i.e., $H_{1}\cap H_{2}\cap H_{3}=\emptyset$.

Thus, a graph $G=(V,E)$ with $\mathrm{QEC}(G)<-1/2$ is a block graph which
admits “cactus-like” structure, see Figure 2.

Figure 2: “Cactus-like” graph

##  5 Graphs Consisting of Two Maximal Cliques

For natural numbers $l\geq 1$, $m>l$ and $n>l$, let $V=\\{1,2,\dots,m+n-l\\}$
and consider its two subsets:

$H_{1}=\\{1,2,\dots,m\\},\qquad H_{2}=\\{m-l+1,m-l+2,\dots,m-l+n\\}.$ (5.1)

Note that $V=H_{1}\cup H_{2}$. Let $E$ be the set of two-element subsets
$\\{x,y\\}\subset V$ satisfying $x,y\in H_{1}$ or $x,y\in H_{2}$. Then
$G=(V,E)$ becomes a graph which is denoted by $G=K_{m}\cup_{l}K_{n}$, see
Figure 3. Obviously, $G=K_{m}\cup_{l}K_{n}$ has exactly two maximal cliques
$H_{1}$ and $H_{2}$. We will prove that any graph (recall that we always
assume that a graph is connected) with exactly two maximal cliques is of this
form.

Figure 3: A connected graph consisting of two maximal cliques

######  Proposition 5.1.

Let $G=(V,E)$ be a (connected) graph with exactly two maximal cliques. Then
there exist three natural numbers $l\geq 1$, $m>l$ and $n>l$ such that $G\cong
K_{m}\cup_{l}K_{n}$.

Although Proposition 5.1 pertains to an elementary understanding of graph
theory, for later convenience we show an outline of the argument.

######  Lemma 5.2.

Let $G=(V,E)$ be a graph with exactly two maximal cliques $H_{1}$ and $H_{2}$.

  1. (1)

For any $a\in H_{1}\backslash H_{2}$ and $b\in H_{2}\backslash H_{1}$ we have
$a\not\sim b$.

  2. (2)

$V=H_{1}\cup H_{2}$.

  3. (3)

$H_{1}\cap H_{2}\neq\emptyset$.

  4. (4)

For any $a\in H_{1}\backslash H_{2}$ and $b\in H_{2}\backslash H_{1}$ we have
$d_{G}(a,b)=2$.

###### Proof.

(1) Suppose that $a\in H_{1}\backslash H_{2}$ and $b\in H_{2}\backslash H_{1}$
are adjacent. There exists a maximal clique containing $\\{a,b\\}$, which is
different from $H_{1}$ and $H_{2}$. This implies that $a\not\sim b$ for any
pair of $a\in H_{1}\backslash H_{2}$ and $b\in H_{2}\backslash H_{1}$ .

(2) In order to prove by contradiction we suppose $V\neq H_{1}\cup H_{2}$.
Take $a\in V\backslash(H_{1}\cup H_{2})$. Since $G$ is connected, there exists
$b\in V$ such that $a\sim b$. Then a maximal clique containing $\\{a,b\\}$
exists and is different from $H_{1}$ and from $H_{2}$. We thus come to a
contradiction.

(3) Suppose that $H_{1}\cap H_{2}=\emptyset$. Take $a\in H_{1}$ and $b\in
H_{2}$ arbitrarily. Since $G$ is connected, there exists a walk connecting $a$
and $b$. Since this walk is kept in $H_{1}\cup H_{2}$ by (2), we may find
$a^{\prime}\in H_{1}$ and $b^{\prime}\in H_{2}$ such that $a^{\prime}\sim
b^{\prime}$. This contradicts to the result of (1).

(4) By (1) we know that $d_{G}(a,b)\geq 2$. On the other hand, taking $x\in
H_{1}\cap H_{2}$ we obtain a walk $a\sim x\sim b$, which implies that
$d_{G}(a,b)\leq 2$. ∎

###### Proof of Proposition 5.1.

Let $H_{1}$ and $H_{2}$ be the two maximal cliques of $G$. We set $m=|H_{1}|$,
$n=|H_{2}|$ and $l=|H_{1}\cap H_{2}|$. By Lemma 5.2 we see that $H_{1}\cong
K_{m}$, $H_{2}\cong K_{n}$ and $H_{1}\cap H_{2}\cong K_{l}$ with $l\geq 1$ and
$m,n>l$. Moreover, there is no edge connecting vertices $a\in H_{1}\backslash
H_{2}$ and $b\in H_{2}\backslash H_{1}$. We conclude that
$G=K_{m}\cup_{l}K_{n}$. ∎

The distance matrix of $G=K_{m}\cup_{l}K_{n}$ is easily written down according
to (5.1). In fact, taking Lemma 5.2 (4) into account, we obtain the distance
matrix $D$ in a block-matrix form as follows:

$D=\begin{bmatrix}J-I&J&J\\\ J&J-I&2J\\\ J&2J&J-I\end{bmatrix}$ (5.2)

Then $\mathrm{QEC}(G)$ is obtained by means of the basic formula in
Proposition 2.1. The computation is just a routine and is deferred to the
Appendix.

######  Theorem 5.3.

For $l\geq 1$, $m>l$ and $n>l$ we have

$\mathrm{QEC}(K_{m}\cup_{l}K_{n})=-1+\frac{-(m-l)(n-l)+\sqrt{\mathstrut
mn(m-l)(n-l)}}{m+n-l}$ (5.3)

######  Corollary 5.4 ([4, Proposition 4.4]).

Let $m\geq 2$ and $n\geq 2$. Then $K_{m}\cup_{1}K_{n}$ is a graph obtained
from $K_{m}$ and $K_{n}$ by concatenating a vertex, in other words, it is the
star product $K_{m}\cup_{1}K_{n}=K_{m}*K_{n}$, and we have

$\displaystyle\mathrm{QEC}(K_{m}\cup_{1}K_{n})$
$\displaystyle=\mathrm{QEC}(K_{m}*K_{n})$
$\displaystyle=\frac{-mn+\sqrt{\mathstrut mn(m-1)(n-1)}}{m+n-1}$
$\displaystyle=-\left(1+\sqrt{\bigg{(}1-\dfrac{1}{m}\bigg{)}\bigg{(}1-\dfrac{1}{n}\bigg{)}}\,\right)^{-1}.$
(5.4)

######  Corollary 5.5.

Let $m\geq 3$ and $n\geq 3$. Then $K_{m}\cup_{2}K_{n}$ is a graph obtained
from $K_{m}$ and $K_{n}$ by concatenating an edge and we have

$\mathrm{QEC}(K_{m}\cup_{2}K_{n})=\frac{-mn+n-2+\sqrt{\mathstrut
mn(m-2)(n-2)}}{m+n-2}$ (5.5)

##  6 Characterization of Graphs Along $QEC(P_{d})$

######  Proposition 6.1.

Let $d\geq 3$. If $\mathrm{QEC}(G)<\mathrm{QEC}(P_{d})$, we have
$\operatorname{diam\,}(G)\leq d-2$ and $\operatorname{diam\,}(\Gamma(G))\leq
d-3$.

###### Proof.

Suppose that $\operatorname{diam\,}(G)>d-2$. Then
$\operatorname{diam\,}(G)\geq d-1$ and $P_{d}$ is isometrically embedded in
$G$. By Proposition 2.3 we obtain $\mathrm{QEC}(P_{d})\leq\mathrm{QEC}(G)$,
which contradicts to the assumption. Therefore, if
$\mathrm{QEC}(G)<\mathrm{QEC}(P_{d})$, we have $\operatorname{diam\,}(G)\leq
d-2$. In that case, since $\mathrm{QEC}(G)<\mathrm{QEC}(P_{d})<-1/2$, it
follows from Theorem 4.5 that $\Gamma(G)$ is a tree. We then see from
Proposition 3.7 that
$\operatorname{diam\,}(\Gamma(G))=\operatorname{diam\,}(G)-1\leq d-3$. ∎

###  6.1 $\mathrm{QEC}(G)<\mathrm{QEC}(P_{3})$

For a graph with $\mathrm{QEC}(G)<\mathrm{QEC}(P_{3})$ we have
$\operatorname{diam\,}(\Gamma(G))=0$, which means that $G$ has just one
maximal clique. Hence $G=K_{n}$ with $n\geq 2$. Since
$\mathrm{QEC}(K_{n})=-1$, we have the following assertions immediately.

######  Proposition 6.2 ([4]).

For a graph $G$ we have $\mathrm{QEC}(G)=\mathrm{QEC}(P_{2})=-1$ if and only
if $G=K_{n}$ with $n\geq 2$.

######  Proposition 6.3 ([4]).

There exists no graph $G$ such that
$\mathrm{QEC}(P_{2})<\mathrm{QEC}(G)<\mathrm{QEC}(P_{3})=-2/3$.

###  6.2 $\mathrm{QEC}(G)<\mathrm{QEC}(P_{4})$

Let $G$ be a graph satisfying $\mathrm{QEC}(G)<\mathrm{QEC}(P_{4})$. It
follows from Proposition 6.1 that $\operatorname{diam\,}(\Gamma(G))\leq 1$,
that is, $\operatorname{diam\,}(\Gamma(G))=0$ or
$\operatorname{diam\,}(\Gamma(G))=1$. The case of
$\operatorname{diam\,}(\Gamma(G))=0$ is discussed already in Subsection 6.1.

In the case of $\operatorname{diam\,}(\Gamma(G))=1$, the clique graph
$\Gamma(G)$ consists of two vertices, which means that $G$ has exactly two
maximal cliques. By Proposition 5.1 we obtain $G=K_{m}\cup_{l}K_{n}$ with
$l\geq 1$, $m>l$ and $n>l$. On the other hand, since $\mathrm{QEC}(G)<-1/2$,
we see from Lemma 4.2 that $l=1$. Thus, $G$ is necessarily of the form
$G=K_{m}\cup_{1}K_{n}=K_{m}*K_{n}$ with $m\geq n\geq 2$.

With the help of the formula in Corollary 5.4 we may easily determine $m\geq
n\geq 2$ such that
$\mathrm{QEC}(K_{m}*K_{n})<\mathrm{QEC}(P_{4})=-(2-\sqrt{2})$. As a result we
obtain the following assertions.

######  Proposition 6.4 ([4]).

For a graph $G$ we have $\mathrm{QEC}(G)=\mathrm{QEC}(P_{3})=-2/3$ if and only
if $G=P_{3}=K_{2}*K_{2}$.

######  Proposition 6.5 ([4]).

For a graph $G$ we have
$\mathrm{QEC}(P_{3})<\mathrm{QEC}(G)<\mathrm{QEC}(P_{4})=-(2-\sqrt{2})$ if and
only if $G=K_{m}*K_{2}$ with $m\geq 3$ or $G=K_{3}*K_{3}$.

###  6.3 $\mathrm{QEC}(G)<\mathrm{QEC}(P_{5})$

If a graph $G$ satisfies
$\mathrm{QEC}(G)<\mathrm{QEC}(P_{5})=-(5-\sqrt{5})/5$, then
$\operatorname{diam\,}(\Gamma(G))\leq 2$. The case of
$\operatorname{diam\,}(\Gamma(G))=0$ is already discussed in Subsection 6.1.
If $\operatorname{diam\,}(\Gamma(G))=1$, we have $G=K_{m}*K_{n}$ with $m\geq
n\geq 2$. Then, as is discussed in Subsection 6.2, we may employ the explicit
formula for $\mathrm{QEC}(K_{m}*K_{n})$ in Corollary 5.4. The result will be
stated in Propositions 6.9 and 6.10.

Consider the case of $\operatorname{diam\,}(\Gamma(G))=2$. Since $\Gamma(G)$
is a tree, it is necessarily a star $\Gamma(G)=K_{1,s}$ with $s\geq 2$. Then
$G$ is a graph obtained as follows: Let $n\geq s$ and $m_{1}\geq
m_{2}\geq\dotsb\geq m_{s}\geq 2$. We choose $s$ vertices from $K_{n}$ and to
each of the $s$ vertices we make a star product with
$K_{m_{1}},\dots,K_{m_{s}}$, see Figure 4. Such a graph is denoted by
$G=K_{n}*(K_{m_{1}},\dots,K_{m_{s}})$.

Figure 4: $K_{n}*(K_{m_{1}},\dots,K_{m_{s}})$

######  Lemma 6.6.

Consider two graphs $G=K_{n}*(K_{m_{1}},\dots,K_{m_{s}})$ with $n\geq s$,
$m_{1}\geq m_{2}\geq\dotsb\geq m_{s}\geq 2$, and
$G^{\prime}=K_{n^{\prime}}*(K_{m_{1}^{\prime}},\dots,K_{m_{r}^{\prime}})$ with
$n^{\prime}\geq r$ and $m_{1}^{\prime}\geq m_{2}^{\prime}\geq\dotsb\geq
m_{r}^{\prime}\geq 2$. If $n^{\prime}\leq n$, $r\leq s$, $m_{1}^{\prime}\leq
m_{1},\dots,m_{r}^{\prime}\leq m_{r}$, then $G^{\prime}$ is isometrically
embedded in $G$. Hence $\mathrm{QEC}(G^{\prime})\leq\mathrm{QEC}(G)$.

###### Proof.

Obvious. ∎

######  Lemma 6.7.

Let $n\geq s\geq 2$ and $m_{1}\geq m_{2}\geq\dots\geq m_{s}\geq 2$. If
$m_{1}\geq 3$, we have

$\mathrm{QEC}(P_{4})<\mathrm{QEC}(K_{n}*(K_{m_{1}},\dots,K_{m_{s}}))$

###### Proof.

It is known that

$\mathrm{QEC}(K_{2}*(K_{3},K_{2}))=-\frac{2(6-\sqrt{21})}{5}\approx-0.5669,$

see [19], where $K_{2}*(K_{3},K_{2})$ is referred to as No.5-7. Then we have

$\mathrm{QEC}(P_{4})<\mathrm{QEC}(K_{2}*(K_{3},K_{2}))<\mathrm{QEC}(P_{5}).$

On the other hand, for $n\geq s\geq 2$ and $m_{1}\geq 3$,
$K_{n}*(K_{m_{1}},\dots,K_{m_{s}})$ contains $K_{2}*(K_{3},K_{2})$ as an
isometrically embedded subgraph. Hence

$\mathrm{QEC}(P_{4})<\mathrm{QEC}(K_{2}*(K_{3},K_{2}))\leq\mathrm{QEC}(K_{n}*(K_{m_{1}},\dots,K_{m_{s}})),$

as desired. ∎

######  Lemma 6.8 ([4, Theorem 4.3]).

For $n\geq s\geq 2$ we have

$\mathrm{QEC}(K_{n}*(\overbrace{K_{2},\dots,K_{2}}^{\text{$s$
times}}))=-(2-\sqrt{2})=\mathrm{QEC}(P_{4}).$

######  Proposition 6.9.

For a graph $G$ we have $\mathrm{QEC}(G)=\mathrm{QEC}(P_{4})=-(2-\sqrt{2})$ if
and only if $G=K_{4}*K_{3}$ or $G=K_{n}*(K_{2},\dots,K_{2})$ ($K_{2}$ appears
$s$ times) with $n\geq s\geq 2$.

###### Proof.

As is discussed in Subsection 6.2, a graph $G$ with
$\operatorname{diam\,}(\Gamma(G))=1$ is of the form $K_{m}*K_{n}$ with $m\geq
n\geq 2$. Then, using the explicit formula for $\mathrm{QEC}(K_{m}*K_{n})$ in
Corollary 5.4, we see easily that
$\mathrm{QEC}(K_{m}*K_{n})=\mathrm{QEC}(P_{4})$ if and only if $m=4$ and
$n=3$.

A graph $G$ with $\operatorname{diam\,}(\Gamma(G))=2$ is of the form
$G=K_{n}*(K_{m_{1}},\dots,K_{m_{s}})$ with $n\geq s\geq 2$ and $m_{1}\geq
m_{2}\geq\dotsb\geq m_{s}\geq 2$. By Lemma 6.7,
$\mathrm{QEC}(G)\leq\mathrm{QEC}(P_{4})$ may occur only when
$m_{1}=m_{2}=\dotsb=m_{s}=2$. On the other hand, in that case, the equality
$\mathrm{QEC}(G)=\mathrm{QEC}(P_{4})$ holds by Lemma 6.8. ∎

######  Proposition 6.10.

For $m\geq n\geq 2$ we have
$\mathrm{QEC}(P_{4})<\mathrm{QEC}(K_{m}*K_{n})<\mathrm{QEC}(P_{5})$ if and
only if

  1. (i)

$n=3$ and $5\leq m\leq 54$;

  2. (ii)

$n=4$ and $4\leq m\leq 7$;

  3. (iii)

$n=m=5$.

###### Proof.

Straightforward by the explicit formula for $\mathrm{QEC}(K_{m}*K_{n})$. ∎

By Proposition 6.10 all graphs $G$ such that
$\mathrm{QEC}(P_{4})<\mathrm{QEC}(G)<\mathrm{QEC}(P_{5})$ with
$\operatorname{diam\,}(\Gamma(G))=1$ are determined. The case of
$\operatorname{diam\,}(\Gamma(G))=2$, i.e.,
$G=K_{n}*(K_{m_{1}},\dots,K_{m_{s}})$ remains to be checked. The work in this
line is in progress.

## Appendix: Calculating $\mathrm{QEC}(K_{m}\cup_{l}K_{n})$

Let $D$ be the distance matrix of $G=K_{m}\cup_{l}K_{n}$, where $l\geq 1$ and
$m,n>l$. Using the block-matrix form of $D$ as in (5.2), we will calculate
$\mathrm{QEC}(G)$ explicitly.

For $f\in\mathbb{R}^{l}$, $g\in\mathbb{R}^{m-l}$ and $h\in\mathbb{R}^{n-l}$ we
set

$\displaystyle\psi(f,g,h)$ $\displaystyle=\left\langle\begin{bmatrix}f\\\ g\\\
h\end{bmatrix},D\begin{bmatrix}f\\\ g\\\ h\end{bmatrix}\right\rangle$
$\displaystyle=\langle{\bm{1}},f\rangle^{2}+\langle{\bm{1}},g\rangle^{2}+\langle{\bm{1}},h\rangle^{2}-\langle
f,f\rangle^{2}-\langle g,g\rangle^{2}-\langle h,h\rangle^{2}$
$\displaystyle\qquad+2\langle{\bm{1}},f\rangle\langle{\bm{1}},g\rangle+2\langle{\bm{1}},f\rangle\langle{\bm{1}},h\rangle+4\langle{\bm{1}},g\rangle\langle{\bm{1}},h\rangle$

and

$\displaystyle\varphi(f,g,h,\lambda,\mu)=\psi(f,g,h)$
$\displaystyle-\lambda(\langle f,f\rangle+\langle g,g\rangle+\langle
h,h\rangle-1)$
$\displaystyle-\mu(\langle{\bm{1}},f\rangle+\langle{\bm{1}},g\rangle+\langle{\bm{1}},h\rangle).$
(A.1)

It then follows from Proposition 2.1 that $\mathrm{QEC}(G)$ coincides with the
maximum of $\lambda\in\mathbb{R}$ appearing in the stationary points of
$\psi(f,g,h,\lambda,\mu)$. Since $G$ is not complete, it is sufficient to
explore stationary points of $\psi(f,g,h,\lambda,\mu)$ with $\lambda>-1$.

By direct computation together with condition

$\langle\bm{1},f\rangle+\langle\bm{1},g\rangle+\langle\bm{1},h\rangle=0$

we have

$\frac{\partial\varphi}{\partial f_{i}}=-2(\lambda+1)f_{i}-\mu=0.$ (A.2)

Then we see that $f_{i}$ is constant independent of $1\leq i\leq l$, say
$f_{i}=\xi$. Thus, (A.2) becomes

$\xi=-\frac{1}{\lambda+1}\cdot\frac{\mu}{2}\,.$ (A.3)

(From the beginning we may assume that $\lambda>-1$ as noted before.)
Similarly, it follows from $\partial\varphi/\partial
g_{i}=\partial\varphi/\partial h_{i}=0$ that $g_{i}$ and $h_{i}$ are
respectively constant. Setting $g_{i}=\eta$ and $h_{i}=\zeta$, we obtain

$\displaystyle(\lambda+1)\eta-(n-l)\zeta=-\frac{\mu}{2}\,,$ (A.4)
$\displaystyle-(m-l)\eta+(\lambda+1)\zeta=-\frac{\mu}{2}\,,$ (A.5)

and the constraints become

$\displaystyle l\xi+(m-l)\eta+(n-l)\zeta=0,$ (A.6) $\displaystyle
l\xi^{2}+(m-l)\eta^{2}+(n-l)\zeta^{2}=1.$ (A.7)

Our task is to solve the system of equations (A.3)–(A.7).

In view of (A.4) and (A.5) we set

$\Delta=\det\begin{bmatrix}\lambda+1&-(n-l)\\\
-(m-l)&\lambda+1\end{bmatrix}=(\lambda+1)^{2}-(m-l)(n-l).$ (A.8)

(Case I) $\Delta\neq 0$. The equations (A.4) and (A.5) have a unique solution:

$\eta=-\frac{1}{\lambda+n+1-l}\cdot\frac{\mu}{2}\,,\qquad\zeta=-\frac{1}{\lambda+m+1-l}\cdot\frac{\mu}{2}\,.$
(A.9)

Inserting (A.3) and (A.9) into (A.6), we obtain

$l\Delta+(\lambda+1)\\{(m-l)(\lambda+n+1-l)+(n-l)(\lambda+m+1-l)\\}=0$ (A.10)

after simple calculation. The solutions are easily written down as

$\lambda_{\pm}=-1+\frac{-(m-l)(n-l)\pm\sqrt{mn(m-l)(n-l)}}{m+n-l}\,.$

Checking that $\lambda_{+}\neq-1$ and $\Delta\neq 0$ for
$\lambda=\lambda_{+}$, we see that $\lambda_{+}$ is a candidate of
$\mathrm{QEC}(G)$.

(Case II) $\Delta=0$. From (A.4) and (A.5) we obtain

$(\lambda+n-l+1)\frac{\mu}{2}=0,\qquad(\lambda+m-l+1)\frac{\mu}{2}=0.$

If $m\neq n$, we obtain $\mu=0$ and $\xi=\eta=\zeta=0$, which do not fulfill
(A.7). Hence there is no stationary points. Assume that $m=n$. Then
$\lambda=-1-(m-l)$ appears in the stationary points. However, since we are
only interested in $\lambda>-1$, there exists no candidate for our
$\mathrm{QEC}(G)$ in the case of $\Delta=0$.

Finally, we conclude from (Case I) and (Case II) that
$\lambda_{+}=\mathrm{QEC}(G)$.

## Acknowledgements

NO is grateful to Institut Teknologi Bandung (ITB) for their hospitality as an
adjunct professor during 2023–2024. This work is also supported in part by
JSPS Grant-in-Aid for Scientific Research No. 23K03126.

## 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] P. N. Choudhury and R. Nandi: Quadratic embedding constants of graphs: Bounds and distance spectra, Linear Algebra Appl. 680 (2024), 108–125.
  * [6] M. M. Deza and M. Laurent: “Geometry of Cuts and Metrics,” Springer-Verlag, Berlin, 1997.
  * [7] G. Indulal and I. Gutman: On the distance spectra of some graphs, Mathematical Communications 13 (2008), 123–131.
  * [8] W. Irawan and K. A. Sugeng, Quadratic embedding constants of hairy cycle graphs, Journal of Physics: Conference Series 1722 (2021) 012046.
  * [9] G. Jaklič and J. Modic: On Euclidean distance matrices of graphs, Electron. J. Linear Algebra 26 (2013), 574–589.
  * [10] G. Jaklič and J. Modic: Euclidean graph distance matrices of generalizations of the star graph, Appl. Math. Comput. 230 (2014), 650–663.
  * [11] L. Liberti, G. Lavor, N. Maculan and A. Mucherino: Euclidean distance geometry and applications, SIAM Rev. 56 (2014), 3–69.
  * [12] H. Lin, Y. Hong, J. Wang, J. Shub, On the distance spectrum of graphs, Linear Algebra Appl. 439 (2013), 1662–1669.
  * [13] Z. Z. Lou, N. Obata and Q. X. Huang: Quadratic embedding constants of graph joins, Graphs and Combinatorics 38 (2022), 161 (22 pages).
  * [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: Complete multipartite graphs of non-QE class, Electronic J. Graph Theory Appl. 11 (2023), 511–527.
  * [19] N. Obata and A. Y. Zakiyyah: Distance matrices and quadratic embedding of graphs, Electronic J. Graph Theory Appl. 6 (2018), 37–60.
  * [20] M. Purwaningsih and K. A. Sugeng, Quadratic embedding constants of squid graph and kite graph, Journal of Physics: Conference Series 1722 (2021) 012047.
  * [21] F. S. Roberts and J. H. Spencer: A characterization of clique graphs, J. Combinat. Theory B 10 (1971), 102–108.
  * [22] I. J. Schoenberg: Remarks to Maurice Fréchet’s article “Sur la définition axiomatique d’une classe d’espace distanciś vectoriellement applicable sur l’espace de Hilbert”, Ann. of Math. 36 (1935), 724–732.
  * [23] I. J. Schoenberg: Metric spaces and positive definite functions, Trans. Amer. Math. Soc. 44 (1938), 522–536.
  * [24] J. L. Szwarcfiter: 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.