Constructing total graph

asked 2022-04-26 13:31:49 +0200

vidyarthi
167 ●1 ●3 ●15

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.

edit retag flag offensive close merge delete

add a comment

2 Answers

Sort by » oldest newest most voted

answered 2022-04-27 15:39:51 +0200

rburing

10644 ●4 ●77 ●211 https://www.rburing.nl/

updated 2022-04-27 15:45:33 +0200

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

edit flag offensive delete link

Comments

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

vidyarthi ( 2022-04-28 08:54:12 +0200 )edit

add a comment

answered 2022-04-28 08:53:24 +0200

vidyarthi
167 ●1 ●3 ●15

updated 2022-04-28 09:01:48 +0200

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.

edit flag offensive delete link

add a comment

Your Answer

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

Add Answer

Constructing total graph

2 Answers

Comments

Your Answer

Question Tools

Stats

Related questions

Constructing total graph edit

2 Answers

Comments

Your Answer

Question Tools

Stats

Related questions

Constructing total graph