Введение
Граф, в котором все пары ребер являются автоморфными. Теория графов. В математической области теории графов, краево-транзитивный граф — это граф G, такой что для любых двух ребер e₁ и e₂ графа G существует автоморфизм G, отображающий e₁ в e₂. Иными словами, граф является краево-транзитивным, если его группа автоморфизмов действует транзитивно на множестве его ребер.
graph theory
In the mathematical field of graph theory, an edge transitive graph is a graph G such that, given any two edges and of G, there is an automorphism of G that maps to
In other words, a graph is edge transitive if its automorphism group acts transitively on its edges.
Примеры и свойства
Количество связных простых краевых транзитивных графов на n вершинах равно 1, 1, 2, 3, 4, 6, 5, 8, 9, 13, 7, 19, 10, 16, 25, 26, 12, 28. Краевые транзитивные графы включают в себя все симметричные графы, такие как вершины и ребра куба. Примеры графов, краевых, но не вершинных транзитивных графов, включают полные двудольные графы, где m ≠ n, в том числе звездные графы. Для графов на n вершинах существует (n-1)/2 таких графов при нечетном n и (n-2)/2 при четном n. Дополнительные краевые транзитивные графы, которые не являются симметричными, могут быть образованы как подграфы этих полных двудольных графов в некоторых случаях. Подграфы полных двудольных графов Km,n существуют, когда m и n имеют общий делитель, больший 2. Когда наибольший общий делитель равен 2, подграфы существуют, когда 2n/m является четным, или если m=4 и n является нечетным кратным 6. Таким образом, краевые транзитивные подграфы существуют для K3,6, K4,6 и K5,10, но не для K4,10. Альтернативный способ построения некоторых краевых транзитивных графов – добавление вершин в середины ребер симметричного графа с v вершинами и e ребрами, что создает двудольный граф с e вершинами порядка 2 и v вершинами порядка 2e/v. Краевой транзитивный граф, который также является регулярным, но все еще не является вершинным транзитивным, называется полусимметричным. Граф Грея, кубический граф на 54 вершинах, является примером регулярного графа, который является краевым транзитивным, но не вершинным транзитивным. Граф Фолькмана, тетраэдрический граф на 20 вершинах, является наименьшим графом такого типа. Вершинная связность краевого транзитивного графа всегда равна его минимальной степени.
Edge transitive graphs include all symmetric graph, such as the vertices and edges of the cube. Examples of edge but not vertex transitive graphs include the complete bipartite graphs where m ≠ n, which includes the star graphs For graphs on n vertices, there are (n 1)/2 such graphs for odd n and (n 2) for even n.
Additional edge transitive graphs which are not symmetric can be formed as subgraphs of these complete bi partite graphs in certain cases. Subgraphs of complete bipartite graphs Km,n exist when m and n share a factor greater than 2. When the greatest common factor is 2, subgraphs exist when 2n/m is even or if m=4 and n is an odd multiple of 6. So edge transitive subgraphs exist for K3,6, K4,6 and K5,10 but not K4,10. An alternative construction for some edge transitive graphs is to add vertices to the midpoints of edges of a symmetric graph with v vertices and e edges, creating a bipartite graph with e vertices of order 2, and v of order 2e/v. An edge transitive graph that is also regular, but still not vertex transitive, is called semi symmetric. The Gray graph, a cubic graph on 54 vertices, is an example of a regular graph which is edge transitive but not vertex transitive. The Folkman graph, a quartic graph on 20 vertices is the smallest such graph. The vertex connectivity of an edge transitive graph always equals its minimum degree.