On the enumeration of certain weighted graphs

DOI10.1016/J.DAM.2007.04.001zbMATH Open1149.90162arXivmath/0606163OpenAlexW2076656020MaRDI QIDQ997075FDOQ997075

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)

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

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

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

zbMATH Keywords

weighted graphsrational generating functionsrational convex polytopesEhrhart (quasi-)polynomial

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35)

Cites Work

• Effective lattice point counting in rational convex polytopes
• MacMahon's partition analysis: The Omega package
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Computing the Continuous Discretely
• Lectures on Polytopes
• Title not available (Why is that?)
• Combinatorics and commutative algebra.
• Title not available (Why is that?)
• Title not available (Why is that?)
• On certain polytopes associated with graphs
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Ordered structures and partitions
• Title not available (Why is that?)
• A fast algorithm for MacMahon's partition analysis
• Algorithms – ESA 2004
• Linear extensions of ranked posets, enumerated by descents. A problem of Stanley from the 1981 Banff conference on ordered sets
• Enumerating solutions of a system of linear inequalities related to magic squares
• ENUMERATION OF WEIGHTED COMPLETE GRAPHS

Cited In (18)

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

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)