综述-圈

• 摘要
• 无向图中的圈

摘要

圈的概念在图论中起着基础性作用.

无向图中的圈

• 令 \(G\) 是无向图. 记 \(n=|V(G)|,~m=|E(G)|\). 用 \(\delta(G)\) 表示图 \(G\) 的最小度. 用 \(\ell(G),~circ(G)\) 分别表示图 \(G\) 的最长路和最长圈的长度.
  • \(\ell(G)\geqslant \delta(G)\)，\(circ(G)\geqslant \delta(G)+1\). Dirac，1952.
  • \(\ell(G)\geqslant 2m/n,~circ(G)\geqslant 2m/(n-1)\). Erdos 和 Gallai，1959.

G. A. Dirac, Some theorems on abstract graphs, Proc. London Math. Soc. 2 (1952) 69-81.
P. Erdos, T. Gallai, On maximal paths and circuits, Acta Math. Sci. Hungar. 10 (1959) 337-356.

• 若 \(G\) 是2-连通图，则 \(circ(G)\geqslant \min\{2\delta, n\}\).

• 令 \(G^w\) 是边赋权图. 用 \(\ell^w(G),~circ^w(G)\) 分别表示图 \(G\) 的最重路和最重圈的长度，这里最重是指边权之和最大.

  • 若 \(\sum_{u\in N^-(v)} w(uv)\geqslant 1\)，则 \(circ^w(G^w)\geqslant 1\).
  • 若

A. Frieze, C. McDiarmid, B. Reed, On a conjecture of Bondy and Fan, Ars Combinatoria 33 (1992) 329-336.