#### Document Type

Technical Report

#### Publication Date

Fall 10-1-1975

#### Abstract

Let f ne a positive-valued function on the vertices of a graph G. An f-star subgraph F consists of vertex-disjoint stars, where each vertex v meets at most f(v) edges of F; a maximum f-star subgraph contains the greatest number of edges possible. Let G be bipartite, with vertex sets S, T; let f(v) = 1 for all vɛS. Then there is a maximum f-star subgraph that contains a maximum matching. Let G have a perfect matching, let f(v)=1 for vɛS, f(v)≥2 for vɛT. Then an f-star subgraph covering all vertices of S can be found in 0(E log V) time. Also, a collection of vertex-disjoint paths of length 1 or 2 covering all vertives can be found in 0(E log V) time.

#### Recommended Citation

Gabow, Harold N., "A Note on Degree-Constrained Star Subgraphs of Bipartite Graphs ; CU-CS-083-75" (1975). *Computer Science Technical Reports*. 81.

https://scholar.colorado.edu/csci_techreports/81