search

math1um / objects-invariants-properties

Objects, Invariants and Properties for Graph Theory (GT) automated conjecturing: in particular with the Sage program CONJECTURING: http://nvcleemp.github.io/conjecturing/
GNU General Public License v3.0
15 stars 6 forks source link

Add edge_bipartite_number invariant #394

Closed math1um closed 7 years ago

math1um commented 7 years ago

The edge_bipartite_number of a graph G is the largest number of edges in an induced bipartite subgraph of G.

A naive algorithm is to consider every subset of vertices, check if it induces a bipartite graph and, in this case, record the number of edges in that subgraph. Then return the largest saved number.

Another algorithm could be written using the Tarjan-Trojanowski idea: an edge e is either in a m-largest (largest with respect to edge count) induced bipartite subgraph or it is not. Consider the case where edge e is included in the subgraph (then all other edges its endpoints induce must also be included) or e is not (so at least one of its endpoints also can't be included - then you'd have to split into 2 cases). Recurse.

Its useful to code the naive algorithm as a check on any more sophisticated algorithm.

Doctests:

  1. For any complete graph, edge_bipartite_number is 2.
  2. For any bipartite graph, its the order of the graph.
  3. For the bowtie graph (two triangles which share a vertex), its 4.

This invariant is mentioned in (attached): Caro, Y., and Y. Roditty. "On the vertex-independence number and star decomposition of graphs." Ars Combinatoria 20 (1985): 167-180. caro-roditty-independence-star-decomposition-1985.pdf

Cf: Issue #307

rbarden commented 7 years ago

These doctests are incorrect for the size of graphs. CompleteGraphs are 1, bipartite graphs are the size, and bowtie (implemented as graphs.ButterflyGraph()) is 2