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]



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


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


D. G. Corneil, H. Lerchs, and L. Stewart Burlingham. “Complement reducible graphs”. In: Discrete Appl. Math. 3.3 (1981), pp. 163–174. url:


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.


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:


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


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