Reports

 

A Note on Degree-Constrained Star Subgraphs of Bipartite Graphs ; CU-CS-083-75 Public Deposited

Downloadable Content

Download PDF
https://scholar.colorado.edu/concern/reports/bz60cx02x
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.
Creator
Date Issued
  • 1975-10-01
Academic Affiliation
Last Modified
  • 2019-12-21
Resource Type
Rights Statement
Language

Relationships

Items