Tutte conjectured that every 4-edge-connected graph admits a nowhere-zero 3-flow. In this paper, we show that this conjecture is true for Cayley graph on generalized dihedral groups and generalized quaternion groups, ...Tutte conjectured that every 4-edge-connected graph admits a nowhere-zero 3-flow. In this paper, we show that this conjecture is true for Cayley graph on generalized dihedral groups and generalized quaternion groups, which generalizes the result of F. Yang and X. Li [Inform. Process. Lett., 2011, 111： 416-419]. We also generalizes an early result of M. Nanasiova and M. Skoviera [J. Algebraic Combin., 2009, 30： 103-110].展开更多
The base graph of a simple matroid M = （E, A） is the graph G such that V（G） = A and E（G） = {BB＇： B, B＇ B, [B ／ B＇｜ = 1}, where the same notation is used for the vertices of G and the bases of M. It is prov...The base graph of a simple matroid M = （E, A） is the graph G such that V（G） = A and E（G） = {BB＇： B, B＇ B, [B ／ B＇｜ = 1}, where the same notation is used for the vertices of G and the bases of M. It is proved that the base graph G of connected simple matroid M is Z3-connected if ｜V（G）｜ ≥5. We also proved that if M is not a connected simple matroid, then the base graph G of M does not admit a nowhere-zero 3-flow if and only if IV（G）[ =4. Furthermore, if for every connected component Ei （ i≥ 2） of M, the matroid base graph Gi of Mi=MIEi has IV（Gi）｜≥5, then G is Z3-connected which also implies that G admits nowhere-zero 3-flow immediately.展开更多
基金Acknowledgements The first author was supported by the Natural Science Foundation of China （Grant No. 11301254）, the Natural Science Foundation of Henan Province （Grant No. 132300410313）, and the Natural Science Foundation of Education Bureau of Henan Province （Grant No. 13A110800）. The second author was supported by the National Natural Science Foundation of China （Grant No. 11171129） and the Doctoral Fund of Ministry of Education of China （Grant No. 20130144110001）.
文摘Tutte conjectured that every 4-edge-connected graph admits a nowhere-zero 3-flow. In this paper, we show that this conjecture is true for Cayley graph on generalized dihedral groups and generalized quaternion groups, which generalizes the result of F. Yang and X. Li [Inform. Process. Lett., 2011, 111： 416-419]. We also generalizes an early result of M. Nanasiova and M. Skoviera [J. Algebraic Combin., 2009, 30： 103-110].
文摘The base graph of a simple matroid M = （E, A） is the graph G such that V（G） = A and E（G） = {BB＇： B, B＇ B, [B ／ B＇｜ = 1}, where the same notation is used for the vertices of G and the bases of M. It is proved that the base graph G of connected simple matroid M is Z3-connected if ｜V（G）｜ ≥5. We also proved that if M is not a connected simple matroid, then the base graph G of M does not admit a nowhere-zero 3-flow if and only if IV（G）[ =4. Furthermore, if for every connected component Ei （ i≥ 2） of M, the matroid base graph Gi of Mi=MIEi has IV（Gi）｜≥5, then G is Z3-connected which also implies that G admits nowhere-zero 3-flow immediately.
