Accession Number : AD0710378

Title :   PARTITIONING GRAPHS SUBJECT TO EDGE CONSTRAINTS.

Descriptive Note : Master's thesis,

Corporate Author : NAVAL POSTGRADUATE SCHOOL MONTEREY CALIF

Personal Author(s) : Solberg,James L.

Report Date : JUN 1970

Pagination or Media Count : 30

Abstract : A problem of partitioning a given graph into a minimal number of subgraphs subject to edge and node constraints is considered. Two parameters associated with the subgraph, one corresponding to the maximum number of nodes and the other to the maximum number of external edges, define a feasible partition element. Complete graphs, complete bipartite graphs, and two families of infinite graphs are considered, and relations between the parameters are used to obtain the results. For the infinite graphs, the problem is somewhat different. A largest feasible partition element is found and can be used in determining the minimal number of feasible elements in a finite graph with the same structure as the infinite one. (Author)

Descriptors :   (*GRAPHICS, *COMBINATORIAL ANALYSIS), THEOREMS, THESES

Subject Categories : Numerical Mathematics

Distribution Statement : APPROVED FOR PUBLIC RELEASE