CORES OF SYMMETRIC GRAPHS
CORES OF SYMMETRIC GRAPHS
复制标题
DOI：
10.1017/s1446788708000815
复制
发表时间：
2008-10
影响因子：
0.7
通讯作者：
P. Cameron;P. A. Kazanidis
中科院分区：
文献类型：
--
作者：
P. Cameron;P. A. Kazanidis
图Γ的核是与Γ同态等价的最小图Δ（即在两个方向上都存在同态）。Γ的核在同构下是唯一的，是Γ的导出子图。我们给出一个在某种意义上与核对偶的结构。图Γ的船体是一个图，它包含Γ作为一个生成子图，并允许Γ的所有自同态，其核是一个与Γ的核同阶的完全图。这种结构与半群理论中出现的同步置换群的概念有关;我们通过用图表征这些置换群来提供更多的见解。已知点传递图的核是点传递的。在某些情况下，我们可以做更强的陈述：例如，如果Γ是一个非边传递图，我们证明要么Γ的核是完全的，要么Γ是它自己的核。秩3图是非边传递图。我们研究了其中的一些族，以决定核心的两种选择中的哪一种实际上成立。我们将看到这个问题是非常困难的，在某些情况下等价于有限几何中未解决的问题（例如，关于极空间中的传播，卵形和分割成卵形）。
Abstract The core of a graph Γ is the smallest graph Δ that is homomorphically equivalent to Γ (that is, there exist homomorphisms in both directions). The core of Γ is unique up to isomorphism and is an induced subgraph of Γ. We give a construction in some sense dual to the core. The hull of a graph Γ is a graph containing Γ as a spanning subgraph, admitting all the endomorphisms of Γ, and having as core a complete graph of the same order as the core of Γ. This construction is related to the notion of a synchronizing permutation group, which arises in semigroup theory; we provide some more insight by characterizing these permutation groups in terms of graphs. It is known that the core of a vertex-transitive graph is vertex-transitive. In some cases we can make stronger statements: for example, if Γ is a non-edge-transitive graph, we show that either the core of Γ is complete, or Γ is its own core. Rank-three graphs are non-edge-transitive. We examine some families of these to decide which of the two alternatives for the core actually holds. We will see that this question is very difficult, being equivalent in some cases to unsolved questions in finite geometry (for example, about spreads, ovoids and partitions into ovoids in polar spaces).