Timeline for Efficient computation of a vertex-partition for graphs
Current License: CC BY-SA 2.5
8 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Jan 31, 2011 at 20:12 | comment | added | Tracy Hall | I get the pendant vertex in one side of the partition, and the three vertices of the triangle in the other. There are some situations that give rise to a trivial partition, for example if the graph is not 2-connected and two 1-separated parts of the graph each have an even number of spanning trees, or if there is an induced even cycle the removal of whose edges leaves its vertices in separate components. | |
| Dec 20, 2010 at 16:49 | comment | added | Bill Thurston | A triangle with an edge attached to one vertex is a simple example of a non-bipartite graph where Roland Bacher's partition is not trivial. The vertex with 3 edges is in one element of the partition, the other three vertices in the other. | |
| Sep 14, 2010 at 0:51 | comment | added | sleepless in beantown | I shall have to explore this a little further and try to modify my answer, Roland. | |
| Sep 14, 2010 at 0:50 | comment | added | sleepless in beantown | continued comment @Roland Bacher, any vertex in an odd cycle in an arbitrary general graph will have one path which yields a (+1) labeling and one path which yields a (-1) labeling. Am I interpreting your question correctly now? In that case, I'm not sure that your partitioning will yield anything of interest for arbitrary general graphs. It should yield (1) if there are an even number of spanning trees in which the vertex has distance has odd parity. Each $\varphi_{T_i}$ is a bipartite coloring of spanning tree $T_i$, with two possible colorings. $k$ spanning trees -> $2^k$ $\Pi\varphi$ | |
| Sep 14, 2010 at 0:43 | comment | added | sleepless in beantown | "Doing a bipartite partitioning of one of the spanning trees of an arbitrary single-component connected general graph" appears to be what you are asking for. If there are odd cycles in your graph, different spanning trees will yield different partitions. Then, you would like to take all of the possible spanning trees and multiply them, so that any vertex which has an odd number of ($-1$) labels will still be labeled ($-1$). Example: $C_3$ has three spanning trees yielding the ordered label lists (-1,1,-1) (1,-1,-1) (-1,-1,1), whose product yields (1,1,1) which is not a partition. | |
| Sep 13, 2010 at 13:46 | comment | added | Roland Bacher | This partition is not necessarily creating the bipartite coloring if $\Gamma$ is bipartite: It is trivial for a bipartite connected graph with even complexity. It gives however the bipartition otherwise. Bipartite graphs are however not very interesting for this invariant: I am interested in arbitrary general graphs. | |
| Sep 13, 2010 at 11:24 | history | edited | sleepless in beantown | CC BY-SA 2.5 |
corrected typos
|
| Sep 13, 2010 at 11:19 | history | answered | sleepless in beantown | CC BY-SA 2.5 |