What happens to the cost of the nodes when the graph is converted to its corresponding Line Graph?

Question

I have a graph G. I want to convert the graph to its corresponding Line Graph. The graph G has cost associated with its nodes. I want to know how what happens to the cost of the nodes when the graph is converted to the Line Graph.

Answer 1

Given a graph (with the cost associated to each vertex in () brackets:

1 (8) ------ 2 (7)
 |  \         |
 |   \        |
 |   3 (9)    |
 |   /        |
 |  /         |
4 (6) ------ 5 (10)

You can associate costs to the dual graph by giving the edges in the dual the cost associated with the vertex:

          (8)
  [1,2] ------- [1,3]
    | \         /   \
    |  \ (8)   /(8)  \ (9)
    |   \     /       \
(7) |    [1,4] ----- [3,4]
    |         \  (6)  /
    |      (6) \     / (6)
    |           \   /
  [2,5] ------- [4,5]
          (10)

So the connection [1,4] to [3,4] goes through the vertex 4 which has an associated cost of 6 so the edge in the dual representing this gets a cost of 6.