Premium
Nowhere‐Zero Flows on Signed Complete and Complete Bipartite Graphs
Author(s) -
Máčajová Edita,
Rollová Edita
Publication year - 2015
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.21793
Subject(s) - bipartite graph , signed graph , mathematics , combinatorics , zero (linguistics) , conjecture , flow (mathematics) , nowhere dense set , graph , discrete mathematics , computer science , geometry , philosophy , linguistics , set (abstract data type) , programming language
Bouchet's conjecture asserts that each signed graph which admits a nowhere‐zero flow has a nowhere‐zero 6‐flow. We verify this conjecture for two basic classes of signed graphs—signed complete and signed complete bipartite graphs by proving that each such flow‐admissible graph admits a nowhere‐zero 4‐flow and we characterise those which have a nowhere‐zero 2‐flow and a nowhere‐zero 3‐flow.