# On a conjecture for the signless Laplacian spectral radius of cacti with
given matching number111L. You’s research is supported by the National Natural
Science Foundation of China (Grant No. 11571123) and the Guangdong Provincial
Natural Science Foundation (Grant No. 2015A030313377), S. Li’s research is
supported by the National Natural Science Foundation of China (Grant No.
11271149).

Yun Shena, 222Email address<EMAIL_ADDRESS> Lihua Youa,333Corresponding
author<EMAIL_ADDRESS>Minjie Zhangb,444Email address<EMAIL_ADDRESS>Shuchao Lib,555Email address<EMAIL_ADDRESS>
(a School of Mathematical Sciences, South China Normal University,
Guangzhou, 510631, P.R. China
b Faculty of Mathematics and Statistics, Central China Normal University,
Wuhan, 430079, P.R. China )

Abstract A connected graph $G$ is a cactus if any two of its cycles have at
most one common vertex. Let $\ell_{n}^{m}$ be the set of cacti on $n$ vertices
with matching number $m.$ S.C. Li and M.J. Zhang determined the unique graph
with the maximum signless Laplacian spectral radius among all cacti in
$\ell_{n}^{m}$ with $n=2m$. In this paper, we characterize the case $n\geq
2m+1$. This confirms the conjecture of Li and Zhang (S.C. Li, M.J. Zhang, On
the signless Laplacian index of cacti with a given number of pendant vetices,
Linear Algebra Appl. 436, 2012, 4400–4411). Further, we characterize the
unique graph with the maximum signless Laplacian spectral radius among all
cacti on $n$ vertices.

AMS Classification: 05C50, 15A18

Keywords Cactus; Signless Laplacian matrix; Spectral radius; Matching number.

##  1 Introduction

Spectral graph theory (for example, [11, 12, 16] et al) studies properties of
graphs using the spectrum of related matrices. In this paper, we consider only
simple graphs (i.e., finite,undirected graphs without loops or multiple
edges), and follow [2, 4, 11, 12, 16] for terminology and notations.

Let $G=(V,E)$ be a simple graph with vertex set
$V=V(G)=\\{v_{1},v_{2},\ldots,$ $v_{n}\\}$ and edge set $E=E(G)$. Let
$A(G)=(a_{ij})$ denote the adjacency matrix of $G$, where $a_{ij}=1$ if vertex
$v_{i}$ and vertex $v_{j}$ are adjacent in $G$ and $0$ otherwise. Let
$diag(G)=diag(d_{1},d_{2},\ldots,d_{n})$ be the diagonal matrix with degree of
the vertices of $G$ and $Q(G)=diag(G)+A(G)$ be the signless Laplacian matrix
of $G$. It is well known that $A(G)$ is a real symmetric matrix and $Q(G)$ is
a positive semidefinite matrix. The eigenvalues of $Q(G)$ can be ordered as

$q_{1}(G)\geq q_{2}(G)\geq\cdots\geq q_{n}(G)\geq 0,$

where $q_{1}(G)$ is the largest signless Laplacian eigenvalue of $G$ and it is
called the signless Laplacian spectral radius of $G$, denoted by $q(G)$. It is
easy to see that if $G$ is connected, then $A(G)$ and thus $Q(G)$ is a
nonnegative irreducible matrix. By the Perron-Frobenius theory, $q(G)$ has
multiplicity one and there exists a unique positive unit eigenvector, say
$\textbf{x}=(x_{1},x_{2},\ldots,x_{n})^{T},$ corresponding to $q(G),$ which is
called the Perron vector of $Q(G)$. It will be convenient to associate a
labelling of vertices of $G$ (with respect to x) in which $x_{v}$ is a label
of $v.$ The signless Laplacian characteristic polymomial of $G,$ is equal to
det$(xI_{n}-Q(G)),$ denoted by $\psi(G,x)$ ( or, for short, by $\psi(G)$).

In order to state our results, we introduce some notation and terminology. Let
$P_{n},S_{n}$ and $C_{n}$ be the path, star and cycle on $n$ vertices,
respectively. Let $G-v,$ $G-uv$ denote the graph obtained from $G$ by deleting
vertex $v\in V(G),$ or an edge $uv\in E(G),$ respectively (this notation is
naturally extended if more than one vertex or edge is deleted). Similarly, Let
$G+v$ be obtained from $G$ by adding vertex $v\notin V(G)$ (note, if a vertex
$v$ is added to $G,$ then its neighbours in $G$ should be specified somehow),
$G+uv$ be obtained from $G$ by adding an edge $uv\notin E(G),$ where $u,v\in
V(G).$ For $v\in V(G),$ let $N_{G}(v)$ (or $N(v)$ for short) denote the set of
all the adjacent vertices of $v$ in $G.$

The degree of a vertex $v$ in $G$ is denoted by $d_{G}(v).$ If $d_{G}(v)=1,$
then $v$ is a pendant vertex of $G$. An edge associated with a pendant vertex
is a pendant edge. Two distinct edges in a graph $G$ are independent if they
do not have a common end vertex in $G.$ A set of pairwise independent edges of
$G$ is called a matching of $G,$ while a matching of maximum cardinality is a
maximum matching of $G.$ The matching number $m$ of $G$ is the cardinality of
a maximum matching of $G.$ Let $M$ be a matching of $G.$ The vertex $v$ in $G$
is $M$-saturated if $v$ is incident with an edge in $M;$ otherwise, $v$ is
$M$-unsaturated. A perfect matching $M$ of $G$ means that each vertex of $G$
is $M$-saturated. Clearly, every perfect matching is maximum.

We call graph $G$ a cactus if $G$ is connected and any two of its cycles have
at most one common vertex. For a cactus graph $G,$ we call it a $bundle$ if
all cycles of $G$ have exactly one common vertex. Let $\ell_{n}^{m}$ denote
the set of cacti with $n$ vertices and matching number $m.$

Recently there is a lot of work on the spectral radius or the signless
Laplacian spectral radius of graphs, see [6, 13, 14, 15, 17, 19, 24, 26, 28,
32, 36, 40, 41, 45, 49] et al. Some investigation on graphs with prefect
matching or with given matching number is an important topic in the theory of
graph spectra, see [7, 8, 9, 10, 18, 20, 22, 23, 27, 28, 29, 32, 46, 47, 48]
et al. Cacti has been an interesting topic in chemical and mathematical
literature, see [1, 3, 5, 21, 27, 29, 30, 31, 32, 33, 35, 37, 38, 39, 42, 43,
44, 50] et al.

Li and Zhang [32] determined the unique graph with the maximum signless
Laplacian spectral radius among all cacti in $\ell_{n}^{m}$ with $n=2m$, and
gave a conjecture about the case $n\geq 2m+1$ as follows.

######  Conjecture 1.1.

([32], Conjecture 3.4) Let $G$ be a graph in $\ell_{n}^{m}.$ Then

(i)  If $n=2m+1,$ then $q(G)\leq\frac{5+\sqrt{4n-3}}{2}$ with equality if and
only if $G\cong H_{m}^{0}.$

(ii)  If $n\geq 2m+2,$ then $q(G)\leq q(H_{m-1}^{n-2m+1})$ with equality if
and only if $G\cong H_{m-1}^{n-2m+1},$ where $q(H_{m-1}^{n-2m+1})$ is the
largest root of the equation $x^{3}-(n-2m+7)x^{2}+(3n-8m+8)x+2m-8=0.$

In this paper, some useful lemmas are given in Section 2. In Section 3, we
characterize the unique graph with the maximum signless Laplacian spectral
radius among all cacti in $\ell_{n}^{m}$ with the case $n\geq 2m+1$. This
improves and confirms Conjecture 1.1 of Li and Zhang in [32]. Further, we
characterize the unique graph with the maximum signless Laplacian spectral
radius among all cacti on $n$ vertices.

##  2 Some preliminaries

In this section, we introduce some lemmas which we need to use in the
presentations and proofs of our main results in Sections 3.

######  Lemma 2.1.

([25], Theorem 2.1) Let $u$ and $v$ be distinct vertices of a connected graph
$G.$ Suppose that $w_{1},w_{2},\ldots,w_{s}(s\geq 1)$ are neighbors of $v$ but
not $u$ and they are all different from $u.$ Let
$x$=$(x_{1},x_{2},\ldots,x_{n})^{T}$ be the Perron vector of $Q(G),$ $H$
obtained from $G$ by deleting the edges $vw_{i}$ and adding the edges $uw_{i}$
for $i=1,2,\ldots,s.$ If $x_{v}\leq x_{u},$ then $q(G)<q(H).$

######  Lemma 2.2.

([16], Theorem 8.17) Let $G$ be a connected graph with a non-pendant edge
$e=uv$ satisfying $N(u)\cap N(v)=\emptyset$. Let $H$ be the graph obtained
from $G$ by deleting edge $uv$, identifying vertex $u$ and vertex $v$, and
adding a new pendant edge to $u(=v)$. Then $q(G)<q(H)$.

######  Definition 2.3.

([2], Chapter 2) Let $A=(a_{ij}),B=(b_{ij})$ be $n\times n$ matrices. If
$a_{ij}\leq b_{ij}$ for all $i$ and $j$, then $A\leq B$. If $A\leq B$ and
$A\neq B$, then $A<B$.

######  Lemma 2.4.

([2], Chapter 2) Let $A,B$ be $n\times n$ matrices with the spectral radius
$\rho(A)$ and $\rho(B)$. If $0\leq A\leq B$, then $\rho(A)\leq\rho(B)$.
Furthermore, if $0\leq A<B$ and $B$ is irreducible, then $\rho(A)<\rho(B)$.

######  Lemma 2.5.

([2], Chapter 2) Let $m<n$, $A,B$ be $n\times n$, $m\times m$ nonnegative
matrices with the spectral radius $\rho(A)$ and $\rho(B)$, respectively. If
$B$ is a principal submatrix of $A$, then $\rho(B)\leq\rho(A)$. Furthermore,
if $A$ is irreducible, then $\rho(B)<\rho(A)$.

By Lemmas 2.4–2.5 and the definitions of $Q(G)$ and $q(G)$, we have the
following result in terms of graphs.

######  Corollary 2.6.

Let $G$ be a connected graph. If $H$ be a subgraph of $G$, then $q(H)\leq
q(G)$. If $H$ is a proper subgraph of $G$, then $q(H)<q(G)$.

Let $I_{p}$ be the $p\times p$ identity matrix and $J_{p,q}$ be the $p\times
q$ matrix in which every entry is $1$, or simply $J_{p}$ if $p=q$. Let $M$ be
a matrix of order $n$, $\sigma(M)$ be the spectrum of the matrix $M$.

######  Definition 2.7.

([34]) Let $M$ be a real matrix of order $n$ described in the following block
form

$M=\left(\begin{array}[]{ccc}M_{11}&\cdots&M_{1t}\\\ \vdots&\ddots&\vdots\\\
M_{t1}&\cdots&M_{tt}\\\ \end{array}\right),$ (2.1)

where the diagonal blocks $M_{ii}$ are $n_{i}\times n_{i}$ matrices for any
$i\in\\{1,2,\ldots,t\\}$ and $n=n_{1}+\ldots+n_{t}$. For any
$i,j\in\\{1,2,\ldots,t\\}$, let $b_{ij}$ denote the average row sum of
$M_{ij}$, i.e. $b_{ij}$ is the sum of all entries in $M_{ij}$ divided by the
number of rows. Then $B(M)=(b_{ij})$ (simply by $B$) is called the quotient
matrix of $M$. In addition, if for each pair $i,j$, $M_{ij}$ has constant row
sum, then $B(M)$ is called the equitable quotient matrix of $M$.

######  Lemma 2.8.

([45]) Let $M=(m_{ij})_{n\times n}$ be defined as (2.1), and for any
$i,j\in\\{1,2,\ldots,t\\}$, the row sum of each block $M_{ij}$ be constant.
Let $B=B(M)=(b_{ij})$ be the equitable quotient matrix of $M$, and $\lambda$
be an eigenvalue of $B$. Then $\lambda$ is also an eigenvalue of $M$.

######  Lemma 2.9.

([45]) Let $M$ be defined as (2.1), and for any $i,j\in\\{1,2,\ldots,t\\}$,
$M_{ii}=l_{i}J_{n_{i}}+p_{i}I_{n_{i}},$ $M_{ij}=s_{ij}J_{n_{i},n_{j}}$ for
$i\not=j$, where $l_{i},p_{i},s_{ij}$ are real numbers, $B=B(M)$ be the
quotient matrix of $M$. Then

$\sigma(M)=\sigma(B)\cup\\{p_{i}^{[n_{i}-1]}\mid i=1,2,\ldots,t\\},$ (2.2)

where $\lambda^{[t]}$ means that $\lambda$ is an eigenvalue with multiplicity
$t$.

$\cdots$$\underbrace{\quad\quad\quad\quad\quad\quad\quad}$$k$$v_{0}$$\cdots$$\overbrace{\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad}$$s$Fig.1
$H_{s}^{k}$$\cdots$$\underbrace{\quad\quad\quad\quad\quad\quad\quad}$$k-1$$v_{0}$$\cdots$$\overbrace{\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad}$$s$Fig.2
$L_{s}^{k}$

######  Lemma 2.10.

Let $n$ be positive integer and $s,k$ be nonnegative integers with $2s+k+1=n$,
$H_{s}^{k}$ be a graph on $n$ vertices as in Fig. 1. Then

$\psi(H_{s}^{k})=(x-1)^{\frac{n+k-3}{2}}(x-3)^{\frac{n-k-3}{2}}[x^{3}-(n+3)x^{2}+3nx-2n+2k+2].$
(2.3)

Proof. Clearly, we have

$Q(H_{s}^{k})=\left(\begin{array}[]{ccccccccccc}n-1&1&1&1&1&\cdots&1&1&1&\cdots&1\\\
1&2&1&0&0&\cdots&0&0&0&\cdots&0\\\ 1&1&2&0&0&\cdots&0&0&0&\cdots&0\\\
1&0&0&2&1&\cdots&0&0&0&\cdots&0\\\ 1&0&0&1&2&\cdots&0&0&0&\cdots&0\\\
\vdots&\vdots&\vdots&\vdots&\vdots&\ddots&\vdots&\vdots&\vdots&\ddots&\vdots\\\
1&0&0&0&0&\cdots&2&1&0&\cdots&0\\\ 1&0&0&0&0&\cdots&1&2&0&\cdots&0\\\
1&0&0&0&0&\cdots&0&0&1&\cdots&0\\\
\vdots&\vdots&\vdots&\vdots&\vdots&\ddots&\vdots&\vdots&\vdots&\ddots&\vdots\\\
1&0&0&0&0&\cdots&0&0&0&\cdots&1\\\ \end{array}\right),$

then it can be written as follows:

$Q(H_{s}^{k})=\left(\begin{array}[]{cccccc}(n-2)J_{1}+I_{1}&J_{1,2}&J_{1,2}&\cdots&J_{1,2}&J_{1,k}\\\
J_{2,1}&J_{2}+I_{2}&0&\cdots&0&0\\\ J_{2,1}&0&J_{2}+I_{2}&\cdots&0&0\\\
\vdots&\vdots&\vdots&\ddots&\vdots&\vdots\\\
J_{2,1}&0&0&\cdots&J_{2}+I_{2}&0\\\ J_{k,1}&0&0&\cdots&0&I_{k}\\\
\end{array}\right).$ (2.4)

Let $B_{1}(H_{s}^{k})$ be the corresponding equitable quotient matrix of
$Q(H_{s}^{k})$. Then by (2.4) and Lemma 2.9, we have
$\sigma(Q(H_{s}^{k}))=\sigma(B_{1}(H_{s}^{k}))\cup\\{1^{[\frac{n+k-3}{2}]}\\}$,
where

$B_{1}(H_{s}^{k})=\left(\begin{array}[]{cccccc}n-1&2&2&\cdots&2&k\\\
1&3&0&\cdots&0&0\\\ 1&0&3&\cdots&0&0\\\
\vdots&\vdots&\vdots&\ddots&\vdots&\vdots\\\ 1&0&0&\cdots&3&0\\\
1&0&0&\cdots&0&1\\\ \end{array}\right).$

Further, we can write $B_{1}(H_{s}^{k})$ as follows:

$B_{1}(H_{s}^{k})=\left(\begin{array}[]{ccc}(n-2)J_{1}+I_{1}&2J_{1,s}&kJ_{1}\\\
J_{s,1}&3I_{s}&0\\\ J_{1}&0&I_{1}\\\ \end{array}\right).$

Let $B_{2}(H_{s}^{k})$ be the corresponding equitable quotient matrix of
$B_{1}(H_{s}^{k})$. Then by Lemma 2.9, we have
$\sigma(B_{1}(H_{s}^{k}))=\sigma(B_{2}(H_{s}^{k}))\cup\\{3^{[s-1]}\\},$ where

$B_{2}(H_{s}^{k})=\left(\begin{array}[]{ccc}n-1&2s&k\\\ 1&3&0\\\ 1&0&1\\\
\end{array}\right).$

Thus we have

$\sigma(Q(H_{s}^{k}))=\sigma(B_{2}(H_{s}^{k}))\cup\\{1^{[\frac{n+k-3}{2}]},3^{[\frac{n-k-3}{2}]}\\},$
(2.5)

and by direct computing, we know the signless Laplacian characteristic
polynomial of $B_{2}(H_{s}^{k})$ is as follows:

$\det(xI_{n}-B_{2}(H_{s}^{k}))=x^{3}-(n+3)x^{2}+3nx-2n+2k+2.$ (2.6)

Therefore, we complete the proof of (2.3) by (2.5) and (2.6). $\square$

######  Lemma 2.11.

Let $n,k$ be positive integers and $s$ be nonnegative integer with $2s+k+2=n$,
$L_{s}^{k}$ be a graph on $n$ vertices in Fig. 2, and
$f(x)=x^{5}-(n+5)x^{4}+(6n+4)x^{3}-(12n-2k-10)x^{2}+(9n-6k-12)x-2n+2k+4$. Then

$\psi(L_{s}^{k})=(x-1)^{\frac{n+k-6}{2}}(x-3)^{\frac{n-k-4}{2}}f(x).$ (2.7)

Proof. Clearly, we have

$Q(L_{s}^{k})=\left(\begin{array}[]{ccccccccccc}n-2&1&1&\cdots&1&1&1&0&1&\cdots&1\\\
1&2&1&\cdots&0&0&0&0&0&\cdots&0\\\ 1&1&2&\cdots&0&0&0&0&0&\cdots&0\\\
\vdots&\vdots&\vdots&\ddots&\vdots&\vdots&\vdots&\vdots&\vdots&\ddots&\vdots\\\
1&0&0&\cdots&2&1&0&0&0&\cdots&0\\\ 1&0&0&\cdots&1&2&0&0&0&\cdots&0\\\
1&0&0&\cdots&0&0&2&1&0&\cdots&0\\\ 0&0&0&\cdots&0&0&1&1&0&\cdots&0\\\
1&0&0&\cdots&0&0&0&0&1&\cdots&0\\\
\vdots&\vdots&\vdots&\ddots&\vdots&\vdots&\vdots&\vdots&\vdots&\ddots&\vdots\\\
1&0&0&\cdots&0&0&0&0&0&\cdots&1\\\ \end{array}\right)$

and it can be written as follows:

$Q(L_{s}^{k})=\left(\begin{array}[]{ccccccc}(n-3)J_{1}+I_{1}&J_{1,2}&\cdots&J_{1,2}&J_{1}&0&J_{1,k-1}\\\
J_{2,1}&J_{2}+I_{2}&\cdots&0&0&0&0\\\
\vdots&\vdots&\ddots&\vdots&\vdots&\vdots&\vdots\\\
J_{2,1}&0&\cdots&J_{2}+I_{2}&0&0&0\\\ J_{1}&0&\cdots&0&J_{1}+I_{1}&J_{1}&0\\\
0&0&\cdots&0&J_{1}&I_{1}&0\\\ J_{k-1,1}&0&\cdots&0&0&0&I_{k-1}\\\
\end{array}\right).$ (2.8)

Let $B_{1}(L_{s}^{k})$ be the corresponding equitable quotient matrix of
$Q(L_{s}^{k})$, then by (2.8) and Lemma 2.9, we have
$\sigma(Q(L_{s}^{k}))=\sigma(B_{1}(L_{s}^{k}))\cup\\{1^{[\frac{n+k-6}{2}]}\\}$,
where

$B_{1}(L_{s}^{k})=\left(\begin{array}[]{ccccccc}n-2&2&\cdots&2&1&0&k-1\\\
1&3&\cdots&0&0&0&0\\\ \vdots&\vdots&\ddots&\vdots&\vdots&\vdots&\vdots\\\
1&0&\cdots&3&0&0&0\\\ 1&0&\cdots&0&2&1&0\\\ 0&0&\cdots&0&1&1&0\\\
1&0&\cdots&0&0&0&1\\\ \end{array}\right).$

Further, we can write $B_{1}(L_{s}^{k})$ as follows:

$B_{1}(L_{s}^{k})=\left(\begin{array}[]{ccccc}(n-3)J_{1}+I_{1}&2J_{1,s}&J_{1}&0&(k-1)J_{1}\\\
J_{s,1}&3I_{s}&0&0&0\\\ J_{1}&0&J_{1}+I_{1}&J_{1}&0\\\ 0&0&J_{1}&I_{1}&0\\\
J_{1}&0&0&0&I_{1}\\\ \end{array}\right).$

Let $B_{2}(L_{s}^{k})$ be the corresponding equitable quotient matrix of
$B_{1}(L_{s}^{k})$, then by Lemma 2.9, we have
$\sigma(B_{1}(L_{s}^{k}))=\sigma(B_{2}(L_{s}^{k}))\cup\\{3^{[s-1]}\\},$ where

$B_{2}(L_{s}^{k})=\left(\begin{array}[]{ccccc}n-2&2s&1&0&k-1\\\ 1&3&0&0&0\\\
1&0&2&1&0\\\ 0&0&1&1&0\\\ 1&0&0&0&1\\\ \end{array}\right).$

Thus

$\sigma(Q(L_{s}^{k}))=\sigma(B_{2}(L_{s}^{k}))\cup\\{1^{[\frac{n+k-6}{2}]},3^{[\frac{n-k-4}{2}]}\\},$
(2.9)

and by direct computing, we know the signless Laplacian characteristic
polynomial of $B_{2}(L_{s}^{k})$, $\det(xI_{n}-B_{2}(L_{s}^{k}))=f(x).$

Combining the above arguments, (2.7) holds. $\square$

######  Proposition 2.12.

([32], (3.1), (3.2)) Let
$h(x)=x^{5}-(k+9)x^{4}-(n-7k-32)x^{3}+(4n-14k-54)x^{2}-(4n-7k-40)x+n-k-8$.
Then the following equations $(\ref{eq210})$ and $(\ref{eq211})$ are the
equations $(3.1)$ and $(3.2)$ in [32], respectively.

$\psi(H_{s}^{k})=(x-1)^{\frac{n+k-3}{2}}(x-3)^{\frac{n-k-3}{2}}[x^{3}-(k+6)x^{2}-(n-4k-12)x+n-k-7].$
(2.10) $\psi(L_{s}^{k})=(x-1)^{\frac{n+k-6}{2}}(x-3)^{\frac{n-k-4}{2}}h(x).$
(2.11)

Comparing (2.3) with (2.10), and comparing (2.7) with (2.11), we can find that
they are different equations. The reason is that in the proof of Eq.(3.1) in
[32], $A_{3}=B_{n-k-2}$ should be
$A_{3}=B_{n-k-2}-2(x^{2}-4x+3)^{\frac{n-k-3}{2}}.$ Thus Theorems 3.1-3.3 and
Conjecture 3.4 in [32] may be revised as follows.

######  Proposition 2.13.

([32], Theorem 3.1) Let $n$ be positive integer, $k,s$ be nonnegative integers
with $k<n$ and $s=\lfloor\frac{n-k-1}{2}\rfloor,$ $G$ be a cactus with $n$
vertices and $k$ pendant vertices.

(i)  If $n-k\equiv 1\pmod{2}$, then $q_{1}(G)\leq q_{1}(H_{s}^{k})$, with
equality if and only if $G\cong H_{s}^{k},$ where $H_{s}^{k}$ is depicted in
Fig. 1 and $q_{1}(H_{s}^{k})$ is the largest root of the equation
$x^{3}-(n+3)x^{2}+3nx-2n+2k+2=0.$

(ii)  If $n-k\equiv 0\pmod{2}$, then $q_{1}(G)\leq q_{1}(L_{s}^{k})$, with
equality if and only if $G\cong L_{s}^{k},$ where $L_{s}^{k}$ is depicted in
Fig. 2 and $q_{1}(L_{s}^{k})$ is the largest root of the equation
$x^{5}-(n+5)x^{4}+(6n+4)x^{3}-(12n-2k-10)x^{2}+(9n-6k-12)x-2n+2k+4=0$.

######  Proposition 2.14.

([32], Theorem 3.2) Let $n$ be positive integer and $s$ be nonnegative integer
with $s=\lfloor\frac{n-1}{2}\rfloor,$ $G$ be a cactus on $n$ vertices. Then

(i)  $q_{1}(G)\leq\frac{(n+2)+\sqrt{n^{2}-4n+12}}{2}$ for odd $n,$ and the
equality holds if and only if $G\cong H_{s}^{0}.$

(ii)  $q_{1}(G)\leq\frac{(n+1)+\sqrt{n^{2}-2n+9}}{2}$ for even $n,$ and the
equality holds if and only if $G\cong H_{s}^{1}.$

######  Proposition 2.15.

([32], Theorem 3.3) Let $n$ be even, $G$ be a cactus with $n$ vertices and a
perfect matching. Then $q_{1}(G)\leq\frac{(n+1)+\sqrt{n^{2}-2n+9}}{2},$ and
the equality holds if and only if $G\cong H_{m-1}^{1},$ where $m=\frac{n}{2}$.

######  Conjecture 2.16.

([32], Conjecture 3.4) Let $G$ be a cactus on $n$ vertices with matching
number $m.$

(i)  If $n=2m+1,$ then $q_{1}(G)\leq\frac{(n+2)+\sqrt{n^{2}-4n+12}}{2},$ and
the equality holds if and only if $G\cong H_{m}^{0}.$

(ii)  If $n\geq 2m+2,$ then $q_{1}(G)\leq q_{1}(H_{m-1}^{n-2m+1}),$ and the
equality holds if and only if $G\cong H_{m-1}^{n-2m+1},$ where
$q_{1}(H_{m-1}^{n-2m+1})$ is the largest root of the equation
$x^{3}-(n+3)x^{2}+3nx-4m+4=0.$

##  3 Main result

Let $G$ be a cactus with $n$ vertices and matching number $m.$ Clearly,
$m\leq\frac{n}{2}$. If $n=2m$, Proposition 2.15 characterized the unique graph
with the maximum signless Laplacian spectral radius among all cacti in
$\ell_{n}^{m}$. Now we will determine the case of $n\geq 2m+1$ and thus show
Conjecture 2.16 is true. The technique used in the proof is motivated by [27,
32] et al.

######  Theorem 3.1.

Let $G$ be a graph in $\ell_{n}^{m}.$

(i)  If $n=2m+1,$ then $q(G)\leq\frac{(n+2)+\sqrt{n^{2}-4n+12}}{2}$ with
equality if and only if $G\cong H_{m}^{0}.$

(ii)  If $n\geq 2m+2,$ then $q(G)\leq q(H_{m-1}^{n-2m+1})$ with equality if
and only if $G\cong H_{m-1}^{n-2m+1},$ where $q(H_{m-1}^{n-2m+1})$ is the
largest root of the equation of $x^{3}-(n+3)x^{2}+3nx-4m+4=0.$

Proof. Let $G=(V,E)\in\ell_{n}^{m}$ such that its signless Laplacian spectral
radius is the largest in $\ell_{n}^{m}$, where
$V=\\{v_{1},v_{2},\ldots,v_{n}\\}$. Let
$\textbf{x}=(x_{v_{1}},x_{v_{2}},\ldots,x_{v_{n}})^{T}$ be the Perron vector
of $Q(G)$, where $x_{v_{i}}$ corresponds to the vertex $v_{i},i=1,2,\ldots,n.$

Let $M$ be a maximum matching of $G.$ Then $|M|=m,$ and there are three cases
for a non-pendant edge $e=uv$ in $G:$ (1) $e=uv$ is an $M$-saturated edge; (2)
$e=uv$ has exactly one $M$-saturated vertex; (3) $e=uv$ is an $M$-unsaturated
edge but both $u$ and $v$ are $M$-saturated vertices.

We first prove that the graph $G$ is a bundle. In order to do so we will prove
the following four claims.

Claim 1. If $T$ is an induced subtree of $G$, and $T$ is attached to a vertex
$v$, where $v$ is on some cycle of $G,$ then $T$ is a star whose center is
$v$.

###### Proof.

Suppose that there exists a tree $T$ attached to $v_{1},$ but $T$ is not a
star, where $v_{1}$ is on some cycle of $G$. Then there must exist a path
$P=v_{1}u_{1}u_{2}$ of length 2 in $T.$ Take
$V_{1}=N_{G}(u_{1})\backslash\\{v_{1}\\}$,
$V_{2}=N_{G}(v_{1})\backslash\\{u_{1}\\}$ and

$G_{1}=\left\\{\begin{array}[]{cc}G-\\{u_{1}x\hskip 2.84544pt|\hskip
2.84544ptx\in V_{1}\\}+\\{v_{1}x\hskip 2.84544pt|\hskip 2.84544ptx\in
V_{1}\\},&\mbox{ if }x_{v_{1}}\geq x_{u_{1}};\\\ G-\\{v_{1}x\hskip
2.84544pt|\hskip 2.84544ptx\in V_{2}\\}+\\{u_{1}x\hskip 2.84544pt|\hskip
2.84544ptx\in V_{2}\\},&\mbox{ if }x_{v_{1}}<x_{u_{1}}.\end{array}\right.$

In $G_{1}$, $T$ is transformed to a new tree, denoted by $T_{1}$. It is
obvious that the number of pendant vertices of $T_{1}$ is more than the number
of pendant vertices of $T$. If there still exists a path $Q$ of length 2 in
$T_{1}$ of $G_{1}$, repeatedly the similar operation as above, till there are
no path with length 2 in $T_{1}$. At this moment, $T_{1}$ is transformed to a
star, denoted by $T_{2}$, and the new graph is denoted by $G_{2}.$ By Lemma
2.1, we have $q(G)<q(G_{1})<q(G_{2})$.

Assume that $|V(T)|=n_{1}$, so there are at most
$\lfloor\frac{n_{1}}{2}\rfloor$ edges of $T$ in the maximum matching of $G$.
Therefore, we can add a new edge by connecting two pendant vertices of
$T_{2}$, and add another new edge by connecting another two pendant vertices
of $T_{2}$, till the new graph, say $G^{*}$, satisfying
$G^{*}\in\ell_{n}^{m}.$ By Corollary 2.6, we have $q(G_{2})<q(G^{*})$, and
thus $q(G)<q(G^{*}),$ it is a contradiction by the assumption of $G$. ∎

Claim 2. All cycles of $G$ are with length 3.

###### Proof.

We assume that there exists a cycle, say $C^{0}={v_{1}v_{2}\ldots v_{l}v_{1}}$
in $G,$ such that its length $l\geq 4$. As $G$ is a cactus, we know
$v_{i}v_{j}\not\in E_{G}$ for any $|i-j|\geq 2$. We will complete the proof of
Claim 2 by the following three cases.

Case 1: There exists an edge $uv$ on $C^{0}$ such that $uv\in M.$

It is obvious that $N(u)\cap N(v)=\emptyset$ by the definition of a cactus.
Let $G_{1}$ be the graph obtained from $G$ by deleting edge $uv$, identifying
vertex $u$ and vertex $v$, adding a new vertex $w$ and a new pendant edge $uw$
to $u$. By Lemma 2.2, $q(G)<q(G_{1}).$ Take $M_{1}=M-uv+uw$, then $M_{1}$ is a
matching of $G_{1}.$ It is easy to see that $M_{1}$ is a maximum matching of
$G_{1},$ thus $G_{1}\in\ell_{n}^{m},$ it is a contradiction by the assumption
of $G$.

Case 2: There exists an edge $uv\in C^{0}$ having exactly one $M$-saturated
vertex.

Without loss of generality, we assume that $u$ is an $M$-saturated vertex and
$v$ is an $M$-unsaturated vertex. Similar to the proof of Case 1, we obtain
$G_{1}$ from $G$ and take $M_{1}=M$. Then we can show $M_{1}$ is a maximum
matching of $G_{1}$, thus $G_{1}\in\ell_{n}^{m},$ and $q(G)<q(G_{1}),$ it is a
contradiction.

Case 3: All edges on $C^{0}$ are $M$-unsaturated edges but all vertices of
$C^{0}$ are $M$-saturated.

Then for any $i\in\\{1,2,\ldots,l\\}$, $v_{i}$ is adjacent to a vertex $w_{i}$
such that $v_{i}w_{i}\in M$ and $w_{i}\neq v_{i-1},w_{i}\neq v_{i+1}$ (if
$i=l,v_{i+1}=v_{1}$; if $i=1,v_{i-1}=v_{l}$).

Subcase 3.1: $x_{v_{1}}\geq x_{v_{2}}.$

Let $G_{1}=G-v_{2}v_{3}+v_{1}v_{3}.$ Then we have $q(G)<q(G_{1})$ by Lemma
2.1. Take $M_{1}=M$, then $M_{1}$ is a matching of $G_{1}.$ Now we show that
$M_{1}$ is a maximum matching of $G_{1}$.

If $M_{2}$ is a maximum matching of $G_{1}$ and $|M_{2}|>m$, then
$v_{1}v_{3}\in M_{2}$ (otherwise, $M_{2}\subset E(G_{1}-v_{1}v_{3})\subset
E(G)$ is a matching of $G$, it is a contradiction). If $w_{1},w_{3}$ are
$M_{2}$-saturated, then we take $M_{3}=M_{2}-v_{1}v_{3}$. Clearly, $M_{3}$ is
a matching of $G$ with $|M_{3}|=|M_{2}|-1\geq m$. If $|M_{3}|>m$, it implies a
contradiction by $G\in\ell_{n}^{m}$. Thus $|M_{3}|=m$ and $M_{3}$ is also a
maximum matching of $G$. We note that $v_{1}$ is $M_{3}$-unsaturated, then
$v_{2}$ must be $M_{3}$-saturated. Similar to the proof of Case 2, we can
obtain a contradiction. Therefore $w_{1}$ is $M_{3}$-unsaturated or $w_{3}$ is
$M_{3}$-unsaturated. Without loss of generality, we assume that $w_{1}$ is
$M_{3}$-unsaturated. Then $M_{4}=M_{2}-v_{1}v_{3}+v_{1}w_{1}$ is a matching of
$G$ with $|M_{4}|=|M_{3}|>m$, it is a contradiction by $G\in\ell_{n}^{m}$.
Combining the above arguments, we have $G_{1}\in\ell_{n}^{m},$ it is a
contradiction by the assumption of $G$.

Subcase 3.2: $x_{v_{1}}<x_{v_{2}}.$

Let $G_{1}=G-v_{1}v_{l}+v_{2}v_{l}.$ Similar to the proof of Subcase 3.1, we
can show a contradiction, so we omit it. ∎

Claim 3.  Any two cycles of $G$ have exactly one common vertex.

###### Proof.

On the contrary, by any two cycles of $G$ have no common edges, we can assume
that there are two disjoint cycles $C^{1}$ and $C^{2}$ in $G$ connecting by
the shortest path $P=v_{1}v_{2}\ldots v_{s}$ of length $s-1(s\geq 2)$ with
$V_{P}\cap V_{C^{1}}=\\{v_{1}\\}$ and $V_{P}\cap V_{C^{2}}=\\{v_{s}\\}.$ In
view of Claim 2, let $C^{1}=v_{1}w_{1}w_{2}v_{1},C^{2}=v_{s}u_{1}u_{2}v_{s}.$
Now we will show that there exists an $m$-matching, say $M_{1},$ such that
$\\{w_{1}v_{1},w_{2}v_{1},u_{1}v_{s},u_{2}v_{s}\\}\cap M_{1}=\emptyset.$
Noting that the proof of $\\{u_{1}v_{s},u_{2}v_{s}\\}\cap M_{1}=\emptyset$ is
similar to the proof of $\\{w_{1}v_{1},w_{2}v_{1}\\}\cap M_{1}=\emptyset,$ now
we only show $\\{w_{1}v_{1},w_{2}v_{1}\\}\cap M_{1}=\emptyset.$

In fact, if ${w_{1}v_{1},w_{2}v_{1}}\notin M,$ we take $M_{1}=M,$ then our
result holds. Otherwise, without loss of generality, we assume that
$w_{2}v_{1}\in M.$

Case 1:  $w_{1}$ is not saturated by $M.$

Let $M_{1}=M-w_{2}v_{1}+w_{1}w_{2}.$ It is easy to see that $M_{1}$ is an
$m$-matching of $G$ and $\\{w_{1}v_{1},w_{2}v_{1}\\}\cap M_{1}=\emptyset,$
then our result holds in this case.

Case 2:  $w_{1}$ is saturated by $w_{1}t_{1}$ in $M.$

In this case, $d_{G}(w_{1})\geq 3.$ Let
$V_{1}=N_{G}(v_{1})\backslash\\{w_{1},w_{2}\\}$,
$V_{2}=N_{G}(w_{1})\backslash\\{v_{1},w_{2}\\}$ and

$G_{1}=\left\\{\begin{array}[]{cc}G-\\{v_{1}x\hskip 2.84544pt|\hskip
2.84544ptx\in V_{1}\\}+\\{w_{1}x\hskip 2.84544pt|\hskip 2.84544ptx\in
V_{1}\\},&\mbox{ if }x_{w_{1}}\geq x_{v_{1}};\\\ G-\\{w_{1}x\hskip
2.84544pt|\hskip 2.84544ptx\in V_{2}\\}+\\{v_{1}x\hskip 2.84544pt|\hskip
2.84544ptx\in V_{2}\\},&\mbox{ if }x_{w_{1}}<x_{v_{1}}.\end{array}\right.$

By Lemma 2.1, $q(G)<q(G_{1}).$ Take

$M_{2}=\left\\{\begin{array}[]{cc}M,&\mbox{ if }x_{w_{1}}\geq x_{v_{1}};\\\
M-w_{1}t_{1}-w_{2}v_{1}+w_{1}w_{2}+v_{1}t_{1},&\mbox{ if
}x_{w_{1}}<x_{v_{1}}.\end{array}\right.$

Then $M_{2}$ is an $m$-matching of $G_{1}.$

Now we show $G_{1}\in\ell_{n}^{m}.$ Otherwise, let $M_{3}$ be a maximum
matching of $G_{1}$ with $|M_{3}|>m$, now we will obtain a contradiction by
the following two subcases.

Subcase 2.1:  $x_{w_{1}}\geq x_{v_{1}}$.

Then $w_{1}t\in M_{3}$ where $t\in N_{G}(v_{1})\backslash\\{w_{1},w_{2}\\}$.
Otherwise, $M_{3}\subset E(G_{1})-\\{w_{1}t\hskip 1.42271pt|\hskip
1.42271ptt\in N_{G}(v_{1})\backslash\\{w_{1},w_{2}\\}\\}\subset E(G)$ is a
matching of $G$, it is a contradiction by $G\in\ell_{n}^{m}$ and $|M_{3}|>m$.

If $v_{1}$ is $M_{3}$-saturated, then $v_{1}w_{2}\in M_{3}$ by
$d_{G_{1}}(v_{1})=2$. Thus we take

$M_{4}=\left\\{\begin{array}[]{cc}M_{3}-w_{1}t-v_{1}w_{2}+v_{1}t+w_{1}w_{2},&v_{1}\mbox{
is }M_{3}\mbox{-saturated};\\\ M_{3}-w_{1}t+v_{1}t,&v_{1}\mbox{ is
}M_{3}\mbox{-unsaturated}.\end{array}\right.$

Clearly, $M_{4}$ is an $|M_{3}|$-matching of $G$, it is a contradiction by
$G\in\ell_{n}^{m}$ and $|M_{3}|>m$.

Subcase 2.2:  $x_{w_{1}}<x_{v_{1}}$.

Then $v_{1}t\in M_{3}$ where $t\in N_{G}(w_{1})\backslash\\{v_{1},w_{2}\\}$.
Otherwise, $M_{3}\subset E(G_{1})-\\{v_{1}t\hskip 1.42271pt|\hskip
1.42271ptt\in N_{G}(w_{1})\backslash\\{v_{1},w_{2}\\}\\}\subset E(G)$ is a
matching of $G$, it is a contradiction by $G\in\ell_{n}^{m}$ and $|M_{3}|>m$.

If $w_{1}$ is $M_{3}$-saturated, then $w_{1}w_{2}\in M_{3}$ by
$d_{G_{1}}(w_{1})=2$. Take

$M_{4}=\left\\{\begin{array}[]{cc}M_{3}-v_{1}t-w_{1}w_{2}+w_{1}t+v_{1}w_{2},&w_{1}\mbox{
is }M_{3}\mbox{-saturated};\\\ M_{3}-v_{1}t+w_{1}t,&w_{1}\mbox{ is
}M_{3}\mbox{-unsaturated}.\end{array}\right.$

Clearly, $M_{4}$ is an $|M_{3}|$-matching of $G$, it is a contradiction by
$G\in\ell_{n}^{m}$ and $|M_{3}|>m$.

Combining the above two subcases, we have $G_{1}\in\ell_{n}^{m}.$ Then it
implies a contradiction by the assumption of $G$, $q(G)<q(G_{1})$ and
$G_{1}\in\ell_{n}^{m}.$

Thus, there exists an $m$-matching $M_{1}$ of $G$ such that
$\\{w_{1}v_{1},w_{2}v_{1},u_{1}v_{s},u_{2}v_{s}\\}\cap M_{1}=\emptyset.$ Now
we take

$G_{2}=\left\\{\begin{array}[]{cc}G-v_{1}w_{1}-v_{1}w_{2}+v_{s}w_{1}+v_{s}w_{2},&\mbox{if
}x_{v_{s}}\geq x_{v_{1}};\\\
G-v_{s}u_{1}-v_{s}u_{2}+v_{1}u_{1}+v_{1}u_{2},&\mbox{if
}x_{v_{s}}<x_{v_{1}}.\end{array}\right.$

By Lemma 2.1, $q(G)<q(G_{2}).$ Let $M_{5}=M_{1}$, it is obvious that $M_{5}$
is an $m$-matching of $G_{2}$.

Now we show $G_{2}\in\ell_{n}^{m}.$ Otherwise, let $M_{6}$ be a maximum
matching of $G_{2}$ with $|M_{6}|>m$. We only consider the case $x_{v_{s}}\geq
x_{v_{1}}$ because the proof of the case $x_{v_{s}}<x_{v_{1}}$ is similar to
the case $x_{v_{s}}\geq x_{v_{1}}$.

Then $v_{s}w_{1}\in M_{6}$ or $v_{s}w_{2}\in M_{6}$. Otherwise $M_{6}\subset
E(G_{2}-v_{s}w_{1}-v_{s}w_{2})\subset E(G)$ is a matching of $G$, it is a
contradiction by $G\in\ell_{n}^{m}$ and $|M_{6}|>m$. Without loss of
generality, we assume that $v_{s}w_{1}\in M_{6}$. Then we have the following
results.

(i) There exists some $t\in N_{G}(v_{1})\backslash\\{w_{1},w_{2}\\}$ such that
$v_{1}t\in M_{6}$. Otherwise, $M_{6}-v_{s}w_{1}+v_{1}w_{1}\subset E(G)$ is an
$|M_{6}|$-matching of $G$, it is a contradiction by $G\in\ell_{n}^{m}$ and
$|M_{6}|>m$.

(ii) There exists some $r\in N_{G}(w_{2})\backslash\\{v_{1},w_{1}\\}$ such
that $w_{2}r\in M_{6}$. Otherwise, $M_{6}-v_{s}w_{1}+w_{1}w_{2}\subset E(G)$
is an $|M_{6}|$-matching of $G$, it is a contradiction by $G\in\ell_{n}^{m}$
and $|M_{6}|>m$.

(iii) There exist no pendant vertices $z$ such that $w_{1}z\in E(G)$.
Otherwise, $M_{6}-v_{s}w_{1}+w_{1}z\subset E(G)$ is an $|M_{6}|$-matching of
$G$, it is a contradiction by $G\in\ell_{n}^{m}$ and $|M_{6}|>m$.

By (ii), we have $d_{G}(w_{2})\geq 3$. Then we let
$V_{3}=N_{G}(w_{2})\backslash\\{v_{1},w_{1}\\}$ and

$G_{3}=\left\\{\begin{array}[]{cc}G-\\{v_{1}x\hskip 2.84544pt|\hskip
2.84544ptx\in V_{1}\\}+\\{w_{2}x\hskip 2.84544pt|\hskip 2.84544ptx\in
V_{1}\\},&\mbox{ if }x_{w_{2}}\geq x_{v_{1}};\\\ G-\\{w_{2}x\hskip
2.84544pt|\hskip 2.84544ptx\in V_{3}\\}+\\{v_{1}x\hskip 2.84544pt|\hskip
2.84544ptx\in V_{3}\\},&\mbox{ if }x_{w_{2}}<x_{v_{1}}.\end{array}\right.$

By Lemma 2.1, $q(G)<q(G_{3}).$ Similar to the proof of Case 2, we can show
$G_{3}\in\ell_{n}^{m}$, it is a contradiction by the assumption of $G$.

By the above arguments, we know $G_{2}\in\ell_{n}^{m}$. But it implies a
contradiction by the assumption of $G$, $q(G)<q(G_{2})$ and
$G_{2}\in\ell_{n}^{m}.$ Combining the above arguments, we completes the proof
of Claim 3. ∎

Claim 4. Any three cycles contained in $G$ have exactly one common vertex.

###### Proof.

We assume that there exists three cycles say $C^{1},C^{2}$ and $C^{3}$ in $G$
such that they have no common vertex. By Claim 2, let $V_{C^{1}}\cap
V_{C^{2}}=\\{u\\},V_{C^{1}}\cap V_{C^{3}}=\\{v\\}$ and $V_{C^{2}}\cap
V_{C^{3}}=\\{w\\}.$ Then $u,v$ and $w$ at the same cycle $C^{4}.$ Thus
$C^{1}\cap C^{4}=\\{u,v\\},$ a contradiction to the definition of a cactus.
Then any three cycles have common vertices, and thus any three cycles have
exactly one common vertex by Claim 3. ∎

By Claims 3 and 4, we know that all of the cycles contained in $G$ have
exactly one common vertex, say $v_{0},$ $i.e.$ $G$ is a $bundle.$ Now we know
that the graph in $\ell_{n}^{m}$ having the largest signless Laplacian
spectral radius is a $bundle$ with some pendant trees attached, and these
trees are stars by Claim 1. Now we will show these stars are attached to the
vertex $v_{0}$ of $G$.

Claim 5. If $G$ contains pendant edges, then all pendant edges are attached to
the common vertex $v_{0}$.

###### Proof.

On the contrary, by Claim 2 we can assume that there exists a cycle, say
$v_{0}v_{1}v_{2}v_{0},$ in $G$ such that $v_{1}$ is adjacent to $i$ pendant
vertices and $v_{2}$ is adjacent to $j$ pendant vertices, where $i,j\geq 0$
and $i+j\geq 1.$ We will complete the proof by the following four cases.

Case 1: $i\geq 1,j=0$ or $i=0,j\geq 1.$

Without loss of generality, let $i\geq 1,j=0.$ The proof of the case
$i=0,j\geq 1$ is similar, we omit it. Let
$V_{1}=N_{G}(v_{1})\backslash\\{v_{0},v_{2}\\}$,
$V_{2}=N_{G}(v_{0})\backslash\\{v_{1},v_{2}\\}$.

Subcase 1.1: There exists a pendant edge, say $v_{1}v^{\prime}_{1},$ attached
to $v_{1}$ being in $M.$

Take

$G_{1}=\left\\{\begin{array}[]{cc}G-\\{v_{1}x\hskip 2.84544pt|\hskip
2.84544ptx\in V_{1}\\}+\\{v_{0}x\hskip 2.84544pt|\hskip 2.84544ptx\in
V_{1}\\},&\mbox{ if }x_{v_{0}}\geq x_{v_{1}};\\\ G-\\{v_{0}x\hskip
2.84544pt|\hskip 2.84544ptx\in V_{2}\\}+\\{v_{1}x\hskip 2.84544pt|\hskip
2.84544ptx\in V_{2}\\},&\mbox{ if }x_{v_{0}}<x_{v_{1}}.\end{array}\right.$
(3.1)

By Lemma 2.1, $q(G)<q(G_{1}).$

In the case $x_{v_{0}}\geq x_{v_{1}}$, we set

$M_{1}=\left\\{\begin{array}[]{cc}M-v_{1}v^{\prime}_{1}-v_{0}v_{2}+v_{1}v_{2}+v_{0}v^{\prime}_{1},&\mbox{
if }v_{0}v_{2}\in M;\\\ M-v_{1}v^{\prime}_{1}+v_{1}v_{2},&\mbox{ if
}v_{0}v_{2}\not\in M.\end{array}\right.$

Then $M_{1}$ is an $m$-matching of $G_{1}.$ Now we show $M_{1}$ is a maximum
matching of $G_{1}$. If $M_{2}$ is a maximum matching of $G_{1}$ and
$|M_{2}|>m$, then there exists $u\in V_{1}$ such that $v_{0}u\in M_{2}$. If
not, $M_{2}\subset E(G_{1}-\\{v_{0}x\hskip 2.84544pt|\hskip 2.84544ptx\in
V_{1}\\})\subset E(G)$ is a matching of $G$, it is a contradiction. What’s
more, we have $v_{1}v_{2}\in M_{2}$ by $d_{G_{1}}(v_{1})=d_{G_{1}}(v_{2})=2$.
Then $M_{3}=M_{2}-v_{1}v_{2}-v_{0}u+v_{1}u+v_{0}v_{2}$ is a matching of $G$
with $|M_{3}|=|M_{2}|>m$, it is a contradiction by $G\in\ell_{n}^{m}$.
Therefore $G_{1}\in\ell_{n}^{m},$ and thus it is a contradiction by the
assumption of $G$.

In the case $x_{v_{0}}<x_{v_{1}}$, we set

$M_{1}=\left\\{\begin{array}[]{cc}M,&\mbox{ if }v_{0}v_{2}\in M;\\\
M-v_{0}u+v_{0}v_{2},&\mbox{ if }v_{0}v_{2}\not\in M,\end{array}\right.$

where $u\in V_{2}$ and $uv_{0}\in M$. Then $M_{1}$ is an $m$-matching of
$G_{1},$ and it is easy to check that $G_{1}\in\ell_{n}^{m},$ thus it is a
contradiction by the assumption of $G$.

Subcase 1.2: Each of the pendant edges attached to $v_{1}$ is not in $M.$

Then $v_{1}v_{0}\in M$ or $v_{1}v_{2}\in M.$ If $v_{1}v_{0}\in M,$ we set
$M_{1}=M-v_{1}v_{0}+v_{0}v_{2}+v_{1}u$, where $u\in V_{1}$. Then $M_{1}$ is an
$(m+1)$-matching of $G,$ it implies a contradiction by the assumption of $G.$

Thus $v_{1}v_{2}\in M.$ Then $v_{0}$ must be $M$-saturated by $v_{0}w$ where
$w\in V_{2}$. Otherwise, if $v_{0}$ is not $M$-saturated, we take
$M_{1}=M-v_{1}v_{2}+v_{1}u+v_{0}v_{2}$ where $u\in V_{1}$ is an
$(m+1)$-matching of $G$, it is a contradiction by the assumption of $G.$ Thus
$v_{0}$ must be $M$-saturated by $v_{0}w$ where $w\in V_{2}$.

Take $G_{1}$ as (3.1), then $q(G)<q(G_{1})$ by Lemma 2.1. We set

$M_{1}=\left\\{\begin{array}[]{cc}M,&\mbox{ if }x_{v_{0}}\geq x_{v_{1}};\\\
M-v_{1}v_{2}-v_{0}w+v_{1}w+v_{0}v_{2},&\mbox{ if
}x_{v_{0}}<x_{v_{1}}.\end{array}\right.$

Then $M_{1}$ is an $m$-matching of $G_{1}.$ Similar to the proof of Subcase
1.1, it is easy to check that $G_{1}\in\ell_{n}^{m},$ thus it is a
contradiction by the assumption of $G$.

Case 2: $i\geq 2,j\geq 2.$

If $x_{v_{1}}\geq x_{v_{2}},$ it is easy to see that there exists a pendant
edge $v_{2}v^{\prime}_{2},$ such that $v_{2}v^{\prime}_{2}\notin M.$ Let
$G_{1}=G-v_{2}v^{\prime}_{2}+v_{1}v^{\prime}_{2},$ By Lemma 2.1,
$q(G)<q(G_{1}).$ Obviously, $G_{1}\in\ell_{n}^{m},$ a contradiction.

If $x_{v_{1}}<x_{v_{2}},$ it is easy to see that there exists a pendant edge
$v_{1}v^{\prime}_{1},$ such that $v_{1}v^{\prime}_{1}\notin M.$ Let
$G_{1}=G-v_{1}v^{\prime}_{1}+v_{2}v^{\prime}_{1}.$ By Lemma 2.1,
$q(G)<q(G_{1}).$ Obviously, $G_{1}\in\ell_{n}^{m},$ a contradiction.

Case 3: $i\geq 2,j=1$ or $i=1,j\geq 2.$

Without loss of generality, we assume that $i\geq 2,j=1.$ Let
$v_{2}v^{\prime}_{2}$ be the only pendant edge attached to $v_{2}$. It is easy
to see that there exists a pendant edge $v_{1}v^{\prime}_{1}$ such that
$v_{1}v^{\prime}_{1}\notin M$ by $i\geq 2$.

Subcase 3.1:  $x_{v_{1}}<x_{v_{2}}.$

Let $G_{1}=G-v_{1}v^{\prime}_{1}+v_{2}v^{\prime}_{1}.$ By Lemma 2.1,
$q(G)<q(G_{1}).$ Obviously, $G_{1}\in\ell_{n}^{m},$ a contradiction.

Subcase 3.2:  $x_{v_{1}}\geq x_{v_{2}}.$ Noting that
$\\{v_{2}^{\prime}\\}=N_{G}(v_{2})\setminus\\{v_{0},v_{1}\\},$ we let
$G_{1}=G-v_{2}v^{\prime}_{2}+v_{1}v^{\prime}_{2}.$ By Lemma 2.1,
$q(G)<q(G_{1}).$

Subcase 3.2.1:  $v_{2}v^{\prime}_{2}\notin M.$

Then $M_{1}=M$ is an $m$-matching of $G_{1},$ and it is obvious to show
$G_{1}\in\ell_{n}^{m},$ which implies a contradiction by the assumption of
$G.$

Subcase 3.2.2:  $v_{2}v^{\prime}_{2}\in M.$

Then the matching number of $G_{1}$ is less than or equal to $m$. If not,
there exists a matching $M_{1}$ of $G_{1}$ with $|M_{1}|>m$, then
$v_{1}v^{\prime}_{2}\in M_{1}$. Otherwise, if $v_{1}v^{\prime}_{2}\not\in
M_{1},$ $M_{1}\subset E(G_{1}-v_{1}v^{\prime}_{2})\subset E(G)$, and thus
$M_{1}$ is a matching of $G$ with $|M_{1}|>m=|M|$, which implies a
contradiction by $G\in\ell_{n}^{m}.$ Therefore,
$M_{2}=M_{1}-v_{1}v^{\prime}_{2}+v_{1}v^{\prime}_{1}$ is a matching of $G$
with $|M_{2}|=|M_{1}|>m$, which implies a contradiction by $G\in\ell_{n}^{m}.$

If the matching number of $G_{1}$ is equal to $m$, say,
$G_{1}\in\ell_{n}^{m},$ we obtain a contradiction by the assumption of $G.$

If the matching number of $G_{1}$ is less than $m$, we set
$G_{2}=G_{1}+v^{\prime}_{1}v^{\prime}_{2},$ then $q(G)<q(G_{1})<q(G_{2})$ by
Lemma 2.1 and Corollary 2.6. On the other hand, we will show
$G_{2}\in\ell_{n}^{m},$ which implies a contradiction by the assumption of
$G.$

First, $M-v_{2}v^{\prime}_{2}+v^{\prime}_{1}v^{\prime}_{2}$ is an $m$-matching
of $G_{2}$. Second, if there exists a matching $M_{3}$ of $G_{2}$ with
$|M_{3}|>m$, then $v^{\prime}_{1}v^{\prime}_{2}\in M_{3}$. Otherwise, if
$v^{\prime}_{1}v^{\prime}_{2}\not\in M_{3},$ $M_{3}\subset
E(G_{2}-v^{\prime}_{1}v^{\prime}_{2})=E(G_{1})$, and thus $M_{3}$ is a
matching of $G_{1}$ with $|M_{3}|>m$, which implies a contradiction because
the matching number of $G_{1}$ is less than $m$. Further,
$M_{4}=M_{3}-v^{\prime}_{1}v^{\prime}_{2}\subset
E(G_{2}-v^{\prime}_{1}v^{\prime}_{2})=E(G_{1})$, and thus $M_{4}$ is a
matching of $G_{1}$ with $|M_{4}|\geq m$, which implies a contradiction
because the matching number of $G_{1}$ is less than $m$. Combining the above
arguments, $G_{2}\in\ell_{n}^{m}$ and we complete the proof of Case 3.

Case 4: $i=j=1.$

Let $v_{1}v^{\prime}_{1}$ be the only pendant edge attached to $v_{1}$, and
$v_{2}v^{\prime}_{2}$ be the only pendant edge attached to $v_{2}$. Then
$v_{1}v^{\prime}_{1},v_{2}v^{\prime}_{2}$ at least one in $M.$ Otherwise,
$v_{1}v^{\prime}_{1}\notin M$ and $v_{2}v^{\prime}_{2}\notin M,$ then
$v_{1}v_{2}\in M.$ Now we take
$M_{1}=M-v_{1}v_{2}+v_{1}v^{\prime}_{1}+v_{2}v^{\prime}_{2}$. Obviously,
$M_{1}$ is an $(m+1)$-matching of $G$, it is a contradiction by the assumption
of $G.$

Subcase 4.1: $v_{1}v^{\prime}_{1}\in M,v_{2}v^{\prime}_{2}\notin M$ or
$v_{1}v^{\prime}_{1}\notin M,v_{2}v^{\prime}_{2}\in M.$

Without loss of generality, we assume $v_{1}v^{\prime}_{1}\in M$ and
$v_{2}v^{\prime}_{2}\notin M.$ Then $v_{0}v_{2}\in M.$ Otherwise,
$M_{1}=M+v_{2}v^{\prime}_{2}$ is an $(m+1)$-matching of $G,$ it is implies a
contradiction by the assumption of $G.$

Take
$G_{1}=\left\\{\begin{array}[]{cc}G-v_{2}v^{\prime}_{2}+v_{1}v^{\prime}_{2},&\mbox{
if }x_{v_{1}}\geq x_{v_{2}};\\\
G-v_{1}v^{\prime}_{1}+v_{2}v^{\prime}_{1},&\mbox{ if
}x_{v_{1}}<x_{v_{2}}.\end{array}\right.$ Then $q(G)<q(G_{1})$ by Lemma 2.1.
Further, we set

$M_{1}=\left\\{\begin{array}[]{cc}M,&\mbox{ if }x_{v_{1}}\geq x_{v_{2}};\\\
M-v_{1}v^{\prime}_{1}-v_{0}v_{2}+v_{0}v_{1}+v_{2}v^{\prime}_{1},&\mbox{ if
}x_{v_{1}}<x_{v_{2}}.\end{array}\right.$

Then $M_{1}$ is an $m$-matching of $G_{1},$ and it is obvious the check that
$G_{1}\in\ell_{n}^{m},$ which implies a contradiction by the assumption of
$G.$

Subcase 4.2: $v_{1}v^{\prime}_{1}\in M$ and $v_{2}v^{\prime}_{2}\in M.$

It is easy to see that $v_{0}v_{1}\not\in M$, $v_{0}v_{2}\not\in M$ and
$v_{1}v_{2}\not\in M.$

Subcase 4.2.1:  $x_{v_{1}}\geq x_{v_{2}}.$

Let $G_{1}=G-v_{2}v^{\prime}_{2}+v_{1}v^{\prime}_{2},$
$G_{2}=G_{1}+v^{\prime}_{1}v^{\prime}_{2}.$ By Lemma 2.1 and Corollary 2.6, we
have $q(G)<q(G_{1})<q(G_{2}).$ It is clear that
$M_{1}=M-v_{1}v^{\prime}_{1}-v_{2}v^{\prime}_{2}+v_{1}v_{2}+v^{\prime}_{1}v^{\prime}_{2}$
is an $m$-matching of $G_{2}.$ Now we show $G_{2}\in\ell_{n}^{m}.$

On the contrary, we assume that $M_{2}$ is a maximum matching of $G_{2},$ and
$|M_{2}|>|M|=m.$

If $v^{\prime}_{1}v^{\prime}_{2}\in M_{2},$ then $v_{0}v_{1}\in M_{2},$ or
$v_{0}v_{2}\in M_{2},$ or $v_{1}v_{2}\in M_{2}.$ Noting that
$d_{G_{2}}(v_{2})=2$ and $d_{G_{2}}(v_{1})=4$, we set

$M_{3}=\left\\{\begin{array}[]{cc}M_{2}-v^{\prime}_{1}v^{\prime}_{2}-v_{0}v_{1}+v_{1}v^{\prime}_{1}+v_{2}v^{\prime}_{2},&\mbox{
if }v_{0}v_{1}\in M_{2};\\\
M_{2}-v^{\prime}_{1}v^{\prime}_{2}-v_{0}v_{2}+v_{1}v^{\prime}_{1}+v_{2}v^{\prime}_{2},&\mbox{
if }v_{0}v_{2}\in M_{2};\\\
M_{2}-v^{\prime}_{1}v^{\prime}_{2}-v_{1}v_{2}+v_{1}v^{\prime}_{1}+v_{2}v^{\prime}_{2},&\mbox{
if }v_{1}v_{2}\in M_{2}.\end{array}\right.$

Clearly, $M_{3}$ is a matching of $G$ and $|M_{3}|=|M_{2}|>m,$ it is a
contradiction by the assumption of $G.$ Thus
$v^{\prime}_{1}v^{\prime}_{2}\notin M_{2}.$ Therefore $v_{1}v^{\prime}_{1}\in
M_{2}$ or $v_{1}v^{\prime}_{2}\in M_{2}.$

If $v_{1}v^{\prime}_{1}\in M_{2},$ we note that $M_{2}\subset E(G)$, then
$M_{2}$ is a matching of $G.$ But $|M_{2}|>m,$ it is a contradiction by the
assumption of $G.$

If $v_{1}v^{\prime}_{2}\in M_{2},$ then $v_{0}v_{2}\in M_{2}.$ Otherwise, we
set $M_{3}=M_{2}-v_{1}v^{\prime}_{2}+v_{1}v_{2}+v^{\prime}_{1}v^{\prime}_{2}$
is also a matching of $G_{2},$ but $|M_{3}|>|M_{2}|,$ it is a contradiction by
he assumption of $M_{2}.$ Thus
$M_{4}=M_{2}-v_{0}v_{2}-v_{1}v^{\prime}_{2}+v_{1}v^{\prime}_{1}+v_{2}v^{\prime}_{2}$
is a matching of $G,$ and $|M_{4}|>m,$ it is a contradiction by the assumption
of $G.$

Combining the above arguments, we have $G_{2}\in\ell_{n}^{m},$ it is a
contradiction by the assumption of $G.$

Subcase 4.2.2:  $x_{v_{1}}<x_{v_{2}}.$

Let $G_{1}=G-v_{1}v^{\prime}_{1}+v_{2}v^{\prime}_{1},$
$G_{2}=G_{1}+v^{\prime}_{1}v^{\prime}_{2}.$ By Lemma 2.1 and Corollary 2.6, we
have $q(G)<q(G_{1})<q(G_{2}).$ It is clear that
$M_{1}=M-v_{1}v^{\prime}_{1}-v_{2}v^{\prime}_{2}+v_{1}v_{2}+v^{\prime}_{1}v^{\prime}_{2}$
is an $m$-matching of $G_{2},$ and similar to the proof of Subcase 4.2.1 we
can show $G_{2}\in\ell_{n}^{m},$ it implies a contradiction by the assumption
of $G.$ ∎

Now we come back to complete the proof of Theorem 3.1.

By Claim 2, we conclude that the lengths of all cycles in $G$ are 3. By Claim
3 and Claim 4, all cycles have exactly one common vertex, say $v_{0}.$ By
Claim 1 and Claim 5, all trees attached to a vertex of a cycle are stars (thus
all trees are pendant edges) and these pendant edges attached to the same
vertex $v_{0}.$ Therefore, if $n=2m+1,$ then $G\cong H_{m}^{0}$ or $G\cong
H_{m-1}^{2},$ where $H_{m}^{0}$ and $H_{m-1}^{2}$ are depicted in Fig. 1. On
the other hand, by Corollary 2.6, we know that $q(H_{m-1}^{2})<q(H_{m}^{0}),$
then $G\cong H_{m}^{0}$ when $n=2m+1.$ If $n\geq 2m+2,$ then $G\cong
H_{m-1}^{n-2m+1},$ where $H_{m-1}^{n-2m+1}$ is depicted in Fig. 1.

By (2.3), we have

$\psi(H_{m}^{0})=(x-1)^{\frac{n-1}{2}}(x-3)^{\frac{n-3}{2}}[x^{2}-(n+2)x+2n-2]$

and

$\psi(H_{m-1}^{n-2m+1})=(x-1)^{n-m-1}(x-3)^{m-2}[x^{3}-(n+3)x^{2}+3nx-4m+4].$

If $n\geq 3$ and $s\geq 1$, we note that $C_{3}$ is a subgraph of $H_{s}^{t}$,
then $q(H_{s}^{t})\geq q(C_{3})=4$ by Corollary 2.6, and thus
$q(H_{m}^{0})=\frac{(n+2)+\sqrt{n^{2}-4n+12}}{2}$ and $q(H_{m-1}^{n-2m+1})$ is
the largest root of the equation $x^{3}-(n+3)x^{2}+3nx-4m+4=0.$ $\square$

Let $n,m$ be positive integers, and $G$ be a graph in $\ell_{n}^{m}.$ Clearly,
$1\leq m\leq\lfloor\frac{n}{2}\rfloor$. Then by Corollary 2.6, Proposition
2.15 and Theorem 3.1, we obtain the following result immediately.

######  Theorem 3.2.

Let $G$ be a cactus on $n(\geq 3)$ vertices. Then

(i)  If $n$ is odd, then $q(G)\leq\frac{(n+2)+\sqrt{n^{2}-4n+12}}{2}$ with
equality if and only if $G\cong H_{\frac{n-1}{2}}^{0}.$

(ii)  If $n$ is even, then $q(G)\leq\frac{(n+1)+\sqrt{n^{2}-2n+9}}{2}$ with
equality if and only if $G\cong H_{\frac{n}{2}-1}^{1}.$

## References

  * [1] K. Balasubramanian, Recent developments in tree-pruning methods and polynomials for cactus graphs and trees. Methods of mathematical chemistry (Galveston, TX, 1989), J. Math. Chem. 4 (1-4) (1990) 89–102.
  * [2] A. Berman, R.J. Plemmons, Nonnegative Matrices in the Mathematical Sciences, New York: Academic Press, 1979.
  * [3] M. Bona, M. Bousquet, G. Labelle, and P. Leroux, Enumeration of $m$-ary cacti, Adv. Appl. Math. 24 (2000) 22–56.
  * [4] J.A. Bondy, U.S.R. Murty, Graph Theory with Applications, American Elsevier Publishing Co., New York. 1976.
  * [5] B. Borovićanin and M. Petrović, On the index of cactuses with $n$ vertices, Publ. Inst. Math. (Beograd) 79(93) (2006) 13–18.
  * [6] G.X. Cai, Y.Z. Fan, The signless Laplacian spectral radius of graphs with given chormatic number, Appl. Math. 22 (2009) 161–167.
  * [7] A. Chang, Bounds on the second largest eigenvalue of a tree with perfect matchings, Linear Algebra Appl. 283 (1998) 247–255.
  * [8] A. Chang, On the largest eigenvalue of a tree with perfect matching, Discrete Math. 269 (2003) 45–63.
  * [9] A. Chang, F. Tian, On the spectral radius of unicyclic graphs with perfect matchings, Linear Algebra Appl. 370 (2003) 237–250.
  * [10] A. Chang, F. Tian, A. Yu, On the index of bicyclic graphs with perfect matchings, Discrete Math. 283 (2004) 51–59.
  * [11] F.R.K. Chung, Spectral Graph Theory, CBMS Regional Conference Series in Mathematics, vol. 92, Publishied for the Conference Board of the Mathematical Sciences, Washington, DC. 1997.
  * [12] D.M. Cvetkovic̀, M. Doob, H. Sachs, Spectral of graphs theory and applications, third ed., Johann Ambrosius Barth, Heidelberg. 1995.
  * [13] D. Cvetković, P. Rowlinson, S. Simić, Signless Laplacians of finite graphs, Linear Algebra Appl. 423 (2007) 155–171.
  * [14] D. Cvetković, S. Simić, Towards a spectral theory of graphs based on the signless Laplacian, I, Publ. Inst. Math. (Beograd) 85 (99) (2009) 19–33.
  * [15] D. Cvetković, S. Simić, Towards a spectral theory of graphs based on the signless Laplacian, $\amalg,$ Linear Algebra Appl. 432 (2010) 2257–2272.
  * [16] D. Cvetkovic, P. Rowlinson, S. Simic, An Introduction to the Theory of Graph Spectra, London, 2010.
  * [17] Y.Z. Fan, D. Yang, The signless Laplacian spectral radius of graphs with given number of pendant vertices, Graphs Combin. 25 (2009) 291–298.
  * [18] L.H. Feng, G.H. Yu and X.D. Zhang, Spectral radius of graphs with given matching number, Linear Algebra Appl. 422 (1) (2007) 133–138.
  * [19] L.H. Feng, G.H. Hu, On three conjectures involving the signless Laplacian spectral radius of graphs, Publ. Inst. Math. (Beograd) 85 (2009) 35–38.
  * [20] L.H. Feng, Q. Li, X.D. Zhang, Minimizing the Laplacian spectral radius of trees with given matching number, Linear and Multilinear Algebra. 55 (2) (2007) 199–207.
  * [21] D. Geller, B. Manvel, Reconstruction of cacti, Canad. J. Math. 21 (1969) 1354–1360.
  * [22] X.Y. Geng, S.C. Li, S.X. Li, On the index of tricyclic graphs with perfect matchings, Linear Algebra Appl. 431 (2009) 2304–2316.
  * [23] X.Y. Geng, S.C. Li, On the spectral radius of tricyclic graphs with a maximum matching, Linear Algebra Appl. 36 (2012) 4043–4051.
  * [24] P. Hansen, C. Lucas, Bounds and conjectures for the signless Laplacian index of graphs, Linear Algebra Appl. 432 (2010) 3319–3336.
  * [25] Y. Hong, X.D. Zhang, Sharp upper and lower bounds for largest eigenvalue of the Laplacian matrices of trees, Discrete Math. 296 (2005) 187–197.
  * [26] Y.P. Hou, J.S. Li, Bounds on the largest eigenvalues of trees with a given size of matching, Linear Algebra Appl. 324 (2002) 203–217.
  * [27] A.L Hou, S.C. Li, Ordering n-vertex cacti with matching number q by their spectral radii, Quaestiones Mathematicae. 37 (2014) 401–414.
  * [28] A.L. Hou, S.C. Li, Ordering $n$-vertex unicyclic graphs with matching number $q$ by their signless Laplacian spectral radii, submitted for publication.
  * [29] Z.W. Huang, H.Y. Deng and S.K. Simic, On the spectral radius of cactuses with perfect matching, Appl Anal. Discrete math. 5 (2011) 14–21.
  * [30] N. Khan, A. Pal, M. Pal, Edge colouring of cactus graphs, Adv. Model. Optim. 11 (4) (2009) 407–421.
  * [31] S. Li, H. Yang, Q. Zhao, Sharp bounds on Zagreb indices of cacti with $k$ pendent vertices, Filomat 26 (2012) 1189–1200.
  * [32] S.C. Li, M.J. Zhang, On the signless Laplacian index of cacti with a given number of pendant vetices, Linear Algebra Appl. 436 (2012) 4400–4411.
  * [33] A.H. Lin, R. Luo, X.Y. Zha, A sharp lower bound of the Randić index of cacti with $r$ pendants, Discrete Appl. Math. 156 (10) (2008) 1725–1735.
  * [34] Chia-an Liu, Chih-wen Weng, Spectral radius of bipartite graphs, arXiv:1402.5621v1 [math.CO] 23 Feb 2014.
  * [35] H.Q. Liu, M. Lu, A unified approach to extremal cacti for different indices. MATCH Commun. Math. Comput. Chem. 58 (1) (2007) 183–194.
  * [36] J. Liu, B. Liu, The maximum clique and the signless Laplacian eigenvalues, Czechoslovak Math. J. 58 (2008) 1233–1240.
  * [37] Y. Liu, The Laplacian spread of cactuses, Discrete Math. Theor. Comput. Sci. 12(3) (2010) 35–40.
  * [38] M. Lu, L.Z. Zhang and F. Tian, On the Randić index of cacti, MATCH Commun. Math. Comput. Chem. 56(2006) 551–556.
  * [39] F. Ma and H. Deng. On the sum-connectivity index of cacti. Mathematical and Computer Modelling. 54 (1-2) (2011) 497–507.
  * [40] C.S. Oliveira, L.S.de Lima, N.M.M.de Abreu, S. Kirkland, Bounds on the Q-spread of a graph, Linear Algebra Appl. 432 (2010) 2342–2351.
  * [41] C.S. Oliveira, L.S.de Lima, N.M.M.de Abreu, P. Hansen, Bounds on the index of the signless Laplacian of a graph, Discrete Appl. Math. 158 (2010) 355–360.
  * [42] M. Petrović, T. Aleksić, V. Simić, On the least eigenvalue of cacti, Linear Algebra Appl. 435 (2011) 2357–2364.
  * [43] J.C. Wu, H.Y. Deng and Q. Jiang, On the spectral radius of cacti with $k$-pendant vertices, Linear Multilinear Algebra, 58(3) (2010) 391–398.
  * [44] Rundan Xing, Bo Zhou, On least eigenvalues and least eigenvectors of real symmetric matrices and graphs, Linear Algebra Appl. 438 (2013) 2378–2384.
  * [45] L.H. You, M. Yang, J.X. Li, Spectrum of a class of matrices and its applications, submitted.
  * [46] G.H. Yu, On the maximal signless Laplacian spectral radius of graphs with given matching number, Proc. Japan Acad. Ser. A 84 (2008) 163–166.
  * [47] J.M. Zhang, T.Z Huang and J.M. Guo, On the Signless Laplacian spectral radius of bicyclic graphs with perfect matchings, The Scientific World Journal. (2014) Article ID 374501.
  * [48] J.M. Zhang, T.Z. Huang and J.M. Guo, On the Signless Laplacian spectral radius of unicyclic graphs with fixed matching number, Publ. Inst. Math. 97(111) (2015), 187–197.
  * [49] X.D. Zhang, The signless Laplacian spectral radius of graphs with given degree sequences, Discrete Appl. Math. 157 (2009) 2928–2937.
  * [50] B. Zmazek, J. Zerovnik, The obnoxious center problem on weighted cactus graphs. The 1st Cologne-Twente Workshop on Graphs and Combinatorial Optimization (CTW 2001), Discrete Appl. Math. 136 (2-3) (2004) 377–386.


# MEGEX: Data-Free Model Extraction Attack against Gradient-Based Explainable
AI

Takayuki Miura
NTT Social Informatics Laboratories
Tokyo, Japan
<EMAIL_ADDRESS>
Satoshi Hasegawa
NTT Social Informatics Laboratories
Tokyo, Japan
<EMAIL_ADDRESS>
&Toshiki Shibahara
NTT Social Informatics Laboratories
Tokyo, Japan
<EMAIL_ADDRESS>

###### Abstract

The advance of explainable artificial intelligence, which provides reasons for
its predictions, is expected to accelerate the use of deep neural networks in
the real world like Machine Learning as a Service (MLaaS) that returns
predictions on queried data with the trained model. Deep neural networks
deployed in MLaaS face the threat of model extraction attacks. A model
extraction attack is an attack to violate intellectual property and privacy in
which an adversary steals trained models in a cloud using only their
predictions. In particular, a data-free model extraction attack has been
proposed recently and is more critical. In this attack, an adversary uses a
generative model instead of preparing input data. The feasibility of this
attack, however, needs to be studied since it requires more queries than that
with surrogate datasets. In this paper, we propose MEGEX, a data-free model
extraction attack against a gradient-based explainable AI. In this method, an
adversary uses the explanations to train the generative model and reduces the
number of queries to steal the model. Our experiments show that our proposed
method reconstructs high-accuracy models – 0.97$\times$ and 0.98$\times$ the
victim model accuracy on SVHN and CIFAR-10 datasets given 2M and 20M queries,
respectively. This implies that there is a trade-off between the
interpretability of models and the difficulty of stealing them.

##  1 Introduction

With the advance of deep neural networks (DNNs), artificial intelligence (AI)
based on DNNs is expected to solve various social problems. As a DNN-based
cloud service, Machine Learning as a Service (MLaaS) has become increasingly
common. MLaaS receives queries from users and returns predictions by a
deployed model. To support decision-making on the basis of the predictions in
the real world, explainable AI [1], which also provides reasons for the
predictions, has attracted attention. In Google Cloud, for example, gradient-
based explainable AI can be used to show the importance of each element in
input data.111https://cloud.google.com/explainable-ai

The model deployed in MLaaS is crucial to its service, but the model is under
threat of being stolen by adversaries. The threat is called a model extraction
attack [17]. In this attack, an adversary prepares input data and queries them
to the target victim model. By using the predictions, the adversary trains a
clone model with the same accuracy as the victim model as shown in Fig. 1.

Figure 1: Model Extraction Attack.

Since companies developing DNNs spend a lot of money on training highly
accurate models, they are concerned about protecting such valuable models to
maintain their competitive advantages. In addition to this problem, the
adversary can use the stolen model for other attacks including adversarial
examples and a model inversion attack [12].

In most model extraction attacks, adversaries must collect input data for
queries. Valuable models, in fact, are often trained using the rare dataset,
for instance, sales data collected by a company. In such cases, input data is
difficult for the adversary even to collect. For this reason, a data-free
model extraction attack has been proposed [18, 7], in which the adversary
prepares a generative model to generate input data instead of collecting them
(as shown in Fig. 2). In a data-free model extraction attack, the adversary
can steal even a valuable model that is trained with the rare dataset. On the
other hand, the disadvantage of the attack is that the adversary requires more
queries since the adversary has to train the generative models from scratch to
generate adequate input data. Since numerous queries increase the financial
cost of querying data and the possibility of being detected as abnormal users,
the currently proposed data-free model extraction attacks do not seem to be
severe threats. However, only a few studies have been conducted to improve the
efficiency of the data-free model extraction attacks. Therefore, further
studies must be conducted to clarify the threat of the attacks before DNNs are
used more widely in the real world.

Figure 2: Data-Free Model Extraction Attack.

In this paper, we focus on explainable AI, which has become more commonly used
recently to improve the usability of DNNs in the real world. We propose MEGEX,
a data-free model extraction attack against gradient-based explainable AI. In
MEGEX, we assume that the victim model is explainable AI with Vanilla Gradient
[13]. The adversary uses the explanations for computing the exact gradients to
train the generative model and reduces the number of queries to 6/7 times that
of the existing method. Our experiment shows that MEGEX achieves a more
accurate clone model with CIFAR-10. The adversary in the existing method
obtains a clone model with 80.6% test accuracy while the adversary in MEGEX
obtains a clone model with $\ell_{1}$ norm loss function has 92.3% test
accuracy. This implies that there is a trade-off between the interpretability
of models and the difficulty of data-free model extraction attacks.

##  2 Related Work

#### Explainable AI

DNNs achieve high accuracy in various tasks, but their low transparency causes
problems such as unfair and untrusted predictions. To improve transparency of
DNNs, explainable AI is actively studied by adding post-hoc explanations [11,
13, 19, 14, 15] and designing transparent models [4, 10]. In image recognition
tasks, gradient-based methods are commonly used to show the importance of an
individual pixel [13, 14, 15]. The most basic method is Vanilla Gradient [13]
that computes a gradient of a prediction with respect to an individual pixel.
The gradient map produced by Vanilla Gradient is used as to explain which part
of the image is important for the prediction. On the basis of Vanilla
Gradient, many improved methods have been proposed. For example, SmoothGrad
[14] reduces noise in a gradient map, and Integrated Gradients [15] solves the
problem that not all important pixels have large gradients.

In this paper, we aim to take the first step to study data-free model
extraction attacks to explainable AI by proposing an attack against
VanillaGrad. Although the targeted explanation method is limited, this paper
sheds light on new threats against explainable AI.

#### Model Extraction Attacks

As MLaaS becomes common, model extraction attacks that steal models in MLaaS
have attracted attention [17, 21, 20, 3]. In the attacks, attackers prepare
surrogate datasets in advance, query data in the datasets via MLaaS API and
obtain predictions by the models in MLaaS. Finally, the attackers train clone
models using queried data and predictions. Many researchers have studied the
threat of model extraction attacks from practical and theoretical
perspectives. Yu et al. proposed an attack that reduced the number of queries
with transfer learning [21]. Yan et al. proposed a cache side channel attack
to steal a DNN’s architecture [20]. Chandrasekaran et al. theoretically
discussed the threat of model extraction attacks by formalizing them as active
learning [3].

Considering the limited ability of attackers, data-free model extraction
attacks have been proposed [18, 7]. In this attack, attackers are assumed to
have difficulty preparing surrogate datasets. For example, medical data are
difficult for attackers to collect in advance. Data-free model extraction
attacks are based on a knowledge distillation method [5] that does not use
training data. We explain this attack in detail in Section 3.

#### Model Extraction Attacks to Explainable AI

There have been only a few studies on model extraction attacks against
explainable AI [8, 2]. Milli et al. proposed an attack that used a loss
regarding the distance between a gradient-based explanation of a victim model
and that of a clone model and experimentally showed that the loss improved the
efficiency of the attack [8]. Ulrich et al. proposed an attack that used
counterfactual explanations of the targeted model for training the clone model
efficiently [2].

In the above attacks, attackers are assumed to prepare surrogate datasets in
advance. In other words, data-free model extraction attacks against
explainable AI have not been proposed yet.

##  3 Preliminaries

In this section, we introduce basic notions before describing our proposed
method.

###  3.1 Deep Neural Networks

In this paper, we assume DNNs as follows. Let $f:{\bf X}\to{\bf Y}$ be a DNN
where ${\bf X}=\mathbb{R}^{d}$ is an input data space and ${\bf
Y}:=\Delta_{\geq 0}^{c}=\\{y\in\mathbb{R}^{c}_{\geq
0}\mid\sum_{i=1}^{c}y_{i}=1\\}$ is a space of outputs, i.e., confidence
values. A DNN $f$ classifies input data into $c$ classes. We do not assume
specific DNN architectures. In other words, we assume that $f$ is a typical
DNN such as ResNet for the image classification task. The only assumption is
that a softmax function is used for the activation function in the last layer.

When training a DNN, we use supervised training data $(x,y)\in{\bf
X}\times{\bf C}$, where $x$ is input data, $y$ is a one-hot vector of its
label, and ${\bf C}\subset{\bf Y}$ is a set of one-hot vectors. An objective
function is typically defined by using a loss function $l:{\bf Y}\times{\bf
Y}\to\mathbb{R}_{\geq 0}$ as follows:

$\mathcal{L}(\theta_{f},D):=\sum_{i=1}^{N}l(f(x_{i}),y_{i}).$

Here $D=\\{(x_{i},y_{i})\\}_{i=1,\ldots,N}\in({\bf X}\times{\bf C})^{N}$ is a
training dataset, and a vector $\theta_{f}$ is the parameter of the DNN $f$.
The goal of the training is to find the parameter minimizing
$\mathcal{L}(\theta_{f},D)$. The parameter $\theta_{f}$ is iteratively updated
on the basis of optimization methods, for instance, stochastic gradient
descent (SGD). Specifically, $\mathcal{L}(\theta_{f},D)$ is minimized by
updating the parameter $\theta_{f}$ in the opposite direction of the gradient
$\nabla_{\theta_{f}}\mathcal{L}(\theta_{f},D)$.

###  3.2 Gradient-Based Explainable AI

The Vanilla Gradient [13] is a gradient-based explanation method that
highlights important pixels in input images for prediction results by a DNN.
Let $f:{\bf X}\to{\bf Y}$ be a DNN required to explain and $x\in{\bf X}$ be an
input image. The Vanilla Gradient returns the following vector as an
explanation:

${\rm VG}(x):=\nabla_{x}f(x)\in{\bf X}^{c}.$

A large partial differential value means that change in the corresponding
pixel causes a large change in the prediction results. Such a pixel can be
regarded as an important pixel for the prediction results. Therefore, the map
of the partial differential values is used to explain the prediction result by
the DNN.

######  Remark 1.

In this paper, we use two gradients $\nabla_{\theta_{f}}$ and $\nabla_{x}$.
The former is differential values with respect to the parameter of a DNN, and
the latter is those with respect to pixels of an input image. The difference
between these two gradients needs to be carefully recognized.

###  3.3 Data-Free Model Extraction Attacks

In model extraction attacks, an adversary steals a trained model by making a
copy of the model using its predictions. We call the trained model $f:{\bf
X}\to{\bf Y}$ a victim model and the copied model $\hat{f}:{\bf X}\to{\bf Y}$
a clone model. For the adversary, the victim model is a black-box and the
adversary can only use its predictions for queries. The goal of the adversary
is to obtain a high-accuracy clone model.

In most model extraction attacks, adversaries collect input data $x\in{\bf X}$
and query them to the victim model to obtain the training dataset for the
clone model $\\{(x_{i},f(x_{i}))\\}$. Querying data to the victim model and
training the clone model are conducted alternately.

In contrast, a data-free model extraction attack, which has been proposed
recently, does not require adversaries to collect input data. In this attack,
an adversary trains a generative model instead of collecting input data. The
generative model is a DNN $G:\mathbb{R}^{r}\to{\bf X}$ that transforms noise
drawn from a Gaussian distribution into input data. The adversary queries the
generated input data $x\in{\bf X}$ to the victim model and obtains training
data $(x,f(x))$. The clone model $\hat{f}$ is trained to be similar to the
victim model $f$. On the other hand, the generative model is trained to
generate data whose prediction by the clone model is different from that by
the victim model. In other words, the generative model is trained to increase
the loss function of the clone model. Since the loss function regarding such
generated data is large, the parameter of the clone model is expected to be
effectively updated. Although the generative model $G$ does not learn a
distribution of an input data space ${\bf X}$, it learns to generate input
data such that they help the clone model training at each stage.

#### Formalization

The training of the clone and the generative model is formalized as follows.
Let $z\sim\mathcal{N}(0,I_{r})$ be a noise drawn from Gaussian distribution
and $l:{\bf Y}\times{\bf Y}\to\mathbb{R}$ be a loss function. Then the
objective function is

$\mathcal{L}:=\mathcal{L}(\theta_{G},\theta_{\hat{f}},\theta_{f},z):=-l(f(G(z)),\hat{f}(G(z))).$

The corresponding optimization problem is

$\min_{\theta_{G}}\max_{\theta_{\hat{f}}}\mathbb{E}_{z\sim\mathcal{N}(0,I_{r})}[\mathcal{L}(\theta_{G},\theta_{\hat{f}},\theta_{f},z)].$
(1)

This problem is solved by computing the gradients for the generative model $G$
and the clone model $\hat{f}$ alternately. Specifically, the adversary needs
two gradients $\nabla_{\theta_{\hat{f}}}\mathcal{L}$ and
$\nabla_{\theta_{G}}\mathcal{L}$. The adversary can compute the former by the
backpropagation, but cannot compute the latter.

Hence the following approximation is usually used. First, for $x=G(z)$, set

$L(x):=l(f(x),\hat{f}(x)).$ (2)

Then we see $\mathcal{L}=-L\circ G(z)$. The following proposition holds, which
is also essential to our proposed method described in the next section.

######  Proposition 2.

Set $x:=G(z)$. If an adversary has the gradient $\nabla_{x}L(x)$, then the
adversary can obtain the gradient $\nabla_{\theta_{G}}\mathcal{L}$. Therefore,
an adversary with $\nabla_{x}L(x)$ is able to train the generative model.

###### Proof.

By the chain rule, we see

$\nabla_{\theta_{G}}\mathcal{L}=-\nabla_{\theta_{G}}G(z)\cdot\nabla_{x}L(x).$
(3)

The adversary can compute $\nabla_{\theta_{G}}G(z)$ by the backpropagation.
Therefore, we see that the adversary is able to obtain
$\nabla_{\theta_{G}}\mathcal{L}$ and train the generative model. ∎

By this proposition, we see that it is enough for the adversary to know
$\nabla_{x}L(x)$. The adversary, however, cannot compute it in the existing
data-free model extraction attacks. Thus, the adversary uses the following
approximation.

#### Approximation of Gradients

In the studies by Truong et al. [18] and Kariyappa et al. [7], the adversary
uses zeroth-order gradient estimation with additional $m$ queries to obtain
$\nabla_{x}L(x)$:

$\nabla_{x}L(x)\approx\frac{1}{m}\sum_{i=1}^{m}\frac{d(L(x+\varepsilon
u_{i})-L(x))}{\varepsilon}u_{i},$ (4)

where $u_{1},\ldots,u_{m}$ are random $d$-dimensional vectors whose norms are
one. In this method, for one training of the generative model, the adversary
needs to query $m+1$ input images.

#### Loss Functions

The existing method [18] shows the difference in the loss function used by the
adversary causes the difference in the clone model accuracy. We introduce loss
functions used in the existing methods.

In MAZE [7], an adversary uses KL-divergence

$l_{{\rm KL}}(y,\hat{y})=\sum_{i=1}^{c}y_{i}\log\frac{y_{i}}{\hat{y}_{i}}$

as a loss function. In data-free model extraction (DFME) [18], in addition to
KL-divergence, an adversary uses the L1 norm with reconstructed logits

$l_{\ell_{1}}(y,\hat{y})=||\sigma^{*}(y)-\sigma^{*}(\hat{y})||_{1}$

as a loss function in order to prevent gradients from vanishing. We call this
loss function the $\ell_{1}$ norm loss. Here a function
$\sigma^{*}:Y\to\mathbb{R}^{c}$ is the inverse function of the softmax
function under the assumption that the sum of logits is zero. This function is
described as follows:

$\sigma^{*}(y)_{i}=\log y_{i}-\frac{1}{c}\sum_{j=1}^{c}\log y_{j}$

for each $1\leq i\leq c$.

##  4 MEGEX: Data-Free Model Extraction Attacks to Gradient-Based Explainable
AI

In this section, we propose MEGEX – a data-free model extraction attack
against gradient-based explainable AI.

###  4.1 Overview

Let $f:{\bf X}\to{\bf Y}$ be a victim model that outputs an explanation of
Vanilla Gradient. As with DFME, the adversary trains both a clone model
$\hat{f}:{\bf X}\to{\bf Y}$ and a generative model $G:\mathbb{R}^{r}\to{\bf
X}$ that generates input data. In the proposed method, MEGEX, the adversary
can use the gradient ${\rm VG}(x)=\nabla_{x}f(x)$ to train the generative
model.

Figure 3: MEGEX: a data-free model extraction attack against gradient-based
explainable AI

The overview of the proposed method is shown in Fig. 3 and Algorithm 1.

Algorithm 1 : MEGEX

1:victim model $f$, query budget $Q$, positive numbers $N_{G},N_{C}$, learning
rates $\eta_{G},\eta_{C}$

2:clone model$\hat{f}$

3:Initialize $G,\hat{f},q\leftarrow 0$

4:while $q<Q$ do

5: for $i\leftarrow 1,\ldots,N_{G}$ do $\triangleright$ Training of $G$

6: $z\leftarrow\mathcal{N}(0,I_{r})$ $\triangleright$ Noise drawn from
Gaussian distribution

7: $x\leftarrow G(z)$

8: $y\leftarrow f(x)$,
$\hat{y}\leftarrow\hat{f}(x),\nabla_{x}f(x)\leftarrow{\rm VG}(x)$

9: Compute $\nabla_{x}L(x)$ by $y,\hat{y},\nabla_{x}f(x)$. $\triangleright$
Key of the proposal

10:
$\nabla_{\theta_{G}}\mathcal{L}\leftarrow\nabla_{\theta_{G}}G(z)\cdot\nabla_{x}L(x)$

11: $\theta_{G}\leftarrow\theta_{G}-\eta_{G}\nabla_{\theta_{G}}\mathcal{L}$

12: for $i\leftarrow 1,\ldots,N_{C}$ do $\triangleright$ Training of $\hat{f}$

13: $z\leftarrow\mathcal{N}(0,I_{r})$ $\triangleright$ Noise drawn from
Gaussian distribution

14: $x\leftarrow G(z)$

15: $y\leftarrow f(x)$, $\hat{y}\leftarrow\hat{f}(x)$

16: Compute $\nabla_{\theta_{\hat{f}}}\mathcal{L}$. $\triangleright$
Backpropagation

17:
$\theta_{\hat{f}}\leftarrow\theta_{\hat{f}}+\eta_{C}\nabla_{\theta_{\hat{f}}}\mathcal{L}$

18: $q\leftarrow q+N_{G}+N_{C}$

  1. 1.

Generate $N_{G}$ input data and query them to the victim model. Train the
generative model using the predictions and explanations (lines 3-9). Here we
use the explanations to compute the gradient $\nabla_{\theta_{G}}\mathcal{L}$.

  2. 2.

Generate $N_{C}$ input data and query them to the victim model. Train the
clone model with the pair of input data and the predictions (lines 10-15).

  3. 3.

Repeat 1 and 2 until the number of queries reaches query budget $Q$.

###  4.2 Training Generative Models Using Gradient-Based Explanations

In a data-free model extraction attack, an adversary solves the problem (1) by
computing the gradients of the objective function with respect to parameters
of a clone model and a generative model alternately. To train the clone model,
it is necessary to compute the gradient
$\nabla_{\theta_{\hat{f}}}\mathcal{L}$. This can be computed by the adversary
using the backpropagation. On the other hand, the adversary cannot obtain the
gradient $\nabla_{\theta_{G}}\mathcal{L}$ to train the generative model in the
existing method. By Proposition 2, it is enough to compute $\nabla_{x}L(x)$
since we see that
$\nabla_{\theta_{G}}\mathcal{L}=-\nabla_{\theta_{G}}G(z)\cdot\nabla_{x}L(x)$.
Here, by the chain rule, we have

$\nabla_{x}L(x)=\nabla_{x}f(x)\cdot\nabla_{y}l(f(x),\hat{f}(x))+\nabla_{x}\hat{f}(x)\cdot\nabla_{\hat{y}}l(f(x),\hat{f}(x)),$
(5)

where $y$ is the first variable and $\hat{y}$ is the second variables of the
loss function. In the existing method, the adversary obtains the terms other
than $\nabla_{x}f(x)$. Now the adversary also obtains explanations with
Vanilla Gradient ${\rm VG}(x)=\nabla_{x}f(x)$ in MEGEX. Thus, the adversary
can compute $\nabla_{x}L(x)$ by equation (5) exactly. In this method, the
adversary can use any almost everywhere differentiable loss function to train
the generative model.

######  Example 3.

If the loss function is KL-divergence, we can compute

$\nabla_{x}L(x)=\sum_{j=1}^{c}(1+\log\frac{f_{j}(x)}{\hat{f}_{j}(x)})\nabla_{x}f_{j}(x)-\frac{f_{j}(x)}{\hat{f}_{j}(x)}\nabla_{x}\hat{f}_{j}(x).$

If the loss function is $\ell_{1}$ norm loss, by setting
$v:=\sigma^{*}(f(x))$, $s:=\sigma^{*}(\hat{f}(x))$,
$A:=\frac{1}{c}\sum_{j=1}^{c}\frac{1}{f_{j}(x)}$,
$\hat{A}:=\frac{1}{c}\sum_{j=1}^{c}\frac{1}{\hat{f}_{j}(x)}$, we can compute

$\nabla_{x}L(x)=\sum_{i=1}^{c}{\rm
sign}(v_{i}-s_{i})\bigl{(}(\frac{1}{f_{i}(x)}-A)\nabla_{x}f_{i}(x)-(\frac{1}{\hat{f}_{i}(x)}-\hat{A})\nabla_{x}\hat{f}_{i}(x)\bigr{)}.$

###  4.3 Comparison of the Numbers of Queries

In MEGEX, the adversary consumes $B\cdot(N_{G}+N_{C})$ query budget in one
iteration (from lines 3 to 15 in Algorithm 1). In contrast, in the existing
method DFME [18] and MAZE [7], the adversary needs to query extra $m$ input
data for zeroth-order gradient estimation. Hence, the adversary consumes
$B\cdot(N_{G}\cdot(m+1)+N_{C})$ query budget in one iteration. Therefore, we
see that our proposed method reduces the number of queries with the ratio

$\frac{N_{G}+N_{C}}{N_{G}\cdot(m+1)+N_{C}}.$

In accordance with DFME and MAZE, we use $N_{G}=1,N_{C}=5$ and a batch size
$B=256$. In DFME and MAZE, $m=1$ and $m=10$, respectively. Therefore, the
number of queries the proposed method needs is 6/7 times that of DFME and 3/8
times that of MAZE. In addition, the adversary in MEGEX can use the exact
gradients to train the generative models.

##  5 Experimental Evaluation

We compare our proposed method (MEGEX) with the existing method (DFME). MEGEX
needs fewer queries and gives the adversary an exact gradient to train the
generative model. Thus, we can expect MEGEX to achieve a more accurate clone
model with fewer queries than that without explanations. In this section, we
experimentally evaluate the clone model accuracy per query in both methods
with two datasets: CIFAR-10 and SVHN. From the format of datasets, we see that
${\bf X}=\mathbb{R}^{32\times 32\times 3}$ and ${\bf
Y}=\\{y\in\mathbb{R}^{10}_{\geq 0}\mid\sum_{i=1}^{10}y_{i}=1\\}$.

###  5.1 Experimental Setup

The implementation of MEGEX was based on that of DFME.
222https://github.com/cake-lab/datafree-model-extraction We refer to DFME [18]
for neural network architectures and hyperparameters.

We evaluate the test data accuracy of clone models. For each pair, {KL-
divergence, $\ell_{1}$ norm loss} $\times$ {MEGEX, DFME}, we train a clone
model and a generative model using the victim model five times.

There were a few trials where the clone model was not trained at all. For this
reason, if the accuracy of clone models stays less than 40% at 10M queries, we
stop the training and redo it.

#### Neural Network Architectures

For each dataset, we use the same architectures as those in the work by Truong
et al. [18]. The victim model architecture is a ResNet-34 and the clone model
architecture is a ResNet-18. The generative model architecture is a neural
network with three convolutional layers, interleaved with linear up-sampling
layers, batch normalization layers, and rectified linear unit (ReLU)
activations for all layers except the last one. The last layer is the
hyperbolic tangent function.

#### Training by an Adversary

For each dataset, the following are common settings. The adversary uses KL-
divergence and $\ell_{1}$ norm loss as a loss function and also uses
$N_{G}=1,N_{C}=5,B=256$ in Algorithm 1. The clone model is trained with an SGD
optimizer, and the generative model is trained with an Adam optimizer.

The query budgets and the learning rates are different for each dataset. The
query budget $Q$ is $20{\rm M}=2.0\times 10^{7}$ for CIFAR-10 and 2M for SVHN.
For CIFAR-10, the adversary uses the learning rate of the generative model
$\eta_{G}$ of $5.0\times 10^{-4}$ and that of the clone model $\eta_{C}$ of
0.1 and for SVHN, that of the generative model $\eta_{G}$ of $5.0\times
10^{-5}$ and that of the clone model $\eta_{C}$ of 0.1. In particular, for
CIFAR-10, the adversary uses a learning rate scheduler that multiplies the
learning rate by a factor 0.3 at $0.1\times$ , $0.3\times$, and $0.5\times$
the total query budget. For SVHN, learning rate schedulers are not used.

In DFME, the adversary uses $m=1$ and $\varepsilon=0.001$ for zeroth-order
gradient estimation.

###  5.2 Experimental Results

Table 1: Accuracy (normalized accuracy): Normalized accuracy is the clone accuracy divided by the victim accuracy Dataset (budget) | Victim | MEGEX-$\ell_{1}$ | MEGEX-KL | DFME-$\ell_{1}$ | DFME-KL
---|---|---|---|---|---
CIFAR-10 (20M) | 95.5$\%$ | 92.3$\%$ ($0.97\times$) | 72.1$\%$ ($0.75\times$) | 80.6$\%$ ($0.84\times$) | 72.1$\%$ ($0.75\times$)
SVHN (2M) | 94.8$\%$ | 92.5$\%$ ($0.98\times$) | 89.9$\%$ ($0.95\times$) | 92.5$\%$ ($0.98\times$) | 89.7$\%$ ($0.95\times$)

The results of the experiments are shown in Table 1. We plot the mean values
of the clone model accuracy in the five experiments in Figs. 4 and 5 for each
dataset. The horizontal axis is the number of queries, and the vertical axis
is the test data accuracy of clone models. The error bars express the standard
deviations of the results of the five experiments. The accuracy of the victim
model is 95.5% with CIFAR-10 and 94.8% with SVHN.

#### CIFAR-10

MEGEX with $\ell_{1}$ norm loss achieves the test data accuracy of 72.1% at 1M
queries, 90.4% at 10M queries, and 92.3% at 20M queries. DFME with $\ell_{1}$
norm loss achieves 33.6% at 1M queries, 74.5% at 10M queries, and 80.6% at 20M
queries.

For CIFAR-10, our result of DFME-$\ell_{1}$ is worse than that of the paper by
Truong et al. [18], where DFME-$\ell_{1}$ achieves 88.1% at 20M queries.
Nevertheless, the mean of five trials of MEGEX with $\ell_{1}$ norm loss still
outperforms the result reported in the paper.

Both methods with KL-divergence achieve test data accuracy of $72.1\%$ at 20M
queries. We consider this result comes from vanishing gradients, which is also
reported by Truong et al. [18]. Though MEGEX uses the exact direction
gradients, they are too small to train the generative model efficiently.

#### SVHN

When the dataset is SVHN, there is no difference between the results of MEGEX
and DFME. As with CIFAR-10, we also consider this result comes from vanishing
gradients.

Both methods with $\ell_{1}$ norm loss achieve around $92\%$ at 0.5M queries.
We consider that this is because the SVHN dataset is an easy task for
ResNet-18 with $\ell_{1}$ norm. Both methods with KL-divergence have low
accuracy until around $0.5$M queries and achieve around $90\%$ at $1.6$M
queries.

Figure 4: Test accuracy with respect to the number of queries for CIFAR-10.
Figure 5: Test accuracy with respect to the number of queries for SVHN.

##  6 Conclusion

In this research, we are the first to propose a data-free model extraction
attack against gradient-based explainable AI and point out a new threat to
explainable AI. In the proposed method, MEGEX, using the explanations, the
adversary can train the generative model efficiently. Our experiments show
that this method reconstructs high-accuracy models – 0.97$\times$ and
0.98$\times$ the victim model accuracy on SVHN and CIFAR-10 datasets given 2M
and 20M queries respectively. In particular, with CIFAR-10, the adversary in
the existing method obtains a clone model with 80.6% test accuracy while the
adversary in MEGEX obtains a clone model with $\ell_{1}$ norm loss function
with 92.3% test accuracy. This implies that there is a trade-off between the
interpretability of models and the difficulty of stealing them. With the
advance of machine learning, this problem may become real in the near future.

Before that, we need to investigate whether it is possible to achieve data-
free model extraction attacks against other gradient-based explainable AI,
like SmoothGrad and Integrated Gradient. We also have to evaluate the existing
defense results [6, 9, 16], which are proposed against the existing model
extraction attacks.

## References

  * [1] Amina Adadi and Mohammed Berrada.  Peeking inside the black-box: A survey on explainable artificial intelligence (XAI).  IEEE Access, 6:52138–52160, 2018.
  * [2] Ulrich Aïvodji, Alexandre Bolot, and Sébastien Gambs.  Model extraction from counterfactual explanations.  arXiv preprint arXiv:2009.01884, 2020.
  * [3] Varun Chandrasekaran, Kamalika Chaudhuri, Irene Giacomelli, Somesh Jha, and Songbai Yan.  Exploring connections between active learning and model extraction.  In 29th USENIX Security Symposium (USENIX Security 20), pages 1309–1326, 2020.
  * [4] Sanjeeb Dash, Oktay Gunluk, and Dennis Wei.  Boolean decision rules via column generation.  In Proceedings of the 32nd Advances in Neural Information Processing Systems, pages 4655–4665.
  * [5] Geoffrey Hinton, Oriol Vinyals, and Jeff Dean.  Distilling the knowledge in a neural network.  arXiv preprint arXiv:1503.02531, 2015.
  * [6] Mika Juuti, Sebastian Szyller, Samuel Marchal, and N Asokan.  Prada: protecting against dnn model stealing attacks.  In 2019 IEEE European Symposium on Security and Privacy (EuroS&P), pages 512–527. IEEE, 2019.
  * [7] Sanjay Kariyappa, Atul Prakash, and Moinuddin Qureshi.  Maze: Data-free model stealing attack using zeroth-order gradient estimation.  arXiv preprint arXiv:2005.03161, 2020.
  * [8] Smitha Milli, Ludwig Schmidt, Anca D Dragan, and Moritz Hardt.  Model reconstruction from model explanations.  In Proceedings of the Conference on Fairness, Accountability, and Transparency, pages 1–9, 2019.
  * [9] Tribhuvanesh Orekondy, Bernt Schiele, and Mario Fritz.  Prediction poisoning: Towards defenses against dnn model stealing attacks.  In International Conference on Learning Representations, 2019.
  * [10] Tejaswini Pedapati, Avinash Balakrishnan, Karthikeyan Shanmugam, and Amit Dhurandhar.  Learning global transparent models consistent with local contrastive explanations.  Proceedings of the 34th Advances in Neural Information Processing Systems, 2020.
  * [11] Marco Tulio Ribeiro, Sameer Singh, and Carlos Guestrin.  "Why should I trust you?" explaining the predictions of any classifier.  In Proceedings of the 22nd ACM SIGKDD international conference on knowledge discovery and data mining, pages 1135–1144, 2016.
  * [12] Yi Shi, Yalin E Sagduyu, Kemal Davaslioglu, and Jason H Li.  Active deep learning attacks under strict rate limitations for online api calls.  In 2018 IEEE International Symposium on Technologies for Homeland Security (HST), pages 1–6. IEEE, 2018.
  * [13] Karen Simonyan, Andrea Vedaldi, and Andrew Zisserman.  Deep inside convolutional networks: Visualising image classification models and saliency maps.  arXiv preprint arXiv:1312.6034, 2013.
  * [14] Daniel Smilkov, Nikhil Thorat, Been Kim, Fernanda Viégas, and Martin Wattenberg.  Smoothgrad: removing noise by adding noise.  arXiv preprint arXiv:1706.03825, 2017.
  * [15] Mukund Sundararajan, Ankur Taly, and Qiqi Yan.  Axiomatic attribution for deep networks.  In Proceedings of the 34th International Conference on Machine Learning, pages 3319–3328, 2017.
  * [16] Sebastian Szyller, Buse Gul Atli, Samuel Marchal, and N Asokan.  Dawn: Dynamic adversarial watermarking of neural networks.  arXiv preprint arXiv:1906.00830, 2019.
  * [17] Florian Tramèr, Fan Zhang, Ari Juels, Michael K Reiter, and Thomas Ristenpart.  Stealing machine learning models via prediction apis.  In 25th USENIX Security Symposium (USENIX Security 16), pages 601–618, 2016.
  * [18] Jean-Baptiste Truong, Pratyush Maini, Robert Walls, and Nicolas Papernot.  Data-free model extraction.  arXiv preprint arXiv:2011.14779, 2020.
  * [19] Sandra Wachter, Brent Mittelstadt, and Chris Russell.  Counterfactual explanations without opening the black box: Automated decisions and the gdpr.  Harv. JL & Tech., 31:841, 2017.
  * [20] Mengjia Yan, Christopher W Fletcher, and Josep Torrellas.  Cache telepathy: Leveraging shared resource attacks to learn dnn architectures.  In 29th USENIX Security Symposium (USENIX Security 20), pages 2003–2020, 2020.
  * [21] Honggang Yu, Kaichen Yang, Teng Zhang, Yun-Yun Tsai, Tsung-Yi Ho, and Yier Jin.  Cloudleak: Large-scale deep learning models stealing through adversarial examples.  In Proceedings of Network and Distributed Systems Security Symposium (NDSS), 2020.