Degrees and Matchings.

Abstract

Let n, b, d be positive integers. D. Hanson proposed to evaluate f(n,b,d), the largest possible number of edges in a graph with n vertices having no vertex of degree greater than d and no set of more than b independent edges. Using the alternating path method, he found partial results in this direction. he author completes Hanson's work; the proof technique has a linear programming flavor and uses Berge's matching formula. (Author)

Document Details

Document Type
Technical Report
Publication Date
Mar 01, 1972
Accession Number
AD0742348

Entities

People

  • V. Chvatal

Organizations

  • Stanford University

Tags

DTIC Thesaurus Topics

  • Applied Mathematics
  • Computer Programming
  • Computing-Related Activities
  • Convex Programming
  • Interdisciplinary Science
  • Linear Programming
  • Mathematical Programming
  • Mathematics
  • Operations Research

Readers

  • Gender and Food Studies
  • Graph Algorithms and Convex Optimization.