SOME PROPERTIES OF 3-POLYTOPAL GRAPHS.
Item
-
Title
-
SOME PROPERTIES OF 3-POLYTOPAL GRAPHS.
-
Identifier
-
AAI8302520
-
identifier
-
8302520
-
Creator
-
JOFFE, PETER MELVYN.
-
Contributor
-
Joseph Malkevitch
-
Date
-
1982
-
Language
-
English
-
Publisher
-
City University of New York.
-
Subject
-
Mathematics
-
Abstract
-
By a well-known theorem of Steinitz, a graph (without multiple edges or loops) is the edge graph of convex 3-dimensional polytope if and only if it is planar and 3-connected. Plane graphs of this type (i.e., 3-polytopal), which we shall also refer to as p-graphs, are the objects of our investigation.;Theorem (Steinitz). Each p-graph may be generated from K(,4) (the tetrahedron) by a succession of edge-additions. Equivalently: each p-graph, other than K(,4), contains an edge which is deletable (i.e., its removal, followed by the suppression of any resulting 2-valent vertices, yields a smaller p-graph).;We strengthen this theorem (and thus also the findings of Kotzig and Jucovic concerning edges of "low weight" in p-graphs) by demonstrating that:;Theorem. Each p-graph (NOT=) K(,4) contains a deletable edge shared by an i-gon and a j-gon such that i (LESSTHEQ) 5 and i + j (LESSTHEQ) 13.;Some of the theory developed to obtain this is also employed to determine sets of generating operations for the bicubic p-graphs, for the cyclically-4-connected bicubic p-graphs, and--in a sense--for the Hamiltonian bicubic p-graphs. These are of interest in view of Barnette's well-known conjecture that all bicubic p-graphs are Hamiltonian.;A second line of inquiry is that of determining the existence--or otherwise--of a HIST (a spanning tree without 2-valent vertices) in graphs of various sorts--usually 3-polytopal. In this connection the following are proved: if G is connected with (GREATERTHEQ) 4 vertices then G('2) has a HIST; if G has n (GREATERTHEQ) 6 vertices, each of valence (GREATERTHEQ) 1/2n, then G has a HIST; the HIST problem for non-cubic 3-polytopal graphs is NP-hard. Further, we derive a necessary condition for a cubic plane graph to have a HIST--one that is also a sufficient condition for Halin graphs. In addition we construct two special (infinite) classes of non-cubic p-graphs whose members have no HIST's; one comprised of 4-valent cyclically-4-connected p-graphs, and the other comprised of p-graphs whose duals also possess no HIST. Also presented are two Eberhard type theorems concerning the face vectors of Halin graphs.
-
Type
-
dissertation
-
Source
-
PQT Legacy CUNY.xlsx
-
degree
-
Ph.D.
-
Program
-
Mathematics
