# On the permanental nullity and matching number of graphs††thanks: This work
is supported by NSFC (11371180) and a project of QHMU(2015XZJ12).

Tingzeng Wua, Hong-Jian Laib
aSchool of Mathematics and Statistics, Qinghai Nationalities University,
Xining, Qinghai 810007, P.R. China
bDepartment of Mathematics, West Virginia University,
Morgantown, WV, USA _E-mail address_<EMAIL_ADDRESS><EMAIL_ADDRESS>
Abstract: For a graph $G$ with $n$ vertices, let $\nu(G)$ and $A(G)$ denote
the matching number and adjacency matrix of $G$, respectively. The permanental
polynomial of $G$ is defined as $\pi(G,x)={\rm per}(Ix-A(G))$. The permanental
nullity of $G$, denoted by $\eta_{per}(G)$, is the multiplicity of the zero
root of $\pi(G,x)$. In this paper, we use the Gallai-Edmonds structure theorem
to derive a concise formula which reveals the relationship between the
permanental nullity and the matching number of a graph. Furthermore, we prove
a necessary and sufficient condition for a graph $G$ to have
$\eta_{per}(G)=0$. As applications, we show that every unicyclic graph $G$ on
$n$ vertices satisfies $n-2\nu(G)-1\leq\eta_{per}(G)\leq n-2\nu(G)$, that the
permanental nullity of the line graph of a graph is either zero or one, and
that the permanental nullity of a factor critical graph is always zero.
AMS classification: 05C31; 05C50; 15A15
Keywords: Permanental polynomial; Permanental nullity; Matching number

##  1 Introduction

Let $G=(V(G),E(G))$ be a simple graph with $n$ vertices and $m$ edges. The
neighborhood of vertex $v\in V(G)$ in a graph $G$, denoted by $N_{G}(v)$ (or
just $N(v)$, when $G$ is understood from the context), is the set of vertices
adjacent to $v$. For $T\subseteq V(G)$, we use $G[T]$ to denote the induced
subgraph of $G$ by $T$. The line graph $L(G)$ of $G$ is the graph whose vertex
set is $E(G)$, where two vertices of $L(G)$ are adjacent in $L(G)$ if and only
if the corresponding edges are adjacent in $G$.

A set $M$ of edges in $G$ is a matching if every vertex of $G$ is incident
with at most one edge in $M$. For two matchings $M$ and $N$, the symmetric
difference of $M$ and $N$ is defined to be $M\triangle N=(M\cup N)-(M\cap N)$.
A vertex $v$ said to be covered (or saturated) by $M$ if some edge of $M$ is
incident with $v$. A maximum matching is one which covers as many vertices as
possible. In particular, a maximum matching covering all vertices of $G$ is
called a perfect matching. A near-perfect matching in a graph $G$ is one
covering all but exactly one vertex of $G$. The size of a maximum matching in
$G$ is called the matching number of $G$ and is denoted by $\nu(G)$. A graph
$G$ is said to be factor-critical if $G-v$ has a perfect matching for every
$v\in V(G)$.

The permanent of an $n\times n$ matrix $A=(a_{ij})(i,j=1,2,\ldots,n)$ is
defined as

${\rm per}(A)=\sum_{\sigma}\prod_{i=1}^{n}a_{i\sigma(i)},$

where the sum is taken over all permutations $\sigma$ of $\\{1,2,\ldots,n\\}$.
Valiant [25] showed that computing the permanent of a matrix is #P-complete
even when restricted to (0, 1)-matrices.

For an $n$ by $n$ matrix $A$, define ${\rm per}(xI-A)$ to be the permanental
polynomial of $A$. If $G$ is a graph and $A(G)$ is the adjacency matrix of
$G$, then permanental polynomial of $G$ is defined to be $\pi(G,x)={\rm
per}(xI-A(G))$. That is, the permanental polynomial of $A(G)$. The permanental
spectrum of $G$, denoted by $ps(G)$, is the collection of all roots (together
with their multiplicities) of $\pi(G,x)$. The multiplicity of the zero root of
$\pi(G,x)$, denoted by $\eta_{per}(G)$, is called the permanental nullity
(per-nullity for short) of $G$.

It seems that the permanental polynomials of graphs were first considered by
Turner [24]. Subsequently, Merris et al. [20] and Kasum et al. [15]
systematically introduced permanental polynomial and its potential
applications in mathematical and chemical studies, respectively. Since then,
very few research papers on the permanental polynomial were published for a
period of time (see [5]). This may be due to the difficulty of computing the
permanent ${\rm per}(xI-A(G))$. However, permanental polynomials and their
applications have received a lot of attention from researchers in recent
years, as shown in [1, 3, 6, 9, 11, 12, 13, 14, 22, 26, 28] and the references
therein.

The spectrum of a graph (i.e., the roots of the characteristic polynomial of a
graph with their multiplicities. See [10]) encodes useful combinatorial
information of the graph. The relationship between the structural properties
of a graph and its spectrum has been studied extensively over the years.
Nevertheless, only a few results on the permanental spectrum have been
published. Brenner and Brualdi [4] proved the following: If $A$ is an $n$ by
$n$ matrix with nonnegative entries and spectral radius $\rho$, then every
root of the permanental polynomial of $A$ must be in $\\{z:|z|\leq\rho\\}$.
Merris [19] observed that if $A$ is hermitian with eigenvalues
$\lambda_{1}\geq\lambda_{2}\geq\ldots\geq\lambda_{n}$, then each real
permanental root of $A$ is in the interval $[\lambda_{n},\lambda_{1}]$.
Borowiecki [2] proved that $G$ has
$ps(G)=\\{i\lambda_{1},\ldots,i\lambda_{n}\\}$ if and only if $G$ is bipartite
without cycles of length $4k$ ($k=1,2,\ldots$), where $i$ is imaginary unit
and $\\{\lambda_{1},\ldots,\lambda_{n}\\}$ is the adjacency spectrum of $G$.
Zhang et al. [29] proved that every graph does not have a negative real
permanental root. In particular, they showed that a bipartite graph has no
real permanental roots except possibly zero. Additionally, several papers have
been published on graphs uniquely determined by their permanental spectra, see
[16, 17, 23, 30], among others.

In [21], Wu and Zhang introduced the per-nullity of a graph, and presented
some elementary properties of per-nullity. Furthermore, they characterized the
extremal graphs of order $n$ whose per-nullities are $n-2$, $n-3$, $n-4$ and
$n-5$, respectively. It is natural to consider the problem of computing the
per-nullity of graphs. In this paper, we investigate the problem of computing
the per-nullity of graphs, and find a relationship between per-nullity and
matching number of a graph. The rest of this paper is organized as follows. In
Section 2, we demonstrate some preliminaries on per-nullity of graphs. In
Section 3, using the Gallai-Edmonds structure theorem, we obtain a
relationship between the per-nullity and the matching number of a graph. In
Section 4, we determine all graphs with zero per-nullity. In the last section,
we apply our main results to several classes of graphs, including unicyclic
graphs, line graphs and factor critical graphs.

##  2 Preliminaries

A Sachs graph is a simple graph such that each component is regular and has
degree 1 or 2. In other words, the components are single edges and cycles.

######  Lemma 2.1.

(R. Merris et al. [20]) Let G be a graph with
$\pi(G,x)=\sum\limits_{k=0}^{n}b_{k}(G)x^{n-k}$. Then

$b_{k}(G)=(-1)^{k}\sum_{H}2^{c(H)},1\leq k\leq n,$

where the sum is taken over all Sachs subgraphs $H$ of $G$ on $k$ vertices,
and $c(H)$ is the number of cycles in $H$.

Let $S(G)$ be a maximum Sachs subgraph of $G$ (i.e., $S(G)$ has the maximum
number of vertices among all Sachs subgraph of $G$). By the definition of a
Sachs graph, $S(G)$ has three possible structures: a maximum matching, union
of disjoint cycles, or union of some disjoint single edges and cycles. In
[21], two elementary properties of per-nullity of graphs are introduced as
follows.

######  Lemma 2.2.

(T. Wu and H. Zhang [21]) Let $G$ be a simple graph with $n$ vertices.
(i) $\eta_{per}(G)=n$ if and only if $G$ is an empty graph.
(ii) If $G_{1},G_{2},...,G_{t}$ are the connected components of $G$, then
$\eta_{per}(G)=\sum_{i=1}^{t}\eta_{per}(G_{i})$.

######  Lemma 2.3.

(T. Wu and H. Zhang [21]) Let $G$ be a graph with $n$ vertices and $S(G)$ be a
maximum Sachs subgraph of $G$. Then $\eta_{per}(G)=n-|V(S(G))|$.

In the following we present the famous Gallai-Edmonds structure theorem on
matchings of graphs. Definition 2.4(i) comes from [18, 27]. The notation of
Definition 2.4 (i) and (ii) will be used throughout this paper.

######  Definition 2.4.

Let $G$ be a graph.
(i) Let $D(G)$ be the set of all vertices in $G$ which are not saturated by at
least one maximum matching of $G$. Define $B(G)=\\{v\in(V(G)-D(G))\;:$ there
exist a $u\in B(G)$ with $uv\in E(G)\\}$. Finally let $C(G)=V(G)-(D(G)\cup
B(G))$. This yields a vertex-partition of $V(G)$ into $B(G)$, $C(G)$ and
$D(G)$, which is well-defined for every graph and does not depend on the
choices of any maximum matching.
(ii) Let $D_{0}^{\prime}(G)$ be the set of all isolated vertices in $G[D(G)]$
and $\mbox{$\cal F$}(G)$ be the set of components in $G[D(G)]$ each of which
has order at least 3.

With this partition, the Gallai-Edmonds structure theorem is stated as
follows.

######  Theorem 2.5.

(Gallai-Edmonds Structure Theorem [18, 27]) Let $G$ be a graph and let $B(G)$,
$C(G)$ and $D(G)$ be the vertex-partition defined above. Each of the following
holds.
(i) The components of the subgraph induced by $D(G)$ are factor-critical.
(ii) The subgraph induced by $C(G)$ has a perfect matching.
(iii) Any maximum matching $M$ of $G$ contains a near-perfect matching of each
component of $G[D(G)]$ and a perfect matching of each component of $G[C(G)]$,
and $M$ matches all vertices of $B(G)$ with vertices in distinct components of
$G[D(G)]$.
(iv) The size of maximum matching is $\frac{1}{2}(|V(G)|-c(D(G))+|B(G)|)$,
where $c(D(G))$ denotes the number of components of the graph spanned by
$D(G)$.

By Theorem 2.5, we obtain the following lemma, which will be used later in our
arguments.

######  Lemma 2.6.

Let $G$ be a graph with $\mbox{$\cal F$}(G)\neq\emptyset$ and without a
perfect matching. If a maximum matching $M$ of $G$ covers as many isolated
vertices in $G[D(G)]$ as possible, then there must exist at least one
component of $G[D(G)]$ in $\mbox{$\cal F$}(G)$ not covered by $M$.

###### Proof.

Since $G$ does not have a perfect matching, it follows from Theorem 2.5(iv)
that $c(G[D(G)])>|B(G)|$. By Theorem 2.5(iii), $M$ contains a subset $M_{BD}$
which matches $B(G)$ with vertices in distinct components of $D(G)$. Let
$W\subseteq D(G)$ be the set of vertices covered by $M_{BD}$. Then $W$
consists of some isolate vertices in $G[D(G)]$ and some vertices of components
each of which has at least 3 vertices in $G[D(G)]$. If all vertices in $W$ are
taken isolate vertices in $G[D(G)]$, or if $G[D(G)]$ does not have any
isolated vertices, then the conclusion follows from the fact that
$c(G[D(G)])>|B(G)|$ and the assumption that $\mbox{$\cal F$}(G)\neq\emptyset$.
Let $D_{0}^{\prime\prime}(G)$ be a subset of $D_{0}^{\prime}(G)$. Define
$B^{\prime}(G)=\\{u\in B(G)~{}:$ for some $w\in D(G)$, $uw\in M_{BD}\\}$,
$B_{1}^{\prime}(G)=\\{v\in B^{\prime}(G)~{}:$ for some $w\in
D_{0}^{\prime\prime}(G)\subseteq D_{0}^{\prime}(G)$, $vw\in M_{BD}\\}$, and
$B_{2}^{\prime}(G)=B^{\prime}(G)-B_{1}^{\prime}(G)$. Since the choice of $M$
maximizes $|B_{1}^{\prime}(G)|$, for every vertex $v\in B_{2}^{\prime}(G)$,
$N_{G}(v)\cap(D_{0}^{\prime}(G)-D_{0}^{\prime\prime}(G))=\emptyset$. It
follows from the definition of $D(G)$ that there must be a vertex in
$B^{\prime}(G)$ adjacent to at least two components in $G[D(G)]$ that are in
$\mbox{$\cal F$}(G)$. The conclusion of the lemma now follows. ∎

######  Theorem 2.7.

(G. Chartrand et al. [8]) Let $G$ be a nontrivial connected graph. Then the
line graph $L(G)$ contains a perfect matching if and only if $|E(G)|\equiv 0$
(mod 2).

######  Corollary 2.8.

(G. Chartrand et al. [8]) The line graph $L(G)$ of a nontrivial graph $G$ has
a perfect matching if and only if every component of $L(G)$ has even order.

Let $G$ be a connected graph with at least 3 edges and $|E(G)|\equiv 1$ (mod
2). Then as $G$ has a spanning tree, $G$ has an edge $e$ such that $G-e$ is
either connected or has two components with one being an isolated vertex. If
$G$ is 2-edge-connected, then for any $e\in E(G)$, $G-e$ is connected and has
an even number of edges. With these observations, we have the following
consequence of Theorem 2.7.

######  Theorem 2.9.

Let $G$ be a connected graph with at least 3 edges and with $|E(G)|\equiv 1$
(mod 2). Each of the following holds.
(i) The line graph $L(G)$ contains a near-perfect matching.
(ii) If, in addition, $G$ is 2-edge-connected, then $L(G)$ is factor-critical.

##  3 A relationship between the per-nullity and the matching number of graphs

By Lemma 2.2 and by working componentwise, it suffices to discuss connected
graphs in this sections. We start with a lemma.

######  Lemma 3.1.

Let $G$ be a factor-critical graph with $n\geq 3$ vertices. Each of the
following holds.
(i) Every vertex $v\in V(G)$ lies in an odd cycle of $G$.
(ii) There exist an odd cycle $C$ and a maximum matching $M$ of $G$ such that
$G$ is covered by $E(C)\cup M$ and such that the maximum degree of
$G[E(C)\cup(M-E(G[V(C)]))]$ is 2. (Thus $G[E(C)\cup M]$ is a maximum Sachs
subgraph of $G$.)

###### Proof.

Since $G$ is a factor-critical graph, $|V(G)|$ is odd, and $G$ is connected
and not a bipartite graph. If $G$ is an odd cycle, then Lemma 3.1 is obvious.
Thus, suppose that $G$ is not a cycle below.

Let $uv$ be an edge of $G$. Since $G$ is factor-critical, $G-v$ has a perfect
matching $M_{v}$. Similarly, $G-u$ has a perfect matching $M_{u}$. It follows
that the symmetric difference $M_{u}\triangle M_{v}$ contains exactly one path
$P$ of even length joining $u$ and $v$. By the choices of $M_{u}$ and $M_{v}$,
the edge $uv$ is not in $P$, and so $C=P+uv$ is an odd containing $v$. Since
$M_{v}$ covers all vertices of $G-v$, $E(C)\cup(M_{v}-E(G[V(C)]))$ is a cover
of $G$. By the definition of $M_{v}$, no edge in $M_{v}-E(G[V(C)])$ is
incident with an edge in $C$, and so the maximum degree of
$G[E(C)\cup(M-E(G[V(C)]))]$ is 2. This completes the proof of the lemma. ∎

######  Lemma 3.2.

Let $G$ be a connected graph with $n$ vertices and with the size of a maximum
matching being $\nu(G)$. The following are equivalent.
(i) $\eta_{per}(G)=n-2\nu(G)$.
(ii) Either $G$ has a perfect matching or $E(G[D(G)])=\emptyset$.

###### Proof.

Assume (i) to prove (ii). By Lemma 2.3, the equality $\eta_{per}(G)=n-2\nu(G)$
implies that a maximum matching of $G$ is a maximum Sachs subgraph. By the
definition of $D(G)$, we observe that if $D(G)=\emptyset$, then $G$ has a
perfect matching, and so (ii) holds. Hence we assume that $D(G)\neq\emptyset$.
Suppose that there exists at least one components of $G[D(G)]$ having at least
3 vertices. By Lemma 2.6, there must be at least one component of $G[D(G)]$ in
$\mbox{$\cal F$}(G)$ not covered by $M$. Let $\mbox{$\cal F$}_{M}(G)$ denote
all such components. By Lemma 3.1, for each $L\in\mbox{$\cal F$}_{M}(G)$,
there exists an odd cycle $C_{L}$ and a subset $M_{L}\subset M\cap E(L)$, such
that $E(C_{L})\cup M_{L}$ covers $V(L)$ and such that the maximum degree of
$L[E(C_{L})\cup M_{L}]$ is at most 2. Thus, $H=G[\cup_{\small L\in\mbox{$\cal
F$}_{M}(G)}(E(C_{L})\cup M_{L})]$ is a Sachs graph $H$ such that $|V(H)|$ is
more than the number of vertices in $G$ covered by the maximum matching $M$.
This implies that any maximum matching of $G$ is not a maximum Sachs subgraph,
contrary to the fact that any maximum matching must also be a maximum Sachs
subgraph. Therefore, $\mbox{$\cal F$}(G)=\emptyset$ and so
$E(G[D(G)])=\emptyset$.

We now assume (ii) to prove (i). If $G$ has a perfect matching, then the
perfect matching is a maximum Sachs subgraph of $G$. By Lemma 2.3,
$\eta_{per}(G)=n-2\nu(G)$. Suppose that $G$ does not have a perfect matching
and $E(G[D(G)])=\emptyset$. Since every maximum matching of $G$ is a maximum
Sachs subgraph of $G$, it follows by Lemma 2.3 that $\eta_{per}(G)=n-2\nu(G)$.
∎

######  Definition 3.3.

For a maximum matching $M$ of $G$ such that

the number of isolated vertices in $G[D(G)]$ covered by $M$ is maximized, (1)

define $M(G)$ to be the number of components of order at least 3 in $G[D(G)]$
each of which has just a vertex not covered by $M$.

By Theorem 2.5(i), every graph in $\mbox{$\cal F$}(G)$ is factor-critical. By
Lemma 3.2, if $\mbox{$\cal F$}(G)\neq\emptyset$, then
$\eta_{per}(G)<n-2\nu(G)$. The next lemma describes the per-nullity of the
graphs with $\mbox{$\cal F$}(G)\neq\emptyset$.

######  Lemma 3.4.

Let $G$ be a connected graph with $n$ vertices and without a perfect matching,
If $\mbox{$\cal F$}(G)\neq\emptyset$, then

$\eta_{per}(G)=n-2\nu(G)-M(G).$

###### Proof.

Let $M$ be a maximum matching of $G$ satisfying (1). Since $G$ does not have a
perfect matching, by Theorem 2.5, $c(D(G))>|B(G)|$. Then there exists at least
one $H\in\mbox{$\cal F$}(G)$ such that $H$ has just a vertex not covered by
$M$. By Lemma 3.1 every $H\in\mbox{$\cal F$}(G)$ has an odd cycle $C_{H}$ such
that $E(E(C_{H}))\cup(M-E(G[V(C_{H})]))]$ is a cover of $H$. It follows that
$G$ has a maximum Sachs subgraph $S(G)$ consisting of disjoint odd cycles
$\\{C_{H}:H\in\mbox{$\cal F$}(G)\\}$, and a subset of $M$. It is routine to
verify that $|S(G)|=2\nu(G)+M(G)$, and so by Lemma 2.3, we have
$\eta_{per}(G)=n-2\nu(G)-M(G)$. ∎

By applying Lemmas 3.2 and 3.4, we obtain the main result of this section.
Recall that $D(G)$ and $M(G)$ are defined in Definitions 2.4 and 3.3, for a
given maximum matching $M$ of $G$.

######  Theorem 3.5.

Let $G$ be a connected graph with $n$ vertices, and let $M$ be a maximum
matching of $G$ satisfying (1). Then

$\eta_{per}(G)=\left\\{\begin{array}[]{ll}n-2\nu(G)&\mbox{ if $G$ has a
perfect matching or $\mbox{$\cal F$}(G)=\emptyset$,}\\\ n-2\nu(G)-M(G)&\mbox{
otherwise. }\end{array}\right.$

##  4 The graphs with zero per-nullity

For a simple graph $G$ on $n$ vertices, it is known that
$0\leq\eta_{per}(G)\leq n-2$. In this section, we will characterize the graphs
with zero per-nullity. Note that by Lemma 2.3,

$\eta_{per}(G)=0$ if and only if $G$ has a spanning Sachs subgraph.  (2)

######  Theorem 4.1.

Let $n\geq 2$ be an integer, $G$ be a connected graph on $n$ vertices. Then
$\eta_{per}(G)=0$ if and only if one of the following holds:
(i) $G$ has a perfect matching, or
(ii) $G[D(G)]$ has no isolated vertices, or
(iii) $G[D(G)]$ has isolated vertices and $G$ has a maximum matching covering
every isolated vertices of $G[D(G)]$.

###### Proof.

Assume first that $G$ satisfies one of (i), (ii) and (iii). We are to show
that $\eta_{per}(G)=0$.

If (i) holds, then by Theorem 3.5, $\eta_{per}(G)=0$. Hence we may assume that
$G$ has no perfect matchings, and so $|D(G)|>0$.

Suppose (ii) holds. Then $|\mbox{$\cal F$}(G)|=c(D(G))$. By Lemma 3.1, each
$H\in\mbox{$\cal F$}(G)$ has a Sachs subgraph $S(H)$ to cover $V(H)$. Let $M$
be a perfect matching of $G[C(G)]$. Then $S(G)=M\cup(\cup_{H\in\mbox{$\cal
F$}(G)}E(S(H)))$ is a spanning Sachs subgraph of $G$, and so by (2),
$\eta_{per}(G)=n-|V(S(G))|=0$.

Finally, we assume that $G$ has a maximum matching $M$ covering every isolated
vertices of $G[D(G)]$. By Lemma 3.1, a Sachs subgraph exists to cover every
graph in $\mbox{$\cal F$}(G)$. Edges in these Sachs subgraphs in the graphs of
$\mbox{$\cal F$}(G)$ together with a subset of $M$ induces a spanning Sachs
subgraph of $G$. By (2), $\eta_{per}(G)=n-|V(S(G))|=0$.

Conversely, we assume that $\eta_{per}(G)=0$ to show (i) or (ii) or (iii) must
occur. Choose a maximum matching $M$ satisfying (1). By Theorem 3.5, if
$M(G)=0$, then the assumption $\eta_{per}(G)=0$ leads to $|V(G)|=2\nu(G)$. In
this case, $G$ has a perfect matching, and so (i) follows. Hence we assume
that $M(G)>0$. By Lemma 3.4, $|V(G)|=2\nu(G)+M(G)$. This implies that either
all components of order 1 in $G[D(G)]$ is covered by $M$, whence (ii) holds;
or every component of $G[D(G)]$ is in $\mbox{$\cal F$}(G)$, whence (iii)
follows. This completes the proof of the theorem. ∎

##  5 Some applications

In this section, we determine the per-nullity of some classes of graphs as
applications of Theorems 3.5 and 4.1. An unicyclic graph is a connected graph
with equal number of vertices and edges. The theorem below determines the per-
nullity of unicyclic graphs.

######  Theorem 5.1.

Let $G$ be an unicyclic graph with $n$ vertices and the unique cycle in $G$ is
denoted by $C_{\ell}$. Then

$\eta_{per}(G)=\begin{cases}n-2\nu(G)-1&\text{if $\ell$ is odd and
$\nu(G)=\frac{\ell-1}{2}+\nu(G-C_{\ell})$,}\\\
n-2\nu(G)&\text{otherwise}.\end{cases}$

###### Proof.

Since $C_{\ell}$ is the only one cycle in $G$, it is routine to see that only
$C_{\ell}\in\mbox{$\cal F$}(G)$ is a factor-critical component. By Theorem
3.5, we have $n-2\nu(G)-1\leq\eta_{per}(G)\leq n-2\nu(G)$.

If $\eta_{per}(G)=n-2\nu(G)-1$, then by Theorem 3.5, there exists a maximum
matching $M$ of $G$ satisfying (1), and $|\mbox{$\cal F$}(G)|=1$. Since $G$ is
an unicyclic graph, the factor-critical component of $G$ must be $C_{\ell}$.
This implies that $C_{\ell}$ is odd. By $(iii)$ of Theorem 2.5, we have
$\nu(G)=\frac{\ell-1}{2}+\nu(G-C_{\ell})$.

Assume that $C_{\ell}$ is odd and $\nu(G)=\frac{\ell-1}{2}+\nu(G-C_{\ell})$.
Then $C_{\ell}$ is factor-critical, and there exists a maximum matching
covering all vertices of $C_{\ell}$ excepting a vertex. It follows from
Theorem 3.5 that $\eta_{per}(G)=n-2\nu(G)-1$.

By Theorem 3.5, it is routine to verify that in this case,
$\eta_{per}(G)=n-2\nu(G)$ if and only if $G$ has a perfect matching or if
$\mbox{$\cal F$}(G)=\emptyset$, The theorem now follows. ∎

######  Theorem 5.2.

Let $G$ be an unicyclic graph with a unique cycle $C$. Then $\eta_{per}(G)=0$
if and only if $G$ is an odd cycle, $G$ has a perfect matching, or $G-V(C)$
has a perfect matching.

###### Proof.

By (i) and (ii) of Theorem 4.1, it is routine to verify that if $G$ is an odd
cycle or $G$ has a perfect matching, then $\eta_{per}(G)=0$. Thus we assume
that $G$ is not an odd cycle and $G$ does not have a perfect matching, and
that $G-V(C)$ has a perfect matching $M_{C}$. Then $E(C)\cup M_{C}$ is a
spanning Schas subgraph of $G$, and so by (2), $\eta_{per}(G)=0$.

Conversely, assume that $\eta_{per}(G)=0$, and that $G$ is not an odd cycle
and $G$ does not have a perfect matching. We are to show that $G-V(C)$ has a
perfect matching. By contradiction, suppose that $G-V(C)$ does not have a
perfect matching. By Theorem 4.1, (ii) or (iii) of Theorem 4.1 must hold.
Since $G$ is an unicyclic graph, the cycle $C$ of $G$ must be the only factor-
critical component order at least 3 in $G[D(G)]$. Hence $|V(C)|$ is odd. If
Theorem 4.1 (ii) holds, then $G$ must be an odd cycle, contrary to the
assumption that $G$ is not an odd cycle. Hence Theorem 4.1 (iii) must hold. By
Theorem 2.5 (iii), $G-V(C)$ has a perfect matching. This completes the proof
of the theorem. ∎

By Theorems 2.7, 2.9 and 3.5, we obtain the following results.

######  Theorem 5.3.

Let $L(G)$ be the line graph of $G$. Then the per-nullity of $L(G)$ equals
zero or one.

######  Theorem 5.4.

Let $G$ be a factor-critical graph. Then $\eta_{per}(G)=0$.

## References

  * [1] F. Belardo, V. De Filippis, S.K. Simić, Computing the permanental polynomial of a matrix from a combinatorial viewpoint, MATCH Commun. Math. Comput. Chem. 66 (2011) 381–396.
  * [2] M. Borowiecki, On spectrum and per-spectrum of graphs, Publ. Inst. Math. 38 (1985) 31–33.
  * [3] M. Borowiecki, T. Jóźwiak, Computing the permanental polynomial of a multigraph, Discuss. Math. TV (1982) 9–16.
  * [4] J.L. Brenner, R.A. Brualdi, Eigenschaften der permanentefunktion, Arch. Math. 18 (1967) 585–586.
  * [5] G.G. Cash, The permanental polynomial, J. Chem. Inf. Comput. Sci. 40 (2000) 1203–1206.
  * [6] G.G. Cash, Permanental polynomials of smaller fullerenes, J. Chem. Inf. Comput. Sci. 40 (2000) 1207–1209.
  * [7] G.G. Cash, A differential-operator approach to the permanental polynomial, J. Chem. Inf. Comput. Sci. 42 (2002) 1131–1135.
  * [8] G. Chartrand, A.D. Polimeni, M.J. Stewart, The existance of 1-factors in line graphs, squares and total graphs, Indag. Math. 35 (1973) 228–232.
  * [9] R. Chen, A note on the relations between the permanental and characteristic polynomials of coronoid hydrocarbons, MATCH Commun. Math. Comput. Chem. 51 (2004) 137–148.
  * [10] D. Cvetković, M. Doob, H. Sachs, Spectra of Graphs, Academic Press, New York, 1980.
  * [11] J. Geelen, An algebraic approach to matching problems, RIMS Kokyuroku 1185 (2001) 63–71.
  * [12] I. Gutman, Permanents of adjacency matrices and their dependence on molecular structures, Polycyclic Aromatic Compounds 12 (1998) 281–287.
  * [13] I. Gutman, G.G. Cash, Relations between the permanental and characteristic polynomials of fullerenes and benzenoid hydrocarbons, MATCH Commun. Math. Comput. Chem. 45 (2002) 55–70.
  * [14] Y. Huo, H. Liang, F. Bai, An efficient algorithm for computing permanental polynomials of graphs, Comput. Phys. Comm. 175 (2006) 196–203.
  * [15] D. Kasum, N. Trinajstić, I. Gutman, Chemical graph theory. III. On permanental polynomial, Croat. Chem. Acta. 54 (1981) 321–328.
  * [16] S. Liu, H. Zhang, On the characterizing properties of the permanental polynomials of graphs, Linear Algebra Appl. 438 (2013) 157–172.
  * [17] S. Liu, H. Zhang, Characterizing properties of permanental polynomials of lollipop graphs, Linear Multilinear Algebra 62 (2014) 419–444.
  * [18] L. Lovász, M.D. Plummer, Matching Theory, American Mathematical Society, 2009.
  * [19] R. Merris, Two problems involving Schur functions, Linear Algebra and Appl. 10 (1975) 155–162.
  * [20] R. Merris, K.R. Rebman, W. Watkins, Permanental polynomials of graphs, Linear Algebra Appl. 38 (1981) 273–288.
  * [21] T. Wu, H. Zhang, Per-spectral characterizations of graphs with extremal per-nullity, Linear Algebra Appl. 484 (2015) 13–26.
  * [22] T. Wu, H. Zhang, Some analytical properties of the permanental polynomial of a graph, Ars Combin. 123 (2015) 261–267.
  * [23] T. Wu, H. Zhang, Per-spectral and adjacency spectral characterizations of a complete graph removing six edges, Discrete Appl. Math., 2015, doi:10.1016/j.dam.2015.09.014.
  * [24] J. Turner, Generalized matrix functions and the graph isomorphism problem, SIAM J. Appl. Math. 16 (1968) 520–526.
  * [25] L.G. Valiant, The complexity of computing the permanent, Theoret. Comput. Sci. 8 (1979) 189–201.
  * [26] W. Yan, F. Zhang, On the permanental polynomial of some graphs, J. Math. Chem. 35 (2004) 175–188.
  * [27] Q. Yu, G. Liu, Graph Factors and Matching Extensions, Springer, 2009.
  * [28] H. Zhang, W. Li, Computing the permanental polynomials of bipartite graphs by Pfaffian orientation, Discrete Appl. Math. 160 (2012) 2069–2074.
  * [29] H. Zhang, S. Liu, W. Li, A note on the permanental roots of bipartite graphs, Disscu. Math. Graph Theory 34 (2014) 49–56.
  * [30] H. Zhang, T. Wu, H. Lai, Per-spectral characterizations of some edge-deleted subgraphs of a complete graph, Linear Multilinear Algebra 63 (2015) 397–410.