維度 ,也稱為圖的歐幾里得維度(例如,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)。
下表總結了各種引數化圖族的圖維度。