0
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ Question 1 seems somewhat ill-posed. What should it mean for these two definitions to be equivalent? $\endgroup$ Aug 25, 2020 at 15:10
  • $\begingroup$ 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. $\endgroup$
    – karl
    Aug 26, 2020 at 2:27
  • $\begingroup$ I'm far more interested in Question 2 though if you have come across something @ChristianKomusiewicz $\endgroup$
    – karl
    Aug 26, 2020 at 2:28

1 Answer 1

1
$\begingroup$

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

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

$\endgroup$
1
  • $\begingroup$ Thanks! This is pretty detailed $\endgroup$
    – karl
    Sep 7, 2020 at 17:31

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.