维度 ,也称为图的欧几里得维度(例如,Buckley 和 Harary 1988),是欧几里得空间 的最小维度 ,其中图 可以被嵌入,且每条边的长度都等于 1,每个顶点的位置都不同(但边可以交叉或重叠,点可以位于不与其关联的边上;Erdős et al. 1965)。
任何最大顶点度为 的连通图 connected graph 的图维度最多为 ,除了效用图 utility graph (Frankl et al. 2018)。此外,任何色数为 的图 chromatic number 的图维度最多为 。这可以通过将空间划分为 个正交的二维平面来实现,然后在每个平面上,将具有一种颜色的顶点放置在以平面原点为中心的半径为 的圆上(因此所有点的平方范数为 1/2)(J. Tan,私人通信,2021 年 10 月 26 日)。
对于任何非空图 ,图的笛卡尔积 graph Cartesian product 满足
(1)
|
(Erdős et al. 1965, Buckley 和 Harary 1988)。虽然这两个参考文献都声明该定理适用于“任何”图,但如果将 视为空图 empty graph ,则 同构于梯子图 ladder rung graph 。然而,对于 ,(因为根据图维度的定义,顶点不能重叠),并且 ,因为每个 路径都可以放置在 1 维线上。
单点图 singleton graph 的图维度为 ,路径图 path graphs (对于 )的图维度为 ,一般来说,任何维度为 2 或更小的图都被称为单位距离图 unit-distance graph。
完全图 complete graph 的维度是 (Erdős et al. 1965, Buckley 和 Harary 1988)。对于完全二分图 complete bipartite graph ,其中 ,
(2)
|
(Erdős et al. 1965, Buckley 和 Harary 1988)。
的维度由 给出,对于 (Erdős et al. 1965)。
超立方体图 hypercube graph 的维度为 ,对于 (Erdős et al. 1965)。
轮图 wheel graph 的图维度对于 为 2(因此是单位距离图 unit-distance),否则为 3(因此不是单位距离图)(Erdős et al. 1965, Buckley 和 Harary 1988)。
下表总结了各种参数化图族的图维度。