The line graph of a graph consisting of a single loop should again be
a single loop.
sage: g = DiGraph(matrix([[1]]),format='adjacency_matrix')
sage: g.loops()
[(0, 0, None)]
sage: lg = g.line_graph()
sage: lg.num_edges() # PROBLEM: there should be one
edge
0
My motivation:
The de Bruijn graphs are defined recursively by
DB_n = line_graph(DB_{n-1}), n >= 1
starting with DB_0 the graph with one vertex and two loops. The
number of vertices of DB_n is then 2^n.
sage: DB0 = DiGraph(matrix([[2]]),format='adjacency_matrix')
sage: DB0.loops()
[(0, 0, None), (0, 0, None)]
sage: DB1 = DB0.line_graph()
sage: DB1.num_verts() # there should be 2 vertices
1
sage: DB1.num_edges() # and 4 edges
0
Starting with the correct DB1, which does not have multiple loops,
there is still a problem:
sage: DB1 = DiGraph(matrix([[1,1],[1,1]]),format='adjacency_matrix')
sage: DB2 = DB1.line_graph()
sage: DB2.num_edges() # there should be 8 edges
(loops missing)
6
Dave
--
To post to this group, send an email to [email protected]
To unsubscribe from this group, send an email to
[email protected]
For more options, visit this group at http://groups.google.com/group/sage-devel
URL: http://www.sagemath.org
