On the enumeration of certain weighted graphs
We enumerate weighted simple graphs with a natural upper bound condition on the sum of the weight of adjacent vertices. We also compute the generating function of the numbers of these graphs, and prove that it is a rational function. In particular, we show that the generating function for connected bipartite simple graphs is of the form p1(x)/(1-x)m+1 p 1 ( x ) / ( 1 - x ) m + 1 . For nonbipartite simple graphs, we get a generating function of the form p2(x)/(1-x)m+1(1+x)l p 2 ( x ) / ( 1 - x ) m + 1 ( 1 + x ) l . Here m  is the number of vertices of the graph, p1(x) p 1 ( x ) is a symmetric polynomial of degree at most m , p2(x) p 2 ( x ) is a polynomial of degree at most m+l m + l , and l is a nonnegative integer. In addition, we give computational results for various graphs.
weighted graphs rational convex polytopes rational generating functions ehrhart (quasi-)polynomial