|
|||||
|
|
| 给定P3的无桥图的定向直径 | |
| 引用本文： | 李瑞娟,陈淑凤.给定P3的无桥图的定向直径[J].应用数学学报,2022(3):355-368. |
| 作者姓名： | 李瑞娟 陈淑凤 |
| 作者单位： | 山西大学数学科学学院 |
| 摘 要： | 设G是一个无向多重图,G的定向直径是指G的所有强连通定向中直径的最小值.Dankelmann,Guo,Surmacs J.Graph Theory,2018,88:5-17]证明了n阶无桥图G的定向直径至多为n-Δ+3,这里Δ是G的最大度.设H是G的一个生成子图,定义■,利用上述结论他们还证明了,给定边e的无桥图G的定向直径至多为n-|NG(e)|+5,以及给定无桥子图H的无桥图G的定向直径至多为n-|NG(H)|+3.设P3=uvw是G的一条长为2的路.易见P3包含两条边且这两条边均是P3的桥.本文利用将一条路收缩为一点的方法证明了给定P3的无桥图G的定向直径的上界为n-|NG(P3)|+5.特别地,若P3在一个4圈上或P3不在一个圈上但uv,vw分别在一个3圈上,定向直径至多为n-|NG(P3)|+4.最后举例说明了上述上界是紧的. |
| 关 键 词： | 定向直径 无桥图 强连通定向 |