Name
Abstract | ||
|---|---|---|
Let $G$ be a simple graph on $n$ vertices, $n\geq 3$. It is well known that if $G$ satisfies the Ore condition that $d(x)+d(y)\geq n$ for every pair of nonadjacent vertices $x$ and $y$, then $G$ has a Hamiltonian circuit, which implies that $G$ has a nowhere-zero 4-flow. But it is not necessary for $G$ to have a nowhere-zero 3-flow. In this paper, we prove that with six exceptions, all graphs satisfying the Ore condition have a nowhere-zero 3-flow. More precisely, if $G$ is a graph on $n$ vertices, $n\geq 3$, in which $d(x)+d(y)\geq n$ for every pair of nonadjacent vertices $x$ and $y$, then $G$ has no nowhere-zero 3-flow if and only if $G$ is one of six completely described graphs. |
Year | DOI | Venue |
|---|---|---|
2008 | 10.1137/060677744 | SIAM J. Discrete Math. |
Keywords | Field | DocType |
hamiltonian circuit,nowhere-zero 3-flows,ore condition,geq n,nowhere-zero 4-flow,nonadjacent vertex,nowhere-zero 3-flow,simple graph | Graph,Discrete mathematics,Combinatorics,Vertex (geometry),Hamiltonian (quantum mechanics),Hamiltonian path,Ore condition,Mathematics | Journal |
Volume | Issue | ISSN |
22 | 1 | 0895-4801 |
Citations | PageRank | References |
22 | 1.34 | 3 |
Authors | ||
2 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Genghua Fan | 1 | 412 | 65.22 |
| Chuixiang Zhou | 2 | 71 | 5.11 |