考克斯特图

考克斯特图是一个 非哈密顿 三次对称图，具有 28 个顶点和 42 条边，可以如上图所示构建。它也可以构建为 graph expansion of 的图扩展，步长为 1、2 和 4，其中 是 爪状图 (Biggs 1993, p. 147)。在三次对称图的 Foster 普查中，它被表示为 。它是 距离正则 和 距离传递 的，交集数组为 。

上面展示了许多嵌入方式（例如，Read 和 Wilson 1998，第 162 页）。

考克斯特图的直线交叉数是 11，这是由 G. Exoo 在 1990 年左右确定的（G. Exoo，私人通讯，2019 年 5 月 12 日）。它是一个具有 28 个节点的 三次图，其最小可能的 图交叉数 为 11，使其成为 最小三次交叉数图（Pegg 和 Exoo 2009，Clancy et al. 2019）。

正如 Bondy (1972) 首次证明的那样，它也是 次哈密顿 的。

考克斯特图由其 谱 确定 (van Dam 和 Haemers 2002)。

考克斯特图的 二分双图 是 三次对称图 。

它也是一个 单位距离图，如上面的 单位距离嵌入 所示（Gerbracht 2008，私人通讯，2010 年 1 月 4 日）。

考克斯特图在 Wolfram 语言 中实现为GraphData["CoxeterGraph"].

如果从考克斯特图中 删除 任何边，则生成的图是 哈密顿连通图（上图左侧），它在 Wolfram 语言 中实现为GraphData["EdgeExcisedCoxeterGraph"]。三角形替换的考克斯特图（上图右侧）在关于 非哈密顿顶点传递图、H-*-连通图 和 哈密顿分解 的猜想中作为一个特殊的图出现。它在 Wolfram 语言 中实现为GraphData["TriangleReplacedCoxeterGraph"].