论文标题
关于定向网格的最大维纳指数
On maximum Wiener index of directed grids
论文作者
论文摘要
本文致力于定向图的维也纳索引，更准确地说是针对导向的网格。网格$ g_ {m，n} $是笛卡尔产品$ p_m \ box p_n $在$ m $和$ n $ vertices上的路径，并且在特定情况下，当$ m = 2 $时，它是一种称为梯形图$ l_n $。 Kraneršumenjak等。证明，当所有层同构对一个因子的所有层同构指向一个因子（对应于另一个因素的endvertex）时，这是针对另一个因素的指向，这是针对相反方式的定向路径，以相同的方式定向，这证明了通过将$ l_n $的边缘定向获得的最大维也纳指数，该路径是通过相同方式指向一个因子的。然后，他们推测，这种方向对$ g_ {m，n} $的自然概括将在$ g_ {m，n} $的所有方向中达到最大维纳索引。在本文中，我们通过表明$ g_ {m，n} $的梳状方向的构想来反驳猜想。
This paper is devoted to Wiener index of directed graphs, more precisely of directed grids. The grid $G_{m,n}$ is the Cartesian product $P_m\Box P_n$ of paths on $m$ and $n$ vertices, and in a particular case when $m=2$, it is a called the ladder graph $L_n$. Kraner Šumenjak et al. proved that the maximum Wiener index of a digraph, which is obtained by orienting the edges of $L_n$, is obtained when all layers isomorphic to one factor are directed paths directed in the same way except one (corresponding to an endvertex of the other factor) which is a directed path directed in the opposite way. Then they conjectured that the natural generalization of this orientation to $G_{m,n}$ will attain the maximum Wiener index among all orientations of $G_{m,n}$. In this paper we disprove the conjecture by showing that a comb-like orientation of $G_{m,n}$ has significiantly bigger Wiener index.
