Electronic Theses and Dissertations

Date of Award

2012

Document Type

Dissertation

Degree Name

Ph.D. in Mathematics

First Advisor

Bing Wei

Second Advisor

James Reid

Third Advisor

Haidong Wu

Abstract

The class of k-trees is defined recursively as follows: the smallest k-tree is the k-clique. If G is a graph obtained by attaching a vertex v to a k-clique in a k-tree, then G is also a k-tree. Trees, connected acyclic graphs, are k-trees for k = 1. We introduce a new parameter known as the shell of a k-tree, and from the shell special subclasses of k-trees, tree-like k-trees, are classified. Tree-like k-trees are generalizations of paths, maximal outerplanar graphs, and chordal planar graphs with toughness exceeding one. Let fs = fs( G) be the number of independent sets of cardinality s of G. Then the polynomial I(G; x) = [special characters omitted] fs(G)x s is called the independence polynomial. All rational roots of the independence polynomials of paths are found, and the exact paths whose independence polynomials have these roots are characterized. Additionally trees are characterized that have ?1/q as a root of their independence polynomials for 1 ? q ? 4. The well known vertex and edge reduction identities for independence polynomials are generalized, and the independence polynomials of k-trees are investigated. Additionally, sharp upper and lower bounds for fs of maximal outerplanar graphs, i.e. tree-like 2-trees, are shown along with characterizations of the unique maximal outerplanar graphs that obtain these bounds respectively. These results are extensions of the works of Wingard, Song et al., and Alameddine. Let M1 and M2 be the first and second Zagreb index respectively. Then the minimum and maximum M1 and M2 values for k-trees are determined, and the unique k-trees that obtain these minimum and maximum values respectively are characterized. Additionally, the Zagreb indices of tree-like k-trees are investigated.

Included in

Mathematics Commons

Share

COinS
 
 

To view the content in your browser, please download Adobe Reader or, alternately,
you may Download the file to your hard drive.

NOTE: The latest versions of Adobe Reader do not support viewing PDF files within Firefox on Mac OS and if you are using a modern (Intel) Mac, there is no official plugin for viewing PDF files within the browser window.