1
$\begingroup$

I'VE COMPLETELY REVISED MY QUESTION

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]

NOTE:
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

$\endgroup$
1
  • 1
    $\begingroup$ Might there be a Sage forum for mailing list for Sage users? If so, that would be a better place to ask this question. $\endgroup$
    – David Roberts
    Feb 23, 2013 at 10:31

2 Answers 2

1
$\begingroup$

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):
     ed=[]
     for u,v in G.edges(labels=False):
         if (v,u) in ed:  continue
         ed += [(u,v)]

     g=DiGraph(ed)
     return g
$\endgroup$
3
  • $\begingroup$ 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. $\endgroup$
    – jtaa
    Feb 23, 2013 at 14:10
  • $\begingroup$ Note for that for the line graph you will get 2 vertices for the pair of reverse edges. $\endgroup$
    – joro
    Feb 23, 2013 at 14:45
  • $\begingroup$ 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? $\endgroup$
    – jtaa
    Feb 23, 2013 at 17:49
1
$\begingroup$

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 ) ])
$\endgroup$

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