labeling

替一張圖的各個元件標記數值或者符號。一張圖的標記情形，稱作一種「標號」。

根據元件的不同，標號可分為許多種類型，例如點標號（vertex labeling）、邊標號（edge labeling）。

《Pearls in Graph Theory: A Comprehensive Introduction》

magic labeling

用1 2 3 ...的數字分別標記每一條邊，讓每一個點接觸的數字和為定值。

Kn,n有magic labeling（n≠2）。
一張二分圖如果可以拆成兩個Hamilton cycle，則有magic labeling。
一張圖如果可以拆成兩個部分，兩個都有magic labeling，且其中一個是regular，則有magic labeling。

幻方（magic square）可以等價轉換成K_n,n，所以邊長大於二的幻方一定都有magic labeling。

antimagic labeling

用1 2 3 ...的數字分別標記每一條邊，讓每一個點接觸的數字和皆相異。

尚未證實：K₂以外的連通圖皆有antimagic labeling。
尚未證實：K₂以外的樹皆有antimagic labeling。

graceful labeling

用1 2 3 ...的數字分別標記每一條邊，1 2 3 ...的數字分別標記每一個點，讓每一條邊等於其兩端點的差值。

尚未證實：所有樹皆有graceful labeling。

ICPC 7663

consecutive labeling

用1 2 3 ...的數字分別標記每一條邊與每一個點，讓每一條邊等於其兩端點的差值。

每一種graceful labeling皆可等價調整成一種consecutive labeling。但是反過來不見得行。

尚未證實：所有樹皆有consecutive labeling。

conservative labeling

無向圖上，用1 2 3 ...的數字分別標記每一條邊，並且設定方向（即是orientation的概念），讓每個點的流入數字和等於流出數字和（類似flow的概念）。

Kirchhoff's current law即是在說總流入等於總流出的性質。

strongly conservative labeling

改用n+1 n+2 n+3 ...的數字，必須支援各種n。

一張圖可以拆成兩個Hamilton cycle，則此圖有strongly conservative labeling。

minimum linear arrangement

用1 2 3 ...的數字分別標記每一個點，讓每一條邊等於其兩端點的差值，所有邊權重總和盡量小。