ASKSAGE: Sage Q&A Forum - RSS feedhttps://ask.sagemath.org/questions/Q&A Forum for SageenCopyright Sage, 2010. Some rights reserved under creative commons license.Thu, 28 Apr 2022 08:54:12 +0200Constructing total graphhttps://ask.sagemath.org/question/62168/constructing-total-graph/ 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. Tue, 26 Apr 2022 13:31:49 +0200https://ask.sagemath.org/question/62168/constructing-total-graph/Answer by vidyarthi for <p>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$.</p>
<p>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. </p>
https://ask.sagemath.org/question/62168/constructing-total-graph/?answer=62191#post-id-62191By 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.Thu, 28 Apr 2022 08:53:24 +0200https://ask.sagemath.org/question/62168/constructing-total-graph/?answer=62191#post-id-62191Answer by rburing for <p>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$.</p>
<p>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. </p>
https://ask.sagemath.org/question/62168/constructing-total-graph/?answer=62178#post-id-62178There is a [subdivide_edges](https://doc.sagemath.org/html/en/reference/graphs/sage/graphs/generic_graph.html#sage.graphs.generic_graph.GenericGraph.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](/upfiles/165106666588089.png)Wed, 27 Apr 2022 15:39:51 +0200https://ask.sagemath.org/question/62168/constructing-total-graph/?answer=62178#post-id-62178Comment by vidyarthi for <p>There is a <a href="https://doc.sagemath.org/html/en/reference/graphs/sage/graphs/generic_graph.html#sage.graphs.generic_graph.GenericGraph.subdivide_edges">subdivide_edges</a> method but it doesn't seem to give control over the names of the new vertices.</p>
<p>If I understood the definition correctly then the implementation can go like this:</p>
<pre><code>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
</code></pre>
<p>Example 1:</p>
<pre><code>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)]
</code></pre>
<p>Example 2:</p>
<pre><code>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))
</code></pre>
<p><img src="/upfiles/165106666588089.png" alt="total graph of path graph"></p>
https://ask.sagemath.org/question/62168/constructing-total-graph/?comment=62192#post-id-62192Thanks! This uses looping unlike my answer, which uses the subdivide_edges methodThu, 28 Apr 2022 08:54:12 +0200https://ask.sagemath.org/question/62168/constructing-total-graph/?comment=62192#post-id-62192