\documentclass{amcjou}
\usepackage{graphicx}
\usepackage{array}
\newtheorem{theorem}{Theorem}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{definition}[theorem]{Definition}
%\newcommand{\qed}{\hfill\rule{1.4ex}{1.4ex}\vspace{1mm}\smallskip}
%\pagestyle{empty}
%\setlength{\textwidth}{16cm}
%\setlength{\textheight}{24cm}
%\addtolength{\hoffset}{-1.25cm}
%\addtolength{\voffset}{-2.5cm}
\begin{document}
\begin{frontmatter}
\titledata{Large sets of long distance equienergetic graphs}
{This work was supported by
the research program P1-0285 of the Slovenian Agency for Research and
the research grant 144015G of the Serbian Ministry of Science.}
\authordata{Dragan Stevanovi\'c}
{University of Primorska---FAMNIT, Glagolja\v ska 8, 6000 Koper, Slovenia, \\
and\\
Mathematical Institute, Serbian Academy of Science and Arts, \\
Knez Mihajlova 36, 11000 Belgrade, Serbia}
{dragan.stevanovic@upr.si}
{}
\keywords{Distance spectrum; Distance energy; Join; Regular graphs.}
\msc{05C50}
\begin{abstract}
Distance energy of a graph is a recent energy-type invariant,
defined as the absolute deviation of the eigenvalues of the distance matrix of the graph.
%It is a useful molecular descriptor in QSPR modelling,
%as demonstrated by Consonni and Todeschini in
%[MATCH Commun. Math. Comput. Chem. 60 (2008), 3--14].
Two graphs of the same order are said to be distance equienergetic
if they have equal distance energy,
while they have distinct spectra of their distance matrices.
Examples of pairs of distance equienergetic graphs appear in the literature already,
but most of them have diameter two only.
We describe here the distance spectrum of
a special composition of regular graphs, and,
as an application, we show that for any $n\geq 3$,
there exists a set of $n+1$ distance equienergetic graphs
which have order~$6n$ and diameter $n-1$ each.
\end{abstract}
\end{frontmatter}
\section{Introduction}
Let $G=(V,E)$ be a simple graph with $n$~vertices
$V=\{v_{1}, v_{2}, \dots, v_{n}\}$.
The energy of a graph $E=E(G)=\sum_{i=1}^{n}|\lambda_{i}|$,
where $\lambda_{i}$, $i=1,\dots,n$ are the eigenvalues
of an adjacency matrix of~$G$,
has well-known chemical applications~\cite{Gut1,Gut2,Gut3}.
Following the recent definition of the Laplacian energy in~\cite{GuZh},
it was observed that
other energy-type invariants can be defined as the
{\em absolute deviation of eigenvalues from their average value}
for a suitable graph matrix.
Let $d_{G}(v_{i},v_{j})$ denote the length of the shortest path
between the vertices $v_{i}$ and~$v_{j}$ of~$G$.
The matrix $D(G)=(d_{G}(v_{i},v_{j}))$, indexed by the vertices of~$G$, is
the {\em distance matrix} of~$G$.
Since its trace is zero, we can define
the {\em distance energy}~$DE(G)$ of~$G$ as
the sum of absolute values of the eigenvalues of the distance matrix~$D(G)$.
The distance energy, together with a handful of other invariants,
has been studied by Consonni and Todeschini~\cite{Todes}
for possible use in QSPR modelling.
Their study reveals that
the distance energy is a useful molecular descriptor:
the values $DE(G)$ or $DE(G)/n$ appear among the best univariate models
for the motor octane number of the octane isomers or
the water solubility of polychlorobiphenyls.
Two graphs of the same order are said to be distance equienergetic
if they have equal distance energy,
while they have distinct distance spectra.
Examples of distance equienergetic graphs appear
in the literature~\cite{InGV,RaGR,InGu},
but most of them have diameter two only.
We show here that new pairs of distance equienergetic graphs
can be constructed as compositions of regular graphs.
The particular composition that we consider is defined as follows.
Let $G_{i}=(V_{i},E_{i})$, $i=1,\dots,n$ be arbitrary finite graphs.
The {\em joined union} $G[G_{1},\dots,G_{n}]$ is
the graph $H=(W,F)$ with:
\begin{eqnarray*}
W &=& \bigcup_{i=1}^{n} V_{i}, \\
F &=& \bigcup_{i=1}^{n} E_{i} \cup
\bigcup_{(v_{i},v_{j})\in E} V_{i}\times V_{j}.
\end{eqnarray*}
In other words, the joined union is obtained
from the union of graphs $G_{1}$, \dots, $G_{n}$
by joining with an edge
each pair of a vertex from~$G_{i}$ and a vertex from~$G_{j}$
whenever $v_{i}$ and~$v_{j}$ are adjacent in~$G$.
For example, the usual join of two graphs $G$ and~$H$ is
a special case of the joined union: $K_{2}[G,H]$,
where $K_{2}$ is the complete graph on two vertices.
In the next section,
we describe the distance spectrum of the joined union of regular graphs
in the terms of their adjacency spectrum and
the eigenvalues of the auxiliary matrix, determined by the graph~$G$.
Then in Section 3
we show that the sets of graphs with equal distance energy can be constructed
as a joined union of regular graphs for which
all adjacency eigenvalues are at least~$-2$.
As an example, we show that for any $n\geq 3$,
there exists a set of $n+1$ distance equienergetic graphs
which have order $6n$ and diameter $n-1$ each.
\section{The distance spectrum of the joined union}
\begin{theorem}
\label{th-joinedu}
Let $G=(V,E)$ be a simple graph with $n$ vertices $v_{1},\dots,v_{n}$,
and for $i=1,\dots,n$,
let $G_{i}=(V_{i},E_{i})$ be an $r_{i}$-regular graph of order~$m_{i}$ and
eigenvalues of the adjacency matrix~$A_{G_{i}}$:
$\lambda_{i,1}=r_{i}\geq\lambda_{i,2}\geq\dots\geq\lambda_{i,m_{i}}$.
The distance spectrum of the joined union $G[G_{1},\dots,G_{n}]$
consists of the eigenvalues $-\lambda_{i,j}-2$
for $i=1,\dots,n$ and $j=2,3,\dots,m_{i}$ and
the eigenvalues of the matrix
\begin{equation}
\label{eq-auxmatrix}
\left[\begin{array}{ccccc}
2m_{1}-r_{1}-2 & d_{G}(v_{1},v_{2})m_{2} & d_{G}(v_{1},v_{3})m_{3} & \dots & d_{G}(v_{1},v_{n})m_{n} \\
d_{G}(v_{2},v_{1})m_{1} & 2m_{2}-r_{2}-2 & d_{G}(v_{2},v_{3})m_{3} & \dots & d_{G}(v_{2},v_{n})m_{n} \\
d_{G}(v_{3},v_{1})m_{1} & d_{G}(v_{3},v_{2})m_{2} & 2m_{3}-r_{3}-2 & \dots & d_{G}(v_{3},v_{n})m_{n} \\
\dots & \dots & \dots & & \dots \\
d_{G}(v_{n},v_{1})m_{1} & d_{G}(v_{n},v_{2})m_{2} & d_{G}(v_{n},v_{3})m_{3} & \dots & 2m_{n}-r_{n}-2 \\
\end{array}\right].
\end{equation}
\end{theorem}
\medskip\noindent
{\bf Proof}.\quad
The distance matrix $D(H)$ of the joined union $H=G[G_{1},\dots,G_{n}]$
is a block matrix of the form
$$
D(H) = \left[\begin{array}{cccc}
2(J-I)-A_{G_{1}} & d_{G}(v_{1},v_{2})J & \dots & d_{G}(v_{1},v_{n})J \\
d_{G}(v_{2},v_{1})J & 2(J-I)-A_{G_{2}} & \dots & d_{G}(v_{2},v_{n})J \\
\dots & \dots & \dots & \dots \\
d_{G}(v_{n},v_{1})J & d_{G}(v_{n},v_{2})J & \dots & 2(J-I)-A_{G_{n}}
\end{array}\right],
$$
where $I$ and $J$ are the unit and the all-one matrices of corresponding orders.
First, let $i\in\{1,\dots,n\}$.
As a regular graph,
$G_{i}$ has all-one vector~$j$ as an eigenvector of the adjacency matrix~$A_{G_{i}}$
corresponding to the eigenvalue~$r_{i}$,
while other eigenvectors are orthogonal to~$j$.
(Note that $G_{i}$ need not be connected,
and thus, $r_{i}$ need not be a simple eigenvalue of~$G_{i}$.)
Let $\lambda$ be an arbitrary eigenvalue of~$A_{G_{i}}$
with the corresponding eigenvector~$x$, such that $j^{T}x=0$.
Then the vector~$y$, given by
$$
y_{u}=\left\{\begin{array}{rl}x_{u}, & u\in V_{i}\\
0, & u\notin V_{i}\end{array}\right.
$$
is an eigenvector of~$D(H)$ corresponding to the eigenvalue $-\lambda-2$:
since $y$ has zeros at coordinates corresponding to $\bigcup_{j\neq i} V_{j}$,
we have
\begin{eqnarray*}
D(H)y
&=& \left[\begin{array}{c}
d_{G}(v_{1},v_{i})J\\
\dots \\
d_{G}(v_{i-1},v_{i})J\\
2(J-I)-A_{G_{i}} \\
d_{G}(v_{i+1},v_{i})J\\
\dots \\
d_{G}(v_{n},v_{i})J
\end{array}\right]x
= \left(\begin{array}{c}
d_{G}(v_{1},v_{i})Jx\\
\dots \\
d_{G}(v_{i-1},v_{i})Jx\\
2Jx-2x-A_{G_{i}}x \\
d_{G}(v_{i+1},v_{i})Jx\\
\dots \\
d_{G}(v_{n},v_{i})Jx
\end{array}\right)
= -(2+\lambda)y.
\end{eqnarray*}
There exists a total of $\left(\sum_{i=1}^{n} |V_{i}|\right)-n$
mutually orthogonal eigenvectors of~$D(H)$ of this form.
Moreover, they are all orthogonal to the vectors
$$
(j^{i})_{u}=\left\{\begin{array}{rl}1, & u\in V_{i}\\
0, & u\notin V_{i}\end{array}\right.
\qquad i=1,\dots,n.
$$
In particular,
this means that the vectors $j^{1}$, $j^{2}$, \dots, $j^{n}$ are
spanned by the $n$~remaining eigenvectors of~$D(H)$,
which, due to the fact that
$j^{1}$, $j^{2}$, \dots, $j^{n}$ are linearly independent, implies that
the remaining eigenvectors of~$D(H)$ have the form
$\sum_{i=1}^{n} \alpha_{i} j^{i}$ for suitable coefficients $\alpha_{1}$,\dots,$\alpha_{n}$.
Let $\nu$ be an eigenvalue of~$D(H)$
with an eigenvector of the form $\sum_{i=1}^{n} \alpha_{i} j^{i}$.
Then from $A_{G_{i}} j = r_{i}j$, $i=1,\dots,n$, we have
\begin{eqnarray*}
D(H)\sum_{i=1}^{n} \alpha_{i} j^{i}
&=& \sum_{i=1}^{n} \alpha_{i} D(H)j^{i}
=\sum_{i=1}^{n} \alpha_{i}
\left[\begin{array}{c}
d_{G}(v_{1},v_{i})J\\
\dots \\
d_{G}(v_{i-1},v_{i})J\\
2(J-I)-A_{G_{i}} \\
d_{G}(v_{i+1},v_{i})J\\
\dots \\
d_{G}(v_{n},v_{i})J
\end{array}\right]j \\
&=& \sum_{i=1}^{n} \alpha_{i}
\left((2m_{i}-r_{i}-2)j^{i}+\sum_{k\neq i}d_{G}(v_{k},v_{i})m_{i}j^{k}\right) \\
&=& \sum_{i=1}^{n}
\left((2m_{i}-r_{i}-2)\alpha_{i} + \sum_{k\neq i}d_{G}(v_{i},v_{k})m_{k}\alpha_{k}\right)j^{i}
=\nu \sum_{i=1}^{n} \alpha_{i} j^{i}.
\end{eqnarray*}
From the last equality
we get the system of equations in $\alpha_{1}$, \dots, $\alpha_{n}$:
\begin{equation}
\label{eq-system}
(2m_{i}-r_{i}-2-\nu)\alpha_{i} + \sum_{k\neq i}d_{G}(v_{i},v_{k})m_{k}\alpha_{k}=0,
\qquad i=1,\dots,n,
\end{equation}
which may have a nontrivial solution
only if its determinant is equal to zero,
i.e., only if $\nu$ is an eigenvalue of~(\ref{eq-auxmatrix}).
Further, it is obvious from above that
any nontrivial solution of~(\ref{eq-system}) forms
an eigenvector of~$D(H)$ corresponding to eigenvalue~$\nu$.
Since all $n$~remaining eigenvectors of~$D(H)$ must be formed in this way,
we conclude that each eigenvalue of~(\ref{eq-auxmatrix})
is an eigenvalue of~$D(H)$ as well.
\qed
\medskip
For example, let $G$ be an $r_{1}$-regular graph of order~$n_{1}$
and the eigenvalues $\lambda_{1}=r_{1}\geq\lambda_{2}\geq\dots\geq\lambda_{n_{1}}$
of its adjacency matrix, and
let $H$ be an $r_{2}$-regular graph of order~$n_{2}$
and the eigenvalues $\mu_{1}=r_{2}\geq\mu_{2}\geq\dots\geq\mu_{n_{2}}$
of its adjacency matrix.
From the previous theorem,
the distance spectrum of the join $G\nabla H$, which is the same as $K_{2}[G,H]$,
consists of the eigenvalues $-\lambda_{i}-2$ for $i=2,\dots,n_{1}$,
then $-\mu_{j}-2$ for $j=2,\dots,n_{2}$, and
two eigenvalues $(m_1-r_1/2)+(m_2-r_2/2)-2 \pm \sqrt{((m_{1}-r_{1}/2)-(m_2-r_{2}/2))^{2}+m_{1}m_{2}}$.
\section{Long distance equienergetic graphs}
Sets of graphs with equal distance energy can be constructed as a joined union of
regular graphs for which all adjacency eigenvalues are at least~$-2$,
when the corresponding eigenvalues~$-\lambda-2$
of the distance matrix are always negative.
Such graphs are, for example,
the empty graph $\overline K_{m}$,
the complete graph $K_{m}$,
the cycle $C_{m}$,
as well as regular line graphs~\cite{CvDS}
(which are itself line graphs of regular or semiregular graphs).
For such graphs, we can use the well-known fact that
the sum of all adjacency eigenvalues is~$0$ (see, e.g., \cite{CvDS})
in order to determine the distance energy of the joined union.
\begin{theorem}
\label{co-dejoinedu}
Let $G=(V,E)$ be a simple graph with $n$ vertices $v_{1},\dots,v_{n}$,
and for $i=1,\dots,n$,
let $G_{i}$ and $H_{i}$ be $r_{i}$-regular graphs of order~$m_{i}$
whose smallest eigenvalue of the adjacency matrix is at least~$-2$.
Then
$$
DE(G[G_{1},\dots,G_{n}])=DE(G[H_{1},\dots,H_{n}]).
$$
\end{theorem}
\medskip\noindent
{\bf Proof.}\quad
Since graphs $G_{i}$ and $H_{i}$, $i=1,\dots,n$,
have the same order~$m_{i}$ and the degree~$r_{i}$,
both joined unions $G[G_{1},\dots,G_{n}]$ and $G[H_{1},\dots,H_{n}]$ have
the same auxiliary matrix
$$
\left[\begin{array}{ccccc}
2m_{1}-r_{1}-2 & d_{G}(v_{1},v_{2})m_{2} & d_{G}(v_{1},v_{3})m_{3} & \dots & d_{G}(v_{1},v_{n})m_{n} \\
d_{G}(v_{2},v_{1})m_{1} & 2m_{2}-r_{2}-2 & d_{G}(v_{2},v_{3})m_{3} & \dots & d_{G}(v_{2},v_{n})m_{n} \\
d_{G}(v_{3},v_{1})m_{1} & d_{G}(v_{3},v_{2})m_{2} & 2m_{3}-r_{3}-2 & \dots & d_{G}(v_{3},v_{n})m_{n} \\
\dots & \dots & \dots & & \dots \\
d_{G}(v_{n},v_{1})m_{1} & d_{G}(v_{n},v_{2})m_{2} & d_{G}(v_{n},v_{3})m_{3} & \dots & 2m_{n}-r_{n}-2 \\
\end{array}\right],
$$
so that the corresponding part of their distance spectra is equal,
and adds the same amount~$M$ to the distance energy of joined unions.
Next, for $i=1,\dots,n$,
let $G_{i}$ has eigenvalues of the adjacency matrix
$\lambda_{i,1}=r_{i}\geq\lambda_{i,2}\geq\dots\geq\lambda_{i,m_{i}}\geq-2$,
and let $H_{i}$ has eigenvalues of the adjacency matrix
$\mu_{i,1}=r_{i}\geq\mu_{i,2}\geq\dots\geq\mu_{i,m_{i}}\geq-2$.
The remaining distance eigenvalues of $G[G_{1},\dots,G_{n}]$ are
of the form $-\lambda_{i,j}-2$ for $i=1,\dots,n$ and $j=2,\dots,m_{i}$.
Since $\lambda_{i,j}\geq -2$ we have that $|-\lambda_{i,j}-2|=\lambda_{i,j}+2$.
Then from $\sum_{j=1}^{m_{i}} \lambda_{i,j}=0$, we get
$$
\sum_{i=1}^{n} \sum_{j=2}^{m_{i}} |-\lambda_{i,j}-2|
= \sum_{i=1}^{n} \left(\sum_{j=2}^{m_{i}} \lambda_{i,j}\right)+2(m_{i}-1)
= \sum_{i=1}^{n} -r_{i}+2(m_{i}-1).
$$
For the remaining distance eigenvalues $-\mu_{i,j}-2$
of $G[H_{1},\dots,H_{n}]$, $i=1,\dots,n$, $j=2,\dots,m_{i}$,
we similarly get
$$
\sum_{i=1}^{n} \sum_{j=2}^{m_{i}} |-\mu_{i,j}-2|
% = \sum_{i=1}^{n} \left(\sum_{j=2}^{m_{i}} \mu_{i,j}\right)+2(m_{i}-1)
= \sum_{i=1}^{n} -r_{i}+2(m_{i}-1).
$$
Therefore,
$$
DE(G[G_{1},\dots,G_{n}])
=M+\sum_{i=1}^{n} 2m_{i}-r_{i}-2
=DE(G[H_{1},\dots,H_{n}]).
\qquad\qed
$$
In the above theorem,
the graphs $G[G_{1},\dots,G_{n}]$ and $G[H_{1},\dots,H_{n}]$ share
the auxiliary matrix and have a common part of the distance spectra.
Therefore, in order for these graphs to be distance equienergetic,
it is necessary that
the union of adjacency spectra of $G_{1},\dots,G_{n}$,
with vertex degree being deleted from each adjacency spectrum, is
different from the union of adjacency spectra of $H_{1},\dots,H_{n}$.
\subsubsection*{Example}
Let $P_{n}$ and $C_{n}$ be the path and the cycle of order~$n$, respectively.
As an application of Theorem~\ref{co-dejoinedu},
we observe that, for each $n\geq 3$,
the following is a set of
$n+1$ distance equienergetic graphs of order~$6n$ and diameter~$n-1$:
\begin{eqnarray*}
\{ && P_{n}[C_{6},C_{6},\dots,C_{6},C_{6}], \\
&& P_{n}[C_{6},C_{6},\dots,C_{6},C_{3}\cup C_{3}], \\
&& P_{n}[C_{6},C_{6},\dots,C_{3}\cup C_{3},C_{3}\cup C_{3}], \\
&& \dots, \\
&& P_{n}[C_{6},C_{3}\cup C_{3},\dots,C_{3}\cup C_{3},C_{3}\cup C_{3}], \\
&& P_{n}[C_{3}\cup C_{3},C_{3}\cup C_{3},\dots,C_{3}\cup C_{3},C_{3}\cup C_{3}]\qquad\}.
\end{eqnarray*}
Since both $C_{6}$ and $C_{3}\cup C_{3}$ are 2-regular graphs of order 6,
all graphs above have the same auxiliary matrix~(\ref{eq-auxmatrix}),
and thus, share this part of the distance spectra.
The remaining part of the distance spectrum of
%the joined union
%containing $k$~copies of~$C_{6}$ and $n-k$~copies of~$C_{3}\cup C_{3}$
$P_{n}[\underbrace{C_{6},\dots,C_{6}}_{k},\underbrace{C_{3}\cup C_{3},\dots,C_{3}\cup C_{3}}_{n-k}]$,
$0\leq k\leq n$, is
$$
[-4^{n-k},-3^{2k},-1^{4n-2k},0^{k}],
$$
with exponents denoting the multiplicities,
showing that no two graphs above are cospectral.
\begin{thebibliography}{xx}
\bibitem{DEGu} A.A. Dobrynin, R. Entringer, I. Gutman,
{\em Wiener Index of Trees: Theory and Applications},
Acta Appl. Math. 66 (2001), 211--249.
\bibitem{Gut0} I.~Gutman,
{\em The energy of a graph},
Ber. Math.ÐStatist. Sekt. Forschungsz. Graz 103 (1978), 1-Ð22.
\bibitem{Gut1} I.~Gutman,
{\em Total $\pi$-electron energy of benzenoid hydrocarbons},
Topics Curr. Chem. 162 (1992), 29--63.
\bibitem{Gut2} I.~Gutman,
{\em The energy of a graph: old and new results},
in: A.~Betten, A.~Kohnert, R.~Laue, A.~Wassermann (eds.),
Algebraic Combinatorics and Applications,
Springer-Verlag, Berlin, 2001, pp.~196--211.
\bibitem{Gut3} I.~Gutman,
{\em Topology and stability of conjugated hydrocarbons.
The dependence of total $\pi$-electron energy on molecular topology},
J.~Serb. Chem. Soc. 70 (2005), 441--456.
\bibitem{GuZh} I.~Gutman, B.~Zhou,
{\em Laplacian energy of a graph},
Linear Algebra Appl. 414 (2006), 29--37.
\bibitem{Todes} V.~Consonni, R.~Todeschini,
{\em New Spectral Indices for Molecule Description},
MATCH Commun. Math. Comput. Chem. 60 (2008), 3--14.
\bibitem{InGV} G.~Indulal, I.~Gutman, A.~Vijayakumar,
{\em On Distance Energy of Graphs},
MATCH Commun. Math. Comput. Chem. 60 (2008), 461--472.
\bibitem{RaGR} H.S.~Ramane, I.~Gutman, D.S.~Revankar,
{\em Distance Equienergetic Graphs},
MATCH Commun. Math. Comput. Chem. 60 (2008), 473--484.
\bibitem{InGu} G.~Indulal, I.~Gutman,
{\em On the distance spectra of some graphs},
Math. Commun.---Univ. of Croatia 13 (2008), 123--131.
\bibitem{CvDS} D.~Cvetkovi\'c, M.~Doob and H.~Sachs,
\newblock Spectra of Graphs---Theory and Application,
\newblock 3rd edition, Johann Ambrosius Barth Verlag, 1995.
\end{thebibliography}
\end{document}