论文标题
具有给定顺序和块数量的图形方向的直径
Diameter of orientations of graphs with given order and number of blocks
论文作者
论文摘要
图$ g $的强大方向是指向每个边缘的方向分配，以使$ g $连接。 $ g $的定向直径是$ g $的所有强度方向中最小的直径。 $ g $的块是没有切割顶点的最大连接子图。块图是一个图形，其中每个块都是一个集团。我们表明，每个包含$ p $块的订单$ n $的无用图图最多都有$ n- \ lfloor \ frac {p} {2} {2} \ rfloor $。对于所有$ n $和$ p $，带有$ p \ geq 2 $的所有界限都是锋利的。作为推论，我们在定向直径和切割顶点数方面获得了尖锐的上限。我们还表明，$ n $的无用块图的定向直径在上面由$ \ lfloor \ frac {3n} {4} {4} {4} \ rfloor $如果$ n $均匀而$ \ lfloor \ lfloor \ frac \ frac {3（n+1）} {4}} {4} {4} {4} {4} {4} {4} {4} \ rfloor $ n $ If $ n $ IF $ n $
A strong orientation of a graph $G$ is an assignment of a direction to each edge such that $G$ is strongly connected. The oriented diameter of $G$ is the smallest diameter among all strong orientations of $G$. A block of $G$ is a maximal connected subgraph of $G$ that has no cut vertex. A block graph is a graph in which every block is a clique. We show that every bridgeless graph of order $n$ containing $p$ blocks has an oriented diameter of at most $n-\lfloor \frac{p}{2} \rfloor$. This bound is sharp for all $n$ and $p$ with $p \geq 2$. As a corollary, we obtain a sharp upper bound on the oriented diameter in terms of order and number of cut vertices. We also show that the oriented diameter of a bridgeless block graph of order $n$ is bounded above by $\lfloor \frac{3n}{4} \rfloor$ if $n$ is even and $\lfloor \frac{3(n+1)}{4} \rfloor$ if $n$ is odd.
