Numerical Graph Invariants

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

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

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

• spectral radius

Feng ら [FLW14] によると, グラフの metric dimension は, Slater [Sla75] と Harary と Melter の [HM76; HM77] により, 独立に導入されたものである。Feng らは fractional metric dimension を調べているが, 他にも様々な変種が定義されている。

• metric dimension とその変種

グラフに対して simplicial complex などを対応させる 幾何学的なグラフの不変量があると, それの Betti数 などの simplicial complex の numerical invariant を取ることによりグラフの numerical invariant が得られる。 実際, Engström [Eng] は independence complex の total Betti number を考えている。

各辺の長さを\(1\)とし, 2つの頂点を結ぶ最短の道の長さを2頂点の距離として, グラフの頂点集合を 距離空間とみなすことができる。 すると, 距離空間の様々な不変量を用いることができる。 例えば, diameter など。

• diameter

まだまだ多数のグラフの不変量が考えられている。 これまで目にしたものを, 以下に記録してみた。

• Ramsey number
• topological index [Hos71]
• Cheeger constant [HLW06]
• domination number [BBP11]
• Lagrangian [MS65]
• gonality [GSW20]
• bondage number [Bau+83]
• Colin de Verdiére number [Col98; HLS99]
• \(\theta \)-number [Lov79]
• thinness [Shi25]

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

• extremal graph theory

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

References

[Bau+83]

Douglas Bauer, Frank Harary, Juhani Nieminen, and Charles L. Suffel. “Domination alteration sets in graphs”. In: Discrete Math. 47.2-3 (1983), pp. 153–161. url: https://doi.org/10.1016/0012-365X(83)90085-7.

[BBP11]

Arash Behzad, Mehdi Behzad, and Cheryl E. Praeger. “Fundamental dominations in graphs”. In: Bull. Inst. Combin. Appl. 61 (2011), pp. 6–16. arXiv: 0808.4022.

[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.

[Col98]

Yves Colin de Verdière. Spectres de graphes. Vol. 4. Cours Spécialisés [Specialized Courses]. Société Mathématique de France, Paris, 1998, pp. viii+114. isbn: 2-85629-068-X.

[Eng]

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

[FLW14]

Min Feng, Benjian Lv, and Kaishun Wang. “On the fractional metric dimension of graphs”. In: Discrete Appl. Math. 170 (2014), pp. 55–63. arXiv: 1112.2106. url: https://doi.org/10.1016/j.dam.2014.01.006.

[GSW20]

Dion Gijswijt, Harry Smit, and Marieke van der Wegen. “Computing graph gonality is hard”. In: Discrete Appl. Math. 287 (2020), pp. 134–149. arXiv: 1504.06713. url: https://doi.org/10.1016/j.dam.2020.08.013.

[HLS99]

H. van der Holst, L. Lovász, and A. Schrijver. “The Colin de Verdière graph parameter”. In: Graph theory and combinatorial biology (Balatonlelle, 1996). Vol. 7. Bolyai Soc. Math. Stud. János Bolyai Math. Soc., Budapest, 1999, pp. 29–85.

[HLW06]

Shlomo Hoory, Nathan Linial, and Avi Wigderson. “Expander graphs and their applications”. In: Bull. Amer. Math. Soc. (N.S.) 43.4 (2006), 439–561 (electronic). url: http://dx.doi.org/10.1090/S0273-0979-06-01126-8.

[HM76]

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

[HM77]

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

[Hos71]

Haruo Hosoya. “Topological Index. A Newly Proposed Quantity Characterizing the Topological Nature of Structural Isomers of Saturated Hydrocarbons”. In: Bulletin of the Chemical Society of Japan 44.9 (1971), pp. 2332–2339. url: https://doi.org/10.1246/bcsj.44.2332.

[Lov79]

László Lovász. “On the Shannon capacity of a graph”. In: IEEE Trans. Inform. Theory 25.1 (1979), pp. 1–7. url: http://dx.doi.org/10.1109/TIT.1979.1055985.

[MS65]

T. S. Motzkin and E. G. Straus. “Maxima for graphs and a new proof of a theorem of Turán”. In: Canadian J. Math. 17 (1965), pp. 533–540. url: https://doi.org/10.4153/CJM-1965-053-6.

[Nik11]

Vladimir Nikiforov. “Some new results in extremal graph theory”. In: Surveys in combinatorics 2011. Vol. 392. London Math. Soc. Lecture Note Ser. Cambridge Univ. Press, Cambridge, 2011, pp. 141–181. isbn: 978-1-107-60109-3. arXiv: 1107.1121.

[Shi25]

Yaroslav Shitov. “Graph thinness: a lower bound and complexity”. In: Pacific J. Math. 339.2 (2025), pp. 333–343. url: https://doi.org/10.2140/pjm.2025.339.333.

[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.

[Ste11]

Maya Stein. “Extremal infinite graph theory”. In: Discrete Math. 311.15 (2011), pp. 1472–1496. arXiv: 1102.0697. url: https://doi.org/10.1016/j.disc.2010.12.018.