Publication Date

5-25-1970

Abstract

A graph G is transitive if it is transitive when considered as a relation; i.e., if the edges ab and be are in G, so is ac. In this paper, several natural questions concerning transitivity and related concepts are investigated.

Because the terminology and notation of graph theory is not standard, a brief section of definitions and notation is included in Section II. Section III is a study of the transitive cut number of a graph, the minimum number of edges which must be removed from the graph so that the remaining subgraph is transitive. Undirected graphs on n points with maximum cut number are characterized and the maximum calculated in this case. For directed graphs, the problem is much more difficult; only partial results are obtained.

In Section IV, we ask for conditions for the existence of transitive spanning subgraphs. An antidirected digraph is defined as one in which no node has both positive indegree and positive outdegree, and an antidirected tree as an antidirected weakly connected graph which contains no weak cycles. Such graphs are trivially transitive. It is shown that every transitive weakly connected oriented graph contains a spanning antidirected tree, that every tournament on three or more nodes contains a pair of antidirected paths which together span it, and finally that every tournament on six or more nodes contains a spanning antidirected tree.

Degree Name

Mathematics

Level of Degree

Doctoral

Department Name

Mathematics & Statistics

First Committee Member (Chair)

Roger Charles Entringer

Second Committee Member

Donald Ward Dubois

Third Committee Member

Illegible

Fourth Committee Member

Lambert Herman Koopmans

Language

English

Document Type

Dissertation

Comments

Sandia Corporation Doctoral Study Program

Download

Share

COinS