Browse Prior Art Database

DEGREES AND MATCHINGS

IP.com Disclosure Number: IPCOM000128299D
Original Publication Date: 1972-Dec-31
Included in the Prior Art Database: 2005-Sep-15
Document File: 12 page(s) / 27K

Publishing Venue

Software Patent Institute

Related People

V. Chvatal: AUTHOR [+3]

Abstract

Let n , b ~, d be positive integers. D. Hanson proposed to evaluate f(n.,bd) , 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. We complete Hanson's work; our proof technique has a linear programming flavor and uses Berge's matching formula.

This text was extracted from a PDF file.
This is the abbreviated version, containing approximately 26% of the total text.

Page 1 of 12

THIS DOCUMENT IS AN APPROXIMATE REPRESENTATION OF THE ORIGINAL.

DEGREES AND MATCHINGS

by V. Chvatal Computer Science Department Stanford University

Abstract

Let n , b ~, d be positive integers. D. Hanson proposed to evaluate f(n.,bd) , 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. We complete Hanson's work; our proof technique has a linear programming flavor and uses Berge's matching formula.

AMS(MOS) subject classification numbers (1970): Primary 05C35 Secondary 9OC10

Keywords and phrases: Degrees., matchings, independent edges,

Berge's matching formula.

This research was supported by the National Science Foundation under grant number GJ-992, and the Office of Naval Research under grant number N-00014-67-A-0112-0057 NR o44-402. Reproduction in whole or in part is permitted for any purpose of the United States Government.

1. Introduction

Erd6s and Rado 151 proved that given any positive integers n, k there is always an integer a with the following property: if F is any family of more than a sets,, each of cardinality n , then some k members of F have pairwise the sair.Le intersection. Let us denote the smallest such a by q)(n,k) . Some results on cp(n,k) can be

found in 151., 1'] and 13]. Obviously, cp(2.,k) is the maximum number of edges in a graph containing no vertex of degree greater than k-l and no set of more than k-l independent edges. The values of CP(2,k) have been determined by N. Sauer (to appear):

(Equation Omitted)

D. Hanson [61 considered a little more general problem. By an (n,b.,d)-graph we shall mean a graph G such that

(i) G has n vertices) (ii) G contains no set of more than b independent edges,

(iii) G contains no vertex of degree greater than d .

The largest possible number of edges of' an (nb,d)-graph will be denoted by

(Equation Omitted)

Stanford University Page 1 Dec 31, 1972

Page 2 of 12

DEGREES AND MATCHINGS

In the Greek alphabet notation of 171, f(n,b,d) is the maximum of q(G) subject to t,he constraints

(Equation Omitted)

Obviously,

(Equation Omitted)

whenever d > n-l Similarly.,

(Equation Omitted)

whenever n < 2b+l Hence we can restrict ourselves to the case

(Equation Omitted)

Apart from the most difficult case (d odd and < 2b , n small)., thevalues of f(n,b,d) have already been obtained by Hanson [6]. His proof technique is based on the alternating path method. We will adopt a different approach, related to linear programming. This technique simplifies the proofs and enables us to complete the evaluation of f(n,b,d) without much additional effort. The result goes as follows.

THEOREM. Let n , b , d be positive integers with n > 2b+l

A. If

(Equation Omitted)

if d is even.

B. If d < 2b and n > 2b+ b then d+ 1 2

(Equation Omitted)

then max

(Equation Omitted)

(Equation Omitted)

In proving that f(n)bjd) cannot exceed the valu...