给定P_(3)的无桥图的定向直径  

The Oriented Diameter of a Bridgeless Graph with Given P_(3)

作　　者：李瑞娟[1] 陈淑凤 LI RUIJUAN;CHEN SHUFENG(School of Mathematical Sciences,Shanxi University,Taiyuan 030006,China)

机构地区：[1]山西大学数学科学学院,太原030006

出　　处：《应用数学学报》2022年第3期355-368,共14页Acta Mathematicae Applicatae Sinica

基　　金：山西省基础研究计划项目(20210302123202);山西省优秀青年基金(201901D211197)资助项目。

摘　　要：设G是一个无向多重图,G的定向直径是指G的所有强连通定向中直径的最小值.Dankelmann,Guo,Surmacs[J.Graph Theory,2018,88:5-17]证明了n阶无桥图G的定向直径至多为n-Δ+3,这里Δ是G的最大度.设H是G的一个生成子图,定义■,利用上述结论他们还证明了,给定边e的无桥图G的定向直径至多为n-|N_(G)(e)|+5,以及给定无桥子图H的无桥图G的定向直径至多为n-|N_(G)(H)|+3.设P_(3)=uvw是G的一条长为2的路.易见P3包含两条边且这两条边均是P3的桥.本文利用将一条路收缩为一点的方法证明了给定P3的无桥图G的定向直径的上界为n-|N_(G)(P_(3))|+5.特别地,若P3在一个4圈上或P3不在一个圈上但uv,vw分别在一个3圈上,定向直径至多为n-|N_(G)(P_(3))|+4.最后举例说明了上述上界是紧的.Let G be an undirected multigraph.The oriented diameter of G is the minimum diameter of any strongly connected orientation of G.Dankelmann,Guo and Surmacs[J.Graph Theory.88(2018)5-17]showed that every bridgeless graph G of order n has an oriented diameter at most n-Δ+3,whereΔis the maximum degree of G.Let H be a spanning subgraph of G.By defining■and using the above conclusion,they also proved that the oriented diameter of a graph with a given edge e is at most n-|N_(G)(e)|+5,and for every bridgeless subgraph H of G,there is such an oriented diameter at most n-|N_(G)(H)|+3.Let P_(3)=uvw be a path of length 2 in G.It is easy to see that P3 contains two edges and both edges are its bridges.In this paper,we adopt the method of contracting the path to a vertex to prove that the upper bound of the oriented diameter of a graph Gwith given P_(3)is n-|N_(G)(P_(3))|+5.In particular,if P3 is in a 4 circle or P3 is not in a circle but both edges uv and vw are in some two triangles,the oriented diameter of G is at most n-|N_(G)(P_(3))|+4.Finally,examples show that the above bounds is tight.

关 键 词：定向直径 无桥图 强连通定向 

分 类 号：O157.6[理学—数学]