TOPICS
Search

Quadratically Embeddable Graph

A quadratically embeddable graph is a finite simple connected graph G for which 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, Choudhury and Nandi 2023, Obata 2023), i.e., it satisfying v^TDv<=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, counted up to graph isomorphism, are 1, 1, 2, 6, 19, 85, 452, 3174, 26898, ... (OEIS A363960). The corresponding numbers of non-quadratically embeddable connected graphs are 0, 0, 0, 0, 2, 27, 401, 7943, 234182, ... (OEIS A363961). All connected graphs on <=4 vertices 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 graph Cartesian product of two or more quadratically embeddable graphs G_1, G_2, ..., each having two or more vertices, has quadratic embedding constant QEC(G_1 square G_2 square ...)=0 and is therefore quadratically embeddable (Obata and Zakiyyah 2018, p. 44).

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." Elec. J. Graph Th. Appl. 11, 511-527, 2023. https://doi.org/10.5614/ejgta.2023.11.2.14.Obata, N. and Zakiyyah, A. Y. "Distance Matrices and Quadratic Embedding of Graphs." Elec. J. Graph Th. Appl. 6, 37-60, 2018. https://doi.org/10.5614/ejgta.2018.6.1.4.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."

Referenced on Wolfram|Alpha

Quadratically Embeddable Graph

Cite this as:

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

Subject classifications