Godsil Chris, Roberson David E, Rooney Brendan, Šámal Robert, Varvitsiotis Antonios
1Department of Combinatorics & Optimization, University of Waterloo, Waterloo, ON N2L 3G1 Canada.
2Department of Computer Science, University College London, London, WC1E 6BT UK.
Discrete Comput Geom. 2017;58(2):265-292. doi: 10.1007/s00454-017-9899-2. Epub 2017 Jun 19.
An embedding of the vertices of a graph is called if the following holds: For any other embedding satisfying for and adjacent to , there exists an isometry mapping to for all . The notion of universal completability was introduced recently due to its relevance to the positive semidefinite matrix completion problem. In this work we focus on graph embeddings constructed using the eigenvectors of the least eigenvalue of the adjacency matrix of , which we call . We identify two necessary and sufficient conditions for such frameworks to be universally completable. Our conditions also allow us to give algorithms for determining whether a least eigenvalue framework is universally completable. Furthermore, our computations for Cayley graphs on show that almost all of these graphs have universally completable least eigenvalue frameworks. In the second part of this work we study uniquely vector colorable (UVC) graphs, i.e., graphs for which the semidefinite program corresponding to the Lovász theta number (of the complementary graph) admits a unique optimal solution. We identify a sufficient condition for showing that a graph is UVC based on the universal completability of an associated framework. This allows us to prove that Kneser and -Kneser graphs are UVC. Lastly, we show that least eigenvalue frameworks of 1-walk-regular graphs always provide optimal vector colorings and furthermore, we are able to characterize all optimal vector colorings of such graphs. In particular, we give a necessary and sufficient condition for a 1-walk-regular graph to be uniquely vector colorable.
图的顶点嵌入若满足以下条件，则称为[具体条件未给出]：对于任何其他满足[具体条件未给出]且与[具体条件未给出]相邻的嵌入，存在一个等距映射，使得对于所有[具体条件未给出]，将[具体条件未给出]映射到[具体条件未给出]。由于通用完备性与半正定矩阵完备问题相关，它是最近才被引入的。在这项工作中，我们专注于使用图的邻接矩阵最小特征值的特征向量构建的图嵌入，我们将其称为[具体名称未给出]。我们确定了此类框架通用完备的两个充分必要条件。我们的条件还使我们能够给出用于确定最小特征值框架是否通用完备的算法。此外，我们对[具体内容未给出]上的凯莱图的计算表明，几乎所有这些图都具有通用完备的最小特征值框架。在这项工作的第二部分，我们研究唯一向量可着色（UVC）图，即其对应于（补图的）洛夫ász θ数的半定规划有唯一最优解的图。我们基于相关框架的通用完备性确定了一个表明图是UVC的充分条件。这使我们能够证明克内泽尔图和[具体内容未给出] - 克内泽尔图是UVC。最后，我们表明1 - 步行正则图的最小特征值框架总是提供最优向量着色，而且，我们能够刻画此类图的所有最优向量着色。特别地，我们给出了1 - 步行正则图唯一向量可着色的充分必要条件。
