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>
- Re: How to find a inverse of line graph?