On extremal weighted digraphs with no heavy paths (Q968444): Difference between revisions

In this paper, the authors discuss three weighted degree conditions for the existence of heavy or Hamilton paths with one or two given end vertices in 2-connected weighted graphs. In this paper, the authors infer that the existence of heavy paths in weighted paths cannot established by generalising corresponding results in unweighted graphs. They first write the generalised results, which are false or invalid and then improve those results to valid or true results. The first result of the paper states that if \(x\) and \(y\) are two vertices of a 2-connected weighted graph \(G\) and if \(\max\{d^w(v_1),d^w(v_2)\}\geq d\) for every pair of non-adjacent vertices \(v_1\) and \(v_2\) in \(V(G)-\{x, y\}\), then \(G\) contains either an \((x, y)\)-path of weight at least \(d\) or a Hamilton \((x, y)\)-path, where \(d\) is a real number. Then, the authors prove a stronger result which states that for a real number \(d\), if \(x\) is a vertex of a 2-connected weighted graph \(G\) and \(\max\{d^w(v_1), d^w(v_2), d^w(v_3)\}\geq d\) for every three pairwise non-adjacent vertices \(v_1\), \(v_2\) and \(v_3\) in \(V(G)-\{x\}\), then \(G\) contains either an \(x\)-path (a path which starts from \(x\)) of weight at least \(d\) or a Hamilton \(x\)-path. As the third major result of the paper, the authors then show that for a real number \(d\), if \(x\) and \(y\) are two vertices of a 2-connected weighted graph \(G\) and \(\max\{d^w(v_1), d^w(v_2), d^w(v_3)\}\geq d\) for every three pairwise non-adjacent vertices \(v_1\), \(v_2\) and \(v_3\) in \(V(G)-\{x\}\), then at least one of the following statements is true: {\parindent=8mm \begin{itemize}\item[(i)] \(G\) contains an \((x, y)\)-path \(P\) with \(w(P)\geq d\); \item[(ii)] \(G\) contains an \(x\)-path \(P_1\) and a \(y\)-path \(P_2\) which are disjoint with \(w(P_1) + w(P_2)\geq d\); \item[(iii)] \(G\) contains an \(x\)-path \(P_1\) and a \(y\)-path \(P_2\) which are disjoint with \(V(G)=V(P_1)\cup V(P_2)\). \end{itemize}} The proofs given by the authors for the above three results are lengthy, but logical, sound and interesting. At the end of the paper, the authors pose a couple of open problems which highlight the scope for further research in this area. It is a nicely written article and the authors deserve much appreciation for this.