Ask Your Question
1

How to get an arbitrary orientation of a graph.

asked 2013-02-22 20:59:05 +0100

jtaa gravatar image

updated 2013-02-23 12:11:16 +0100

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 digraph GD  
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

Here is an image of a K_4 graph minus an edge and the line graph construction of K_4 that i want Here is an image of a K_4 graph minus an edge and the line graph construction of K_4 that i am after

edit retag flag offensive close merge delete

Comments

I think the `line_graph` method is correct, so I'll edit the title so it is not misleading.

fidbc gravatar imagefidbc ( 2013-02-23 09:49:36 +0100 )edit

2 Answers

Sort by ยป oldest newest most voted
2

answered 2013-02-22 21:58:42 +0100

fidbc gravatar image

updated 2013-02-23 13:46:34 +0100

The line graph you obtain contains cycles of length 2 because the digraph D that to_directed() returns contains arcs (x,y) and (x,y) for each edge xy in the original graph G.

From what you show in your diagram you want the line graph of of D minus all the arcs connecting vertices that came from the same edge in G. Maybe this will do the job

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 ) ])

Here is what L looks like using this code.

Line graph minus some arcs.

edit flag offensive delete link more

Comments

When I create a line graph from D as you defined above it doesn't give me representations of the directed edges inverses. I need the inverses of the arbitrarily oriented edges too, but obviously not having an inverse connected to its original edge. Anyway to do that?

jtaa gravatar imagejtaa ( 2013-02-23 11:00:21 +0100 )edit

maybe to clarify further: the to_directed() method was ok, as it gave me directed edges and their inverses, however i need a method in which the line graph recognises an edge's inverse and doesn't show a connection with the original edge. i.e. in the line graph edge(x,y) is not connected to edge (y,x) for all x,y in the edge set. Note: I added an image of what i'm after in the original post for further clarity

jtaa gravatar imagejtaa ( 2013-02-23 12:03:45 +0100 )edit

Ok, it worked! thanks

jtaa gravatar imagejtaa ( 2013-02-25 04:36:07 +0100 )edit
2

answered 2013-02-23 03:03:39 +0100

Nathann gravatar image

By the way, there's a method called digraphs.RandomDirectedGNP that you may like. It will also produce 2-cycles though :-)

Nathann

edit flag offensive delete link more

Your Answer

Please start posting anonymously - your entry will be published after you log in or create a new account.

Add Answer

Question Tools

1 follower

Stats

Asked: 2013-02-22 20:59:05 +0100

Seen: 830 times

Last updated: Feb 23 '13