Geodesic
Maxmaxflow and counting subgraphs
The electronic journal of combinatorics, Tome 17 (2010)
Cet article a éte moissonné depuis la source The Electronic Journal of Combinatorics website

Voir la notice de l'article

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)$.
DOI : 10.37236/371
Classification : 05C35
Mots-clés : graph, subgraph, flow, cocycle, maxmaxflow, maximum degree, secondlargest degree, degeneracy number, chromatic polynomial 
@article{10_37236_371,
     author = {Bill Jackson and Alan D. Sokal},
     title = {Maxmaxflow and counting subgraphs},
     journal = {The electronic journal of combinatorics},
     year = {2010},
     volume = {17},
     doi = {10.37236/371},
     zbl = {1230.05175},
     url = {http://geodesic.mathdoc.fr/articles/10.37236/371/}
}
TY  - JOUR
AU  - Bill Jackson
AU  - Alan D. Sokal
TI  - Maxmaxflow and counting subgraphs
JO  - The electronic journal of combinatorics
PY  - 2010
VL  - 17
UR  - http://geodesic.mathdoc.fr/articles/10.37236/371/
DO  - 10.37236/371
ID  - 10_37236_371
ER  - 
%0 Journal Article
%A Bill Jackson
%A Alan D. Sokal
%T Maxmaxflow and counting subgraphs
%J The electronic journal of combinatorics
%D 2010
%V 17
%U http://geodesic.mathdoc.fr/articles/10.37236/371/
%R 10.37236/371
%F 10_37236_371
Bill Jackson; Alan D. Sokal. Maxmaxflow and counting subgraphs. The electronic journal of combinatorics, Tome 17 (2010). doi: 10.37236/371

Cité par Sources :