
arXiv: math/0703585
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)$.
Extremal problems in graph theory, cocycle, maxmaxflow, maximum degree, FOS: Physical sciences, chromatic polynomial, Mathematical Physics (math-ph), graph, secondlargest degree, 05C99 (Primary), 05C15, 05C30, 05C35, 05C40, 82B20, 90B10 (Secondary), flow, degeneracy number, FOS: Mathematics, Mathematics - Combinatorics, subgraph, Combinatorics (math.CO), Mathematical Physics
Extremal problems in graph theory, cocycle, maxmaxflow, maximum degree, FOS: Physical sciences, chromatic polynomial, Mathematical Physics (math-ph), graph, secondlargest degree, 05C99 (Primary), 05C15, 05C30, 05C35, 05C40, 82B20, 90B10 (Secondary), flow, degeneracy number, FOS: Mathematics, Mathematics - Combinatorics, subgraph, Combinatorics (math.CO), Mathematical Physics
| selected citations These citations are derived from selected sources. This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | 3 | |
| popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network. | Average | |
| influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | Average | |
| impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network. | Average |
