SES CHARLES V. SCHAEFER, JR.
SCHOOL OF ENGINEERING AND SCIENCE
MATHEMATICAL SCIENCES STOCHASTIC SYSTEMS SEMINAR

Some New Results on Degree Sequences


Professor Nathan Kahl
Seton Hall University



Tuesday, October 30, 2007
4:00pm
Peirce 116


Abstract:  Frank Boesch, former Dean of the Faculty at Stevens, was the founding editor and for many years the editor-in-chief of the journal Networks. One of his best known papers is "The strongest monotone degree conditions for n-connectedness of a graph." In a special issue of Networks dedicated to his memory, we give a simple sufficient degree condition for a graph to be k-edge connected, and also give the strongest monotone degree condition for a graph to be 2-edge connected. We then apply a similar technique to obtain a new lower bound for the independence number of a graph in terms of its vertex degrees, and show that this new bound is the strongest lower bound of this type. We also show that this bound can be "infinitely better" than the well known bound of Caro and Wei.


Refreshments served at 3:45pm.
Dept of Mathematical Sciences • Stevens Institute of Technology • Hoboken, NJ • (201) 216-5449