Graphs-like data structure with weighted vertices

Question

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:

1. 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)
2. 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.

Answer 1

Your description of an example of your question #2 of having vertex weights and distributing the weight on some $v$ to its neighbours sounds reminiscent of the discharging method famously used in proofs towards the 4-colour theorem. That method, though, had weights assigned to vertices and to the faces of the (planar) graph. But I believe the discharging method has found other applications. Here is a thesis on discharging methods: https://tel.archives-ouvertes.fr/tel-02083632/document

As for your general question #2 of example problems studied with vertex weights, consider looking up

• graceful labelings (e.g. https://en.wikipedia.org/wiki/Graceful_labeling)
• channel assignment problems (e.g. https://www.sciencedirect.com/science/article/pii/S0166218X04002562)
• any vertex selection problem (like max clique, min vertex cover, etc) has a vertex-weighted analogue
• problems that choose orderings of vertices (i.e. assign a timestamp to vertices) like in fire-fighter problems (https://www.sciencedirect.com/science/article/pii/S0012365X0600776X) or graph burning problems (https://arxiv.org/abs/1507.06524)
• the definition of threshold graphs involves looking at a vertex-weighted graph and adding an edge between any two vertices whose sum of vertex weights exceeds some threshold value: https://en.wikipedia.org/wiki/Threshold_graph

Here is a paper talking about more application problems of vertex-weighted graphs: https://www.researchgate.net/publication/268065544_Vertex-weighted_graphs_and_their_applications