**Investigating
Graphs Based on Kelmans Research**

By: Christina Marie Rajsz

Ewa Anna Zielonka

**Abstract**

*A.K. Kelmans is prolific researcher in the area of spanning
trees in graph theory. One of his earlier papers has never been translated into
English and remains in Russian. We are attempting to translate a portion of
this paper. His papers are written at a very high technical level. We are using
some of his other papers as a guide*.

A Formula for the Number of
Spanning Trees in Proper

By: Tania Garofalo

Jennifer Michewicz

Anne Ryan

Deborah Thomas

*In network reliability, the
number of spanning trees is a measure of the graph's vulnerability. A split
graph is a graph whose nodes can be partitioned into cliques and an independent
set. Zbigniew Bogdanowicz
developed formulas for the number of spanning trees in special types of split
graphs, called threshold graphs. We are studying split graphs with equal cone
degree (called proper split graphs) and developing a formula for their number
of spanning trees.*

Investigation of the Graph Ω(

By: Rachel Nowetner

Andrea Berkman

Monica Makowski

Pat Farley

Abstract

*In network reliability theory, an
important measure of a graph’s vulnerability is its number of spanning
trees. It has been conjectured that no
multigraph (a graph that allows more than one edge between a pair of nodes)
would have the greatest number of spanning trees among all graphs having the
same number of nodes and edges. However,
in a particular case in which a single edge is to be added to a specific graph
structure, a multigraph has the most spanning trees, except when there are nine
nodes and thirty edges (Ω(**9,30**)). We are
investigating this particular case.*

**An Extension of Turan’s
Theorem to Multigraphs**

By:**
Sarah Bleiler**

**Joseph Di
Lauri**

**Robert Michniewicz**

**Lauren Joy Sunshine**

**In **
**2004****, Aldea, Cruz, Gaccione,
Jablonski, and ****Shelton**** gave an
extension of Turan’s Theorem including the maximum multiplicity of
triangle-free multigraphs. In the paper
entitled “Two Extensions of Turan’s Theorem” Balister and Bollobas present an upper
bound on the edges of a graph G which is free of complete graphs of order r+****1****.
The first extension gives the maximal number of
edges for non r-partite graphs and the second extension states this upper bound
in terms of the square of the graph. We
will further extend their results to multigraphs.**