Publications Meetings The Profession Membership Programs Math Samplings Policy & Advocacy In the News About the AMS
   
Mobile Device Pairing
Green Open Access
Proceedings of the American Mathematical Society
Proceedings of the American Mathematical Society
ISSN 1088-6826(online) ISSN 0002-9939(print)

 

Balanced valuations and flows in multigraphs


Author: F. Jaeger
Journal: Proc. Amer. Math. Soc. 55 (1976), 237-242
MSC: Primary 05C99
MathSciNet review: 0427156
Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

Abstract: A balanced valuation of a multigraph $ H$ is a mapping $ w$ of its vertex-set $ V(H)$ into $ R$ such that $ \forall S \subseteq V(H)$ the number of edges of $ H$ with exactly one vertex in $ S$ is greater than or equal to $ \vert{\sum _{v \in S}}w(v)\vert$; we apply the theory of flows in networks to obtain known and new results on balanced valuations such as:

A cubic multigraph has chromatic index $ 3$ if and only if it has a balanced valuation with values in $ \{ - 2, + 2\} $ (Bondy [5]).

Every planar cubic $ 2$-edge connected multigraph has a balanced valuation with values in $ \{ - 5/3, + 5/3\} $.

Every planar $ 5$-regular $ 4$-edge connected multigraph has a balanced valuation with values in $ \{ - 3, + 3\} $.


References [Enhancements On Off] (What's this?)


Similar Articles

Retrieve articles in Proceedings of the American Mathematical Society with MSC: 05C99

Retrieve articles in all journals with MSC: 05C99


Additional Information

DOI: http://dx.doi.org/10.1090/S0002-9939-1976-0427156-5
PII: S 0002-9939(1976)0427156-5
Article copyright: © Copyright 1976 American Mathematical Society