In (1), the authors defined the cutting number of a cycle and of a graph. In this paper, we extend their results in two ways. First, we define the r-reduced cutting number of a cycle within a graph and the r-reduced cutting number of a graph. We find the minimum and maximum number of edges in a graph on n vertices and r-reduced cutting number k. Second, we extend the definition of r-reduced cutting number of a cycle within a graph to include edge-disjoint collections of cycles, which we call progressions. The cutting power (at level r) of a graph is the length of the shortest progression with r-reduced cutting number at least 2. We determine the cutting powers at level 1 of complete graphs. Finally, we find a formula for the maximum number of edges in a graph on n vertices with cutting power 2 and with a progression of length 2 having r-reduced cutting number k.
展开▼
