82Accesses
3Citations
Abstract
The flow polynomials denote the number of nowhere-zero flows on graphs, and are related to the well-known Tutte polynomials and chromatic polynomials. We will show the decomposition of the flow polynomials by edge-cuts and vertex-cuts of size 2 or 3. Moreover by using this decomposition, we will consider what kind of graphs have the same flow polynomials. Another application of the decomposition results is that if a bridgeless graphG does not admit a nowhere-zerok-flow andG has a small vertex- or edge-cut, then a proper bridgeless subgraph ofG (a graph minor) does not admit a nowhere-zerok-flow either.
This is a preview of subscription content,log in via an institution to check access.
Access this article
Subscribe and save
- Get 10 units per month
- Download Article/Chapter or eBook
- 1 Unit = 1 Article or 1 Chapter
- Cancel anytime
Buy Now
Price includes VAT (Japan)
Instant access to the full article PDF.
Similar content being viewed by others
References
Fan, G.: Integer flows and cycle covers. J. Comb. Theory Ser.B 54, 113–122 (1992)
Jaeger, F.: Nowhere-zero flow problems. In: L.W. Beineke et al.: Selected topics in graph theory3 (chapter 4, pp. 71–95) Academic-Press 1988
Oxley, J.G.: Matroid theory, Oxford Science Publications 1992.
Read, R.C.: An introduction to chromatic polynomials. J. Comb. Theory4, 52–71 (1968)
Seymour, P.D.: Nowhere-zero 6-flows. J. Comb. Theory Ser.B 30, 130–135 (1981)
Seymour, P.D.: Nowhere-zero flow. In: R. Graham et al.: Handbook of combinatorics, Elsevier Science Publishers 1993
Tutte, W.T.: A contribution to the theory of chromatic polynomials. Canad. J. Math.6, 80–91 (1954)
Welsh, D.J.A.: Matroid theory (London Math. Soc., vol. 8), Academic Press London 1976
Author information
Authors and Affiliations
Department of Information Science, University of Tokyo, Tokyo, 113, Japan
K. Sekine
Department of Mathematics, West Virginia University, Morgantown, WV, 26506-63 10, USA
C. Q. Zhang
- K. Sekine
You can also search for this author inPubMed Google Scholar
- C. Q. Zhang
You can also search for this author inPubMed Google Scholar
Rights and permissions
About this article
Cite this article
Sekine, K., Zhang, C.Q. Decomposition of the Flow Polynomial.Graphs and Combinatorics13, 189–196 (1997). https://doi.org/10.1007/BF03352995
Received:
Revised:
Published:
Issue Date:
Share this article
Anyone you share the following link with will be able to read this content:
Sorry, a shareable link is not currently available for this article.
Provided by the Springer Nature SharedIt content-sharing initiative