# almost-bipartite nearly-isolated subgraphs

I am looking for examples/families of graphs with the following (maybe vague-sounding at first) property: the graph $G$ has a relatively large subgraph $B$ such that $B$ is bipartite-plus-a-few-edges and the cut between $B$ and $G-B$ is small.

In a paper called A characterization of the smallest eigenvalue of a graph (J. Graph Theory, 1994) Desai and Rao studied this problem and related it to the signless Laplacian spectrum. What I am after here is locating some explicit examples.

EDIT: I can construct lots of examples by just taking a bipartite graph and loosely attaching it to another large dense graph, and then sprinkling some noise. But I'd like to know if there are well-known interesting graphs/families that already display such a behaviour.

EDIT2: Let's take a concrete example. Do the Paley graphs have such a property?

EDIT3: Just a bounce, since the bounty expires tomorrow...

-
You might consider k-partite graphs with large bipartite compnent or certain mixed product or twisted product graphs. Gerhard "Ask Me About System Design" Paseman, 2012.05.18 – Gerhard Paseman May 18 '12 at 13:14
What are 'twisted product graphs'? I found this presentation (math.unl.edu/~adonsig1/SS6A/Wright.pdf) that mentions such a concept but I'm not sure if that's what you meant. – Felix Goldberg May 18 '12 at 13:50
What range are you considering here when you say "relatively large"? Do you want $B$ to be a constant fraction of $G$, or $n^{\alpha}$ vertices for some $0<\alpha<1$? If the former, Paley graphs may not be the best bet, as they're quasirandom in the sense of Chung-Graham-Wilson (have large eigenvalue gap; equiv. all large subsets of vertices span about the same number of edges) -- I think if you work through their bounds you get that the Paley graph has no nearly bipartite subgraphs of size larger than $q^{1/2+\epsilon}$ vertices, and you might be able to get better bounds by number theory. – Kevin P. Costello May 21 '12 at 19:05
A constant fraction will be better, I think. You are probably right about the Paley graphs, I managed to pick like the worst possible example... Any other suggestions perhaps? – Felix Goldberg May 22 '12 at 0:08