Properties of graph polynomials and related parameters
Date
2017-12
Journal Title
Journal ISSN
Volume Title
Publisher
Stellenbosch : Stellenbosch University
Abstract
ENGLISH ABSTRACT : In this thesis, we investigate various problems related to graph polynomials.
We first define two-variable polynomials for rooted trees and specific
posets, which are motivated by the Tutte polynomial. We observe that these
polynomials also satisfy a deletion-contraction property, and they are connected
to antichains and transversals.
The second problem concerns the average size of independent vertex
sets of a graph, following the work of Jamison on subtrees. The average
size of independent sets is the logarithmic derivative of the independence
polynomial evaluated at one. We characterize extremal graphs among all
n-vertex graphs and all n-vertex trees for this invariant.
In a similar way, the average size of independent edge sets, also called
matchings, is studied. We discover that graphs which minimize this invariant,
maximize the average size of independent sets and vice versa. These
results are expected, in view of the correlation between independent sets
and matchings. Furthermore, we find a bound on the matching energy of a
graph in terms of the average size of matchings.
Finally, we focus on a special class of trees, namely trees with given degree
sequence. Many authors have already worked on different invariants
for trees with prescribed degree sequence using quite diverse techniques.
One surprising fact is that extremal trees for different parameters coincide. Our goal is to generalise and unify these results within one proof. We rediscover
known results for invariants such as the Wiener index, the number
of subtrees, the matching polynomial and the number of independent sets,
and also find new ones, as for rooted spanning forests, related to coefficients
of the Laplacian polynomial, and the solvability of a graph.
AFRIKAANSE OPSOMMING : In hierdie tesis ondersoek ons verskeie probleme in verband met grafiekpolinome. Ons definieer eers ’n polinoom in twee veranderlikes vir gewortelde bome en spesifieke parsieel geordende versamelings, wat gemotveer is deur die Tutte-polinoom. Ons sien dat hierdie polinome ook ’n verwydering-kontraksie-eienskap bevredig, en hulle hou verband met antikettings en transversale. Die tweede probleem gaan oor die gemiddelde grootte van onafhanklike versamelings van punte in ’n grafiek, waar ons die werk van Jamison oor deelbome volg. Die gemiddelde grootte van onafhanklike versamelings is die logaritmiese afgeleide van die onafhanklikheidspolinoom wat by een geëvalueer word. Ons karakteriseer die grafieke en bome met n punte wat die ekstreemwaardes bereik. Op ’n soortgelyke manier word die gemiddelde grootte van onafhanklike versamelings van lyne, wat ook as matchings bekendstaan, bestudeer. Ons vind dat grafieke wat hierdie invariant se minimale waarde bereik, gelyktydig die gemiddelde grootte van onafhanklike puntversamelings maksimeer, en andersom. Hierdie resultate kan verwag word in die lig van die verband tussen onafhanklike versamelings en matchings. Verder vind ons ’n grens vir die energie van ’n grafiek in terme van die gemiddelde grootte van matchings. Uiteindelik fokus ons op ’n spesiale klas bome, naamlik bome met gegewe graadry. Baie navorsers het reeds aan verskillende invariante gewerk vir bome met voorgeskrewe graadry deur gebruik te maak van redelik diverse tegnieke. Een verrassende feit is dat ekstremale bome vir verskillende parameters ooreenstem. Ons doelwit is om hierdie resultate in een bewys te veralgemeen en te verenig. Ons herontdek bekende resultate vir invariante soos die Wiener-indeks, die aantal deelbome, die matching-polinoom en die aantal onafhanklike versamelings, en vind ook nuwes, soos vir gewortelde spanbosse, wat verband hou met koëffisiënte van die Laplace-polinoom, en die oplosbaarheid van ’n grafiek.
AFRIKAANSE OPSOMMING : In hierdie tesis ondersoek ons verskeie probleme in verband met grafiekpolinome. Ons definieer eers ’n polinoom in twee veranderlikes vir gewortelde bome en spesifieke parsieel geordende versamelings, wat gemotveer is deur die Tutte-polinoom. Ons sien dat hierdie polinome ook ’n verwydering-kontraksie-eienskap bevredig, en hulle hou verband met antikettings en transversale. Die tweede probleem gaan oor die gemiddelde grootte van onafhanklike versamelings van punte in ’n grafiek, waar ons die werk van Jamison oor deelbome volg. Die gemiddelde grootte van onafhanklike versamelings is die logaritmiese afgeleide van die onafhanklikheidspolinoom wat by een geëvalueer word. Ons karakteriseer die grafieke en bome met n punte wat die ekstreemwaardes bereik. Op ’n soortgelyke manier word die gemiddelde grootte van onafhanklike versamelings van lyne, wat ook as matchings bekendstaan, bestudeer. Ons vind dat grafieke wat hierdie invariant se minimale waarde bereik, gelyktydig die gemiddelde grootte van onafhanklike puntversamelings maksimeer, en andersom. Hierdie resultate kan verwag word in die lig van die verband tussen onafhanklike versamelings en matchings. Verder vind ons ’n grens vir die energie van ’n grafiek in terme van die gemiddelde grootte van matchings. Uiteindelik fokus ons op ’n spesiale klas bome, naamlik bome met gegewe graadry. Baie navorsers het reeds aan verskillende invariante gewerk vir bome met voorgeskrewe graadry deur gebruik te maak van redelik diverse tegnieke. Een verrassende feit is dat ekstremale bome vir verskillende parameters ooreenstem. Ons doelwit is om hierdie resultate in een bewys te veralgemeen en te verenig. Ons herontdek bekende resultate vir invariante soos die Wiener-indeks, die aantal deelbome, die matching-polinoom en die aantal onafhanklike versamelings, en vind ook nuwes, soos vir gewortelde spanbosse, wat verband hou met koëffisiënte van die Laplace-polinoom, en die oplosbaarheid van ’n grafiek.
Description
Thesis (PhD)--Stellenbosch University, 2017
Keywords
Extremal trees, Tutte polynomials, Graph polynomials, UCTD, Polynomials, Graph parameters, Parameters (Mathematics), Independent set (Graph theory)