论文标题
寻找弗兰克数字的图表$ 3 $
Quest for graphs of Frank number $3$
论文作者
论文摘要
在图$ g $的方向$ o $中，仅当$ o-e $连接强烈时，边缘$ e $才能删除。对于$ 3 $ - 边缘连接的图$ G $，Hörsch和Szigeti将坦克号定义为最低$ k $，$ g $接收$ k $ g $方向，以至于每个边缘$ e $ g $ as $ g $至少在$ k $方向中的一个。他们猜想弗兰克号码最多是每3美元连接的图形$ g $的$ 3 $。他们证明了Petersen Graph的弗兰克数字$ 3 $，但这是该物业的唯一例子。我们显示了一个无限的图表，其中有弗兰克数字$ 3 $。 Hörsch和Szigeti显示，每3美元的$ 3 $ 3 $ 3 $连接的图形最多有$ 3 $。将非$ 3 $边缘色的图表视为坦率的数字大于$ 2 $的候选人很诱人。 Snarks有时是查找关键例子或反例的良好来源。一个人可能会怀疑各种Snarks应该拥有弗兰克数字$ 3 $。但是，我们证明了几个候选人无限类的snarks有弗兰克的$ 2 $。以及广义的彼得森图$ GP（2s+1，s）$。我们制定了许多受我们经验启发的猜想。
In an orientation $O$ of the graph $G$, the edge $e$ is deletable if and only if $O-e$ is strongly connected. For a $3$-edge-connected graph $G$, Hörsch and Szigeti defined the Frank number as the minimum $k$ for which $G$ admits $k$ orientations such that every edge $e$ of $G$ is deletable in at least one of the $k$ orientations. They conjectured the Frank number is at most $3$ for every $3$-edge-connected graph $G$. They proved the Petersen graph has Frank number $3$, but this was the only example with this property. We show an infinite class of graphs having Frank number $3$. Hörsch and Szigeti showed every $3$-edge-colorable $3$-edge-connected graph has Frank number at most $3$. It is tempting to consider non-$3$-edge-colorable graphs as candidates for having Frank number greater than $2$. Snarks are sometimes a good source of finding critical examples or counterexamples. One might suspect various snarks should have Frank number $3$. However, we prove several candidate infinite classes of snarks have Frank number $2$. As well as the generalized Petersen Graphs $GP(2s+1,s)$. We formulate numerous conjectures inspired by our experience.
