A finite simple connected graph is quadratically embeddable if its quadratic
embedding constant is nonpositive, i.e., .

A graph being quadratically embeddable is equivalent to its graph distance matrix being conditionally negative definite (Obata and Zakiyyah 2018,
Obata 2022, Choudhury and Nandi 2023), i.e., it satisfying for all such that (Dyn *et al. *1986).

numbers of quadratically embeddable graphs on , 2, ... vertices are 1, 1, 2, 6, 19, 85, 452, 3174, 26898,
... (OEIS A363960). The corresponding numbers
of non-quadratically embeddable graph are 0, 0, 0, 0, 2, 27, 401, 7943, 234182, ...
(OEIS A363961). All connected graphs on
nodes are therefore quadratically embeddable, and the smallest non-quadratically
embeddable graphs are the two graphs on 5 vertices consisting of the complete
bipartite graph and the graph obtained from the wheel
graph by removing one spoke (Obata and Zakiyyah 2018).

Trees are quadratically embeddable (Obata and Zakiyyah 2018).

The quadratic embedding constant of a graph Cartesian product of graphs ,
,
... each having two or more vertices has , making them quadratically
embeddable (Obata 2022).

## See also

Graph Distance Matrix,

Quadratic Embedding Constant
## Explore with Wolfram|Alpha

## References

Choudhury, P. N. and Nandi, R. "Quadratic Embedding Constants of Graphs: Bounds and Distance Spectra." 27 Jun 2023. https://arxiv.org/abs/2306.15589.Dyn,
N.; Goodman, T.; and Micchelli, C. A. "Positive Powers of Certain Conditionally
Negative Definite Matrices." *Indagationes Math. (Proceedings)* **89**,
163-178, 1986.Obata, N. "Complete Multipartite Graphs of Non-QE
Class." 12 Jun 2022. https://arxiv.org/abs/2206.05848.Obata,
N. and Zakiyyah, A. Y. "Distance Matrices and Quadratic Embedding of Graphs."
*Elec. J. Graph Th. Appl.* **6**, 37-60, 2018.Schoenberg, I. J.
"Metric Spaces and Positive Definite Functions." *Trans. Amer. Math.
Soc.* **44**, 522-536, 1938.Sloane, N. J. A. Sequences
A363960 and A363961
## Cite this as:

Weisstein, Eric W. "Quadratically Embeddable
Graph." From *MathWorld*--A Wolfram Web Resource. https://mathworld.wolfram.com/QuadraticallyEmbeddableGraph.html