Re: Re: How to find a inverse of line graph?

*To*: mathgroup at smc.vnet.net*Subject*: [mg60854] Re: [mg60816] Re: How to find a inverse of line graph?*From*: <bsyehuda at gmail.com>*Date*: Fri, 30 Sep 2005 03:57:34 -0400 (EDT)*References*: <dhaupf$j3l$1@smc.vnet.net> <200509290941.FAA01176@smc.vnet.net>*Reply-to*: bsyehuda at gmail.com*Sender*: owner-wri-mathgroup at wolfram.com

a line graph is an operation on graphs to produce new graphs. Say you have a graph G, and you want to generate a new graph LG so each EDGE of G becomes a vertex in LG the vertices of LG are then connected by edges only if the edges that generated them in G had a common veretx in G. I thinkk that you might find a similar definition in MathWorld.com as well (as in any textbook on graph theory). now, since the number of possible edges in G goes as n^2 where n is the number of vertices in G, there might be much more vertices in LG then in G. On 9/29/05, Jens-Peer Kuska <kuska at informatik.uni-leipzig.de> wrote: > > Hi, > > "line graph of G" can mean G is a function G[x] and > you wish to find an approximation to the numerical data > or it may mean that you have a drwing of the graph > (nodes and edges) and you need a representation of the > edge list. And there may be some more interpretations > what your "G" may be ... and for you Sowen, an inverse operation is not unique if you do not explicit naming of the vertices of LG that corresponds to the edges of G. say you hav an edge (v1,v2) that connects vertices v1 and v2 in G. Then all edges that are connected to either v1 or v2 in G (that is, any edge of the form (v1, some vertex) or (v2, vertex) will generate new vertices in LG that will be neighbors of the vertex that was produced by edge (v1,v2). Now, if you do not have the original names, you will not be able to determine if the connection is due to v1 or due to v2, and therefore you may not generate a graph that will be isomorphic to the original one. If you choose incorrectly (since you don't know what the original graph was) then you easily may create a different degree sequence by your "inverse transformation/mapping" and this is a contradiction to a theorem that ant two isomorphic graphs need to have identical degree sequences (sorted of course). This is not a formal proof, but to deny an operation one negative example is enough, and at least you can generate such example from the argument given above. This is also not a Mathematica related problem. An operation that cannot be done, cannot be done with Mathematica either. OK, I'll generate you an example I'm sorry to dissapoint you, but at least you can stop searching for a non existable solution. start with a graph with vertices set V={1,2,3,4,5} and edges set E={(1,2),(1,3),(1,4),(2,4),(3,5),(4,5)} Then LG will be with edge set VLG={(1,2),(1,3),(1,4),(2,4),(3,5),(4,5)} 1 2 3 4 5 6 and ELG={((1,2),(1,3)),((1,2),(1,4)),((1,2),(2,4)),((1,3),(3,5)),((1,4),(2,4)),((1,4),(4,5)),((2,4),(4,5)),((3,5),(4,5))} so you get a line graph with 6 vertices and 8 edges out of a graph of 5 vertices and 6 edges. BUT you do not have these names, so instead you have VLG={1,2,3,4,5,6} and with these names ELG={(1,2),(1,3),(1,4),(2,5),(3,4),(3,6),(4,6),(5,6)} From ELG (with the names that you really have, i.e., the last line above) you can generate more then one legitimate graph yehuda Regards > Jens > <sowencheung at gmail.com> schrieb im Newsbeitrag > news:dhaupf$j3l$1 at smc.vnet.net... > | Hi, folks > | > | Given a line graph of G, how can I find the G? > | > | Very clueless, I did think about it for a long > time. Anyone would like > | to help? > | > | Thanks! > | > | Sowen > | > > >

**References**:**Re: How to find a inverse of line graph?***From:*"Jens-Peer Kuska" <kuska@informatik.uni-leipzig.de>