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.
@article{10_37236_3953,
author = {Yunhua Liao and Yaoping Hou},
title = {Note on the subgraph component polynomial},
journal = {The electronic journal of combinatorics},
year = {2014},
volume = {21},
number = {3},
doi = {10.37236/3953},
zbl = {1298.05168},
url = {http://geodesic.mathdoc.fr/articles/10.37236/3953/}
}
TY - JOUR
AU - Yunhua Liao
AU - Yaoping Hou
TI - Note on the subgraph component polynomial
JO - The electronic journal of combinatorics
PY - 2014
VL - 21
IS - 3
UR - http://geodesic.mathdoc.fr/articles/10.37236/3953/
DO - 10.37236/3953
ID - 10_37236_3953
ER -
%0 Journal Article
%A Yunhua Liao
%A Yaoping Hou
%T Note on the subgraph component polynomial
%J The electronic journal of combinatorics
%D 2014
%V 21
%N 3
%U http://geodesic.mathdoc.fr/articles/10.37236/3953/
%R 10.37236/3953
%F 10_37236_3953
Yunhua Liao; Yaoping Hou. Note on the subgraph component polynomial. The electronic journal of combinatorics, Tome 21 (2014) no. 3. doi: 10.37236/3953
