首页 | 本学科首页   官方微博 | 高级检索  
     检索      


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 等数据库收录!
设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号