TOPICS
Search

Quadratically Embeddable Graph

A finite simple connected graph G is quadratically embeddable if its quadratic embedding constant QEC(G) is nonpositive, i.e., QEC(G)<=0.

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 v^(T)Dv<=0 for all v in R^n such that sum_(i=1)^(n)v_i=0 (Dyn et al. 1986).

The numbers of quadratically embeddable graphs on n=1, 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 <=4 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 K_(2,3) and the graph obtained from the wheel graph W_5 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 G_1, G_2, ... each having two or more vertices has QEC(G_1 square G_2 square ...)=0, 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 in "The On-Line Encyclopedia of Integer Sequences."

Cite this as:

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