A graph in which every vertex label is the sum of the labels of the edges incident on it.

algorithmscoloringcomputer sciencegraph theory

Suppose $G$ is a simple undirected graph in which every vertex and edge is labeled so that every vertex label is the sum of labels of all the edges incident on that vertex. The following is an example of such a graph.

An example graph

In the above graph, the vertex label $5$ is obtained as $5=1+2+2$. Similarly, the remaining vertex labels can be expressed in terms of the sum of labels of edges incident on it. The following are the questions.

(1) Is there any name for such a graph? Or, any helpful references in this regards?

(2) What are the applications or, significance of such graphs?

Best Answer

This is reminiscent of edge-graceful labelings which follow the same rules as yours, but with more restrictions:

  • The labels on the edges use every value from $1, 2, \dots, q$ exactly once, where $q$ is the number of edges.
  • The labels on the vertices are taken modulo $p$ (where $p$ is the number of vertices) and are also all distinct.

Such labelings exist only for some graphs.

In your case without restrictions, I would just refer to the graph as an edge-labeled graph. This doesn't mention the vertex labels, but those can be inferred from the edge labels anyway, so they don't have to be included as part of the definition.

Labels on edges are sometimes interpreted as distances (how "long" is that edge), and sometimes as weights (how "much" of the edge is there). In the second case, for a vertex $v$, taking the sum of weights of all edges incident to $v$ is a natural replacement for the degree of $v$.

You can also imagine replacing an edge with label $k$ by $k$ parallel edges with the same endpoints. In that case, we get a multigraph in which the former labels on the vertices are just their degrees.

Related Question