On the Enumeration of Certain Weighted Graphs

2006/06/07 by Miklós Bóna, Bóna, Miklós, Hyeong-Kwan Ju +3
Computer Science · Mathematics · #Advanced Combinatorial Mathematics #Combinatorics (math.CO) #FOS: Mathematics #Graph Labeling and Dimension Problems #Graph theory and applications #math.CO

paper · pdf · doi:10.48550/arxiv.math/0606163

25 pages

arxiv created 2006/06/07 · openalex publication_date 2006/06/07 · arxiv updated 2009/12/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

We enumerate weighted graphs with a certain upper bound condition. 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 if the given graph is a bipartite graph, then its generating function is of the form \fracp(x)(1-x)^m+1, where m is the number of vertices of the graph and p(x) is a polynomial of degree at most m.

Related

• Enumeration of graphs with given weighted number of connected components
• Enumeration and structure of inhomogeneous graphs
• Enumeration of connected bipartite graphs with given Betti number
• Characteristic Polynomials and Hypergraph Generating Functions via Heaps of Pieces
• A weighted graph problem from commutative algebra