Maxmaxflow and counting subgraphs

zbMATH Open1230.05175arXivmath/0703585MaRDI QIDQ986701FDOQ986701

Authors: Bill Jackson, Alan D. Sokal 

Publication date: 12 August 2010

Published in: The Electronic Journal of Combinatorics (Search for Journal in Brave)

Abstract: We introduce a new graph invariant Lambda(G) that we call maxmaxflow, and put it in the context of some other well-known graph invariants, notably maximum degree and its relatives. We prove the equivalence of two "dual" definitions of maxmaxflow: one in terms of flows, the other in terms of cocycle bases. We then show how to bound the total number (or more generally, total weight) of various classes of subgraphs of G in terms of either maximum degree or maxmaxflow. Our results are motivated by a conjecture that the modulus of the roots of the chromatic polynomial of G can be bounded above by a function of Lambda(G).

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

File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

Recommendations

• Linear Bound in Terms of Maxmaxflow for the Chromatic Roots of Series-Parallel Graphs
• Maximum modulus of independence roots of graphs and trees
• On zero-free intervals of flow polynomials
• Bounds for the coefficients of flow polynomials
• On the number of \(B\)-flows of a graph

zbMATH Keywords

graphcocyclechromatic polynomialflowmaximum degreesubgraphdegeneracy numbermaxmaxflowsecondlargest degree

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35)

Cited In (3)

• A near-optimal zero-free disk for the Ising model
• Linear Bound in Terms of Maxmaxflow for the Chromatic Roots of Series-Parallel Graphs
• Counting 2-connected deletion-minors of binary matroids

This page was built for publication: Maxmaxflow and counting subgraphs

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