Partitioning Graphs Subject to Edge Constraints

摘要

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)