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.