Pósa-condition and nowhere-zero 3-flows |
| |
Authors: | Jian-Hua Yin Yue Zhang |
| |
Affiliation: | aDepartment of Mathematics, College of Information Science and Technology, Hainan University, Haikou 570228, PR China |
| |
Abstract: | Let G be a simple graph on n vertices and π(G)=(d1,d2,…,dn) be the degree sequence of G, where n≥3 and d1≤d2≤?≤dn. The classical Pósa’s theorem states that if dm≥m+1 for and dm+1≥m+1 for n being odd and , then G is Hamiltonian, which implies that G admits a nowhere-zero 4-flow. In this paper, we further show that if G satisfies the Pósa-condition that dm≥m+1 for and dm+1≥m+1 for n being odd and , then G has no nowhere-zero 3-flow if and only if G is one of seven completely described graphs. |
| |
Keywords: | Pó sa-condition Degree sequence Nowhere-zero 3-flow |
本文献已被 ScienceDirect 等数据库收录! |
|