We define P(x,y) in the following way: Given an initial undirected graph of n vertices, P(x,y)=1 if an induced subgraph with exactly x vertices and y edges exists. Else P(x,y)=0.
For example, let as condider the graph with adjecency matrix A [ 0 1 0 ; 1 0 0 ; 0 0 0; ] (vetrex 1 is connected with vertex 2 and vertex 3 stands alone)
P(3,1)=1, because the initital graph has 3 vertices and 1 edge.
P(2,1)=1, because if we keep vertex 1 and vertex 2 as induced subgraph, we have 2 vertices and 1 edge.
P(2,0)=1, because if we choose vertex 1 and 3 as induced subgraph ( or 2 and 3), we have 2 vertices and 0 edges.
P(1,0)=1, because if we choose any signle vertex as induced subgraph, we have 1 vertex and 0 edges.
The sum of p(X,Y) is 4 in the example.
Let us now assume that we have 3 known integers : n, a, b. We also know that a - b >= n ^ (3/2) and that P(n/2 , a) = 1 and P(n/2, b)=1. ( n is an even number)
Our task is to choose the optimal initial undirected graph with n vertices, in order to minimize the sum of p(x,y) for all possible induced subgraphs. The restrictions mentioned above must also hold.
How can we find the optimal initial graph?I have been thinking about this problem for many hours, but I could not come up with a good solution.
If we ignore the P(n/2 , a) = 1 and P(n/2, b)=1 restrictions, I figured out that the optimal choise would be a graph with an adjecency matrix [ 0 0 0 .... 0 0 0 ; 0 0 0 .... 0 0 0 ....; ........... 0 0 0....] or [ 1 1 1 .... 1 1 1; 1 1 1... 1 1 1; .... 1 1 1...] , as these choices yield n as a sum of p(x,y). But taken into account the restrictions mentioned above, it is not always possible to choose that type of initial graph.