On chromatic and flow polynomial unique graphs |
| |
Authors: | Yinghua Duan Qinglin Yu |
| |
Institution: | a Center for Combinatorics, LPMC, Nankai University, Tianjin, China b Department of Mathematics, University of Mississippi, MS, USA c Department of Mathematics and Statistics, Thompson Rivers University, Kamloops, BC, Canada |
| |
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, Möbius 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. |
| |
Keywords: | Chromatic and flow polynomials Tutte polynomials Chromatic and flow unique graphs _method=retrieve& _eid=1-s2 0-S0166218X07004672& _mathId=si11 gif& _pii=S0166218X07004672& _issn=0166218X& _acct=C000053510& _version=1& _userid=1524097& md5=9d9782e5e5891c1f4ca39cac06b38460')" style="cursor:pointer T-unique graphs and matroids" target="_blank">" alt="Click to view the MathML source" title="Click to view the MathML source">T-unique graphs and matroids |
本文献已被 ScienceDirect 等数据库收录! |
|