Let $G = (V,E)$ be a connected simple graph (unweighted, undirected, no selfloops) on $n$ nodes.
Let $\mathbf{d} := (d_1, d_2, ..., d_n) \in \mathbb{R}_{>0}^n$ be a vector of arbitrary given *node weights*. Now, I want to find symmetric, positive *edge weights* $W := [w_{ij}]_{i,j=1,...,n}$ that fit the given node weights on $G$, i.e. :

- symmetry : $w_{ij} = w_{ji}$
- positivity and $G$-restriction : $w_{ij} > 0 \Leftrightarrow (i,j) \in E$ and $w_{ij} = 0$ otherwise
- fitting the given node weights : $\forall i=1,...,n : \sum_{j=1}^n w_{ij} = d_i$

Thus, I want to find some weighted, undirected graph $G_W$ that is constructed by assigning appropriate edge weights to the edges of $G$, which sum up to the pre-defined degrees.

Surely, there are choices of $\mathbf{d}$ for which no fitting edge weights $W$ exist, think for example of a triangle and $\mathbf{d} = (10, 1, 1)$. However, it is not hard to find non-trivial examples in which for many choices of $\mathbf{d}$ some fitting $W$ does exist.

This problem can also be interpreted as solving an underdetermined system of $n$ linear equations (one for each node) in $\frac{n^2-n}{2}$ free variables (the edge weights), plus the complicated 'positivity constraint'.

Further, one can formulate this as a linear program, which might be infeasible for some choices of $\mathbf{d}$. But I am interested in an algebraic solution (but perhaps this is already NP-complete?).

So my questions are:

- feasibility: For which choices of $\mathbf{d}$ does a solution $W$ exist?
- solving: How to find an explicit solution?
- background: Can you share deeper insights regarding this topic?

(Just as a weird idea, perhaps one can define the $w_{ij}$'s as entries of some vector $\mathbf{v}$ that turns out to be an eigenvector corresponding to the maximum eigenvalue of some irreducible non-negative matrix, thus, $\mathbf{v}$ having all its entries positive by the Perron-Frobenius theorem? Perhaps feasibility corresponds to irreducibility then?)