Strongly 4-path-connectivity in almost regular multipartite tournaments

DOI10.1016/J.DISC.2007.03.048MaRDI QIDQ2463909zbMATH OpenOpenAlexFDO

Authors Irene Stella, Lutz Volkmann, Stefan Winzen

Publication date 6 December 2007

Published in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.disc.2007.03.048

zbMATH Keywords

almost regular digraphs strongly \(k\)-path-connected

Mathematics Subject Classification ID

Directed graphs (digraphs), tournaments (05C20) Connectivity (05C40)

Review text

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.

Recommendations

Cites work

Cited in

(2)

This page was built for publication: Strongly 4-path-connectivity in almost regular multipartite tournaments

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2463909)