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