Numerical Graph Invariants

実数に値を持つ グラフの不変量の中でも有名なものは, chromatic number だろう。 他 にもグラフの色付けに関連して各種不変量が定義されている。

• グラフの色付けに関する不変量

グラフの adjacency matrix の固有値の内, 最大のものを spectral radius といい, グラフの不変量の一つである。

• spectral radius

グラフの metric dimension は, Slater により [Sla75] で定義されたらしい。他にも Harary と Melter の [HM76] や Tomescu の [Tom08] などの文献がある。

• metric dimension

まだまだ多数のグラフの不変量が考えられている。

例えば, グラフに対してsimplicial complex などを対応させる幾何学的なグラフの不変量があると, それの Betti数 などの simplicial complex の numerical invariant を取ることによりグラフの numerical invariant が得られる。

実際, Engström [Eng] は independence complex の total Betti number を考えている。

グラフの不変量を決めたとき, どのようなグラフがその最大値あるいは最小値を取るかを調べる分野を extremal graph theory と呼ぶらしい。

• extremal graph theory

Survey として Nikiforov の [Nik] や Stein の [Ste] がある。 Bollobas の本 [Bol04] もある。

References

[Bol04]

Béla Bollobás. Extremal graph theory. Reprint of the 1978 original. Mineola, NY: Dover Publications Inc., 2004, pp. xx+488. isbn: 0-486-43596-2.

[Eng]

Alexander Engström. Graph colouring and the total Betti number. arXiv: 1412.8460.

[HM76]

Frank Harary and Robert A. Melter. “On the metric dimension of a graph”. In: Ars Combinatoria 2 (1976), pp. 191–195.

[Nik]

Vladimir Nikiforov. Some new results in extremal graph theory. arXiv: 1107.1121.

[Sla75]

Peter J. Slater. “Leaves of trees”. In: Proceedings of the Sixth Southeastern Conference on Combinatorics, Graph Theory, and Computing (Florida Atlantic Univ., Boca Raton, Fla., 1975). Winnipeg, Man.: Utilitas Math., 1975, 549–559. Congressus Numerantium, No. XIV.

[Ste]

Maya Stein. Extremal Infinite Graph Theory. arXiv: 1102.0697.

[Tom08]

Ioan Tomescu. “Discrepancies between metric dimension and partition dimension of a connected graph”. In: Discrete Math. 308.22 (2008), pp. 5026–5031. url: http://dx.doi.org/10.1016/j.disc.2007.08.089.