First time here? Check out the FAQ!

Ask Your Question
3

Constructing total graph

asked 2 years ago

vidyarthi gravatar image

Let G be a graph of order n and size e. The total graph T is the graph associated to G, which consists of order n+e and edges consist of the union of the edges of G, the edges of line graph of G and the edges of the subdivision graph of G.

I know that there is the line_graph() module in SageMath. But, I am unaware of the any module for subdivision graph. In addition, how do we form a disjoint union of edges of the three graphs G, its line and subdivision graphs, when their vertex sets are different. So finally, how can we construct the total graph T in SageMath. Any hints? Thanks beforehand.

Preview: (hide)

2 Answers

Sort by » oldest newest most voted
2

answered 2 years ago

rburing gravatar image

updated 2 years ago

There is a subdivide_edges method but it doesn't seem to give control over the names of the new vertices.

If I understood the definition correctly then the implementation can go like this:

def total_graph(G):
    T = G.union(G.line_graph())
    for (a,b,l) in G.edges():
        T.add_edge(a, (a,b,l))
        T.add_edge(b, (a,b,l))
    return T

Example 1:

sage: graphs.PathGraph(2).edges()
[(0, 1, None)]
sage: total_graph(graphs.PathGraph(2)).edges(sort=False)
[(0, 1, None), ((0, 1, None), 0, None), ((0, 1, None), 1, None)]

Example 2:

sage: graphs.PathGraph(3).edges()
[(0, 1, None), (1, 2, None)]
sage: total_graph(graphs.PathGraph(3)).edges(sort=False)
[((0, 1, None), (1, 2, None), None), (0, 1, None), ((0, 1, None), 0, None), (1, 2, None), ((0, 1, None), 1, None), ((1, 2, None), 1, None), ((1, 2, None), 2, None)]
sage: total_graph(graphs.PathGraph(3))

total graph of path graph

Preview: (hide)
link

Comments

Thanks! This uses looping unlike my answer, which uses the subdivide_edges method

vidyarthi gravatar imagevidyarthi ( 2 years ago )
2

answered 2 years ago

vidyarthi gravatar image

updated 2 years ago

By using the equivalent definition of total graph as the square(or distance-2 graph) of the subdivision graph(the graph formed by subdividing each edge, we obtain the following pseudo-code:

def TotalGraph(G):
      h=G
      k = 1
      G.subdivide_edges(G.edges(), k)
      h=G.distance_graph(list(range(1,3)))
      return h

This seems to work in my case.

Preview: (hide)
link

Your Answer

Please start posting anonymously - your entry will be published after you log in or create a new account.

Add Answer

Question Tools

2 followers

Stats

Asked: 2 years ago

Seen: 369 times

Last updated: Apr 28 '22