Removing Symmetry in Circulant Graphs and Point-Block Incidence Graphs
Removing Symmetry in Circulant Graphs and Point-Block Incidence Graphs
复制标题
DOI：
10.3390/math9020166
复制
发表时间：
2021-01-01
期刊：
影响因子：
2.4
通讯作者：
Narayan, Darren
中科院分区：
文献类型：
--
作者：
Brooks, Josephine;Carbonero, Alvaro;Narayan, Darren
图的自同构是顶点到自身的映射，使得相应边之间的连接被保留。图G中的顶点v是固定的，如果它在G的每一个自同构下都映射到自身。图G的固定数是指图G中顶点的最小数目，当固定时，G中的所有顶点都是固定的。固定数的确定是重要的，因为它可以用于确定图的自同构群-一个著名的和困难的问题。固定数最初是由Gibbons和Laison，Erwin和Harary和Boutin提出并研究的。在本文中，我们研究固定数的图形与底层循环结构，它提供了一个固有的对称性存在。我们首先确定循环图的固定数，表明在许多情况下固定数是2。然而，我们还表明，循环图与孪生，这是对顶点具有相同的邻域，有相当高的固定数。这是第一篇研究点块关联图的固定数的论文，它处于图论和组合设计理论的交叉点。我们还提出了一个令人惊讶的结果，确定无限族的图中，固定任何顶点固定每个顶点，从而消除所有的对称性，从图。
An automorphism of a graph is a mapping of the vertices onto themselves such that connections between respective edges are preserved. A vertex v in a graph G is fixed if it is mapped to itself under every automorphism of G. The fixing number of a graph G is the minimum number of vertices, when fixed, fixes all of the vertices in G. The determination of fixing numbers is important as it can be useful in determining the group of automorphisms of a graph-a famous and difficult problem. Fixing numbers were introduced and initially studied by Gibbons and Laison, Erwin and Harary and Boutin. In this paper, we investigate fixing numbers for graphs with an underlying cyclic structure, which provides an inherent presence of symmetry. We first determine fixing numbers for circulant graphs, showing in many cases the fixing number is 2. However, we also show that circulant graphs with twins, which are pairs of vertices with the same neighbourhoods, have considerably higher fixing numbers. This is the first paper that investigates fixing numbers of point-block incidence graphs, which lie at the intersection of graph theory and combinatorial design theory. We also present a surprising result-identifying infinite families of graphs in which fixing any vertex fixes every vertex, thus removing all symmetries from the graph.