李瑞娟, 陈淑凤
应用数学学报. 2022, 45(3): 355-368.
设 $ G$ 是一个无向多重图, $ G$ 的定向直径是指 $ G$ 的所有强连通定向中直径的最小值. Dankelmann, Guo, Surmacs [J. Graph Theory, 2018, 88: 5--17] 证明了 $ n$ 阶无桥图 $ G$ 的定向直径至多为 $ n-\Delta+3$, 这里 $ \Delta$ 是 $ G$ 的最大度. 设$ H$是 $ G$ 的一个生成子图, 定义 $ N_G(H)=\bigcup\limits_{v\in V(H)}N_G(v)\setminus V(H)$, 利用上述结论他们还证明了, 给定边 $ e$ 的无桥图 $ G$ 的定向直径至多为 $ n-|N_G(e)|+5$, 以及给定无桥子图 $ H$ 的无桥图 $ G$ 的定向直径至多为 $ n-|N_G(H)|+3$. 设 $ P_3=uvw$ 是 $ G$ 的一条长为 2 的路. 易见 $ P_3$ 包含两条边且这两条边均是 $ P_3$ 的桥. 本文利用将一条路收缩为一点的方法证明了给定 $ P_3$ 的无桥图$ G$ 的定向直径的上界为 $ n-|N_G(P_3)|+5$.特别地, 若 $ P_3$ 在一个 4 圈上或 $ P_3$ 不在一个圈上但 $ uv, vw$ 分别在一个 3 圈上, 定向直径至多为 $ n-|N_G(P_3)|+4$. 最后举例说明了上述上界是紧的.
