Strongly 4-path-connectivity in almost regular multipartite tournaments (Q2463909): Difference between revisions

If \(x\) is a vertex of a digraph \(D\), denote by \(d^+(x)\) and \(d^-(x)\) the outdegree and the indegree of \(x\). The global irregularity of \(D\) is defined by \(i_g(D)= \max\{d^+(x), d^-(x)\}- \min\{d^+(y), d^-(y)\}\) over all vertices \(x,y\in V(G)\). If \(i_g(D)= 0\), then \(D\) is regular and if \(i_g(D)\leq 1\), then \(D\) is almost regular. A digraph \(D\) is called strongly \(k\)-path-connected if for any two vertices \(x,y\in V(D)\) there exists an \((x,y)\)-path of order \(k\) and a \((y,x)\)-path of order \(k\) in \(D\). Here the authors prove that if \(D\) is an almost regular \(c\)-partite tournament with \(c\geq 8\) or with \(c=7\) and at least two vertices in every partite set, then \(D\) is strongly \(4\)-path-connected, which is best possible.