On the Circumference of Regular Polyhedral Graphs
Jochen Harant, Helmut Walther · 1990
Consider the class Γ of all 3-regular polyhedral graphs, that is, the class of the planar 3-connected graphs in which each vertex has degree 3. Let C be a circuit of a graph G∈Γ. If one removes from G the vertices of C and all edges incident with them, the resulting graph G-C disintegrates into connected components K 1 ,K 2 ,...,K K . If C is a hamiltonian circuit of G (that is a circuit containing all vertices), then G-C is obviously empty, but in all other cases, however, k > 0 holds. Let C i be the set of those vertices of C having at least one neighbour in K i . Since each vertex has the degree 3 in G, a vertex from C i is incident with exactly one edge which does not belong to C, that is, this vertex is adjacent to one vertex from K i . In addition, there exists for any vertex x∈ C at most one index i such that x is adjacent to one vertex of K i . If one adds to K i the vertices of C i and also all edges whose one end-vertex belongs to C i and the other one to K i , then the resulting graph B i is called a bridge of G over C. Calling also an edge whose two end-vertices belong to C, but not the edge itself, a bridge, then we see that to each vertex of C there exists exactly one bridge in which this vertex lies. A vertex belonging to both C and B i is called a touch point of the bridge B i . Let a bridge over a path be defined accordingly. Let Γ (w) be the class of graphs G in in which there exists for any longest circuit C of G a bridge B over C with at least w touch points. These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.