典型文献
给定P3的无桥图的定向直径
文献摘要：
设G 是一个无向多重图,G 的定向直径是指G 的所有强连通定向中直径的最小值.Dankelmann,Guo,Surmacs[J.Graph Theory,2018,88:5-17]证明了n 阶无桥图G 的定向直径至多为n-A+3,这里A 是G 的最大度.设H 是G 的一个生成子图,定义NG(H)=U NG(v)\v∈V(H)V(H),利用上述结论他们还证明了,给定边e 的无桥图G 的定向直径至多为n-|NG(e)|+5,以及给定无桥子图H 的无桥图G 的定向直径至多为n-|NG(H)|+3.设P3=uvw 是G 的一条长为2 的路.易见P3 包含两条边且这两条边均是P3 的桥.本文利用将一条路收缩为一点的方法证明了给定P3 的无桥图G 的定向直径的上界为n-|NC(P3)|+5.特别地,若P3 在一个4 圈上或P3 不在一个圈上但uv,vw 分别在一个3 圈上,定向直径至多为n-|NC(P3)|+4.最后举例说明了上述上界是紧的.
文献关键词：
定向直径;无桥图;强连通定向
中图分类号：
作者姓名：
李瑞娟;陈淑凤
作者机构：
山西大学数学科学学院,太原030006
文献出处：
引用格式：
[1]李瑞娟;陈淑凤-.给定P3的无桥图的定向直径)[J].应用数学学报,2022(03):355-368
A类：
定向直径,强连通定向,Dankelmann,Surmacs,A+3
B类：
P3,无桥图,重图,中直,最小值,Guo,Graph,Theory,至多,最大度,子图,NG,定边,+5,uvw,易见,上界,NC,一个圈,+4,举例说明
AB值：
0.212858
相似文献
机标中图分类号，由域田数据科技根据网络公开资料自动分析生成，仅供学习研究参考。
