Important Classes and Constructions of Graphs

ここでは, 様々な文献に現れるグラフの class やグラフの構成方法のリストを作ってみた。 単に目にしたものをメモしただけであるが。

まずは, グラフの class に次のようなものがある。

  • 完全グラフ (complete graph)
  • bipartite graph
  • planar graph
  • tree
  • complete bipartite graph
  • perfect graph (Trotignon の survey [Tro])
  • chordal graph
  • cograph [CLB81]
  • hypercube
  • infinite graphs
  • tournament
  • branching graph or Bratelli diagram [Wah]

グラフの構成方法としては, このサイトにあるページとして, まず多面体のグラフがある。

から作られるグラフとして, まずは Cayley graph があるが, Hafezieha, Hosseinzadehb, Hossein-Zadehb, Iranmaneshb [Haf+] によると, 他にも様々なものがあるようである。

  • Cayley graph
  • character graph.
  • directed power graph あるいは power graph [AW]
  • coprime graph [MWY14]
  • coprime order graph [Ban]

References

[AW]

Amrita Acharyya and Allen Williams. Power Graphs of Finite Group. arXiv: 2012.02236.

[Ban]

Subarsha Banerjee. On a new graph defined on the order of elements of a finite group. arXiv: 1911.02763.

[CLB81]

D. G. Corneil, H. Lerchs, and L. Stewart Burlingham. “Complement reducible graphs”. In: Discrete Appl. Math. 3.3 (1981), pp. 163–174. url: http://dx.doi.org/10.1016/0166-218X(81)90013-5.

[Haf+]

Roghayeh Hafezieh, Mohammad Ali Hosseinzadeh, Samaneh Hossein-Zadeh, and Ali Iranmanesh. The influence of cut vertices and eigenvalues on character graphs of solvable groups. arXiv: 1909.09236.

[MWY14]

X. Ma, H. Wei, and L. Yang. “The coprime graph of a group”. In: Int. J. Group Theory 3.3 (2014), pp. 13–23. url: https://doi.org/10.1103/physrevd.90.032007.

[Tro]

Nicolas Trotignon. Perfect graphs: a survey. arXiv: 1301.5149.

[Wah]

Jonas Wahl. Traces on diagram algebras II: Centralizer algebras of easy groups and new variations of the Young graph. arXiv: 2009.08181.