頂点推移グラフとは - わかりやすく解説 Weblio辞書

ウィキペディア

索引トップ用語の索引ランキングカテゴリー

頂点推移グラフ

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2020/02/17 07:07 UTC 版)

ナビゲーションに移動検索に移動

数学のグラフ理論の分野における頂点推移グラフ（ちょうてんすいいグラフ、英: vertex-transitive graph）とは、与えられた任意の二頂点 v₁ および v₂ に対して

f(v_{1})=v_{2}\

対称グラフ（例えば、ピーターセングラフ、ヒーウッドグラフ、正多面体の頂点と辺から成るグラフなど）であれば、有限の頂点推移グラフである。有限のケイリーグラフ（例えば、キューブ連結サイクル（英語版）など）もまた、頂点推移的である。なぜならば、それは半正多面体の頂点と辺から成るため（それらのうち対称であるものは二つしかないが）である。Potočnik、Spiga および Verret は、最大 1280 個の頂点を含む全ての連結立体頂点推移グラフの調査を行った^[2]。

性質

頂点推移グラフの辺連結度（英語版）は、その次数 d に等しい。一方、その頂点連結度（英語版）は少なくとも 2(d+1)/3 である^[3]。そのグラフの次数が 4 以下であるか、グラフが辺推移的であるか、あるいは最小のケイリーグラフであるなら、その頂点連結度も次数 d と等しくなる^[4]。

無限の例

無限な頂点推移グラフは次を含む:

無限路（両方向に無限）
無限正則木。例えば、自由群のケイリーグラフ
正多角形によるタイル張り（英語版）を含む、平面一様充填（英語版）のグラフ（平面充填の一覧（英語版）を参照されたい）
無限ケイリーグラフ
ラドグラフ（英語版）

二つの可算な頂点推移グラフが準等距離同型（quasi-isometric）であるとは、それらの距離函数の比が上下ともに有界であることを言う。有名な予想に、全ての無限な頂点推移グラフはケイリーグラフと準等距離同型である、というものがあったが、その反例はディエステルとリーダー（英語版）によって提唱され^[5]、近年、エスキン、フィッシャーおよびホワイトによってその確証が得られた^[6]。

参考文献

^ Godsil, Chris; Royle, Gordon (2001), Algebraic Graph Theory, Graduate Texts in Mathematics, 207, New York: Springer-Verlag .
^ Potočnik P., Spiga P. and Verret G. (2012), Cubic vertex-transitive graphs on up to 1280 vertices, Journal of Symbolic Computation .
^ Godsil, C. and Royle, G. (2001), Algebraic Graph Theory, Springer Verlag
^ Babai, L. (1996), Technical Report TR-94-10, University of Chicago [1]
^ Diestel, Reinhard; Leader, Imre (2001), “A conjecture concerning a limit of non-Cayley graphs”, Journal of Algebraic Combinatorics 14 (1): 17–25, doi:10.1023/A:1011257718029 .
^ Eskin, Alex; Fisher, David; Whyte, Kevin (2005年). “Quasi-isometries and rigidity of solvable groups”. arXiv:math.GR/0511647. .