Edge-transitive graphs and combinatorial designs
Edge-transitive graphs and combinatorial designs
复制标题
DOI：
10.2140/involve.2019.12.1329
复制
发表时间：
2017-09
期刊：
影响因子：
--
通讯作者：
Heather Newman;Hector Miranda;D. Narayan
中科院分区：
文献类型：
--
作者：
Heather Newman;Hector Miranda;D. Narayan
如果一个图的自同构群作用在它的边上是传递的，则称它是边传递的。已知边传递图要么是点传递图，要么是二部图。本文给出了顶点数小于等于20 $的连通边传递图的一个完全分类。然后给出了边传递二部图的一个构造，并利用这个构造证明了当gcd（m，n）>2时，存在一个连通且边传递的非平凡二部子图.此外，我们还研究了K_{m，n}$的连通$（r，2）$双正则子图的边传递性和唯一性的充分必要条件，并利用这些结果讨论了$gcd（m，n）=2$的情形.然后，我们提出了点传递图中的边传递图的无限族，包括几类循环图。特别地，我们给出了某些循环图的边传递性的必要条件和充分条件。
A graph is said to be edge-transitive if its automorphism group acts transitively on its edges. It is known that edge-transitive graphs are either vertex-transitive or bipartite. In this paper we present a complete classification of all connected edge-transitive graphs on less than or equal to $20$ vertices. We then present a construction for an infinite family of edge-transitive bipartite graphs, and use this construction to show that there exists a non-trivial bipartite subgraph of $K_{m,n}$ that is connected and edge-transitive whenever $gcd(m,n)>2$. Additionally, we investigate necessary and sufficient conditions for edge transitivity of connected $(r,2)$ biregular subgraphs of $K_{m,n}$, as well as for uniqueness, and use these results to address the case of $gcd(m,n)=2$. We then present infinite families of edge-transitive graphs among vertex-transitive graphs, including several classes of circulant graphs. In particular, we present necessary conditions and sufficient conditions for edge-transitivity of certain circulant graphs.