グラフに対する各種操作

グラフに対する操作としては, 辺を潰すのと取り除くのが基本である。 それによりあるグラフが別のグラフの minor である, という概念が定義できる。 Robertson と Seymour により一連の論文 ([RS83]から [RS04]) の中で調べられている。

• contraction
• deletion
• minor

Minor を取る操作で閉じたグラフの類を考えるときには, “forbidden minor” による特徴付けを考える。例えば, 平面グラフを特徴づける Kuratowski の定理とか, 多面体のグラフに関する Steinitz の定理などがある。Robertson と Seymour の仕事は, その一般化と考えられる。 Robertson と Seymour の仕事の解説として, Lovász の [Lov06] がある。またこれらの一般化を Melikhov が [Mel] で考えている。

Capraso [Cap12] は, contraction だけを考えてそれをグラフの間の同値関係に拡張したものを linkage と呼んでいる。その論文の目的は, tropical curve の moduli space を調べることであるが。

Category theory の視点からは, product, coproduct, そして exponential graph (Hom graph) が考えられる。これらについては, Dochtermann の [Doc09] を見るとよい。

• product
• coproduct
• exponential graph (Hom graph)

Hajiabolhassan と Taherkhani [HT10] は graph の fractional power を考えている。

双対多面体に対する操作は, line graph と呼ばれる。Whitney [Whi32] により最初に考えられたらしい。 折れ線グラフも英語で line graph というので, 良い名前ではない。 双対グラフと呼んだ方が良いと思う。

• line graph

他に目についた操作として次のようなものがある。

• \(n\)-cone あるいは generalized Mycielski construction ([Tar01; DS12])
• whiskering や clique-whiskering ([Vil90; CN12])
• \(N\)-flip ([NSS06])
• blow-up ([HHN14])
• corona ([FH70; MM11])

Independence complex を通して, wiskering に対応する simplicial complex に対する操作も考えられている。Biermann と van Tuyl の [BV13] や Frohmader の [Fro] である。

References

[BV13]

Jennifer Biermann and Adam Van Tuyl. “Balanced vertex decomposable simplicial complexes and their \(h\)-vectors”. In: Electron. J. Combin. 20.3 (2013), Paper 15, 12. arXiv: 1202.0044. url: https://doi.org/10.37236/2552.

[Cap12]

Lucia Caporaso. “Geometry of tropical moduli spaces and linkage of graphs”. In: J. Combin. Theory Ser. A 119.3 (2012), pp. 579–598. arXiv: 1001.2815. url: https://doi.org/10.1016/j.jcta.2011.11.011.

[CN12]

David Cook II and Uwe Nagel. “Cohen-Macaulay graphs and face vectors of flag complexes”. In: SIAM J. Discrete Math. 26.1 (2012), pp. 89–101. arXiv: 1003.4447. url: https://doi.org/10.1137/100818170.

[Doc09]

Anton Dochtermann. “Hom complexes and homotopy theory in the category of graphs”. In: European J. Combin. 30.2 (2009), pp. 490–509. arXiv: math/0605275. url: http://dx.doi.org/10.1016/j.ejc.2008.04.009.

[DS12]

Anton Dochtermann and Carsten Schultz. “Topology of Hom complexes and test graphs for bounding chromatic number”. In: Israel J. Math. 187 (2012), pp. 371–417. arXiv: 0907.5079. url: http://dx.doi.org/10.1007/s11856-011-0085-6.

[FH70]

Roberto Frucht and Frank Harary. “On the corona of two graphs”. In: Aequationes Math. 4 (1970), pp. 322–325.

[Fro]

Andrew Frohmader. How to construct a flag complex with a given face vector. arXiv: 1112.6061.

[HHN14]

Hamed Hatami, James Hirst, and Serguei Norine. “The inducibility of blow-up graphs”. In: J. Combin. Theory Ser. B 109 (2014), pp. 196–212. arXiv: 1108.5699. url: https://doi.org/10.1016/j.jctb.2014.06.005.

[HT10]

Hossein Hajiabolhassan and Ali Taherkhani. “Graph powers and graph homomorphisms”. In: Electron. J. Combin. 17.1 (2010), Research Paper 17, 16. arXiv: 0808.0362. url: https://doi.org/10.37236/289.

[Lov06]

László Lovász. “Graph minor theory”. In: Bull. Amer. Math. Soc. (N.S.) 43.1 (2006), 75–86 (electronic). url: http://dx.doi.org/10.1090/S0273-0979-05-01088-8.

[Mel]

Sergey A. Melikhov. Combinatorics of embeddings. arXiv: 1103.5457.

[MM11]

Cam McLeman and Erin McNicholas. “Spectra of coronae”. In: Linear Algebra Appl. 435.5 (2011), pp. 998–1007. arXiv: 1111.1200. url: https://doi.org/10.1016/j.laa.2011.02.007.

[NSS06]

Atsuhiro Nakamoto, Tadashi Sakuma, and Yusuke Suzuki. “\(N\)-flips in even triangulations on the sphere”. In: J. Graph Theory 51.3 (2006), pp. 260–268. url: http://dx.doi.org/10.1002/jgt.20132.

[RS04]

Neil Robertson and P. D. Seymour. “Graph minors. XX. Wagner’s conjecture”. In: J. Combin. Theory Ser. B 92.2 (2004), pp. 325–357. url: http://dx.doi.org/10.1016/j.jctb.2004.08.001.

[RS83]

Neil Robertson and P. D. Seymour. “Graph minors. I. Excluding a forest”. In: J. Combin. Theory Ser. B 35.1 (1983), pp. 39–61. url: http://dx.doi.org/10.1016/0095-8956(83)90079-5.

[Tar01]

Claude Tardif. “Fractional chromatic numbers of cones over graphs”. In: J. Graph Theory 38.2 (2001), pp. 87–94. url: http://dx.doi.org/10.1002/jgt.1025.

[Vil90]

Rafael H. Villarreal. “Cohen-Macaulay graphs”. In: Manuscripta Math. 66.3 (1990), pp. 277–293. url: https://doi.org/10.1007/BF02568497.

[Whi32]

Hassler Whitney. “Congruent Graphs and the Connectivity of Graphs”. In: Amer. J. Math. 54.1 (1932), pp. 150–168. url: https://doi.org/10.2307/2371086.