论文标题
禁用电图的禁止子图
Forbidden subgraphs of power graphs
论文作者
论文摘要
由$ p（g）$表示的组$ g $的无向功率图（或简单的电源图）是一个图形，其顶点是$ g $的元素，其中两个dertices $ u $和$ v $由IF之间的边缘连接，并且仅当$ = v^i $或$ v^i $或$ v = u^j $ for些$ i $ i $ i $ i $ i $ i $ i $ i $ j $。 许多重要的图形类，包括完美的图形，cographs，conordal图，拆分图和阈值图，可以在结构上或按照禁止诱导的子图进行定义。我们检查了这五个类中的每一个，并试图确定哪些组$ g $ power gruph $ p（g）$位于正在考虑的班级中。我们在尼尔氏群体的情况下给出了完整的结果，部分结果会导致更大的一般性。特别是，功率图总是完美的。并且我们完全确定其功率图是阈值或拆分图的组（两个类别的答案相同）。我们给出许多开放问题。
The undirected power graph (or simply power graph) of a group $G$, denoted by $P(G)$, is a graph whose vertices are the elements of the group $G$, in which two vertices $u$ and $v$ are connected by an edge between if and only if either $u=v^i$ or $v=u^j$ for some $i$, $j$. A number of important graph classes, including perfect graphs, cographs, chordal graphs, split graphs, and threshold graphs, can be defined either structurally or in terms of forbidden induced subgraphs. We examine each of these five classes and attempt to determine for which groups $G$ the power graph $P(G)$ lies in the class under consideration. We give complete results in the case of nilpotent groups, and partial results in greater generality. In particular, the power graph is always perfect; and we determine completely the groups whose power graph is a threshold or split graph (the answer is the same for both classes). We give a number of open problems.
