Show simple item record

dc.contributor.authorDay, Dylan
dc.date.accessioned2017-04-07T14:12:23Z
dc.date.available2017-04-07T14:12:23Z
dc.identifier.urihttp://hdl.handle.net/10222/72816
dc.description.abstractThe neighbourhood polynomial of a graph is the generating function for the neighbourhood complex, which contains all subsets of vertices which have a common neighbour. We begin with some formulas for computing the neighbourhood polynomial. We then show a relation between the neighbourhood polynomial of one graph and the domination polynomial of its complement, and prove that computing the neighbourhood polynomial is NP-hard. Concerning the roots of the neighbourhood polynomial, we consider when all the roots are real and what bounds we can place on them. We show the rational roots of neighbourhood polynomials are exactly those numbers of the form -1/2n for natural numbers n. We also answer the question of the closure of the neighbourhood roots, finding the negative real line for the real roots and the complex plane for the complex roots. Finally, we use random graphs to show that almost all neighbourhood polynomials have nonreal roots.en_US
dc.language.isoenen_US
dc.subjectNeighbourhood Polynomialen_US
dc.subjectComplexityen_US
dc.subjectRootsen_US
dc.subjectClosureen_US
dc.subjectSimplicial Complexen_US
dc.subjectGraph Theoryen_US
dc.subjectDomination (Graph theory)
dc.titleOn the Neighbourhood Polynomialen_US
dc.date.defence2017-03-29
dc.contributor.departmentDepartment of Mathematics & Statistics - Math Divisionen_US
dc.contributor.degreeMaster of Scienceen_US
dc.contributor.external-examinern/aen_US
dc.contributor.graduate-coordinatorDr. David Ironen_US
dc.contributor.thesis-readerDr. Karl Dilcheren_US
dc.contributor.thesis-readerDr. Richard Nowakowskien_US
dc.contributor.thesis-supervisorDr. Jason Brownen_US
dc.contributor.ethics-approvalNot Applicableen_US
dc.contributor.manuscriptsNot Applicableen_US
dc.contributor.copyright-releaseNot Applicableen_US
 Find Full text

Files in this item

Thumbnail

This item appears in the following Collection(s)

Show simple item record