Isopathic Graphs and Airport Graphs

This paper explores two kinds of graphs, isopathic graphs and air­ port graphs. A distance property of graphs in general is also examined. Isopathic graphs are graphs in which every maximal path has the same length. The major theorem of this section characterizes isopathic graphs as extended stars, bipartite or hamiltonian. There is then a discussion of the latter two classes of isopathic graphs. At the end of Section I, there is an introduction to isopathic di­graphs, a natural concern after an exposure to isopathic graphs. Airport graphs, more appropriately snob graphs, can be thought of in the following way. It might be advantageous in some milieu that before a person would become friends with another person, A, he would first de­velop friendships with all people who are stronger than A. If in a graph strength corresponds to degree, and friendship to adjacency, an airport graph is formed when all points have this property. The resulting graph has a special structure which is examined in Section II. The concept of the "distance of a graph" is presented in Section III. Here the degree of a point is seen to be of greater importance than is the condition of being a special point. (Special points correspond to the snobs of Section II.) Notation used in this paper is that given in Frank Harary's book, Graph Theory, unless it is explicitly defined as the need arises.