% EJC papers must begin as follows
\documentclass[12pt]{article}
\usepackage{e-jc}
\specs{P3.27}{21(3)}{2014}

% only use standard LaTeX packages
% only include essential packages

% we recommend these ams packages
\usepackage{amsthm,amssymb}

%\usepackage[utf8]{inputenc}
%\usepackage[T1]{fontenc}
%\usepackage[english]{babel}
\usepackage{mathtools}
\usepackage{rotating}
\graphicspath{{figures/}}
\usepackage{graphicx}

% use this command to create hyperlinks (optional and recommended)
\usepackage[colorlinks=true,citecolor=black,linkcolor=black,urlcolor=blue]{hyperref}

% use these commands for typesetting doi and arXiv references in the bibliography
\newcommand{\doi}[1]{\href{http://dx.doi.org/#1}{\texttt{doi:#1}}}
\newcommand{\arxiv}[1]{\href{http://arxiv.org/abs/#1}{\texttt{arXiv:#1}}}

% all overfull boxes must be fixed; i.e. there must be no text protruding into the margins
% use \sloppy to avoid overly wide text
\sloppy

% declare theorem-like environments
\theoremstyle{plain}
\newtheorem{theorem}{Theorem}[section]
\newtheorem{thm}[theorem]{Theorem}
\newtheorem{Theorem}[theorem]{Theorem}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{lem}[theorem]{Lemma}
\newtheorem{Lemma}[theorem]{Lemma}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{Corollary}[theorem]{Corollary}
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{Proposition}[theorem]{Proposition}
\newtheorem{fact}[theorem]{Fact}
\newtheorem{Fact}[theorem]{Fact}
\newtheorem{observation}[theorem]{Observation}
\newtheorem{Observation}[theorem]{Observation}
\newtheorem{claim}[theorem]{Claim}
\newtheorem{Claim}[theorem]{Claim}
\newtheorem{redu}[theorem]{Reduction}

\theoremstyle{definition}
\newtheorem{definition}[theorem]{Definition}
\newtheorem{Definition}[theorem]{Definition}
\newtheorem{example}[theorem]{Example}
\newtheorem{conjecture}[theorem]{Conjecture}

\newtheorem{openproblem}{Open Problem}
%\newtheorem{problem}[theorem]{Problem}
%\newtheorem{question}[theorem]{Question}

\theoremstyle{remark}
\newtheorem{remark}[theorem]{Remark}
\newtheorem{Remark}[theorem]{Remark}
\newtheorem{note}[theorem]{Note}

\newcommand{\Qmat}{\mathbf{Q}}
\newcommand{\Amat}{\mathbf{A}}
\newcommand{\Bmat}{\mathbf{B}}
\newcommand{\Pmat}{\mathbf{P}}
\newcommand{\Dmat}{\mathbf{M}}
\newcommand{\Umat}{\mathbf{U}}
\newcommand{\Vmat}{\mathbf{V}}
\newcommand{\Rmat}{\mathbf{R}}
\newcommand{\uvec}{\mathbf{u}}
\newcommand{\avec}{\boldsymbol{\alpha}}
\newcommand{\cvec}{\mathbf{c}}
\newcommand{\bvec}{\mathbf{b}}
\newcommand{\svec}{\mathbf{s}}
\newcommand{\evec}{\mathbf{e}}
\newcommand{\pvec}{\mathbf{p}}
\newcommand{\rvec}{\mathbf{r}}
\newcommand{\vvec}{\mathbf{v}}
\newcommand{\dvec}{\mathbf{d}}
\newcommand{\Mat}{\mathrm{Mat}}
\newcommand{\p}[1]{p_{#1}}

\newcommand{\nm}[1]{\mbox{\normalsize $#1$}}

\newcommand*\samethanks[1][\value{footnote}]{\footnotemark[#1]}

% Notation
\newcommand{\triangleOp}{\odot}
\renewcommand{\emptyset}{\varnothing}

\DeclarePairedDelimiter\abs{\lvert}{\rvert}


\newcommand{\ditem}{\item[---]}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\title{\bf Note on the subgraph component polynomial}




\author{Yunhua Liao\\
\small Department of Mathematics\\[-0.8ex]
\small Hunan Normal University\\[-0.8ex]
\small Changsha, Hunan 410081 China\\
\and
Yaoping Hou\footnote{Corresponding author: yphou@hunnu.edu.cn}  \\
\small Department of Mathematics\\[-0.8ex]
\small Hunan First Normal University\\[-0.8ex]
\small Changsha, Hunan 410205 China\\
}

\date{\dateline{Dec 9, 2013}{Aug 7, 2014}{Aug 21, 2014}\\
   \small Mathematics Subject Classification: 05C20}


\begin{document}

\maketitle


\begin{abstract}
Tittmann, Averbouch and Makowsky [The enumeration of vertex induced subgraphs with respect to the number of components, \emph{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.
\end{abstract}




\section{Introduction}


 All graphs in this paper are simple and finite. Let $G=(V(G),E(G))$ be a graph. The \emph{order} and the \emph{size} of $G$ are the number of vertices and the number of edges of $G$, respectively. As usual, the \emph{complete graph}, the \emph{cycle}, and the \emph{path} on $n$ vertices  are denoted by $K_n$, $C_n$ and $P_n$, respectively; the \emph{complete bipartite graph} with part sizes $m$ and $n$ is $K_{m,n}$, and $K_{1,n}$ is the \emph{star}. The \emph{open neighborhood} of a vertex $v \in V(G)$ is the set $N_G(v)=\{w: w\in V(G) \quad and \quad \{v,w\} \in E(G)\}$, and the \emph{closed neighborhood} $N[v]=N_G(v)\cup \{v\}$; if there is no ambiguity on $G$, we use $N(v)$ and $N[v]$, respectively. The degree $d(v)$ of vertex $v$ is the number of edges incident with $v$.  A vertex $v$ is called a \emph{pendant vertex} if $d(v)=1$. The \emph{minimum degree} of $G$ is denoted by $\delta (G)$. Given a subset $U\subseteq V(G)$, we write $G[U]$ for the vertex induced subgraph of $G$ by $U$. An \emph{independent set} in $G$ is a set of vertices no two of which are adjacent. The \emph{independence number} $\alpha(G)$ is defined as the cardinality of a maximum independent set in graph $G$.


A graph $G$ is \emph{connected} if any two of its vertices are linked by a path. A \emph{separating set} of a connected graph $G$ is a set of vertices whose removal renders $G$ disconnected. The \emph{ vertex connectivity} $c(G)$ (where $G$ is not a complete graph) is the order of a minimal separating set.  Obviously, $c(G) \leqslant \delta (G)$. A graph is called \emph{k-connected} if its vertex connectivity is  not less than $k$. This means that if a graph $G$ is $k$-connected, then $G[ V\backslash U] $ is connected for every subset $U \subseteq V(G)$ with $|U|< k$. The complete graph $K_n$ has no separating set, but by convention $c(K_n)= n-1$. A connected graph $G$ is said to be \emph{unicycle} if $|V(G)|=|E(G)|$. Observe that a unicycle can be regarded as a cycle with trees attached to its vertices. For more standard definitions, we refer the reader to the text of Diestel \cite{Diestel00}.


 A number of different graph polynomials have been introduced and widely studied: such as the chromatic polynomial \cite{Read}, the Tutte polynomial \cite{Bernardi08,Ellis11,Tutte54}, the matching polynomial \cite{Dong12,Farrell79,Yan09}, the domination polynomial \cite{Akbari10,Kotek12} and the edge elimination polynomial \cite{Averbouch10,Trinks12}. Recently, Tittmann, Averbouch and Makowsky \cite{Tittmann11} defined the \emph{subgraph component polynomial $Q(G;x,y)$}, which counts the number of connected components in induced subgraphs. This polynomial $Q(G;x,y)$ has many interesting properties; for example, it is universal with respect to vertex elimination, and it determines the order, the size, the number of components, and the independence number of $G$. In addition, Tittmann et al. \cite{Tittmann11} found that the star $K_{1,n}$ is determined by $Q(G;x,y)$, and they posed a number of problems concerning this polynomial. In this paper, we are mainly concerned with three of those problems:

\vspace*{2mm}
{\bf Problem 1.} {\em
Are there simple graphs distinguished by the characteristic polynomial $p(G;x)$, the matching polynomial $m(G;x)$, the bivariate chromatic polynomial $P(G;x,y)$ or the Tutte polynomial $T(G;x,y),$  which are not distinguished by $Q(G;x,y)?$}
\vspace*{2mm}

 {\bf Problem 2.} {\em Find more graph invariants which are determined by $Q(G;x,y)$.}
\vspace*{2mm}

 {\bf Problem 3.} {\em  Find more classes of graphs which are determined by $Q(G;x,y)$.}
\vspace*{2mm}

Our main findings are:
\begin{itemize}
  \item We discover much more information  contained in the polynomial $Q(G;x,y)$, e.g. the  vertex connectivity $c(G)$ (Theorem~\ref{theorem:connectivity}), the regularity (Proposition~\ref{proposition:regularity}), and the number of cycles of length four when $G$ is a regular bipartite graph (Theorem~\ref{theorem:4cycle}). It is a well-known fact that the latter parameter is also determined by the Tutte polynomial \cite{Mier04}.
  \item We find several classes of graphs which are determined by $Q(G;x,y)$, e.g. the path $P_n$, the cycle $C_n$, the tadpole graph $T_{m,n}$, the complete bipartite graph $K_{m,n}$, the friendship graph $C_3^n$, the book graph $B_n$, and the $n$-cube $Q^n$ (Section 4).
  \item We find two simple graphs are distinguished by the characteristic polynomial, the matching polynomial and the Tutte polynomial, but are not distinguished by $Q(G;x,y)$ (Proposition~\ref{proposition:power}).
\end{itemize}


   \section{The subgraph component polynomial}
The polynomial $Q(G; x, y)$ was aroses from analyzing community structures in social networks by Tittmann et al., and has been further studied by Garijo et al. in \cite{Garijo11,Garijo13}. Its formal definition is the following.

  Let $k\left( G\right) $ be the number of components of $G$, and let $q_{i,j}\left( G\right) $ be the number of vertex subsets $X\subseteq V$ with $i$ vertices such that $G\left[ X\right] $ has exactly $j$ components, that is
\[
q_{i,j}\left( G\right) =\left\vert \left\{ X\subseteq V:\left\vert
X\right\vert =i\wedge k\left( G\left[ X\right] \right) =j\right\}
\right\vert.
\]
The \emph{subgraph component polynomial $Q(G;x,y)$} of $G$ is defined as an ordinary generating function for these numbers:
\[
Q\left( G;x,y\right) =\sum_{i=0}^{n}\sum_{j=0}^{n}q_{i,j}\left( G\right)
x^{i}y^{j}.
\]
If we sum over all the possible subsets of vertices, the definition can be rewritten in a slightly different way:
\[
Q\left( G;x,y\right) =\sum_{X\subseteq V}
x^{|X|}y^{k(G[X])}.
\]
Tittmann et al. defined three types of vertex elimination operations on graphs:

\begin{itemize}
  \item \emph{Deletion}. $G-v$ denote the graph obtained by simply removing the vertex $v$.
  \item \emph{Extraction}. $G-N[v]$ denote the graph obtained from $G$ by removal of all vertices adjacent to $v$ including $v$ itself.
  \item \emph{Contraction}. $G/v$ denote the graph  obtained from $G$ by removal of $v$ and insertion of edges between all pairs of non-adjacent neighbor vertices of $v$.
\end{itemize}
They showed that $Q(G;x,y)$ satisfies the following linear recurrence relation with respect to the preceding  operations and is universal in this respect.
\begin{proposition}\label{proposition:elimination}{\bf \cite{Tittmann11}}
Let $G=(V,E)$ be a graph and $v\in V$. Then the subgraph component polynomial satisfies the decomposition formula
\begin{equation*}
Q(G;x,y)=Q(G-v;x,y)+x(y-1)Q(G-N[v];x,y)+xQ(G/v;x,y).
\end{equation*}
\end{proposition}
The previous definition of $q_{i,j}(G)$ yields the following observation. If $H$ is subgraph of $G$, then $q_{i,j}(H)\leqslant q_{i,j}(G)$.



Two graphs $G$ and $H$ are said to be  \emph{subgraph component equivalent}, or simply \emph{$Q$-equivalent}, if $Q(G;x,y)=Q(H;x,y)$.  A graph $G$ is \emph{$Q$-unique} if  $Q(H; x,y)=Q(G;,x,y)$ implies that $H$ is isomorphic to $G$ for any graph $H.$   Let $[x^iy^j]Q(G;x,y)$ denote the coefficient of $x^iy^j$ in $Q(G;x,y)$, and let $deg_xQ(G;x,y)$ be the degree of $Q(G;x,y)$ with respect to the variable $x$.

\section{Graph invariants determined by the subgraph component polynomial}
In general, various aspects of combinatorial invariants/properties and numbers of a graph is stored in the coefficients of a specific graph polynomial, such as  polynomials studied in~\cite{Andren,Noy,Trinks12}. In this section, we will study the coefficients of $Q(G;x,y)$.
\begin{proposition} {\bf \cite{Tittmann11}}
\label{prop:number}
The following graph properties can be easily obtained from the subgraph
polynomial:
\begin{enumerate}
\item[(1)]
The number of vertices:%
\[
|G| =\deg _{x}Q\left(
G;x,y\right) =\log _{2}Q\left( G;1,1\right)=\left[ xy\right] Q\left( G;x,y\right)
\]

\item[(2)]
The number of edges:%
\[
|E(G)| =\left[ x^{2}y\right] Q\left( G;x,y\right)
\]

\item[(3)]
The number of components:%
\[
k\left( G\right) =\deg_{y} \left( \left[ x^{|G| }\right] Q\left(
G;x,y\right) \right)
\]
\item[(4)]
The number of independent sets of each size; in particular, the independence number:
\[
\alpha \left( G\right)=\deg _{y}Q\left( G;x,y\right)
\]
\end{enumerate}
\end{proposition}



%It can be easily observe that the star graph $Star_n$ and the complete graph $K_n$ is determined by the subgraph component polynomial.
Since the order, the size and the number of components of a graph $G$ is determined by its subgraph component polynomial $Q(G;x,y)$, it is clear that if $G$ is a tree and $H$ is $Q$-equivalent to $G$, then $H$ is also a tree.
\begin{theorem}\label{theorem:connectivity}%--------------------------
The  vertex connectivity of a graph $G$ is  determined by its subgraph component polynomial.
\end{theorem}
\begin{proof}
As it was shown by Tittmann et al. \cite{Tittmann11} that complete graphs were determined by the subgraph component polynomial, we just need to consider non-complete graphs  here. Let $G=(V,E)$ be a graph of order $n$. Given a vertex subset $S$ with cardinality $s$, then $k(G[V\backslash S])\geqslant 2$ when $S$ is a separating set of $G$. From the definition of the  vertex connectivity $c(G)$, we have the following relation:
\begin{eqnarray*}
 c(G)&=&min \left\{s:\left[x^{n-s}y^{j} \right]Q\left( G;x,y \right)> 0 \wedge j \geqslant 2 \right\}\\
                  &=&n-max\left \{deg_{x}\left(\left [y^j \right]Q\left(G;x,y \right)\right): j\geqslant 2 \right\}.
\end{eqnarray*}
\end{proof}

\begin{remark}
Theorem~\ref{theorem:connectivity} can also be obtained as an application of Theorem 1 of \cite{Tittmann11}.
\end{remark}
Since the vertex connectivity is  a lower bound for the minimum degree $\delta(G)$, and the order and the size of a graph $G$ are determined by $Q(G;x,y)$ as well, then we can conclude that the regularity of graph $G$ is also determined by $Q(G;x,y)$.

\begin{proposition}
\label{proposition:regularity}
Let $G$ be a $k$-regular graph. If $H$ is $Q$-equivalent to $G$, then $H$ is $k$-regular.
\end{proposition}

\begin{theorem}  \label{theorem:4cycle}
Let $G$ be a $k$-regular bipartite graph of order $n$. Then the number of subgraphs isomorphic to $C_4$ and the number of subgraphs isomorphic to $P_4$ are determined by $Q(G;x,y)$.
\end{theorem}
\begin{proof}
There are three non-isomorphic subgraphs of $G$ (paths of order 4, cycles of order 4 and complete bipartite subgraphs $K_{1,3}$), which contribute to $[x^4y]Q(G;x,y)$ (see Fig.~\ref{fig.1}).


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%% Figure  1
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{figure}[ht]
\begin{center}
\includegraphics[width=0.6\linewidth]{1.eps}
\caption{All possible non-isomorphic subgraphs of $G$ with $4$ vertices and 1 component.}
\label{fig.1}
\end{center}
\end{figure}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

Since $G$ is $k$-regular, the contribution of  $K_{1,3}$ is $n {k \choose 3}$. It follows that
\begin{equation}\label{equation:x4y}
\left [x^4y \right ]Q\left (G;x,y\right )=p+c+n{k \choose 3}
\end{equation}
where $p$ is the number of paths of order $4$ and $c$ is the number of cycles of order $4$.

   For a bipartite graph $G$, a subgraph $A \subseteq G$ contribute to $[x^3y]Q(G;x,y)$ if and only if $A$ is isomorphic to $K_{1,2}$. Let $K_{1,2}^+$ be a subgraph obtained from $K_{1,2}$ by adding a new vertex $u$ which is adjacent to at least one of the two vertices $x_1,x_2$ in the partite set of cardinality two. Then $K_{1,2}^+$ is the $P_4$ if the new vertex $u$ is adjacent to only one vertex of $x_1,x_2$, and $K_{1,2}^+$ is the $C_4$ if $u$ is adjacent to both $x_1$ and $x_2$. We can count  the number of $K_{1,2}^+$ (counted with multiplicity) in two ways. As $G$ is $k$-regular, for every subgraph $K_{1,2}$, $x_1$ and $x_2$ have $2k-2$ neighbor vertices (counted with multiplicity) other than the vertex in the partite set of cardinality one. On the other hand, every $P_4$ is counted twice and
every $C_4$ is counted $8$ times in the counting process. Then the following relation holds:
\begin{equation}\label{equation:x3y}
(2k-2)\left [x^3y \right ]Q\left (G;x,y\right )=2p+8c.
\end{equation}
 Equations (\ref{equation:x4y}) and (\ref{equation:x3y}) imply that  $p$ and $c$ can be obtained from the coefficients of $Q(G;x,y)$.
\end{proof}


\section{Graphs determined by their subgraph component polynomial}

The Tutte polynomial is a well-studied graph polynomial. In \cite{Mier04}, Mier and Noy found that wheels, squares of cycles, ladders, M\"{o}bius Ladders, complete multipartite graphs, and hypercubes are determined by their Tutte polynomials. In \cite{Tittmann11}, it was shown that the star, complete graphs, and the class of empty graphs $E_n$  are $Q$-unique.  To find more classes of graphs   which  are determined by $Q(G;x,y)$  is an open problem posed in \cite{Tittmann11}. In this section we will show that paths, cycles, tadpole graphs, complete bipartite graphs, friendship graphs, book graphs and hypercubes are  $Q$-unique.

\subsection{Paths, cycles, tadpole graphs and complete bipartite graphs}

The cycle $C_n$ is a 2-connected unicycle with $n$ vertices.
\begin{proposition}\label{theorem:cycle}
The cycle $C_n$ is $Q$-unique.
\end{proposition}
\begin{proof}
Let $H$ be $Q$-equivalent to the cycle $C_n$. Then, by Proposition~\ref{prop:number} and Theorem~\ref{theorem:connectivity}, $H$ is a 2-connected graph, and $|V(H)|=|E(H)|=n$. Thus, it follows that $H\cong C_n$.
\end{proof}


\begin{theorem} \label{theorem:path}
The path $P_n$ is $Q$-unique.
\end{theorem}
\begin{proof}
Let $H$ be $Q$-equivalent to the path $P_n$. By Proposition~\ref{prop:number}, $H$ is a tree of order $n$. Since removing a vertex in a path could increase the number of connected components by at most 1, $deg_y[x^{n-1}]Q(H;x,y)=deg_y[x^{n-1}]Q(P_n;x,y)\leqslant 2$.

\bigskip
\noindent
{\bf Claim.} There are at most two leaves in $H$.

\begin{proof}
Suppose that $H$ has at least three leaves, say $x,y,z$. As $H$ is a tree, there is a unique path $P_y$ from $x$ to $y$, and we denote the unique path from $x$ to $z$ by $P_z$. Let $meet_{yz}$ be the last vertex in the intersection of $P_y$ and $P_z$. That is, the path from $meet_{yz}$ to $y$ and the path from $meet_{yz}$ to $z$ are disjoint except at $meet_{yz}$. Let $X=V(H)\backslash meet_{yz}$, then $|X|=n-1$ and $k(G[X])\geqslant 3$ which leads to $deg_y[x^{n-1}]Q(H;x,y)\geqslant 3$, a contradiction.
\end{proof}

As a tree has at least two leaves, then $H$ has exactly two leaves. Therefore, $H$ is the path $P_n$.
\end{proof}

The $(m,n)$-tadpole graph $T_{m,n}$ is the graph obtained by joining a path $P_m$ to  a cycle $C_n$ with a bridge.
\begin{theorem}
The tadpole graph $T_{m,n}$ is $Q$-unique.
\end{theorem}
\begin{proof}
Let $H$ be $Q$-equivalent to $T_{m,n}$. Then, by Proposition~\ref{prop:number} and Theorem~\ref{theorem:connectivity}, $H$ is a 1-connected graph, and $|V(H)|=|E(H)|=m+n$. It follows that $H$ is unicyclic. Similar to the proof of the Claim in Theorem~\ref{theorem:path}, we can prove that $H$ has  at most one pendant vertex. Since $H$ is connected but not 2-connected, then $H$ can be constructed by joining one path to a cycle by a bridge. In addition, the order of the path is counted by $[x^{m+n-1}y^2]Q(H;x,y)$. This proves the theorem.
\end{proof}




%A complete bipartite graph $K_{m,n}$ is a bipartite graph $(X,Y,E)$ such that for every two vertices $x \in X$ and $y \in Y$, $\{x,y\}$ is an edge in $K_{m,n}$.

\begin{theorem}
The complete bipartite graph $K_{m,n}$ is $Q$-unique.
\end{theorem}
\begin{proof}
Let $H$ be a graph with the same subgraph component polynomial as $K_{m,n}$, for some $m\geqslant n$. Then, by Proposition~\ref{prop:number} and Theorem~\ref{theorem:connectivity}, $H$ is a $n$-connected graph, $|H|=m+n$, $|E(H)|=mn$, and $\alpha(H)=m$. For every vertex subset $A$ of cardinality $m+1$, $K_{m,n}[A]$ is connected and so $deg_y[x^{m+1}]Q(H;x,y)=deg_y[x^{m+1}]Q(K_{m,n};x,y)=1$. Let $X=\{x_1,x_2,\dots,x_m\}$ be a maximum independent set of $H$, and $Y=V(H)\backslash X=\{y_1,y_2,\dots,y_n\}$. We claim that every vertex in $X$ is adjacent to every vertex in $Y$. If not, we can assume that there are two vertices $x_i \in X$, $y_j \in Y$ such that $\{x_i,y_j\} \notin E(H)$. Let $Z=X\cup \{y_j\}$. Then $|Z|=m+1$ and $k(H[Z]) \geqslant 2$ which leads to $deg_y[x^{m+1}]Q(H;x,y) \geqslant 2$, a contradiction. Therefore, $|E(K_{m,n})|=mn=|E(H)|$. Hence $Y$ is an independent set of $H$, so $H\cong K_{m,n}$.
\end{proof}

\subsection{Friendship graphs and  book graphs}
The \emph{friendship graph} $C_3^n$ can be constructed by joining $n$ copies of the cycle $C_3$ with a common vertex $u$, see Fig.~\ref{friendship}. Wang et al. \cite{Wang10} found that the friendship graph $C_3^n$ can be determined by the signless Laplacian spectrum.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%% Figure
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{figure}[h]
\begin{center}
\includegraphics[width=0.3\linewidth]{friendship.eps}
\caption{The friendship graph $C_3^8$.}
\label{friendship}
\end{center}
\end{figure}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%% Figure
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{theorem}\label{theorem:friend}
The friendship graph $C_3^n$ is $Q$-unique.
\end{theorem}
\begin{proof}
Let $H$ be $Q$-equivalent to $C_3^n$. Then, by Theorem~\ref{theorem:connectivity}, $H$ is a 1-connected graph, $|V(H)|=2n+1$, $|E(H)|=3n$, and $\alpha(H)=n$.
  Since $[x^{2n}y^n]Q(H;x,y)=[x^{2n}y^n]Q(C_3^n;x,y)=1$, then there is a subgraph of $H$ with $2n$ vertices and $n$ components. We denote these components by $H_1,H_2,\cdots,H_n$. As $H$ is connected, there must be a vertex $u$ in $H$ such that $u$ is connected to each of  the above $n$ components.

\bigskip\noindent
 {\bf Claim.} Each component $H_i$ has exactly two vertices.

  \begin{proof}
We first claim that $|H_i|\geqslant 2$ for each $i$. If there exists $j$ such that $|H_j|=1$, let $H_j=\{x\}$. Then $V(H)\backslash \{u,x\}$ induces a subgraph in $H$ with $2n-1$ vertices and $n-1$ components; but such a subgraph does not exist in $C_3^n$. Since the total number of vertices in $H$ is $2n+1$, we have $|H_i|=2$ for each $i$.
 \end{proof}

 For each $i$, let $V(H_i)=\{x_i,y_i\}$.   We first prove that neither $x_i$ nor $y_i$ is a pendant vertex. We suppose $x_i$ is a pendant vertex in $H$, then $y_i$ is the unique neighbor vertex of $x_i$ since $x_i,y_i$ constitute a component. Then $V(H)\backslash \{y_i\}$ induces a subgraph in $H$ that has $2n$ vertices and $2$ components; but such a subgraph does not exist in $C_3^n$. Therefore $\{x_i,y_i,u\}$ induces a cycle $C_3$ in $H$ and we complete the proof.
\end{proof}

The \emph{$n$-book graph} $B_n$ can be constructed by joining $n$ copies of the cycle graph $C_4$ with a common edge $\{u,v\}$, see Fig.~\ref{book}.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%% Figure
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{figure}[h]
\begin{center}
\includegraphics[width=0.5\linewidth]{book.eps}
\caption{\label{book}The book graphs $B_3$ and $B_4$.}
\end{center}
\end{figure}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%% Figure
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{theorem}
The book graph $B_n$ is $Q$-unique.
\end{theorem}
\begin{proof}
Let $H$ be a graph $Q$-equivalent to $B_n$. Then $H$ is a 2-connected graph with $2n+2$ vertices, $3n+1$ edges, and $\alpha(H)=n+1$. According to the special structure of $B_n$, the following two equations hold:

\begin{equation}\label{equation:book1}
[x^{2n}y^n]Q(H;x,y)=[x^{2n}y^n]Q(B_n;x,y)=1,
\end{equation}
\begin{equation}\label{equation:book2}
[x^{n+1}y^{n+1}]Q(H;x,y)=[x^{n+1}y^{n+1}]Q(B_n;x,y)=2.
\end{equation}
It follows from Equation~(\ref{equation:book1}) that there are two vertices $u$ and $v$ in $V(H)$ such that $V(H)\setminus \{u,v\}$ induces a subgraph of $H$ with $2n$ vertices and $n$ components. We denote these components by $H_1,\cdots,H_n$. Similar to the proof of the Claim in Theorem~\ref{theorem:friend} we can show $H_i$ has exactly two vertices $x_i,y_i$, for each $i$. $H$ is a $2$-connected graph implies that for each $i$, there is one vertex in $H_i$ adjacent to $u$ and another vertex in $H_i$ adjacent to $v$. Without loss of generality we let $x_i$ adjacent to $u$ and $y_i$ adjacent to $v$. We suppose there is a vertex $y_k$ in the component $H_k$ such that $\{u,y_k\} \in H$. Since $H$ has exactly $3n+1$ edges, then $\{u,v\} \notin H$ and $\{v,x_i\} \notin H$ for each $i$. Therefore, $[x^{n+1}y^{n+1}]Q(H;x,y)=1$ which is a contradiction with Equation~(\ref{equation:book2}). Hence, $\{u,y_i\} \notin H_i$ for each $i$. Analogously, $\{v,x_i\} \notin H_i$ for each $i$. So $ \{x_i,y_i,u,v\}$ constitute a cycle $C_4$ for each $i$ and we have finished the proof.
\end{proof}
\subsection{Hypercubes}
The \emph{n-cube} $Q^n$ is  the product graph of $n$ copies of $K_2$. $n$-cubes have been extensively studied  in computer science \cite{Chen,Gregor,Harary}, and the following two lemmas for the case of vertex fault were shown in \cite{Esfahanian89,Yang04}.
\begin{lemma}\label{lemma:cube1}\cite{Esfahanian89,Yang04}
Let $F$ be a set of at most $2n-3$ vertices in $Q^n$. If $N(u) \varsubsetneq F$ for each vertex $u$ in $Q^n$, then $Q^n-F$ is connected.
\end{lemma}

\begin{lemma}\label{lemma:cube2}\cite{Yang04}
Let $u$ be a vertex in $Q^n$. Then $c(Q^n-N[u])=n-2$.
\end{lemma}
Lemmas~\ref{lemma:cube1} and \ref{lemma:cube2} imply that in order to get a subgraph of $Q^n$ with more than two components, at least $2n-2$ vertices should be deleted.
\begin{lemma}\label{lemma:cube3}
Let $F$ be a set of at most $2n-3$ vertices in $Q^n$. Then $k(Q^n-F) \leqslant 2$.
\end{lemma}

From the proof of Theorem 6.2 in \cite{Mier04}, we can conclude the following characterization of the $n$-cube.

\begin{lemma}\label{lemma:cube}
A connected $n$-regular graph is isomorphic to the $n$-cube if and only if it has $2^n$ vertices, $2^{n-2}{n \choose 2}$ subgraphs isomorphic to $C_4$ and no subgraph isomorphic to $K_{2,3}$.
\end{lemma}


We are now in a position to prove  the  hypercube $Q^n$ is $Q$-unique.



\begin{theorem}\label{theorem:cube}
The $n$-cube $Q^n$ is $Q$-unique for every $n\geqslant 2$.
\end{theorem}
\begin{proof}
Let $H$ be $Q$-equivalent to the $n$-cube $Q^n$. Then $H$ is $n$-connected, $n$-regular, has $2^n$ vertices and $n2^{n-1}$ edges, $\alpha(H)=2^{n-1}$.

\bigskip
\noindent
 {\bf Claim 1.} For every $s\geqslant 1$, $deg_y[x^{2^n-s}]Q(H;x,y)\leqslant s$.


\begin{proof}
If graph $G$ is Hamiltonian, then $k(G-A)\leqslant |A|$ for every subset $A \subseteq V(G)$.  As well and long known, $Q^n$ is  Hamiltonian. Therefore,
for every vertex subset $A \subseteq V(Q^n)$ of cardinality $s$, $k(Q^n[V\backslash A])\leqslant s $. Then $deg_y[x^{2^n-s}]Q(H;x,y)=deg_y[x^{2^n-s}]Q(Q^{n};x,y) \leqslant s$.
\end{proof}

It is evident that $[x^{2^{n-1}}y^{2^{n-1}}]Q(H;x,y)=[x^{2^{n-1}}y^{2^{n-1}}]Q(Q^n);x,y)=2$. Let $X,Y$ be two separating sets of $H$ and  $|X|=|Y|=2^{n-1}$.

\bigskip
\noindent
{\bf Claim 2.} $X$ and $Y$ are disjoint.

\begin{proof}
If not, let us suppose $Z=X\cap Y$ and $|Z|=s\geqslant 1$. Let $X=\{x_1,\dots,x_{2^{n-1}-s},z_1,\dots,z_s\}$, $Y=\{y_1,\dots,y_{2^{n-1}-s},z_1,\dots,z_s\}$, $Z=\{z_1,\dots,z_s\}$ and $U=X\cup Y$. Then $|U|=2^n-s$ and $k(H[U])\geqslant s+1$, which leads to $deg_y[x^{2^n-s}]Q(H;x,y)\geqslant s+1$, a contradiction to Claim 1.
\end{proof}

Claim 2 implies that $H$ is a regular bipartite graph. Consequently, $H$ has $2^{n-2}{n \choose 2}$ subgraphs isomorphic to $C_4$. In view of Lemma \ref{lemma:cube}, we just need to prove that  $H$ has no subgraph isomorphic to $K_{2,3}$. Let $H=(V_1,V_2,E)$ with $|V_1|=|V_2|=2^{n-1}$  and $V_1\cap V_2=\emptyset$. For every pair of vertices $a$ and $b$ at distance $2$ in $H$, $a$ and $b$ belong to the same partite set. Let $n(a,b)$ be the number of common neighbor vertices they have.

\bigskip
\noindent
{\bf Claim 3.} $n(a,b)\leqslant 2$.

\begin{proof}
We suppose on the contrary there is a pair of vertices $a$ and $b$ at distance $2$ in, say $V_1$ such that $n(a,b)\geqslant 3$. Let $c_1,c_2,c_3$ be three vertices which are adjacent to both $a$ and  $b$. Then  $c_1,c_2,c_3\in V_2$. Since  $H$ is $n$-regular, we can let
\begin{eqnarray*}
N(a)&=&\{c_1,c_2,c_3,a_1,a_2,\dots,a_{n-3}\},\\
N(b)&=&\{c_1,c_2,c_3,b_1,b_2,\dots,b_{n-3}\},
\end{eqnarray*}
where $a_i$ and $b_i$ are neighbor vertices of $a$ and $b$, respectively. Let $N(a,b)=N(a)\cup N(b)$. Then $|N(a,b)| \leqslant 2n-3$ and $k(H[V\backslash N(a,b)])\geqslant 3$, which is  a contradiction with Lemma~\ref{lemma:cube3}.
\end{proof}

It follows from Claim 3 that $H$ has no subgraph isomorphism to $K_{2,3}$.
\end{proof}


\section{Distinguishing power}

The Tutte polynomial does not distinguish 1-connected graphs and the subgraph component polynomial does not distinguish  graphs which differ only by the multiplicity of their edges. In this section we shall give a family of 2-connected simple graphs with the same Tutte polynomials but different subgraph component polynomials. Moreover, we find two  $Q$-equivalent simple graphs which can be distinguished by the characteristic polynomial $p(G;x)$, the matching polynomial $m(G;x)$ and the Tutte polynomial $T(G;x,y)$. This gives an answer of a problem (Problem 1 in introduction) of Tittmann et al.

The join $G\vee H$ of two graphs $G=(V,E)$ and $H=(W,F)$ with $V \cap W=\emptyset$ is the graph obtained from $G\cup H$ by introducing edges from each vertex of $G$ to each vertex of $H$ \cite{Harary69}.

The graph $K_1\vee P_n$ is called  the \emph{fan graph} $F_n$. In the fan $F_n$, the vertices corresponding to the path $P_n$ are
labeled from $v_1$ to $v_n$, and the central vertex corresponding to $K_1$ is labeled as $v_0$. $F_{n-1}^+$ arises from $F_{n-1}$ by adding a new vertex $v_n$ and two new edges $\{v_{n-2},v_n\},\{v_{n-1},v_n\}$, see Fig.~\ref{fig.2}.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%% Figure  2
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{figure}[ht]
\begin{center}
\includegraphics[width=0.6\linewidth]{fan.eps}
\caption{The graphs $F_n$, $F_{n-1}^+$.}
\label{fig.2}
\end{center}
\end{figure}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{proposition}
For $n\geqslant 5$, $T(F_n;x,y)=T(F_{n-1}^+;x,y)$ but $Q(F_n;x,y)\neq Q(F_{n-1}^+;x,y)$.
\end{proposition}

\begin{proof}
Observe that $F_n$ and $F_{n-1}^+$ have the same dual graphs. Since $T(G;x,y)=T(G^*;y,x)$ for a planar graph $G$ and its dual graph $G^*$ \cite{Ellis11}, we have $T(F_n;x,y)=T(F_{n-1}^+;x,y)$. We can check that $F_n-\{v_n\}=F_{n-1}^+-\{v_n\}=F_{n-1}$, $F_n/v_n=F_{n-1}^+/v_n=F_{n-1}$, $F_n-N[v_n]=P_{n-2}$ and $F_{n-1}-N[v_n]=F_{n-3}$. Since paths are $Q$-unique, then $Q(P_{n-2};x,y)\neq Q(F_{n-3};x,y)$. Proposition~\ref{proposition:elimination} implies that $Q(F_n;x,y)\neq Q(F_{n-1};x,y)$.
\end{proof}




%Tittmann et al. have found that the two trees shown in Fig.~\ref{tree} have the same subgraph component polynomial.  Let $Tr_1^+$ and $Tr_2^+$ denote $Tr_1\vee K_1$ and $Tr_2\vee K_1$, respectively. By Proposition~\ref{proposition:elimination}, we know $Q(Tr_1^+;x,y)=Q(Tr_2^+;x,y)$.

%Using the graph package for Maple we can easily compute the characteristic polynomial $p(G;x)$ and the Tutte polynomial $T(G;x,y)$.




%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{figure}[h]
\begin{center}
\includegraphics[width=0.5\linewidth]{4.eps}
\caption{The graphs $G_1$, $G_2$.}
\label{power}
\end{center}
\end{figure}
 
\begin{proposition} For the graphs $G_1$ and $G_2$ illustrated in Fig.~\ref{power}, we have
 \label{proposition:power}

 (1)  $Q(G_1;x,y)=Q(G_{2};x,y)$.

 (2)  $p(G_1;x)\neq p(G_{2};x)$.

 (3)  $m(G_1;x)\neq m(G_{2};x)$.

 (4)  $T(G_1;x,y)\neq T(G_{2};x,y)$.


 \end{proposition}
 \begin{proof}
 We eliminate vertices $u$ and $v$ in graphs $G_1$ and $G_2$, respectively. It is not difficult to see that $G_1-u=G_2-v=F_4$, $G_1-N[u]=G_2-N[v]=P_3$ and $G_1/u=G_2/v=F_4$. Then $Q(G_1;x,y)=Q(G_{2};x,y)$. Using the graph package for Maple  we can  obtain the characteristic polynomials, the matching polynomials, and the Tutte polynomials of $G_1$ and $G_2$ as following:
\begin{eqnarray*}
p(G_1;x)&=&x^6-9x^4-8x^3+9x^2+8x-1,\\
p(G_2;x)&=&x^6-9x^4-8x^3+9x^2+6x-4,\\
 m(G_1;x)&=&x^6-9x^4+15x^2-2,\\
m(G_2;x)&=&x^6-9x^4+15x^2-3,
\end{eqnarray*}
\begin{eqnarray*}
 T(G_1;x,y)&=&x^5+4x^4+4x^3y+3x^2y^2+2xy^3+y^4+6x^3\\
             &&{}+9x^2y+7xy^2+3y^3+4x^2+6xy+3y^2+x+y,\\
T(G_2;x,y)&=&x^5+4x^4+4x^3y+3x^2y^2+3xy^3+y^4+6x^3\\
          &&{}+9x^2y+6xy^2+2y^3+4x^2+6xy+3y^2+x+y.
\end{eqnarray*}
\end{proof}






\subsection*{Acknowledgements}
This project was supported by the National Natural Science Foundation of China (No. 1171102) and the Hunan Provincial Innovation Foundation For Postgraduate (No. CX2013B214). The authors are deeply grateful to the referee for her/his fruitful comments and suggestions.



\begin{thebibliography}{99}
\bibitem{Akbari10}
S. Akbari, S. Alikhani, Y. H. Peng,
Charaterization of graphs using domination polynomials,
\emph{European Journal of Combinatorics} 31 (2010) 1714--1724.

\bibitem{Andren}
D. Andren, K. Markstrom,
The bivariate Ising polynomial of a graph,
\emph{Discrete Applied Mathematics} 157 (2009) 2515--2524.

\bibitem{Averbouch10}
I. Averbouch, B. Godlin, J. A. Makowsky,
An extension of the bivariate chromatic polynomial,
\emph{European Journal of Combinatorics} 31(1) (2010) 1--17.

\bibitem{Bernardi08}
O. Bernardi,
Tutte polynomial, subgraphs, orientations and sandpile model: new connections via embeddings,
\emph{The Electronic Journal of Combinatorics} 15 (2008) \#R109.

\bibitem{Chen}
X. B. Chen,
Many-to-many disjoint paths in faulty hypercubes,
\emph{Information Sciences} 179 (2009) 3110--3115.




\bibitem{Diestel00}
R. Diestel,
Graph Theory, in: Graduate Texts in Mathematics, Springer, NewYork, 2000.

\bibitem{Dong12}
F. M. Dong,
A new expression for matching polynomial,
\emph{Discrete Mathematics} 312 (2012) 803--807.

\bibitem{Ellis11}
J. A. Ellis-Monaghan, C. Merino,
Graph polynomials and their apllications I: the Tutte polynomial,
in: Matthias Dehmer (Ed.), Structural Analysis of Complex Networks, Birkh\"{a}user, Springer, New York, 2011, pp.219--256.

\bibitem{Esfahanian89}
A. H. Esfahanian,
Generalized measures of fault tolerance with application to $n-$cube networks,
\emph{IEEE Transactions on Computers} 38(11) (1989) 1586--1591.

\bibitem{Farrell79}
E. J. Farrell,
An introduction to matching polynomials,
\emph{Journal of Combinatorial Theory, Series A} 27 (1979) 75--86.

\bibitem{Garijo11}
D. Garijo, A. Goodall, J. Ne\v set\v ril,
Distinguishing graphs by left and right homomorphism profiles,
\emph{European Journal of Combinatorics}  32 (2011) 1025--1053.

\bibitem{Garijo13}
D. Garijo, A. Goodall, J. Ne\v set\v ril,
Polynomial graph invariants from homomorphism numbers,
in J. Ne\v set\v ril and M. Pellegrini (Eds.), The Seventh European Conference
on Combinatorics, Graph Theory and Applications, Edizioni della Normale, Pisa,
2013, pp. 611--612.




\bibitem{Gregor}
P. Gregor, T. Dvorak,
Path partitions of hypercubes,
\emph{Inf. Process. Lett.} 108 (2008) 402--406.

\bibitem{Harary69}
F. Harary,
Graph Theory,
\emph{Addison-Wesley, Reading, MA}, 1969.


\bibitem{Harary}
F. Harary,
A survey of the theory of hypercube graphs,
\emph{Comput. Math. Applic.} 15 (1988) 277--289.




\bibitem{Kotek12}
T. Kotek, J. Preen, F. Simon, P. Tittmann, M. Trinks,
Recurrence relations and splitting formulas for the domination polynomial,
\emph{The Electronic Journal of Combinatorics} 19(3) (2012) \#P47.

\bibitem{Mier04}
A. de Mier, M. Noy,
On graphs determined by their Tutte polynomial,
\emph{Graphs and Combinatorics} 20  (2004)  105--119.

\bibitem{Noy}
M. Noy,
Graphs determined by polynomial invariants,
\emph{Theoretical Computer Science} 307 (2003) 365--384.


\bibitem{Read}
R. C. Read,
An introduction to chromatic polynomials,
\emph{J. Combin. Theory Ser. B} 4 (1968) 52--71.

\bibitem{Tittmann11}
P. Tittmann, I. Averbouch, J. A. Makowsky,
The enumeration of vertex induced subgraphs with respect to the number of components,
\emph{European Journal of Combinatorics} 32 (2011) 954--974.

\bibitem{Trinks12}
M. Trinks,
The covered components polynomial: A new representation of
the edge elimination polynomial,
\emph{The Electronic Journal of Combinatorics} 19(1) (2012) \#P50.

\bibitem{Tutte54}
W. T. Tutte,
A contribution to the theory of chromatic polynomials,
\emph{Canadian Journal of Mathematics} 6 (1954) 80--91.

%\bibitem{Dohmen03}
%K. Dohmen, A. P\"{O}NITZ, P. Tittmann,
%A new two-variable generalization of the chromatic polynomial,
%Discrete Mathematics and Theoretical Computer Science 6 (2003) 69-90.

\bibitem{Wang10}
J. F. Wang, F. Belardo, Q. X. Huang, B. Borovi\'{c}anin,
On the two largest Q-eigenvalues of graphs,
\emph{Discrete Mathematics} 310 (2010) 2858--2866.




\bibitem{Yang04}
X. F. Yang, D. J. Evans, B. Chen, G. M. Megson, H. Lai,
On the maximal connectecd component of hypercube with faulty vertices,
\emph{International Journal of Computer Mathematics} 81(5) (2004) 515--525.


\bibitem{Yan09}
W. G. Yan, Y. N. Yeh,
On the matching polynomial of subdivision graphs,
\emph{Discrete Apllied Mathematics} 157 (2009) 195--200.







%\bibitem{Averbouch10}
%I. Averbouch, B. Godlin, J.A. Makowsky,
%An extension of the bivariate chromatic polynomial,
%European Journal of Combinatorics 31 (2010) 1-17.


%\bibitem{Mulder98}
%
%A. S. Astratian, T. M. J. Denley, R. H$\ddot{a}$ggkvist,
%Bipartite graphs and their applications,
%Cambridge: Cambridge Univ. Press 1998.
\end{thebibliography}
\end{document}




\end{document}
