Accession Number : AD0742348

Title :   Degrees and Matchings.

Descriptive Note : Technical rept.,

Corporate Author : STANFORD UNIV CALIF DEPT OF COMPUTER SCIENCE

Personal Author(s) : Chvatal,V.

Report Date : MAR 1972

Pagination or Media Count : 19

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)

Descriptors :   (*LINEAR PROGRAMMING, GRAPHICS), SET THEORY, THEOREMS

Subject Categories : Operations Research

Distribution Statement : APPROVED FOR PUBLIC RELEASE