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 Split Graphs

 

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 Ω(9,30)

 

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.