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

  • $\begingroup$ 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. $\endgroup$ – Ingix Oct 23 '18 at 14:59

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.