Name
Abstract | ||
|---|---|---|
It is known that the chromatic polynomial and flow polynomial of a graph are two important evaluations of its Tutte polynomial, both of which contain much information of the graph. Much research is done on graphs determined entirely by their chromatic polynomials and Tutte polynomials, respectively. Oxley asked which classes of graphs or matroids are determined by their chromatic and flow polynomials together. In this paper, we found several classes of graphs with this property. We first study which graphic parameters are determined by the flow polynomials. Then we study flow-unique graphs. Finally, we show that several classes of graphs, ladders, Mobius ladders and squares of n-cycle are determined by their chromatic polynomials and flow polynomials together. A direct consequence of our theorem is a result of de Mier and Noy [A. de Mier, M. Noy, On graphs determined by their Tutte polynomial, Graphs Comb. 20 (2004) 105-119] that these classes of graphs are Tutte polynomial unique. |
Year | DOI | Venue |
|---|---|---|
2008 | 10.1016/j.dam.2007.10.010 | Discrete Applied Mathematics |
Keywords | Field | DocType |
flow-unique graph,graphs comb,m. noy,chromatic and flow polynomials,graphic parameter,tutte polynomial,chromatic polynomial,de mier,flow polynomial,flow polynomial unique graph,direct consequence,chromatic and flow unique graphs,mobius ladder,tutte polynomials,t -unique graphs and matroids,t | Tutte 12-cage,Discrete mathematics,Combinatorics,Indifference graph,Tutte polynomial,Chordal graph,Tutte theorem,Nowhere-zero flow,Chromatic polynomial,Mathematics,Graph coloring | Journal |
Volume | Issue | ISSN |
156 | 12 | Discrete Applied Mathematics |
Citations | PageRank | References |
3 | 0.44 | 7 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Yinghua Duan | 1 | 3 | 0.78 |
| Haidong Wu | 2 | 26 | 8.43 |
| Qinglin Yu | 3 | 102 | 20.73 |