On the enumeration of certain weighted graphs

DOI10.1016/J.DAM.2007.04.001MaRDI QIDQ997075zbMATH OpenOpenAlexFDO

Authors Miklós Bóna, Hyeong-Kwan Ju, Ruriko Yoshida

Publication date 19 July 2007

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/math/0606163

zbMATH Keywords

weighted graphsrational generating functionsrational convex polytopesEhrhart (quasi-)polynomial

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35)

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$.

Recommendations

• Enumeration of graphs with given weighted number of connected components
• ENUMERATION OF WEIGHTED COMPLETE GRAPHS
• scientific article; zbMATH DE number 530033
• Enumeration of unlabelled graphs with specified degree parities
• Generating function for representations of graphs by \(k\)-partite graphs

Cites work

• scientific article; zbMATH DE number 3645097 (Why is no real title available?)
• scientific article; zbMATH DE number 3163858 (Why is no real title available?)
• scientific article; zbMATH DE number 4089320 (Why is no real title available?)
• scientific article; zbMATH DE number 3571502 (Why is no real title available?)
• scientific article; zbMATH DE number 718142 (Why is no real title available?)
• scientific article; zbMATH DE number 1033382 (Why is no real title available?)
• scientific article; zbMATH DE number 3804333 (Why is no real title available?)
• scientific article; zbMATH DE number 1860211 (Why is no real title available?)
• scientific article; zbMATH DE number 2107707 (Why is no real title available?)
• scientific article; zbMATH DE number 835749 (Why is no real title available?)
• scientific article; zbMATH DE number 1405493 (Why is no real title available?)
• scientific article; zbMATH DE number 2223032 (Why is no real title available?)
• A fast algorithm for MacMahon's partition analysis
• Algorithms – ESA 2004
• Combinatorics and commutative algebra.
• Computing the Continuous Discretely
• ENUMERATION OF WEIGHTED COMPLETE GRAPHS
• Effective lattice point counting in rational convex polytopes
• Enumerating solutions of a system of linear inequalities related to magic squares
• Lectures on Polytopes
• Linear extensions of ranked posets, enumerated by descents. A problem of Stanley from the 1981 Banff conference on ordered sets
• MacMahon's partition analysis: The Omega package
• On certain polytopes associated with graphs
• Ordered structures and partitions

Cited in

(18)

• On vertex-weighted realizations of acyclic and general graphs
• Enumeration of graphs with given weighted number of connected components
• Mayer and Ree-Hoover weights of infinite families of 2-connected graphs
• scientific article; zbMATH DE number 10422 (Why is no real title available?)
• A new formula for the generating function of the numbers of simple graphs
• Weighted pebbling numbers on graphs
• Generating function for representations of graphs by \(k\)-partite graphs
• Zig-zag Eulerian polynomials
• ENUMERATION OF WEIGHTED COMPLETE GRAPHS
• Enumeration and structure of inhomogeneous graphs
• Regularity in weighted graphs a symmetric function approach
• On the weights of simple paths in weighted complete graphs
• Vector weighted Stirling numbers and an application in graph theory
• On weighted graph homomorphisms
• Different Volume Computation Methods of Graph Polytopes
• The generating function of whitworth runs
• On the sequence generated by a certain type of matrices
• Proving some conjectures on Kekulé numbers for certain benzenoids by using Chebyshev polynomials

Describes a project that uses

Uses Software

• cdd
• LattE
• Omega

This page was built for publication: On the enumeration of certain weighted graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q997075)