Abstract
In 7 (Johnson, C.R., Kroschel, B.K. and Lundquist, M., 1998, The totally nonnegative completion problem. In: P.M. Pardalos and H. Wolkowicz (Eds) Fields Institute Communications: Topics in Semidefinite and Interior Point Methods (Providence: AMS), pp. 97–108.), the labeled graphs G for which every combinatorially symmetric partial totally nonnegative (TN) matrix, the graph of whose specified entries is G, has a TN completion were identified. In this study, a technical assumption is removed from that work, and the implication is that for other graphs, additional conditions on the specified data must hold. Here, we begin the investigation of what those additional conditions are and for what graphs they suffice. For 3-by-3 partial matrices a complete solution is given, and the ‘adjacent edge conditions’ that arise in the 3-by-3 case are shown to suffice for certain other classes of graphs. Conditions for each of the 24 labeled paths on four vertices are also derived.