| dc.contributor.author | Hickman, Carl Andrew. | en_US |
| dc.date.accessioned | 2014-10-21T12:36:10Z | |
| dc.date.available | 2001 | |
| dc.date.issued | 2001 | en_US |
| dc.identifier.other | AAINQ66659 | en_US |
| dc.identifier.uri | http://hdl.handle.net/10222/55789 | |
| dc.description | Two polynomials arise naturally from the notion of an independent set of vertices in a graph G: (i) the chromatic polynomial, pi(G, x) = sumk ≥1rkx( k) where rk is the number of partitions of V(G) into k independent sets (and x( k) a falling factorial); and (ii) the independence polynomial, iG( x) = sumk≥0i kxk, where ik is the number of independent sets in V of cardinality k. We study here the roots of these polynomials, each respect to a specific graph operation: chromatic roots with respect to edge subdivision, independence roots with respect to graph composition. | en_US |
| dc.description | For a connected graph G of co-rank k = |E| - |V| + 1, it is known that any chromatic root z satisfies |z - 1| ≤ k. We prove that large subdivisions of G , while not changing its co-rank, draw the chromatic roots close to the disk |z - 1| ≤ 1. For 'uniform' subdivisions, we describe the limit points of the roots, and in turn characterize graphs having a subdivision with a chromatic root with negative real part. In fact, infinitely many such roots are achievable from graphs of corank 2, the 3-ary theta graphs. And for each 3 ≤ k ≤ 8, the k-ary theta graph with path lengths 2 has a chromatic root z which maximizes |z -1|. | en_US |
| dc.description | Independence polynomials are (essentially) closed under graph composition. We prove this, and apply it to families of well covered and comparability graphs, finding the topological closures of both real and complex independence roots. For higher composites of a graph G with itself, we prove that their independence roots converge (in the Hausdorff topology) to the Julia set of iG( x) - 1, thereby associating a fractal with G. For graphs with independence number 2, we determine when these fractals are connected. Further, the join of all sufficiently many copies of any graph has a disconnected fractal, proving the existence of many connected graphs with a disconnected independence fractal . | en_US |
| dc.description | Thesis (Ph.D.)--Dalhousie University (Canada), 2001. | en_US |
| dc.language | eng | en_US |
| dc.publisher | Dalhousie University | en_US |
| dc.publisher | | en_US |
| dc.subject | Mathematics. | en_US |
| dc.title | Roots of chromatic and independence polynomials. | en_US |
| dc.type | text | en_US |
| dc.contributor.degree | Ph.D. | en_US |
