Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.


I wish to take a simple undirected graph (i.e. the complete graph K_4) Arbitrarily direct said graph, and then create a line graph from the directed version of the graph.

However, in Sage it appears to create a line graph that shows a connection between two edges (that are just inverses of each other), so what I really want is a line graph that doesn't give an edge connected to its own inverse.

That's why I asked if we could remove cycles of length 2, but that doesn't seem to solve the problem.

Here's what I am trying to work out:

G = graphs.RandomGNP(4,1)
GD = G.to_directed() #orients G
m = GD.size() #number of edges of digraphG
LG = GD.line_graph() #the line graph of the digraph
IM = identity_matrix(QQ,GD.size())
T = LG.adjacency_matrix() #returns the adjacency matrix of the line graph
var('u') #defines u as a variable
X=IM-u*T #defines a new matrix X
Z=X.det() #defines polynomial in u aka inverse of the Ihara zeta function
Z #computes determinant of X
Z.coefficients(u) #extracts coefficients

considering my graph is a complete graph on 4 vertices - the coefficients should be as such:
[coeff,degree of u]
[1,0], [0,1], [0,2],[-8,3],[-2,4]

im only interested in coefficients up to the order of n=#of nodes in the graph, so here for K_4 obviously n=4.
where the coefficient of u^3 corresponds to the negative of twice the number of triangles in K_4
where the coefficient u^4 corresponds to the negative of twice the number of squares in K_4

share|improve this question
Might there be a Sage forum for mailing list for Sage users? If so, that would be a better place to ask this question. –  David Roberts Feb 23 '13 at 10:31
add comment

2 Answers

Not sure if the question is well defined - you can remove 2-cycles in many ways, getting different digraphs.

One possible approach is start with empty set of edges $E$. For all edges $(u,v) \in E(G)$ add $(u,v)$ to $E$ iff $(v,u) \not \in E$.

Here is a sample sage implementation:

 def removedigons(G):
     for u,v in G.edges(labels=False):
         if (v,u) in ed:  continue
         ed += [(u,v)]

     return g
share|improve this answer
I suppose what I want to do is: Create a directed graph, but when I create a line graph from the directed graph - I don't want the line graph to give connections between edges and their own inverse. –  jtaa Feb 23 '13 at 14:10
Note for that for the line graph you will get 2 vertices for the pair of reverse edges. –  joro Feb 23 '13 at 14:45
yes, that's exactly what i want. what i don't want is two vertices (edges) connected to each other when one is the inverse of the other. is there a way to stop that happening? –  jtaa Feb 23 '13 at 17:49
add comment
up vote 0 down vote accepted

I received an answer (from fidelbc on sagemath) elsewhere and this is what I had wanted: G=graphs.CompleteGraph(4) D=G.to_directed() L=D.line_graph() L.delete_edges([((x,y,None), (y,x,None)) for x,y in G.edges( labels=None ) ]) L.delete_edges([((x,y,None), (y,x,None)) for y,x in G.edges( labels=None ) ])

share|improve this answer
add comment

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.