% EJC papers *must* begin with the following two lines.
\documentclass[12pt]{article}
\usepackage{e-jc}

% Please remove all other commands that change parameters such as
% margins or pagesizes.

% only use standard LaTeX packages
% only include packages that you actually need

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

% we recommend the graphicx package for importing figures
\usepackage{graphicx}

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

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

% all overfull boxes must be fixed;
% i.e. there must be no text protruding into the margins


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

\theoremstyle{definition}
\newtheorem{definition}[theorem]{Definition}
\newtheorem{example}[theorem]{Example}
\newtheorem{conjecture}[theorem]{Conjecture}
\newtheorem{open}[theorem]{Open Problem}
\newtheorem{problem}[theorem]{Problem}
\newtheorem{question}[theorem]{Question}

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

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

% if needed include a line break (\\) at an appropriate place in the title

\title{\bf On the resistance matrix of a graph}

% input author, affilliation, address and support information as follows;
% the address should include the country, and does not have to include
% the street address

\author{Jiang Zhou\thanks{Corresponding author.}\\
\small College of Science\\[-0.8ex]
\small College of Computer Science and Technology\\[-0.8ex]
\small Harbin Engineering University\\[-0.8ex]
\small Harbin, PR China\\
\small\tt zhoujiang04113112@163.com\\
\and
Zhongyu Wang\\
\small School of Management\\[-0.8ex]
\small Harbin Institute of Technology\\[-0.8ex]
\small Harbin, PR China\\
\small\tt wangzhy@hit.edu.cn\\
\and
Changjiang Bu\\
\small College of Science\\[-0.8ex]
\small Harbin Engineering University\\[-0.8ex]
\small Harbin, PR China\\
\small\tt buchangjiang@hrbeu.edu.cn
}

% \date{\dateline{submission date}{acceptance date}\\
% \small Mathematics Subject Classifications: comma separated list of
% MSC codes available from http://www.ams.org/mathscinet/freeTools.html}

\date{\dateline{Jul 8, 2015}{Feb 15, 2016}\\
\small Mathematics Subject Classifications: 05C50, 05C12, 15A09}

\begin{document}

\maketitle

% E-JC papers must include an abstract. The abstract should consist of a
% succinct statement of background followed by a listing of the
% principal new results that are to be found in the paper. The abstract
% should be informative, clear, and as complete as possible. Phrases
% like "we investigate..." or "we study..." should be kept to a minimum
% in favor of "we prove that..."  or "we show that...".  Do not
% include equation numbers, unexpanded citations (such as "[23]"), or
% any other references to things in the paper that are not defined in
% the abstract. The abstract will be distributed without the rest of the
% paper so it must be entirely self-contained.

\begin{abstract}
  Let $G$ be a connected graph of order $n$. The resistance matrix of $G$ is defined as $R_G=(r_{ij}(G))_{n\times n}$, where $r_{ij}(G)$ is the resistance distance between two vertices $i$ and $j$ in $G$. Eigenvalues of $R_G$ are called R-eigenvalues of $G$. If all row sums of $R_G$ are equal, then $G$ is called resistance-regular. For any connected graph $G$, we show that $R_G$ determines the structure of $G$ up to isomorphism. Moreover, the structure of $G$ or the number of spanning trees of $G$ is determined by partial entries of $R_G$ under certain conditions. We give some characterizations of resistance-regular graphs and graphs with few distinct R-eigenvalues. For a connected regular graph $G$ with diameter at least $2$, we show that $G$ is strongly regular if and only if there exist $c_1,c_2$ such that $r_{ij}(G)=c_1$ for any adjacent vertices $i,j\in V(G)$, and $r_{ij}(G)=c_2$ for any non-adjacent vertices $i,j\in V(G)$.

  % keywords are optional
  \bigskip\noindent \textbf{Keywords:} Resistance distance; Resistance matrix; Laplacian matrix; Resistance-regular graph; R-eigenvalue
\end{abstract}

\section{Introduction}

All graphs considered in this paper are simple and undirected. Let $V(G)$ and $E(G)$ denote the vertex set and the edge set of a graph $G$, respectively. The resistance distance is a distance function on graphs introduced by Klein and Randi\'{c} \cite{Klein93}. Let $G$ be a connected graph of order $n$. For two vertices $i,j$ in $G$, the \textit{resistance distance} between $i$ and $j$, denoted by $r_{ij}(G)$, is defined to be the effective resistance between them when unit resistors are placed on every edge of $G$. The \textit{resistance matrix} of $G$ is defined as $R_G=(r_{ij}(G))_{n\times n}$. Eigenvalues of $R_G$ are called \textit{R-eigenvalues} of $G$. The resistance (distance) in graphs has been studied extensively [8,9,11,12,14,19-21,24-28]. Some properties of the determinant, minors and spectrum of the resistance matrix can be found in \cite{Bapat04,Bapat08,Bapat11,Maden,Sun,XiaoGutman03}.

It is known that $r_{ij}(G)\leqslant d_{ij}(G)$ ($d_{ij}(G)$ denotes the distance between $i$ and $j$), with equality if and only if $i$ and $j$ are connected by a unique path \cite{Klein93}. Hence for a tree $T$, $R_T$ is equal to the distance matrix of $T$. The determinant and the inverse of the distance matrix of a tree are given in \cite{Graham78,Graham71}. These formulas have been extended to the resistance matrix \cite{Bapat04}. In \cite{Merris}, Merris gave an inequality for the spectrum of the distance matrix of a tree. This inequality also holds for the spectrum of the resistance matrix of any connected graph \cite{Sun}.

For a connected graph $G$ of order $n$, let $D_i=\sum_{j=1}^nd_{ij}(G)$, $R_i=\sum_{j=1}^nr_{ij}(G)$. If $D_1=D_2=\cdots=D_n$, then $G$ is called \textit{transmission-regular} \cite{Aouchiche,Aouchiche13}. Similar to transmission-regular graphs, we say that $G$ is \textit{resistance-regular} if $R_1=R_2=\cdots=R_n$.

In this paper, we show that $R_G$ determines the structure of any connected graph $G$ up to isomorphism. The structure of $G$ or the number of spanning trees of $G$ is determined by partial entries of $R_G$ under certain conditions. We give some characterizations of resistance-regular graphs and graphs with few distinct R-eigenvalues. Applying properties of the resistance matrix, we obtain a characterization of strongly regular graphs via resistance distance.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Preliminaries}

For a graph $G$, let $A_G$ denote the adjacency matrix of $G$, and let $D_G$ denote the diagonal matrix of vertex degrees of $G$. The matrix $L_G=D_G-A_G$ is called the \textit{Laplacian matrix} of $G$.

The \textit{$\{1\}$-inverse} of a matrix $A$ is a matrix $X$ such that $AXA=A$. If $A$ is singular, then it has infinite many $\{1\}$-inverses \cite{GM,Bu}. We use $A^{(1)}$ to denote any $\{1\}$-inverse of $A$. Let $(A)_{uv}$ or $A_{uv}$ denote the $(u,v)$-entry of $A$.

\begin{lemma}\label{lem1}
\textup{\cite{GM,Bu}} Let $G$ be a connected graph. If $L_G^{(1)}$ is a symmetric $\{1\}$-inverse of $L_G$, then $r_{uv}(G)=(L_G^{(1)})_{uu}+(L_G^{(1)})_{vv}-2(L_G^{(1)})_{uv}$.
\end{lemma}

For a real matrix $A$, the \textit{Moore-Penrose inverse} of $A$ is the unique real matrix $A^+$ such that $AA^+A=A$, $A^+AA^+=A^+$, $(AA^+)^\top=AA^+$ and $(A^+A)^\top=A^+A$. Let $I$ denote the identity matrix, and let $J_{m\times n}$ denote an $m\times n$ all-ones matrix.
\begin{lemma}\label{lem4}
\textup{\cite{GutmanXiao}} Let $G$ be a connected graph of order $n$. Then $L_G^+J_{n\times n}=J_{n\times n}L_G^+=0$, $L_GL_G^+=L_G^+L_G=I-\frac{1}{n}J_{n\times n}$.
\end{lemma}

For a vertex $u$ of a graph $G$, let $L_G(u)$ denote the principal submatrix of $L_G$ obtained by deleting the row and column corresponding to $u$. By the Matrix-Tree Theorem \cite{GM}, $L_G(u)$ is nonsingular if $G$ is connected.
\begin{lemma}\label{lem2}
Let $G$ be a connected graph of order $n$. Then $\begin{pmatrix}L_G(u)^{-1}&0\\0&0\end{pmatrix}\in\mathbb{R}^{n\times n}$ is a symmetric $\{1\}$-inverse of $L_G$, where $u$ is the vertex corresponding to the last row of $L_G$.
\end{lemma}
\begin{proof}
Suppose that $L_G=\begin{pmatrix}L_G(u)&x\\x^\top&d_u\end{pmatrix}$, where $d_u$ is the degree of $u$. Since $G$ is connected, $L_G(u)$ is nonsingular. By using the Schur complement formula, we have $\mbox{\rm rank}(L_G)=\mbox{\rm rank}(L_G(u))+\mbox{\rm rank}(d_u-x^\top L_G(u)^{-1}x)=n-1$. By $\mbox{\rm rank}(L_G(u))=n-1$, we get $d_u=x^\top L_G(u)^{-1}x$. Then
\begin{eqnarray*}
L_G\begin{pmatrix}L_G(u)^{-1}&0\\0&0\end{pmatrix}L_G=\begin{pmatrix}I&0\\x^\top L_G(u)^{-1}&0\end{pmatrix}\begin{pmatrix}L_G(u)&x\\x^\top&d_u\end{pmatrix}=L_G.
\end{eqnarray*}
Hence $\begin{pmatrix}L_G(u)^{-1}&0\\0&0\end{pmatrix}$ is a symmetric $\{1\}$-inverse of $L_G$.
\end{proof}

\begin{lemma}\label{lem3}
\textup{\cite{Bu}} Let $M=\begin{pmatrix}A&B\\B^\top&C\end{pmatrix}$ be a nonsingular matrix, and $A$ is nonsingular. Then $M^{-1}=\begin{pmatrix}A^{-1}+A^{-1}BS^{-1}B^\top A^{-1}&-A^{-1}BS^{-1}\\-S^{-1}B^\top A^{-1}&S^{-1}\end{pmatrix}$, where $S=C-B^\top A^{-1}B$.
\end{lemma}
For a connected graph $G$ of order $n$, let $\tau_i=2-\sum_{j\in\Gamma(i)}r_{ij}(G)$, where $\Gamma(i)$ denotes the set of all neighbors of $i$. Let $\tau$ be be the $n\times1$ vector with components $\tau_1,\ldots,\tau_n$.
\begin{lemma}\label{lem6}
\textup{\cite{Bapat04,GM}} Let $G$ be a connected graph of order $n$, and let $X=(L_G+\frac{1}{n}J_{n\times n})^{-1}$, $\widetilde{X}=\mbox{\rm diag}(X_{11},\ldots,X_{nn})$. Then the following hold:\\
(a) $\tau=L_G\widetilde{X}\mathbf{j}+\frac{2}{n}\mathbf{j}$, where $\mathbf{j}$ is an all-ones column vector.\\
(b) $R_G=\widetilde{X}J_{n\times n}+J_{n\times n}\widetilde{X}-2X$.\\
(c) $L_G^+=X-\frac{1}{n}J_{n\times n}$.
\end{lemma}
For a real symmetric matrix $M$ of order $n$, let $\lambda_1(M)\geqslant\lambda_2(M)\geqslant\cdots\geqslant\lambda_n(M)$ denote the eigenvalues of $M$.
\begin{lemma}\label{lem7}
\textup{\cite{Sun}} Let $G$ be a connected graph of order $n$. Then
\begin{eqnarray*}
0>-\frac{2}{\lambda_1(L_G)}\geqslant\lambda_2(R_G)\geqslant-\frac{2}{\lambda_2(L_G)}\geqslant\cdots\geqslant-\frac{2}{\lambda_{n-1}(L_G)}\geqslant\lambda_n(R_G).
\end{eqnarray*}
\end{lemma}
The \textit{Kirchhoff index} of $G$ is defined as $\mbox{\rm Kf}(G)=\frac{1}{2}\sum_{i=1}^n\sum_{j=1}^nr_{ij}(G)$.
\begin{lemma}\label{lem8}
\textup{\cite{GutmanMohar,Zhu}} Let $G$ be a connected graph of order $n$. Then
\begin{eqnarray*}
\mbox{\rm Kf}(G)=n\sum_{i=1}^{n-1}\frac{1}{\lambda_i(L_G)}.
\end{eqnarray*}
\end{lemma}

\begin{lemma}
\textup{\cite{Foster,Sun}} Let $G$ be a connected graph of order $n$. Then
\begin{eqnarray*}
\sum_{ij\in E(G)}r_{ij}(G)=n-1.
\end{eqnarray*}
\end{lemma}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Main results}

All connected graphs in this section have at least two vertices. We first show that the structure of a connected graph is determined by its resistance matrix up to isomorphism, i.e., if two connected graphs have the same resistance matrix, then they are isomorphic.
\begin{theorem}\label{thm1}
For any connected graph $G$, the structure of $G$ is determined by $R_G$ up to isomorphism.
\end{theorem}
\begin{proof}
By Lemma \ref{lem2}, the matrix $\begin{pmatrix}L_G(u)^{-1}&0\\0&0\end{pmatrix}$ is a symmetric $\{1\}$-inverse of $L_G$, where $u$ is the vertex corresponding to the last row of $L_G$. Since $R_G$ is known, by Lemma \ref{lem1}, all entries of $L_G(u)^{-1}$ is known, i.e., $L_G(u)$ is determined by $R_G$. Since each row (column) sum of $L_G$ is $0$, $L_G$ is determined by $R_G$. Hence $G$ is determined by $R_G$ up to isomorphism.
\end{proof}
A vertex of degree one is called a \textit{pendant vertex}. For a vertex $u$ of a connected graph $G$, let $R_G(u)$ denote the principal submatrix of $R_G$ obtained by deleting the row and column corresponding to $u$. Next we show that $R_G(u)$ determines $G$ up to isomorphism if $u$ is not a pendant vertex, i.e., if $u$ is not a pendant vertex of $G$, and $H$ is a connected graph satisfying $R_H(v)=R_G(u)$ for some $v\in V(H)$, then $H$ is isomorphic to $G$.
\begin{theorem}\label{thm2}
For a connected graph $G$, if $u$ is a vertex of $G$ with degree larger than one, then $R_G(u)$ determines $G$ up to isomorphism.
\end{theorem}
\begin{proof}
Without loss of generality, suppose that the first row of $L_G$ corresponds to vertex $u$, and the last row of $L_G$ corresponds to a vertex $v$. By Lemma \ref{lem2}, $\begin{pmatrix}L_G(v)^{-1}&0\\0&0\end{pmatrix}$ is a symmetric $\{1\}$-inverse of $L_G$. Suppose that $L_G(v)=\begin{pmatrix}d_u&L_2\\L_2^\top&L_3\end{pmatrix}$, where $d_u$ is the degree of $u$. Let $S=L_3-d_u^{-1}L_2^\top L_2$. By Lemma \ref{lem3}, we have
\begin{eqnarray*}
\begin{pmatrix}L_G(v)^{-1}&0\\0&0\end{pmatrix}=\begin{pmatrix}d_u^{-1}+d_u^{-2}L_2S^{-1}L_2^\top&-d_u^{-1}L_2S^{-1}&0\\-d_u^{-1}S^{-1}L_2^\top&S^{-1}&0\\0&0&0\end{pmatrix}.
\end{eqnarray*}
Since $R_G(u)$ is known, by Lemma \ref{lem1}, all entries of $S^{-1}$ are known, i.e., $S$ is determined by $R_G(u)$. Since $d_u>1$ and $S=L_3-d_u^{-1}L_2^\top L_2$, the following hold:

(1) For any vertex $i\in V(G)\setminus\{u,v\}$, $i$ and $u$ are adjacent if $(S)_{ii}$ is not an integer, are non-adjacent if $(S)_{ii}$ is an integer. Moreover, the degree of $i$ is $d_i=\lceil(S)_{ii}\rceil$, where $\lceil(S)_{ii}\rceil$ is the smallest integer larger than or equal to $(S)_{ii}$.

(2) There exists a vertex $i\in V(G)\setminus\{u,v\}$ such that $i$ and $u$ are adjacent, and $d_u=(\lceil(S)_{ii}\rceil-(S)_{ii})^{-1}$.

(3) For any vertex $i,j\in V(G)\setminus\{u,v\}$, $i$ and $j$ are adjacent if $(S)_{ij}\leqslant-1$, are non-adjacent if $(S)_{ij}>-1$.

From (1)-(3) we know that $G$ is determined by $S$ up to isomorphism. Since $S$ is determined by $R_G(u)$, $R_G(u)$ determines $G$ up to isomorphism.
\end{proof}

\noindent
\textbf{Remark 1.} Let $P_n$ denote the path with $n$ vertices. Let $G$ be the graph obtained from $P_n$ by attaching a pendant vertex $u$ at a vertex of degree two, and let $v$ be a pendant vertex of $P_{n+1}$. In this case, we have $R_{G}(u)=R_{P_{n+1}}(v)$ and $G$ is not isomorphic to $P_{n+1}$. Hence the condition ``$u$ is a vertex of degree larger than one" in Theorem \ref{thm2} is necessary.

\vspace{3mm}
Let $t(G)$ denote the number of spanning trees of a graph $G$. If $V_1$ and $V_2$ are disjoint subsets of $V(G)$, then we define $E(V_1,V_2)=\{ij\in E(G):i\in V_1,j\in V_2\}$.
\begin{theorem}\label{thm3}
Let $G$ be a connected graph whose vertex set has a partition $V(G)=V_1\cup V_2\cup\{u\}$, and $G-u$ has a unique perfect matching $M$ satisfying $M\subseteq E(V_1,V_2)$. Let $R_G=\begin{pmatrix}R_1&R_3&a_1\\R_3^\top&R_2&a_2\\a_1^\top&a_2^\top&0\end{pmatrix}$, where $R_1$ and $R_2$ are principal matrices of $R_G$ corresponding to $V_1$ and $V_2$ respectively. Then $t(G)$ is determined by $a_1,a_2$ and $R_3$.
\end{theorem}
\begin{proof}
Without loss of generality, suppose that the last row of $L_G$ corresponds to the vertex $u$. By Lemma \ref{lem2}, $\begin{pmatrix}L_G(u)^{-1}&0\\0&0\end{pmatrix}$ is a symmetric $\{1\}$-inverse of $L_G$. Since $G-u$ has a unique perfect matching $M$ satisfying $M\subseteq E(V_1,V_2)$, $L_G(u)$ can be partitioned as $L_G(u)=\begin{pmatrix}L_1&L_3\\L_3^\top&L_2\end{pmatrix}$, where $L_3$ is an upper triangular matrix, $L_1$ and $L_2$ correspond to $V_1$ and $V_2$ respectively. Let $S=L_2-L_3^\top L_1^{-1}L_3$. By Lemma \ref{lem3}, we have
\begin{eqnarray*}
\begin{pmatrix}L_G(u)^{-1}&0\\0&0\end{pmatrix}=\begin{pmatrix}L_1^{-1}+L_1^{-1}L_3S^{-1}L_3^\top L_1^{-1}&-L_1^{-1}L_3S^{-1}&0\\-S^{-1}L_3^\top L_1^{-1}&S^{-1}&0\\0&0&0\end{pmatrix}.
\end{eqnarray*}
Since $a_1$ and $a_2$ are known, by Lemma \ref{lem1}, all diagonal entries of $L_G(u)^{-1}$ are known. Since $R_3$ is also known, by Lemma \ref{lem1}, the matrix $A=-L_1^{-1}L_3S^{-1}$ is known. Hence $\det(A)=\det(-L_3)[\det(L_1)\det(S)]^{-1}$ is determined by $a_1,a_2$ and $R_3$. Note that $-L_3$ is an upper triangular matrix and each diagonal entry of $-L_3$ is $1$. So $\det(A)=[\det(L_1)\det(S)]^{-1}$. From the Matrix-Tree Theorem, we have $t(G)=\det(L_G(u))=\det(L_1)\det(S)$. Hence $t(G)$ is determined by $a_1,a_2$ and $R_3$.
\end{proof}

\begin{theorem}\label{thm6}
Let $G$ be a connected graph with $n$ vertices. Then the following are equivalent:\\
(1) $G$ is resistance-regular.\\
(2) The spectral radius of $R_G$ is
\begin{eqnarray*}
\lambda_1(R_G)=\frac{2\mbox{\rm Kf}(G)}{n}.
\end{eqnarray*}\\
(3) The spectrum of $R_G$ is
\begin{eqnarray*}
\lambda_1(R_G)=\frac{2\mbox{\rm Kf}(G)}{n},~\lambda_i(R_G)=-\frac{2}{\lambda_{i-1}(L_G)},~i=2,\ldots,n.
\end{eqnarray*}\\
(4) $X_{11}=\cdots=X_{nn}$, where $X=(L_G+\frac{1}{n}J_{n\times n})^{-1}$.\\
(5) $(L_G^+)_{11}=\cdots=(L_G^+)_{nn}$.\\
(6) For each $i\in V(G)$, we have $\sum_{j\in\Gamma(i)}r_{ij}(G)=2-\frac{2}{n}$, where $\Gamma(i)$ denotes the set of all neighbors of $i$.
\end{theorem}
\begin{proof}
By [22, Corollary 2.2], we have (1)$\Longleftrightarrow$(2).

(2)$\Longrightarrow$(3). The trace of $R_G$ is
\begin{eqnarray*}
\sum_{i=1}^n\lambda_i(R_G)=\frac{2\mbox{\rm Kf}(G)}{n}+\sum_{i=2}^n\lambda_i(R_G)=0.
\end{eqnarray*}
By Lemmas \ref{lem7} and \ref{lem8}, we have $\lambda_i(R_G)=-\frac{2}{\lambda_{i-1}(L_G)},~i=2,\ldots,n$.

(3)$\Longrightarrow$(2). Obviously.

(1)$\Longleftrightarrow$(4). By part (b) of Lemma \ref{lem6}, we have $R_G\mathbf{j}=n\widetilde{X}\mathbf{j}+(\sum_{i=1}^nX_{ii})\mathbf{j}-2\mathbf{j}$, where $\mathbf{j}$ is an all-ones column vector. Hence $G$ is resistance-regular if and only if $X_{11}=\cdots=X_{nn}$, where $X=(L_G+\frac{1}{n}J_{n\times n})^{-1}$.

By part (c) of Lemma \ref{lem6}, we have (4)$\Longleftrightarrow$(5).

(4)$\Longleftrightarrow$(6). By part (a) of Lemma \ref{lem6}, (4) is equivalent to $\tau=\frac{2}{n}\mathbf{j}$, that is, $\sum_{j\in\Gamma(i)}r_{ij}(G)=2-\frac{2}{n}$ for any $i\in V(G)$.
\end{proof}

\noindent
\textbf{Remark 2.} For any nonsingular matrix $B$, there exists polynomial $p(x)$ such that $B^{-1}=p(B)$ \cite{Ben}. Hence $X=(L_G+\frac{1}{n}J_{n\times n})^{-1}$ is a polynomial in $L_G+\frac{1}{n}J_{n\times n}$. If $G$ is a connected regular graph of degree $r$, then $J_{n\times n}$ is a polynomial in $A_G$ (see [5, Theorem 6.12]). In this case, $X=(rI-A_G+\frac{1}{n}J_{n\times n})^{-1}$ is a polynomial in $A_G$. A graph $G$ of order $n$ is called \textit{walk-regular}, if $(A_G^k)_{11}=\cdots=(A_G^k)_{nn}$ for any $k\geqslant0$ \cite{Brouwer}. For a connected walk-regular graph $G$ of degree $r$, since $X=(rI-A_G+\frac{1}{n}J_{n\times n})^{-1}$ is a polynomial in $A_G$ and $(A_G^k)_{11}=\cdots=(A_G^k)_{nn}$ for any $k\geqslant0$, we have $X_{11}=\cdots=X_{nn}$. By Theorem \ref{thm6}, connected walk-regular graphs (including distance-regular graphs and vertex-transitive graphs) are resistance-regular.

\vspace{3mm}
Graphs with few distinct eigenvalues with respect to adjacency matrix and Laplacian matrix have interesting combinatorial properties \cite{Brouwer,Dam}. Next we consider graphs with few distinct R-eigenvalues.
\begin{theorem}
A connected graph with two distinct R-eigenvalues is a complete graph.
\end{theorem}
\begin{proof}
Let $G$ be a connected graph of order $n$ with two distinct R-eigenvalues $\lambda_1>\lambda_2$. Since $R_G$ is irreducible and nonnegative, $\lambda_1$ is simple. So $R_G-\lambda_2I$ has rank $1$. Since each diagonal entry of $R_G$ is $0$, we have $R_G-\lambda_2I=-\lambda_2J_{n\times n}$, $R_G=\lambda_2(I-J_{n\times n})$. Hence $G$ is resistance-regular. By part (3) of Theorem \ref{thm6}, $L_G$ has only one nonzero eigenvalue. So $G$ is complete.
\end{proof}
A \textit{strongly regular graph} with parameters $(n,k,\lambda,\mu)$ is a $k$-regular graph on $n$ vertices such that for every pair of adjacent vertices there are $\lambda$ vertices adjacent to both, and for every pair of non-adjacent vertices there are $\mu$ vertices adjacent to both. It is well known that a connected regular graph whose adjacency matrix has three distinct eigenvalues is strongly regular \cite{Brouwer}.
\begin{theorem}
A resistance-regular graph with three distinct R-eigenvalues is strongly regular.
\end{theorem}
\begin{proof}
Let $G$ be a resistance-regular graph of order $n$ with three distinct R-eigenvalues. By part (3) of Theorem \ref{thm6}, $L_G$ has two distinct nonzero eigenvalues. Let $\mu_1>\mu_2>0$ be two distinct nonzero eigenvalues of $L_G$. Since $(L_G-\mu_1I)(L_G-\mu_2I)$ has rank $1$ and row sum $\mu_1\mu_2$, we have
\begin{eqnarray*}
(L_G-\mu_1I)(L_G-\mu_2I)=\frac{\mu_1\mu_2}{n}J_{n\times n},
\end{eqnarray*}
\begin{equation}
L_G^2-(\mu_1+\mu_2)L_G+\mu_1\mu_2I=\frac{\mu_1\mu_2}{n}J_{n\times n}.\tag{3.1}
\end{equation}
By Lemma \ref{lem4}, we have
\begin{eqnarray*}
L_GL_G^+=I-\frac{1}{n}J_{n\times n},~L_G^2L_G^+=L_G(I-\frac{1}{n}J_{n\times n})=L_G,~J_{n\times n}L_G^+=0.
\end{eqnarray*}
We multiply $L_G^+$ on both side of (3.1), then
\begin{eqnarray*}
[L_G^2-(\mu_1+\mu_2)L_G+\mu_1\mu_2I]L_G^+=\frac{\mu_1\mu_2}{n}J_{n\times n}L_G^+,\\
L_G-(\mu_1+\mu_2)(I-\frac{1}{n}J_{n\times n})+\mu_1\mu_2L_G^+=0.
\end{eqnarray*}
From part (5) of Theorem \ref{thm6}, we know that $G$ is regular. Since $G$ is a connected regular graph and $L_G$ has two distinct nonzero eigenvalues, $G$ is strongly regular.
\end{proof}

\begin{theorem}
Let $G$ be a connected regular graph with diameter at least $2$. Then $G$ is strongly regular if and only if there exist $c_1,c_2$ such that $r_{ij}(G)=c_1$ for any adjacent vertices $i,j\in V(G)$, and $r_{ij}(G)=c_2$ for any non-adjacent vertices $i,j\in V(G)$.
\end{theorem}
\begin{proof}
Suppose that $G$ has $n$ vertices and $m$ edges. We need to prove that $G$ is strongly regular if and only if there exist $c_1,c_2$ such that
\begin{equation}
R_G=c_1A_G+c_2(J_{n\times n}-I-A_G).\tag{3.2}
\end{equation}
If $G$ is strongly regular, then $r_{ij}(G)$ depends only on the distance between $i$ and $j$ (see \cite{Biggs,Koolen}), i.e., the equation (3.2) holds.

If (3.2) holds, then by Lemma 8, we have $c_1=\frac{n-1}{m}$. Then $\sum_{j\in\Gamma(i)}r_{ij}(G)=\frac{(n-1)k}{m}=2-\frac{2}{n}$ for each $i\in V(G)$, where $k$ is the degree of regular graph $G$. By parts (4) and (6) of Theorem \ref{thm6}, there exists $c_0$ such that $c_0=X_{11}=\cdots=X_{nn}$, where $X=(L_G+\frac{1}{n}J_{n\times n})^{-1}=(kI+\frac{1}{n}J_{n\times n}-A_G)^{-1}$. By part (b) of Lemma \ref{lem6} and (3.2), we have
\begin{eqnarray*}
R_G=2c_0J_{n\times n}-2X=c_2(J_{n\times n}-I)+(c_1-c_2)A_G,
\end{eqnarray*}
\begin{equation}
2c_0J_{n\times n}X^{-1}-2I=c_2(J_{n\times n}-I)X^{-1}+(c_1-c_2)A_GX^{-1}.\tag{3.3}
\end{equation}
Since $G$ is regular, by the equation (3.3), there exist $a_1,a_2,a_3$ such that
\begin{equation}
(c_1-c_2)A_G^2+a_1A_G=a_2I+a_3J_{n\times n}.\tag{3.4}
\end{equation}
If $c_1=c_2$, then by (3.2), we get $R_G=c_1(J_{n\times n}-I)$. In this case, $R_G$ has two distinct eigenvalues. By Theorem 3.5, $G$ is complete, a contradiction to that the diameter of $G$ at least $2$. Hence $c_1\neq c_2$. By the equation (3.4), we know that there exist $\lambda,\mu$ such that $(A_G^2)_{ij}=\lambda$ for any adjacent vertices $i,j\in V(G)$, and $(A_G^2)_{ij}=\mu$ for any non-adjacent vertices $i,j\in V(G)$. Then $G$ is a strongly regular graph with parameters $(n,k,\lambda,\mu)$.
\end{proof}

\section{Concluding remarks}
In this paper, the relationship between the graph structure and resistance matrix is studied, and some spectral properties of the resistance matrix are obtained. We list some problems as follows.

(1) For a connected graph $G$, the structure of $G$ or $t(G)$ is determined by partial entries of $R_G$ under certain conditions (see Theorems \ref{thm2} and \ref{thm3}). Are there some other graph properties can be determined by partial entries of the resistance matrix?

(2) Some equivalent conditions for resistance-regular graphs are given in Theorem \ref{thm6}. From Remark 2, we know that connected walk-regular graphs are resistance-regular. It is natural to consider the problem``Which graphs are resistance-regular?". Note that a transmission-regular graph does not need to be a (degree) regular graph \cite{Aouchiche,Aouchiche13}. Is there a nonregular resistance-regular graph?

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection*{Acknowledgements}
This work is supported by the National Natural Science Foundation of China (No. 11371109), the Natural Science Foundation of the Heilongjiang Province (No. QC2014C001), and the Fundamental Research Funds for the Central Universities.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% \bibliographystyle{plain}
% \bibliography{myBibFile}
% If you use BibTeX to create a bibliography
% then copy and past the contents of your .bbl file into your .tex file

\begin{thebibliography}{10}

\bibitem{Aouchiche} M. Aouchiche and P. Hansen.  \newblock On a conjecture about the Szeged index.  \newblock {\em European J. Combin.}, 31:1662--1666, 2010.

\bibitem{Aouchiche13} M. Aouchiche and P. Hansen.  \newblock Two Laplacians for the distance matrix of a graph.  \newblock {\em Linear Algebra Appl.}, 439:21--33, 2013.

\bibitem{Bapat04} R.B. Bapat.  \newblock Resistance matrix of a weighted graph.  \newblock {\em MATCH Commun. Math. Comput. Chem.}, 50:73--82, 2004.

\bibitem{Bapat08} R.B. Bapat.  \newblock Resistance matrix and q-Laplacian of a unicyclic graph.  \newblock {\em Ramanujan Math. Soc. Lect. Notes Ser.}, 7:63--72, 2008.
    
\bibitem{GM} R.B. Bapat.  \newblock {\em Graphs and Matrices}.  \newblock Springer, London, 2010.

\bibitem{Bapat11} R.B. Bapat and S. Sivasubramanian.  \newblock Identities for minors of the Laplacian, resistance and distance matrices.  \newblock {\em Linear Algebra Appl.}, 435:1479--1489, 2011.
    
\bibitem{Ben} A. Ben-Israel and T.N.E. Greville.  \newblock {\em Generalized Inverses: Theory and Applications}.  \newblock Springer, New York, 2003.

\bibitem{Biggs} N. Biggs.  \newblock Potential theory on distance-regular graphs.  \newblock {\em Combin. Probab. Comput.}, 2:243--255, 1993.

\bibitem{Bollobas}B. Bollob\'{a}s and G. Brightwell. \newblock Random walks and electrical resistances in products of graphs.  \newblock {\em Discrete Appl. Math.}, 73:69--79, 1997.
    
\bibitem{Brouwer} A.E. Brouwer and W.H. Haemers.  \newblock {\em Spectra of Graphs}.  \newblock Springer, New York, 2012.

\bibitem{Bu} C. Bu, B. Yan, X. Zhou and J. Zhou. \newblock Resistance distance in subdivision-vertex join and subdivision-edge join of graphs.  \newblock {\em Linear Algebra Appl.}, 458:454--462, 2014.
    
\bibitem{Chen} H. Chen and F.J. Zhang. \newblock Resistance distance and the normalized Laplacian spectrum.  \newblock {\em Discrete Appl. Math.}, 155:654--661, 2007.
    
\bibitem{Dam} E.R. van Dam and W.H. Haemers. \newblock Graphs with constant $\mu$ and $\overline{\mu}$.  \newblock {\em Discrete Math.}, 182:293--307, 1998.

\bibitem{Foster} R.M. Foster.  \newblock The average impedance of an electrical network.  \newblock In {\em
    Contributions to Applied Mechanics}, pages 333--340. Ann Arbor, Michigan, 1949.
    
\bibitem{Graham78} R.L. Graham and L. Lov\'{a}sz. \newblock Distance matrix polynomials of trees.  \newblock {\em Adv. Math.}, 29:60--88, 1978.

\bibitem{Graham71} R.L. Graham and H.O. Pollack. \newblock On the addressing problem for loop switching.  \newblock {\em Bell Syst. Tech. J.}, 50:2495--2519, 1971.
\bibitem{GutmanMohar}I. Gutman and B. Mohar. \newblock The quasi-Wiener and the Kirchhoff indices coincide.  \newblock {\em J. Chem. Inf. Comput. Sci.}, 36:982--985, 1996.
    
\bibitem{GutmanXiao}I. Gutman and W.J. Xiao. \newblock Generalized inverse of the Laplacian matrix and some applications.  \newblock {\em Bull. Acad. Serbe Sci. Arts (Cl. Sci. Math. Natur.)}, 129:15--23, 2004.
    
\bibitem{Klein93}D.J. Klein and M. Randi\'{c}. \newblock Resistance distance.  \newblock {\em J. Math. Chem.}, 12:81--95, 1993.
    
\bibitem{Koolen}J.H. Koolen, G. Markowsky and J. Park. \newblock On electric resistances for distance-regular graphs.  \newblock {\em European J. Combin.}, 34:770--786, 2013.

\bibitem{Liu}X. Liu, J. Zhou and C. Bu. \newblock Resistance distance and Kirchhoff index of R-vertex join and R-edge join of two graphs.  \newblock {\em Discrete Appl. Math.}, 187:130--139, 2015.

\bibitem{Maden}A.D.G. Maden, I. Gutman and A.S. \c{C}evic. \newblock Bounds for resistance distance spectral radius.  \newblock {\em Hacet. J. Math. Stat.}, 42:43--50, 2013.

\bibitem{Merris}R. Merris. \newblock The distance spectrum of a tree.  \newblock {\em J. Graph Theory}, 14:365--369, 1990.

\bibitem{Sun}L. Sun, W. Wang, J. Zhou and C. Bu. \newblock Some results on resistance distances and resistance matrices.  \newblock {\em Linear and Multilinear Algebra}, 63:523--533, 2015.

\bibitem{XiaoGutman03}W.J. Xiao and I. Gutman. \newblock Resistance distance and Laplacian spectrum.  \newblock {\em Theor. Chem. Acc.}, 110:284--289, 2003.

\bibitem{YangKlein}Y.J. Yang and D.J. Klein. \newblock Resistance distance-based graph invariants of subdivisions and triangulations of graphs.  \newblock {\em Discrete Appl. Math.}, 181:260--274, 2015.

\bibitem{YangZhang}Y.J. Yang and H.P. Zhang. \newblock Some rules on resistance distance with applications.  \newblock {\em J. Phys. A: Math. Theor.}, 41:445203, 2008.

\bibitem{ZhouB}B. Zhou and N. Trinajsti\'{c}. \newblock On resistance-distance and Kirchhoff index.  \newblock {\em J. Math. Chem.}, 46:283--289, 2009.

\bibitem{Zhu}H.Y. Zhu, D.J. Klein and I. Lukovits. \newblock Extensions of the Wiener number.  \newblock {\em J. Chem. Inf. Comput. Sci.}, 36:420--428, 1996.

\end{thebibliography}

\end{document}
