A characterization of planar cubic graphs |
| |
Authors: | Charles H.C Little |
| |
Affiliation: | Department of Mathematics and Computer Science, Royal Melbourne Institute of Technology Ltd., Melbourne, Victoria 3000, Australia |
| |
Abstract: | If S is a collection of circuits in a graph G, the circuits in S are said to be consistently orientable if G can be oriented so that they are all directed circuits. If S is a set of three or more consistently orientable circuits such that no edge of G belongs to more than two circuits of S, then S is called a ring if there exists a cyclic ordering C0, C1,…, Cn ? 1, C0 of the n circuits in S such that if and only if j = i or j ≡ i ? 1 (mod n) or j ≡ i + 1 (mod n). We characterise planar cubic graphs in terms of the non-existence of a ring with certain specified properties. |
| |
Keywords: | |
本文献已被 ScienceDirect 等数据库收录! |
|