Properties of graph polynomials and related parameters

Misanantenaina, Valisoa Razanajatovo (2017-12)

Thesis (PhD)--Stellenbosch University, 2017

Thesis

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.

Please refer to this item in SUNScholar by using the following persistent URL: http://hdl.handle.net/10019.1/102686
This item appears in the following collections: