# How to find the total number of connected Range Graphs which have n vertices on left and m on the right.

A bipartite graph with n vertices on the left part (numbered from $$1$$ to $$n$$) and m on the right part (numbered from $$n+1$$ to $$n+m$$), is said to be a Range Graph, if each vertex on the left satisfies the following property - the numbers of its set of neighbors should form a consecutive range/segment on the right.

For example, suppose n = 10 and m = 13. Then the vertices on the left are $$\{1, 2, …, 10\}$$ and the ones on the right are $$\{11, 12, …, 23\}$$. Now, suppose the neighbors of vertex $$7$$ were $$\{12, 14, 15, 19\}$$, then this would not be a Range Graph, because they aren't consecutive numbers. So for it to be a Range Graph, the neighbors could potentially be, say, $$\{12, 13, 14, 15\}$$.

How to find the total number of connected Range Graphs which have n vertices on left and m on the right.

NOTE:: two Range Graphs are considered to be different if there are two vertices i and j such that one of the graphs has an edge between them, but the other graph doesn't. In other words, the edge set should be different. A graph is said to be connected if every vertex is reachable from every other vertex through some sequence of edges

• As a first step, do you have an idea how to solve the problem without the "connected" condition? This would be the easier problem, IMO. – Ingix Oct 23 '18 at 14:59