Quadratic Embedding Constant

The quadratic embedding constant of a finite simple connected graph on vertices is defined as the maximum of the product over all real -vectors satisfying and , where is the graph distance matrix (Obata and Zakiyyah 2018, Obata 2022, Choudhury and Nandi 2023). Obata and Zakiyyah (2018) give quadratic embedding constants for connected graphs on 5 and fewer vertices (though the value given for the 12th graph on 5 nodes, i.e., the kite graph, is incorect).

Quadratic embedding constants for the singleton graph (Obata and Zakiyyah 2018), complete graphs with (Obata and Zakiyyah 2018, Obata 2022), complete bipartite graphs (Obata and Zakiyyah 2018, Obata 2022), cycle graphs (Obata and Zakiyyah 2018, Obata 2022), path graphs with (Młotkowski 2022, Obata 2022), and wheel graphs (E. Weisstein, Jul. 3, 2023) are given by

			(1)
			(2)
			(3)
			(4)
			(5)
			(6)

Obata (2022) gives quadratic embedding constants for complete -partite graphs in general.

Any graph obtained by deleting two or more disjoint subsets from a complete graph has quadratic embedding constant equal to 0 (Obata and Zakiyyah 2018). This includes the square graph , wheel graph , octahedral graph , queen graph , 16-cell graph , and complete -partite graphs , , etc.

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

For a connected graph whose graph distance matrix has equal row sums, the quadratic embedding constant is given by the second largest eigenvalue of (Obata and Zakiyyah 2018).

A connected graph for which is called a quadratically embeddable graph.