On K-trees and Special Classes of K-trees

<p>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.</p>

Name thesis:degree_name

Ph.D. in Mathematics

Level thesis:degree_level

Dissertation

Year dc:date.available

2012

Author dc:creator

• Estes, John Wheless

Contributors dc:contributor

• Bing Wei
• Talmadge James Reid
• Haidong Wu

• Fibonacci Number
• Independence Polynomial
• K-Degenerate Graph
• K-Tree
• Maximal Outerplanar Graph
• Zagreb Indices
• Mathematics

Repository record dc:identifier

https://egrove.olemiss.edu/etd/101

OAI identifier oai:identifier

oai:egrove.olemiss.edu:etd-1100