Global ETD Search

Search theses and dissertations gathered from participating repositories worldwide. Every result links back to the library that holds it. No account is needed.

Results

Showing 1 to 7 of 7 for “"graph polynomials"”.

  1. The complexity of graph polynomials

    <p>This thesis examines graph polynomials and particularly their complexity. We give short proofs of two results from Gessel and Sagan (1996) which present new evaluations of the Tutte polynomial concerning orientations. A theorem of Massey et al (1997) gives an expression concerning the average …

    oxford Repository record for The complexity of graph polynomials (opens in a new tab)

  2. Graph polynomials and their representations

    Graph polynomials are polynomials associated to graphs that encode the number of subgraphs with given properties. We list different frameworks used to define graph polynomials in the literature. We present the edge elimination polynomial and introduce several graph polynomials equivalent to it. …

    qucosa-diss

  3. Domination in graphs with application to network reliability

    … we investigate different domination-related graph polynomials, like the connected domination polynomial, the independent domination polynomial, and the total domination polynomial. We prove some basic properties of these polynomials and obtain formulas for the calculation in special graph …

    qucosa-diss

  4. Extensions of the Tutte Polynomial and Results on the Interlace Polynomial

    In graph theory, graph polynomials are an important tool to encode information from a graph. The Tutte polynomial, first introduced in 1947, is one of the most important graph polynomials due to its universality. Here, we present three classic definitions of the Tutte polynomial via a …

    waterloo Repository record for Extensions of the Tutte Polynomial and Results on the Interlace Polynomial (opens in a new tab)

  5. Efficient Computation of Chromatic and Flow Polynomials

    This thesis surveys chromatic and flow polynomials, and presents new efficient methods to compute these polynomials on specific families of graphs. The chromatic and flow polynomials of a graph count the number of ways to color and assign flow to the graph; they also contain other important …

    rice Repository record for Efficient Computation of Chromatic and Flow Polynomials (opens in a new tab)

  6. A Combinatorial Tale of Two Scattering Amplitudes: See Two Bijections

    … the zeros of the Kirchoff polynomial and related graph polynomials. Through reformulating the c2-invariant as a purely combinatorial problem, we show how enumerating certain edge bipartitions through fixed-point free involutions can complete a special case of the long sought after c2 completion …

    waterloo Repository record for A Combinatorial Tale of Two Scattering Amplitudes: See Two Bijections (opens in a new tab)

  7. On the chromatic symmetric functions of trees

    The chromatic symmetric function (CSF) of a graph, introduced by Richard Stanley in 1995, is a symmetric function generalization of the chromatic polynomial which enumerates proper colorings by the number of uses of each color. We attack a long-standing open question of Stanley that asks whether …

    washington Repository record for On the chromatic symmetric functions of trees (opens in a new tab)