论文标题
在Meyniel极端图表上
On Meyniel extremal families of graphs
论文作者
论文摘要
我们提供了Meyniel极端图的新结构，这些图是具有猜想最大的渐近COP数字的图形家族。使用跨度子图，我们证明有指数级的具有指定学位的新的Meyniel极值家庭。使用超图上的线性编程问题，我们探索了不是Meyniel极端的家庭的学位。我们给出了具有规定程度的顶点传输图的COP数量上最著名的上限。我们发现新的Meyniel极值定期图具有较大色调，直径较大的常规图，并探索了Meyniel极端图和两部分图之间的联系。
We provide new constructions of Meyniel extremal graphs, which are families of graphs with the conjectured largest asymptotic cop number. Using spanning subgraphs, we prove that there are an exponential number of new Meyniel extremal families with specified degrees. Using a linear programming problem on hypergraphs, we explore the degrees in families that are not Meyniel extremal. We give the best-known upper bound on the cop number of vertex-transitive graphs with a prescribed degree. We find new Meyniel extremal families of regular graphs with large chromatic number, large diameter, and explore the connection between Meyniel extremal graphs and bipartite graphs.
