liao220502的个人博客分享 http://blog.sciencenet.cn/u/liao220502

博文

Note on the subgraph component polynomial

已有 2095 次阅读 2014-9-23 17:25 |系统分类:论文交流|关键词:学者| 子图分支多项式

 

   Tittmann, Averbouch and Makowsky [The enumeration of vertex induced subgraphs with respect to the number of components, European J. Combin. 32 (2011) 954- 974] introduced the subgraph

component polynomial Q(G; x, y) of a graph G, which counts the number of connected components in

vertex induced subgraphs. This polynomial encodes a large amount of combinatorial information

about the underlying graph, such as the order, the size, and the independence number. We show that several other graph invariants, such as the connectivity and the number of cycles of length four in a regular bipartite graph are also determined by the subgraph component polynomial. Then, we

prove that several well- known families of graphs are determined by the polynomial Q(G; x, y).

Moreover, we study the distinguishing power and find simple graphs which are not distinguished by the subgraph component polynomial but distinguished by the characteristic polynomial, the matching polynomial and the Tutte polynomial. These are partial answers to three open problems proposed by Tittmann et al.




https://m.sciencenet.cn/blog-871170-830220.html


下一篇:Tutte polynomial of a small-world Farey graph

0

该博文允许注册用户评论 请点击登录 评论 (0 个评论)

数据加载中...
扫一扫,分享此博文

Archiver|手机版|科学网 ( 京ICP备07017567号-12 )

GMT+8, 2024-5-19 00:17

Powered by ScienceNet.cn

Copyright © 2007- 中国科学报社

返回顶部