頂点推移性とエッジスワッピングプロパティ
シンプルな無向グラフ $G=(V,E)$ある場合は頂点推移的であると言われます$a,b\in V$ グラフ同型があります $\varphi:V\to V$ そのような $\varphi(a) = b$。
グラフと言う $G=(V,E)$いずれかのエッジの場合、エッジスワッピングプロパティがあります$e = \{x,y\} \in E$ グラフ同型があります $\varphi:V\to V$ そのような $\varphi(x) = y$ そして $\varphi(y) = x$。
これらのプロパティのいずれかが、接続されたグラフのもう一方を意味しますか？
回答
Ekinがコメントで述べているように、接続されたグラフの場合、エッジスワッププロパティは、パスに沿ってエッジスワップを構成することにより、頂点推移性を意味します。
他の含意は真実ではありません。隣接する頂点の任意のペアの場合、グラフは対称です$(u_1,v_1)$ そして $(u_2,v_2)$ 自己同型送信があります $u_1$ に $u_2$ そして $v_1$ に $v_2$。エッジの端点を他のエッジの端点にマップする方法を指定できるため、これはエッジ推移性よりも強力であることに注意してください（したがって、このようなグラフはアーク推移性とも呼ばれます）。
現在、ウィキペディアは、頂点推移的および辺推移的であるが対称ではないグラフがあると主張しています。このようなグラフにはエッジスワッピングプロパティを設定できません。そうしないと、エッジ推移性を使用し、必要に応じてエッジをスワッピングすることで、隣接する頂点の任意のペアを隣接する頂点の別のペアに送信できます。
頂点推移性、エッジ推移性、およびエッジスワッピングプロパティの関係について：三角柱グラフはエッジスワッピングプロパティを持っているため、頂点推移的ですが、エッジ推移的ではありません。頂点推移的であるが辺推移的ではなく、頭のてっぺんからエッジスワッピングプロパティを持っているグラフは考えられませんが、そのようなグラフがなかったら驚きます。