We consider the problem of characterizing the generic rigidity of bar-joint frameworks in $\mathbb{R}^d$ in which each vertex is constrained to lie in a given affine subspace. The special case when $d=2$ was previously solved by Streinu and Theran [ Discrete Comput. Geom., 44 (2020), pp. 812--837] and the case when each vertex is constrained to lie in an affine subspace of dimension $t$, and $d\geq t(t-1)$ was solved by Cruickshank et al. [ Int. Math. Res. Not. IMRN, 12 (2020), pp. 3824--3840]. We extend the latter result by showing that the given characterization holds whenever $d\geq 2t$.

We consider the problems of completing a low-rank positive semidefinite square matrix $M$ or a low-rank rectangular matrix $N$ from a given subset of their entries. Following the approach initiated by Singer and Cucuringu [SIAM J. Matrix Anal. Appl., 31 (2010), pp. 1621--1641] we study the local and global uniqueness of such completions by analyzing the structure of the graphs determined by the positions of the known entries of $M$ or $N$. We present combinatorial characterizations of local and global (unique) completability for special families of graphs. We characterize local and global completability in all dimensions for cluster graphs, i.e. graphs which can be obtained from disjoint complete graphs by adding a set of independent edges. These results correspond to theorems for body-bar frameworks in rigidity theory. We also provide a characterization of two-dimensional local completability of planar bipartite graphs, which leads to a characterization of two-dimensional local completability in the rectangular matrix model when the underlying bipartite graph is planar. These results are based on new observations that certain graph operations preserve local or global completability, as well as on a further connection between rigidity and completability. We also prove that a rank condition on the completability stress matrix of a graph is a sufficient condition for global completability. This verifies a conjecture of Singer and Cucuringu given in the paper cited above.

Let [Formula: see text] be a nonseparable plane graph on [Formula: see text] vertices with at least two edges. Suppose that [Formula: see text] has outer face [Formula: see text] and that every 2-vertex-cut of [Formula: see text] contains at least one vertex of [Formula: see text]. Let [Formula: see text] denote the chromatic polynomial of [Formula: see text]. We show that [Formula: see text] for all [Formula: see text]. This result is a corollary of a more general result that [Formula: see text] for all [Formula: see text], where [Formula: see text] is the multivariate Tutte polynomial of [Formula: see text], [Formula: see text], [Formula: see text] for all [Formula: see text] which are not incident to a vertex of [Formula: see text], [Formula: see text] for all [Formula: see text], [Formula: see text] for all other edges [Formula: see text], and [Formula: see text], [Formula: see text] are suitably chosen intervals with [Formula: see text].

Generalizing and unifying earlier results of W. Mader, and A. Frank and B. Jackson, we prove two splitting theorems concerning mixed graphs. By invoking these theorems we obtain min-max formulae for the minimum number of new edges to be added to a mixed graph so that the resulting graph satisfies local edge-connectivity prescriptions. An extension of Edmonds’s theorem on disjoint arborescences is also deduced along with a new sufficient condition for the solvability of the edge-disjoint paths problem in digraphs. The approach gives rise to strongly polynomial algorithms for the corresponding optimization problems.

Let G be a graph with a nowhere zero 4-flow. It is shown that the length of a shortest circuit cover of $E(G)$ is equal to the length of a shortest postman tour of $E(G)$. Using this result an efficient algorithm for constructing shortest circuit covers for graphs that possess two disjoint spanning trees is obtained. It is also deduced that if H is a $2m$-edge connected graph, $m \geqq 2$, then there exists a circuit cover of $E(H)$ of length at most $|E(H)|+\min \{ {{| E(H) |} / {(2m + 1)}}, | V(H) | - 1 \}$ and that if G has a nowhere zero 4-flow, then there exists a circuit cover of $V(G)$ of length at most $2|V(G)| -2$. Finally, it is shown that the equivalence between shortest circuit covers and postman tours may be extended to binary matroids that possess a nowhere zero $\mathbb{Z} _2 ^2$-flow.