| SES |
CHARLES V. SCHAEFER, JR. SCHOOL OF ENGINEERING AND SCIENCE |
|
| MATHEMATICAL SCIENCES | STOCHASTIC SYSTEMS SEMINAR | |
|
|
||
|
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. |
||
|
| ||
| Dept of Mathematical Sciences • Stevens Institute of Technology • Hoboken, NJ • (201) 216-5449 | ||