<p>Your description of an example of your question #2 of having vertex weights and distributing the weight on some <span class="math-container">$v$</span> to its neighbours sounds reminiscent of the <em>discharging method</em> 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: <a href="https://tel.archives-ouvertes.fr/tel-02083632/document" rel="nofollow noreferrer">https://tel.archives-ouvertes.fr/tel-02083632/document</a></p>
<p>As for your general question #2 of example problems studied with vertex weights, consider looking up</p>
<ul>
<li>graceful labelings (e.g. <a href="https://en.wikipedia.org/wiki/Graceful_labeling" rel="nofollow noreferrer">https://en.wikipedia.org/wiki/Graceful_labeling</a>)</li>
<li>channel assignment problems (e.g. <a href="https://www.sciencedirect.com/science/article/pii/S0166218X04002562" rel="nofollow noreferrer">https://www.sciencedirect.com/science/article/pii/S0166218X04002562</a>)</li>
<li>any vertex selection problem (like max clique, min vertex cover, etc) has a vertex-weighted analogue</li>
<li>problems that choose orderings of vertices (i.e. assign a <em>timestamp</em> to vertices) like in fire-fighter problems (<a href="https://www.sciencedirect.com/science/article/pii/S0012365X0600776X" rel="nofollow noreferrer">https://www.sciencedirect.com/science/article/pii/S0012365X0600776X</a>)  or graph burning problems (<a href="https://arxiv.org/abs/1507.06524" rel="nofollow noreferrer">https://arxiv.org/abs/1507.06524</a>)</li>
<li>the definition of <em>threshold graphs</em> involves looking at a vertex-weighted graph and adding an edge between any two vertices whose sum of vertex weights exceeds some threshold value: <a href="https://en.wikipedia.org/wiki/Threshold_graph" rel="nofollow noreferrer">https://en.wikipedia.org/wiki/Threshold_graph</a></li>
</ul>
<p>Here is a paper talking about more application problems of vertex-weighted graphs: <a href="https://www.researchgate.net/publication/268065544_Vertex-weighted_graphs_and_their_applications" rel="nofollow noreferrer">https://www.researchgate.net/publication/268065544_Vertex-weighted_graphs_and_their_applications</a></p>

CC BY-SA 4.0
2020-09-07T17:31:23.760Z
Thanks! This is pretty detailed
karl
CC BY-SA 4.0
2020-09-07T09:47:37.290Z
2020-09-07T09:47:37.290Z
JimN
<p>I am searching for literature related to a graph-like data structure where vertices are weighted instead of edges.</p>
<p>Formally, we can define a weighted-(edge)-graph <span class="math-container">$G=(V,E, w(\cdot))$</span> as a tuple of vertices <span class="math-container">$V$</span> and edges <span class="math-container">$E$</span> and a weights function <span class="math-container">$w: E \to \mathbb{R}$</span>.</p>
<blockquote>
<p>Now, I want to define a new data structure say a weighted-vertex graph as a tuple <span class="math-container">$(V,E,w(\cdot))$</span> of vertices <span class="math-container">$V$</span>, edges <span class="math-container">$E$</span> and a weights function <span class="math-container">$w: V \to \mathbb{R}$</span></p>
</blockquote>
<p>This seems related to graph coloring. Indeed, if we restrict to integer weights, then we can define vertex-colored graphs exactly this way.</p>
<p>My questions are as follows:</p>
<ol>
<li>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)</li>
<li>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?</li>
</ol>
<p>For example, one possible problem comes to mind. (I don't know if this has been studied)</p>
<blockquote>
<p>Suppose <span class="math-container">$G_0 = (V,E,w_0)$</span> and <span class="math-container">$G_1 = (V,E, w_1)$</span> are weighted-vertex-graph that share the same vertices and edges (but different weights). An &quot;action&quot; for a vertex <span class="math-container">$v$</span> consists of distributing <span class="math-container">$w(v)$</span> equally to its neighbors and then setting <span class="math-container">$w(v) = 0$</span>. Graphs <span class="math-container">$G_0$</span> and <span class="math-container">$G_1$</span> are called vertex-weight-isomorphic if you can convert from <span class="math-container">$G_0$</span> to <span class="math-container">$G_1$</span> using a finite sequence of actions. Find an algorithm that outputs whether two graphs are vertex-weight-isomorphic.</p>
</blockquote>
<p>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.</p>

CC BY-SA 4.0
2020-08-25T15:10:50.097Z
Question 1 seems somewhat ill-posed. What should it mean for these two definitions to be equivalent?
Christian Komusiewicz
CC BY-SA 4.0
2020-08-26T02:27:04.730Z
What I initially had in mind was whether any problem that takes as input an weighted-vertex-graph can be solved by first converting to some ``equivalent'' weighted-edge-graph representation and solving the problem there. But now that I think about this some more, this probably still might not make sense.
karl
CC BY-SA 4.0
2020-08-26T02:28:03.003Z
I'm far more interested in Question 2 though if you have come across something @ChristianKomusiewicz
karl
<graph-theory><graph-algorithms><ds.data-structures>
Graphs-like data structure with weighted vertices
karl
# Graphs-like data structure with weighted vertices

(Asked by: username_0 on 2020-08-24)

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.

**Tags:** graph-theory, graph-algorithms, ds.data-structures
> **Comments:**
> **username_1**: Question 1 seems somewhat ill-posed. What should it mean for these two definitions to be equivalent?  
> **username_0**: What I initially had in mind was whether any problem that takes as input an weighted-vertex-graph can be solved by first converting to some ``equivalent'' weighted-edge-graph representation and solving the problem there. But now that I think about this some more, this probably still might not make sense.  
> **username_0**: I'm far more interested in Question 2 though if you have come across something @ChristianKomusiewicz  

---

## 1 answers

### Answer by username_2 on 2020-09-07. Score: 1 | Accepted answer

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>

> **Comments:**
> **username_0**: Thanks! This is pretty detailed  

---

