MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top


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|cite|improve this question

closed as off-topic by Ricardo Andrade, Steven Sam, Lucia, Chris Godsil, Ryan Budney Jun 6 '14 at 6:29

This question appears to be off-topic. The users who voted to close gave this specific reason:

  • "This question does not appear to be about research level mathematics within the scope defined in the help center." – Ricardo Andrade, Steven Sam, Lucia, Chris Godsil, Ryan Budney
If this question can be reworded to fit the rules in the help center, please edit the 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

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|cite|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
up vote 1 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|cite|improve this answer

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