% EJC papers *must* begin with the following two lines.
\documentclass[12pt]{article}
\usepackage{e-jc}
% Please remove all commands that change parameters such as
% margins or page sizes.
% Packages amssymb and amsthm are already loaded.
% We recommend these AMS packages:
\usepackage{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}
%%% authors' packages
\usepackage{amsthm}
\usepackage{bm}
\usepackage{enumitem}
\usepackage{cite}
%%% authors' setting for TikZ
\usepackage{tikz}
\tikzset{every node/.style={draw,circle,inner sep=2pt}}
\usetikzlibrary{matrix}
% Theorem-like environments that are declared in the style file are:
% theorem, lemma, corollary, proposition, fact, observation, claim,
% definition, example, conjecture, open, problem, question, remark, note
%%% authors' abbreviation of Theorem-like environments
\newenvironment{thm}{\begin{theorem}}{\end{theorem}}
\newenvironment{lem}{\begin{lemma}}{\end{lemma}}
\newenvironment{cor}{\begin{corollary}}{\end{corollary}}
\newenvironment{prop}{\begin{proposition}}{\end{proposition}}
\newenvironment{obs}{\begin{observation}}{\end{observation}}
\newenvironment{defn}{\begin{definition}}{\end{definition}}
\newenvironment{exam}{\begin{example}}{\end{example}}
\newenvironment{rem}{\begin{remark}}{\end{remark}}
%%% authors' old Theorem-like settings
%\theoremstyle{plain}
%\newtheorem{thm}{Theorem}[section]
%\newtheorem{cor}[thm]{Corollary}
%\newtheorem{lem}[thm]{Lemma}
%\newtheorem{prop}[thm]{Proposition}
%\newtheorem{remark}[thm]{Remark}
%\newtheorem{conj}[thm]{Conjecture}
%\newtheorem{prob}[thm]{Problem}
%\theoremstyle{definition}
%\newtheorem{defn}[thm]{Definition}
%\newtheorem{exam}[thm]{Example}
%\newtheorem{rem}[thm]{Remark}
%\newtheorem{obs}[thm]{Observation}
%\theoremstyle{remark}
%\numberwithin{equation}{section}
%%% authors' macros
\newcommand{\calD}{\mathcal{D}}
\newcommand{\cof}{\operatorname{cof}}
\newcommand{\cofD}{{\textstyle\cof_{\calD}}}
\newcommand{\detD}{{\textstyle\det_{\calD}}}
\newcommand{\inertia}{\operatorname{inertia}}
\newcommand{\inertiaD}{\inertia_{\calD}}
\newcommand{\CP}[1]{\mathcal{CP}_{#1}}
\newcommand{\lrfloor}[1]{\left\lfloor #1\right\rfloor}
\newcommand{\lrceil}[1]{\left\lceil #1\right\rceil}
\newcommand{\br}{{\bf r}}
\newcommand{\bc}{{\bf c}}
\newcommand{\bb}{{\bf b}}
\newcommand{\be}{{\bf e}}
\newcommand{\bd}{{\bf d}}
\newcommand{\bx}{{\bf x}}
\newcommand{\by}{{\bf y}}
\newcommand{\bphi}{\bm{\phi}}
\newcommand{\bzero}{{\bf 0}}
\newcommand{\bone}{{\bf 1}}
\newcommand{\trans}{^\top}
\newcommand{\floating}[1]{\smash{\raisebox{.5\normalbaselineskip}{#1}}}
\newcommand{\sign}{\operatorname{sign}}
\newcommand{\dist}{\operatorname{dist}}
\newcommand{\dunion}{\mathbin{\dot{\cup}}}
%%%%%%%%%%%%%METADATA%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Give the submission and acceptance dates in the format shown.
% The editors will insert the publication date in the third argument.
\dateline{Jul 20, 2018}{Nov 17, 2018}{TBD}
% Give one or more subject codes separated by commas.
% Codes are available from http://www.ams.org/mathscinet/freeTools.html
\MSC{05C50, 05C12, 15A15}
% Uncomment exactly one of the following copyright statements. Alternatively,
% you can write your own copyright statement subject to the approval of the journal.
% See https://creativecommons.org/licenses/ for a full explanation of the
% Creative Commons licenses.
%
% We strongly recommend CC BY-ND or CC BY. Both these licenses allow others
% to freely distribute your work while giving credit to you. The difference between
% them is that CC BY-ND only allows distribution unchanged and in whole, while
% CC BY also allows remixing, tweaking and building upon your work.
%
% One author:
%\Copyright{The author.}
%\Copyright{The author. Released under the CC BY license (International 4.0).}
%\Copyright{The author. Released under the CC BY-ND license (International 4.0).}
% More than one author:
%\Copyright{The authors.}
\Copyright{The authors. Released under the CC BY license (International 4.0).}
%\Copyright{ The authors. Released under the CC BY-ND license (International 4.0).}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% If needed, include a line break (\\) at an appropriate place in the title.
\title{Graph families with constant distance determinant}
% Input author, affiliation, address and support information as follows;
% The address should include the country, but does not have to include
% the street address. Give at least one email address.
\author{Yen-Jen Cheng
%\thanks{Supported by NASA grant ABC123.}
\\
\small Department of Mathematics\\[-0.8ex]
\small National Taiwan Normal University\\[-0.8ex]
\small Taipei 106, Taiwan\\
\small\tt yjc7755@gmail.com \\
\and
Jephian C.-H. Lin\thanks{Corresponding author. %Partially supported by MOST grant 107-2115-M-110-008-MY2.
}\\
\small Department of Applied Mathematics\\[-0.8ex]
\small National Sun Yat-sen University\\[-0.8ex]
\small Kaohsiung 80424, Taiwan\\
\small\tt jephianlin@gmail.com}
%%% authors' old setting for \author
%\author{Yen-Jen Cheng\footnotemark[2] \and Jephian C.-H. Lin\footnotemark[3]}
%\renewcommand{\thefootnote}{\fnsymbol{footnote}}
%\footnotetext[2]{
% Department of Mathematics, National Taiwan Normal University, Taipei 106, Taiwan
% }
%\footnotetext[3]{
% Department of Applied Mathematics, National Sun Yat-sen University, Kaohsiung 80424, Taiwan
% }
%\renewcommand{\thefootnote}{\arabic{footnote}}
%\date{\today}
\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 may be distributed without the rest of the
% paper so it must be entirely self-contained. Try to include all words
% and phrases that someone might search for when looking for your paper.
\begin{abstract}
This paper introduces a new class of graphs, the clique paths (or the CP graphs), and shows that their distance determinant and distance inertia are independent of their structures. The CP graphs include the family of linear $2$-trees. When a graph is attached with a CP graph, it is shown that the distance determinant and the distance inertia are also independent of the structure of the CP graph. Applications to the addressing problem proposed by Graham and Pollak in 1971 are given.
%
%%% authors' old MSC
%\medskip
%\noindent
%{\bf MSC:}
%\begin{AMS}
%%%05C50, %%Graphs and linear algebra (matrices, eigenvalues, etc.)
%%%05C12, %Distance in graphs
%%%15A15 %Determinants, permanents, other special matrix functions
%05C57, %%Games on graphs
%05C83, %%Graph minors
%15A03, %%Vector spaces, linear dependence, rank
%15A18, %%Eigenvalues, singular values, and eigenvectors
%15A29, %%Inverse problems
%15B35, %%Sign pattern matrices
%15B57. %%Hermitian, skew-Hermitian, and related matrices
%58C15, %%Implicit function theorems; global Newton methods
%65F18. %%Inverse eigenvalue problems
%\end{AMS}
%
%\medskip
%\noindent
%{\bf Keywords:}
%CP graph, linear $2$-tree, distance matrix, determinant, inertia%, cofactor
\end{abstract}
\section{Introduction}
\label{sec:intro}
On a simple connected graph $G$, the distance between two vertices $i$ and $j$ is the length of the shortest path between them, denoted as $\dist_G(i,j)$. The \emph{distance matrix} of a connected graph $G$ is
\[\calD(G)=\begin{bmatrix}\dist_G(i,j)\end{bmatrix}.\]
Various properties of the distance matrix of a graph have been studied intensively; see \cite{AH14} for a survey and the references therein.
Suppose $A$ is an $n\times n$ symmetric matrix. The \emph{inertia} $\inertia(A)$ of $A$ is the triple $(n_+,n_-,n_0)$, where $n_+$, $n_-$, and $n_0$ are the number of positive, negative, and zero eigenvalues of $A$, respectively. The \emph{$i,j$-cofactor} of $A$ is $(-1)^{i+j}\det( A(i|j))$, where $A(i|j)$ is the matrix obtained from $A$ by removing the $i$-th row and the $j$-th column. Let $\cof(A)$ be the sum of all cofactors. That is,
\[\cof(A)=\sum_{i=1}^n\sum_{j=1}^n (-1)^{i+j} \det (A(i|j)).\]
When $A$ is invertible, $\cof (A)=\det(A)(\bone\trans A^{-1}\bone)$, where $\bone$ is the all-ones vector. For convenience, we write $\detD(G)=\det(\calD(G))$, $\inertiaD(G)=\inertia(\calD(G))$, and $\cofD(G)=\cof (\calD(G))$.
In 1971, Graham and Pollak~\cite{GP71} proved that $\detD(T)=(-1)^{n-1}(n-1)2^{n-2}$ for any tree $T$ on $n$ vertices, so the distance determinant is independent of the structure of the tree. (In 2006, a simple proof of this result was given in \cite{YY06}.) Graham, Hoffman, and Hosoya~\cite{GHH77} then gave a generalization by showing both $\detD(G)$ and $\cofD(G)$ are determined by $\detD(G_i)$ and $\cofD(G_i)$ for $i=1,\ldots,k$, where $G_i$'s are the blocks of $G$. (A \emph{block} of a graph is a maximal induced subgraph of $G$ without a cut-vertex.) This means $\detD(G)$ and $\cofD(G)$ are independent of how the blocks are attached to each other. Several variants of the distance matrices were considered, such as the weighted distance matrix \cite{BKN05}, the $q$-analog and the $q$-exponential distance matrix \cite{BLP06,YY07}, and the determinant of these matrices of a tree are shown to be independent of the structure of the tree. These results gave elegant formulas for various types the distance matrices of a tree, or graphs with cut-vertices. A natural question is: Can the distance determinant be a constant for other families of graphs with tree-like structure, or graphs without a cut-vertex?
\begin{figure}[h]
\begin{center}
\begin{tikzpicture}
\node (0) at (0,0) {};
\node (1) at (1,0) {};
\node (2) at (2,0) {};
\node (3) at (0.5,0.866) {};
\node (4) at (1.5,0.866) {};
\node (5) at (1,1.732) {};
\draw (0) -- (1) -- (2) -- (4) -- (5) -- (3) -- (0);
\draw (1) -- (4) -- (3) -- (1);
\node[draw=none,rectangle] at (1,-0.5) {$G_1$};
\end{tikzpicture}
\hfil
\begin{tikzpicture}
\node (0) at (0,0) {};
\node (1) at (1,0) {};
\node (2) at (2,0) {};
\node (3) at (0.5,-0.866) {};
\node (4) at (1.5,-0.866) {};
\node (5) at (2.5,-0.866) {};
\draw (0) -- (1) -- (2) -- (5) -- (4) -- (3) -- (0);
\draw (3) -- (1) -- (4) -- (2);
\node[draw=none,rectangle] at (1.25,-1.366) {$G_2$};
\end{tikzpicture}
\hfil
\begin{tikzpicture}
\node (0) at (0,0) {};
\node (1) at (1,0) {};
\node (2) at (2,0) {};
\node (3) at (0.5,-0.866) {};
\node (4) at (1.5,-0.866) {};
\node (5) at (1.5,0.866) {};
\draw (0) -- (1) -- (2) -- (4) -- (3) -- (0);
\draw (1) -- (4);
\draw (3) -- (1) -- (5) -- (2);
\node[draw=none,rectangle] at (1,-1.366) {$G_3$};
\end{tikzpicture}
\end{center}
\caption{Three $2$-trees}
\label{threektrees}
\end{figure}
The family of $k$-trees is an immediate candidate to answer the question. A \emph{$k$-tree} on $n$ vertices is constructed by the following process: Start with a $k$-clique on vertices $\{1,\ldots,k\}$. For $j=k+1,\ldots, n$, add a new vertex $j$ and join it with an existing $k$-clique. A \emph{linear $k$-tree} is a $k$-tree where each added vertex $j$ is joined with an existing $k$-clique that contains vertex $j-1$. Note that a $1$-tree is a tree, and a linear $1$-tree is a path. Figure~\ref{threektrees} shows three $2$-trees $G_1$, $G_2$, and $G_3$ of the same order. By direct computation, $\detD(G_1)=-8$ and $\detD(G_2)=\detD(G_3)=-9$. It seems giving a negative answer to the questions. However, it also suggests that the family of linear $2$-trees is probably promising.
Indeed, Corollary~\ref{cor:lineartwotree} shows every linear $2$-tree on $n$ vertices has the same distance determinant. (Example~\ref{ex:threetrees} shows that the same behavior does not occur for linear $3$-trees.) Section~\ref{sec:twoCP} defines a $2$-clique path, which is obtained by gluing the edges from several cliques into a path-like structure; the family of linear $2$-trees is a special case of the family of $2$-clique paths. Theorem~\ref{thm:2cpdetinertia} shows the distance determinant only depends on the size of each clique. In fact, the $2$-clique paths belong to a bigger family of graphs, the clique paths (or the CP graphs); see Figure~\ref{G1G2} for some examples of the CP graphs. Section~\ref{sec:CP} defines the CP graphs and shows that the distance determinant of the CP graphs only depends on the input parameters; the distance inertia and $\cofD(G)$ are also considered. Section~\ref{sec:attaching} shows gluing the initial edges of two different CP graphs to any given connected graph will give two new graphs with the same distance determinant.
Finally, we turn our attention to the addressing problem. Graham and Pollak~\cite{GP71} proposed an \emph{addressing scheme} on a graph $G$ as an assignment of strings in $\{0,1,*\}$ of length $d$ to each vertex such that the distance between any pair of vertices is equal to the Hamming distance of their strings, ignoring the digits of $*$. Let $N(G)$ be the minimum $d$ so that there is an addressing scheme on $G$. In \cite{GP71}, it was shown that
\[N(G)\geq \max\{n_+,n_-\},\]
where $\inertiaD(G)=(n_+,n_-,n_0)$, and was conjectured that $N(G)\leq n-1$ for any graph of order $n$.
This conjecture was then proved by Winkler~\cite{Winkler83} in 1983. If $G$ is a tree or a clique tree on $n\geq 2$ vertices, then it is known \cite{GP71,LLL15} that $n_-=N(G)=n-1$. Here a \emph{clique tree} (or a \emph{block graph} in some literature) is a graph whose blocks are cliques. Section~\ref{sec:address} shows that $\inertiaD(G)=(1,n-1,0)$ and $N(G)=n-1$ for any graph $G$ whose blocks are $2$-clique paths, generalizing the known results.
For convenience, we use weighted graphs to record matrices. A \emph{weighted graph} is a simple graph whose vertices and edges are associated with weights. The weight $w(i,j)$ of an edge $\{i,j\}$ is nonzero, and the weight $w(i)$ of a vertex can possibly be zero. The \emph{weighted adjacency matrix} of a weighted graph is $\begin{bmatrix} a_{i,j}\end{bmatrix}$ with
\[\begin{cases}
a_{i,j}=w(i,j) & \text{if }i\neq j,\\
a_{i,j}=w(i) & \text{if }i=j.
\end{cases}\]
The notation $\{\be_i\}_{i=1}^n$ stands for the standard basis of $\mathbb{R}^n$. Define $[n]=\{1,\ldots, n\}$ and $[a,b]=\{a,a+1,\ldots, b\}$. When $a>b$, $[a,b]=\varnothing$.
\section{The CP graphs and their distance matrices}
\label{sec:CP}
A sequence of integers $q_1,\ldots,q_n$ ($n\geq 2$) is called \emph{non-leaping} if $q_1=0$, $q_2=1$, and $2\leq q_k\leq q_{k-1}+1$ for any $k=3,\ldots, n$. (So $q_3=2$ if $n\geq 3$.)
For a given non-leaping sequence, a \emph{neighborhood sequence} is a sequence of sets $W_1,\ldots, W_n$ with the following properties:
\begin{enumerate}
\item $W_1=\varnothing$;
\item $W_2=\{1\}$;
\item for each $k\geq 3$, $|W_k|=q_k$ and $W_k=\{a_k\}\cup [b_k,k-1]$, where $b_k=k-q_k+1$ and $a_k\in W_{k-1}$ with $a_ka_k$. If $aa_k$, then $a$ is adjacent to $a_k$ by Lemma~\ref{abclem} since $\{a_k,k\}\in E(G)$ and $a_ki\geq 3$, then $a_i,a_{i-1}a_k$. If $a\notin V(G)$, then $b\in\{1,2\}$; by the assumption that $k$ is not adjacent to both $1$ and $2$, the only neighbor of $k$ in $\{1,2\}$ is $a_k=b$, a contradiction.
Suppose $a\in V(G)$ and $b>a_k$. Either $a