I am searching for literature related to a graph-like data structure where vertices are weighted instead of edges.
Formally, we can define a weighted-(edge)-graph $G=(V,E, w(\cdot))$ as a tuple of vertices $V$ and edges $E$ and a weights function $w: E \to \mathbb{R}$.
Now, I want to define a new data structure say a weighted-vertex graph as a tuple $(V,E,w(\cdot))$ of vertices $V$, edges $E$ and a weights function $w: V \to \mathbb{R}$
This seems related to graph coloring. Indeed, if we restrict to integer weights, then we can define vertex-colored graphs exactly this way.
My questions are as follows:
- Is the formulation of weighted-vertex graph somehow equivalent to the standard formulation of an undirected weighted-(edge)-graph? (The answer to this is most likely no)
- What are some problems/algorithms studied for weighted-vertex-graphs? As mentioned before, graph coloring is one major class of problems if we restrict to integer weights. Are there any other problems with integer weights or can every problem be formulated as a coloring problem? What about for real weights?
For example, one possible problem comes to mind. (I don't know if this has been studied)
Suppose $G_0 = (V,E,w_0)$ and $G_1 = (V,E, w_1)$ are weighted-vertex-graph that share the same vertices and edges (but different weights). An "action" for a vertex $v$ consists of distributing $w(v)$ equally to its neighbors and then setting $w(v) = 0$. Graphs $G_0$ and $G_1$ are called vertex-weight-isomorphic if you can convert from $G_0$ to $G_1$ using a finite sequence of actions. Find an algorithm that outputs whether two graphs are vertex-weight-isomorphic.
I haven't given this specific problem much thought so it's possible it can be converted to a problem in standard graphs but it seems like these types of problems might be interesting.