维度 ,也称为图的欧几里得维度(例如,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)。
下表总结了各种参数化图族的图维度。