# Remoteness of graphs with given size and connectivity constraints

Peter Dankelmann Financial support by the South Africa National Research
Foundation is greatly acknowledged. University of Johannesburg
South Africa  Sonwabile Mafunda  University of Johannesburg
South Africa  Soka University of America
USA  Sufiyan Mallu The results of this paper form part of this authors PhD
thesis.Financial support by the South Africa National Research Foundation is
greatly acknowledged. University of Johannesburg
South Africa

###### Abstract

Let $G$ be a finite, simple connected graph. The average distance of a vertex
$v$ of $G$ is the arithmetic mean of the distances from $v$ to all other
vertices of $G$. The remoteness $\rho(G)$ of $G$ is the maximum of the average
distances of the vertices of $G$.

In this paper, we give sharp upper bounds on the remoteness of a graph of
given order, connectivity and size. We also obtain corresponding bound s for
$2$-edge-connected and $3$-edge-connected graphs, and bounds in terms of order
and size for triangle-free graphs.

Keywords: Remoteness; transmission; average distance; size; vertex-
connectivity, edge-connectivity
MSC-class: 05C12

##  1 Introduction

In this paper we consider finite, connected graphs with no loops or multiple
edges. In a graph $G$ of order at least two, the average distance
$\bar{\sigma}_{G}(v)$ of a vertex is defined to be the arithmetic mean of the
distances from $v$ to all other vertices of $G$, i.e.,
$\overline{\sigma}_{G}(v)=\frac{1}{n-1}\sum_{w\in V}d_{G}(v,w)$, where the
distance $d_{G}(v,w)$ denotes the usual shortest path distance. The remoteness
$\rho(G)$ of a connected graph $G$ is defined as the maximum of the average
distances of the vertices of $G$, i.e.

$\rho(G)={\rm max}_{v\in V}\bar{\sigma}_{G}(v)$

where $V$ is the vertex set of $G$.
The term remoteness was first used in a paper on automated comparison of graph
invariants [3], and is in wide use nowadays. However, the remoteness of graphs
and closely related concepts had been studied before under different names.
Zelinka [29] studied the vertex deviation, defined as
$\frac{\sigma_{G}(v)}{n}$, where $\sigma_{G}(v)$ denotes the sum of the
distances between $v$ and all other vertices, and $n$ is the number of
vertices. Other authors used terms such as transmission, for example, [20],
total distance or simply distance for $\sigma_{G}(v)$ of $v$.

Bounds on remoteness in terms of order only were given by Zelinka [25] and
later, independently, by Auochiche and Hansen [4].

######  Theorem 1.1.

(Zelinka [25], Aouchiche, Hansen [4])
Let $G$ be a connected graph of order $n\geq 2$. Then

$\rho(G)\leq\frac{n}{2},$

with equality if and only if $G$ is a path.

In [14], Entringer, Jackson and Snyder considered results by Ore [19] to
strengthen the results in Theorem 1.1 by taking into account a bound on the
size of a graph.

######  Theorem 1.2.

(Entringer, Jackson, Snyder [14])
Let $G$ be a connected graph of order $n$ and size at least $m$. Then

$\rho(G)\;\leq\;\dfrac{n+2}{2}-\dfrac{m}{n-1}.$

The proof of Theorem 1.2 given in [14] is elegant and short, but it neither
yields the extremal graphs, nor does it generalise in a natural way, for
example to graphs of higher connectivity. Using an entirely different
approach, we show that the bound in Theorem 1.2 can be strengthened
considerably for $\kappa$-connected graphs, where $\kappa$ is arbitrary and
for $\lambda$-edge-connected graphs, where $\lambda\in\\{2,3\\}$. We also
characterise all extremal graphs for $\kappa=1$. Using a proof similar to that
of Theorem 1.2 we also obtain an improved bound for triangle-free graphs,
which we show to be sharp.

The literature contains several results on remoteness of graphs, ranging from
bounds on remoteness of different classes of graphs to the relation between
remoteness and other graph parameters. There are results on remoteness in
maximal planar graphs and maximal bipartite planar graphs [8], in graphs not
containing certain cycles as [11], and trees [7, 25]. Also relations between
remoteness and other graph parameters have been studied, for example girth
[5], minimum degree see [9], maximum degree see [13] and clique number see
[15]. A survey on proximity and remoteness in graphs has been given in [6].
Recently, the bound in Theorem 1.1 was extended to digraphs by Ai, Gerke,
Gutin and Mafunda [1].

######  Theorem 1.3.

(Ai, Gerke, Gutin, Mafunda [1])
Let $D$ be a strong digraph of order $n\geq 3$. Then

$\rho(D)\leq\frac{n}{2},$

with equality if and only if $D$ is strong and contains a Hamiltonian dipath
$v_{1}v_{2}\dots v_{n}$ such that no directed edge of the form $v_{i}v_{j}$
with $2\leq i+1<j\leq n$ is in $D$.

##  2 Terminology and notation

We use the following notation. For a graph $G$ we denote by $V(G)$ and $E(G)$
the vertex set and edge set, respectively. The order and size of a graph are
the cardinalities of the vertex set and edges, respectively. By an
$(n,m)$-graph we mean a graph of order $n$ and size at least $m$. If $G$ and
$G^{\prime}$ are distinct graphs with the same vertex set, but $E(G)\subset
E(G^{\prime})$, i.e., $G^{\prime}$ is obtained from $G$ by adding edges, then
we write $G\lneqq G^{\prime}$.

If $v$ is a vertex in a graph $G$, then the neighbourhood $N(v)$ of $v$ is the
set of all vertices adjacent to $v$. We will say a graph $G$ is
$\kappa$-connected or $\lambda$-edge-connected if removal of fewer than
$\kappa$ vertices or fewer than $\lambda$ edges, respectively, leaves $G$
connected.

The eccentricity ${\rm ecc}_{G}(v)$ of a vertex $v$ in a graph $G$ is the
distance from $v$ to a vertex farthest from $v$. The largest of all
eccentricities of vertices of $G$ is called the diameter and is denoted by
${\rm diam}(G)$. For $i\in\mathbb{Z}$ let $N_{i}(v)$ be the set of all
vertices $u$ with $d(v,u)=i$, and let $n_{i}(v)=|N_{i}(v)|$. Clearly,
$n_{i}(v)>0$ if and only if $0\leq i\leq{\rm ecc}_{G}(v)$.

We denote the complete graph of order $n$ by $K_{n}$. If
$G_{1},G_{2},\ldots,G_{k}$ are disjoint graphs, then the sequential sum
$G_{1}+G_{2}+\cdots G_{k}$ is the graph obtained from the disjoint union of
$G_{1},G_{2},\ldots,G_{k}$ by joining every vertex in $G_{i}$ to every vertex
in $G_{i+1}$ for $i=1,2,\ldots,k-1$. If $t,k\in\mathbb{N}$, then
$[K_{a_{1}}+K_{a_{2}}+\ldots+K_{a_{t}}]^{k}$ stands for $k$ repetitions of the
pattern $K_{a_{1}}+K_{a_{2}}+\ldots+K_{a_{t}}$. If $G$ is a graph, then the
complement of $G$, denoted by $\overline{G}$, is the graph on the same vertex
set as $G$, in which two vertices are adjacent if they are not adjacent in
$G$. We say that a graph $G$ is triangle-free if $G$ contains no subgraph
isomorphic to $K_{3}$.

If $(k,b)$ and $(k^{\prime},b^{\prime})$ are distinct pairs of integers, then
we write $(k,b)\preceq(k^{\prime},b^{\prime})$ if $(k,b)$ comes before
$(k^{\prime},b^{\prime})$ in the lexicographic ordering of pairs of integers,
i.e., if either $k<k^{\prime}$ or $k=k^{\prime}$ and $b<b^{\prime}$. For
triples of integers the relation $\preceq$ is defined analogously.

##  3 Maximum remoteness of a $\kappa$-connected graph with given order and
size

In this section we give a sharp upper bound on the remoteness of a
$\kappa$-connected graph in terms of order and size. Our results generalize
the bound on remoteness in connected graphs of given order and size in Theorem
1.2. Our proof is entirely different from that in [14], this technique allows
us to determine the extremal graphs in Theorem 1.2, i.e., if $\kappa=1$, and
also for many values of the size if $\kappa>1$.

We first describe a family of $\kappa$-connected graphs of order $n$ and size
at least $m$, which we term $\kappa$-connected path-complete graphs. We prove
some properties of these graphs. We then show that path-complete graphs attain
the maximum remoteness among all $\kappa$-connected graphs of order $n$ and
size at least $m$.

######  Definition 3.1.

A graph $G$ is said to be a $\kappa$-connected path-complete graph if there
exist $\ell,a,b\in\mathbb{N}$, $a\geq\kappa$, with

$G=K_{1}+[K_{\kappa}]^{\ell}+K_{a}+K_{b}.$

For graphs of diameter greater than $2$, Definition 3.1 generalises the path-
complete graphs defined by Soltés in [23], which are the $1$-connected path-
complete graphs defined above.

######  Lemma 3.1.

(a) Let $H$ be a $\kappa$-connected path-complete graph, where
$\kappa\in\mathbb{N}$. Then $\rho(H+e)<\rho(H)$ for every edge $e\in
E(\overline{H})$.
(b) Let $H,H^{\prime}$ be two distinct $\kappa$-connected path-complete graphs
of order $n$. Then either $m(H)<m(H^{\prime})$ and $\rho(H)>\rho(H^{\prime})$,
or $m(H)>m(H^{\prime})$ and $\rho(H)<\rho(H^{\prime})$.
(c) Given $n,\kappa$. Then there exists a $\kappa$-connected path-complete
graph of order $n$ and size $m$ if an only if
$m\equiv\binom{n-1}{2}\pmod{\kappa}$ and
$\frac{1}{2}[n(3\kappa-1)-2\kappa^{2}-\kappa+1-b(\kappa-b)]\leq
m\leq\binom{n-1}{2}$, where $b$ is the integer in $\\{1,2,\ldots,\kappa\\}$
with $b\equiv n-1\pmod{\kappa}$.

###### Proof.

(a) There exist $a,b,\kappa\in\mathbb{N}$ with
$H=K_{1}+[K_{\kappa}]^{\ell}+K_{a}+K_{b}$. If $(a,b)\neq(\kappa,1)$, then the
vertex in $K_{1}$ is the unique vertex attaining the remoteness. If
$(a,b)=(\kappa,1)$, then the vertex in $K_{1}$ and the vertex in $K_{b}$ are
the unique vertex attaining the remoteness. In both cases, adding an arbitrary
edge strictly reduces the total distance of these vertices, and the lemma
holds.
(b) Let $H$ and $H^{\prime}$ be two distinct $\kappa$-connected path-complete
graphs of order $n$. It suffices to show that

$H^{\prime}\lneqq H\quad\textrm{or}\quad H\lneqq H^{\prime},$ (1)

To see this observe that if $H^{\prime}\lneqq H$, then $m(H^{\prime})<m(H)$,
and by part (a), we have $\rho(H^{\prime})>\rho(H)$. Similarly, if $H\lneqq
H^{\prime}$, then $m(H)<m(H^{\prime})$, and $\rho(H)>\rho(H^{\prime})$. In
both cases part (a) of the lemma holds.

To prove (1), note that there exist
$k,k^{\prime},a,a^{\prime},b,b^{\prime}\in\mathbb{N}$ with
$a,a^{\prime}\geq\kappa$ such that

$H=K_{1}+[K_{\kappa}]^{\ell}+K_{a}+K_{b},\quad
H^{\prime}=K_{1}+[K_{\kappa}]^{\ell^{\prime}}+K_{a^{\prime}}+K_{b^{\prime}}.$

Since $H\neq H^{\prime}$, it follows that
$(\ell,b)\neq(\ell^{\prime},b^{\prime})$. We have either
$(\ell,b)\preceq(\ell^{\prime},b^{\prime})$ or
$(\ell^{\prime},b^{\prime})\preceq(\ell,b)$. Without loss of generality we may
assume the former.

First assume that $\ell=\ell^{\prime}$ and $b<b^{\prime}$. Then $H$ is
obtained from $H^{\prime}$ by adding edges between all vertices of a set of
$b^{\prime}-b$ vertices of $K_{b^{\prime}}$ and all vertices in the rightmost
$K_{\kappa}$, and so we have $H^{\prime}\lneqq H$. Now assume that
$\ell<\ell^{\prime}$. Then we obtain the graph $H$ from $H^{\prime}$ by adding
edges as follows. By joining all vertices in the rightmost complete graph
$K_{b^{\prime}}$ to all vertices in the third rightmost complete graph
$K_{\kappa}$ in $H^{\prime}$ we obtain the graph
$K_{1}+[K_{\kappa}]^{\ell^{\prime}}+K_{a^{\prime}+b^{\prime}}$. Applying this
operation again yields the graph
$K_{1}+[K_{\kappa}]^{\ell^{\prime}-1}+K_{a^{\prime}+b^{\prime}+\kappa}$. After
repeating this operation a total of $\ell^{\prime}-k$ times we obtain
$K_{1}+[K_{\kappa}]^{\ell}+K_{\kappa}+K_{a^{\prime}+b^{\prime}+(\ell^{\prime}-\ell-1)\kappa}$,
which equals $K_{1}+[K_{\kappa}]^{\ell}+K_{\kappa}+K_{a+b-\kappa}$. Adding
edges between all vertices of a set of $a-\kappa$ vertices of $K_{a+b-\kappa}$
and all vertices in the rightmost $K_{\kappa}$ yields the graph
$K_{1}+[K_{\kappa}]^{\ell}+K_{a}+K_{b}$, which is $H$. Hence $H^{\prime}\lneqq
H$, and (1) follows. Thus (b) holds.
(c) Fix $n$ and $\kappa$. If for $\ell,a,b\in\mathbb{N}$ the graph
$K_{1}+[K_{\kappa}]^{\ell}+K_{a}+K_{b}$ has order $n$ and is
$\kappa$-connected, then $n=1+\ell\kappa+a+b$, and $a\geq\kappa$. This implies
that $\ell=\frac{n-1-a-b}{\kappa}\leq\frac{n-2-\kappa}{\kappa}$, and
$b=n-1-\ell\kappa-a\leq n-1-(\ell+1)\kappa$. With respect to the order
$\preceq$, the smallest and largest pairs $(\ell,b)$ satisfying these
conditions are $(1,1)$ and $(\ell_{0},b_{0})$, respectively, where
$\ell_{0}=\lfloor\frac{n-2-\kappa}{\kappa}\rfloor$ and
$b_{0}=n-1-(\ell_{0}+1)\kappa$. It thus follows as in the proof of (1) that
the $\kappa$-connected path-complete graph
$K_{1}+K_{\kappa}+K_{n-\kappa-2}+K_{1}$, arising from the pair $(1,1)$, has
maximum size among all $\kappa$-connected path-complete graphs of order $n$.
Simple calculations show that its size is $\binom{n-1}{2}$. The
$\kappa$-connected path-complete graph
$K_{1}+[K_{\kappa}]^{\ell_{0}}+K_{n-1-k\ell_{0}-b_{0}}+K_{b_{0}}$ arising from
the pair $(\ell_{0},b_{0})$ has minimum size among $\kappa$-connected path-
complete graphs of order $n$. Its size is
$\frac{1}{2}\big{(}n(3\kappa-1)-2\kappa^{2}-\kappa+1-b(\kappa-b)\big{)}$.

The proof of part (a) shows that if $m(H)<m(H^{\prime})$, then $H^{\prime}$ is
obtained from $H$ by adding edges, and the number of edges added is a multiple
of $\kappa$. Hence the number of edges of a $\kappa$-connected path-complete
graph of order $n$ is congruent $\binom{n-1}{2}$ modulo $\kappa$. If $H$ is a
$\kappa$-connected path-complete graph of order $n$,
$H=K_{1}+[K_{\kappa}]^{\ell}+K_{a}+K_{b}$, then unless $(\ell,b)=(1,1)$, there
exists a $\kappa$-connected path-complete graph of order $n$ with exactly
$\kappa$ more edges than $H$: the graph
$K_{1}+[K_{\kappa}]^{\ell}+K_{a+1}+K_{b-1}$ (if $b>1$) or the graph
$K_{1}+[K_{\kappa}]^{\ell-1}+K_{\kappa}+K_{a+1}$ (if $\ell>1$ and $b=1$). This
completes the proof of part (c). ∎

For given $n,m\in\mathbb{N}$ for which there exists a $\kappa$-connected path-
complete $(n,m)$-graph, we define $PK_{n,m,\kappa}$ to be such a graph of
minimum size. It follows from Lemma 3.1(a) that there exists at most one
$\kappa$-connected path-complete graph of given order and size, so
$PK_{n,m,\kappa}$ is well-defined.

######  Theorem 3.2.

(a) Let $G$ be a $\kappa$-connected $(n,m)$-graph with $m\leq\binom{n-1}{2}$.
Then

$\rho(G)\leq\rho(PK_{n,m,\kappa}).$ (2)

(b) Assume that $m\equiv\binom{n-1}{2}\pmod{\kappa}$ and
$\frac{1}{2}\big{(}n(3\kappa-1)-2\kappa^{2}-\kappa+1-b(\kappa-b)\big{)}\leq
m\leq\binom{n-1}{2}$, where $b$ is the integer in $\\{1,2,\ldots,\kappa\\}$
with $b\equiv n-1\pmod{\kappa}$. Then equality in (a) holds only if
$G=PK_{n,m,\kappa}$.

###### Proof.

(a) We first prove that there exists a $\kappa$-connected path-complete
$(n,m)$-graph $G^{\prime}$ with

$\rho(G)\leq\rho(G^{\prime}).$ (3)

We may assume that $G$ has maximum remoteness among all $\kappa$-connected
$(n,m)$-graphs, and that among all such graphs of maximum remoteness, $G$ is
one of maximum size. Furthermore, let $v\in V(G)$ with
$\overline{\sigma}(v)=\rho(G)$, $d={\rm ecc}_{G}(v)$, $N_{i}=\\{z\in
V(G)|d_{G}(v,z)=i\\}$ and $|N_{i}|=n_{i}$ for $i\in\\{0,1,\ldots,d\\}$.
Clearly $n_{0}=1$, each $n_{i}$ is a positive integer for $i=1,2,\ldots,d$ and
$\sum_{i=0}^{d}n_{i}=n$.

Claim 1: $G=K_{n_{0}}+K_{n_{1}}+\ldots+K_{n_{d}}$.

Recall that $G$ has maximum size among all graphs of size at least $m$ for
which $\sigma(v,G)$ is maximized. Hence $N_{i}$ induces a complete subgraph of
$G$, and every vertex in $N_{i-1}$ is adjacent to every vertex in $N_{i}$ for
all $i\in\\{1,2,\ldots,d\\}$, otherwise we could add an edge and increase the
size of $G$ without changing $\sigma(v,G)$. Hence Claim 1 follows.

Claim 2: For all $i\in\\{1,2,\ldots,d-3\\}$, we have $n_{i}=\kappa$.

Let $i\in\\{1,2,\ldots,d-3\\}$. Since removing the $n_{j}$ vertices of $N_{j}$
from $G$ yields a disconnected graph, and since $G$ is $\kappa$-connected, we
have $n_{i}\geq\kappa$.

Suppose to the contrary that there exists $j\in\\{1,\ldots,d-3\\}$ such that
$n_{j}>\kappa$. Let $j$ be the smallest such value. Then $n_{i}=\kappa$ for
all $i\in\\{1,\ldots,j-1\\}$. Now consider the graph
$G^{*}=K_{n_{0}}+K_{n_{1}}+\ldots+K_{n_{j}-1}+K_{n_{j+1}+1}+\ldots+K_{n_{d-1}}+K_{n_{d}}$.
Then $m(G^{*})=m(G)+n_{j+2}-n_{j-1}\geq m(G)$ since
$n_{j+2}\geq\kappa=n_{j-1}$ and $G^{*}$ is a $\kappa$-connected $(n,m)$-graph
such that $\sigma(v,G^{*})>\sigma(v,G)$, and thus $\rho(G^{*})>\rho(G)$. This
contradiction to the maximility of $\rho(G)$ proves Claim 2.

Claim 3: $n_{d-2}=\kappa$.

Suppose to the contrary that $n_{d-2}\neq\kappa$. As in Claim 2 we get
$n_{d-2}>\kappa$. Consider the graph
$G^{*}=K_{n_{0}}+K_{n_{1}}+\ldots+K_{n_{d-2}-1}+K_{n_{d-1}+2}+K_{n_{d}-1}$. It
is easy to verify that $m(G^{*})=m(G)+n_{d}-n_{d-3}+n_{d-2}-1$, and so, since
$n_{d-3}=\kappa$ and $n_{d-2}\geq\kappa+1$, we have $m(G^{*})\geq
m(G)+n_{d}>m(G)$. Also $\rho(G^{*})=\rho(G)$. This contradicts our choice of
$G$ as having maximum size among graphs of maximum remoteness, and so Claim 3
follows.

It follows from Claims 1 to 3 that $G$ is a $\kappa$-connected path-complete
graph. Letting $G^{\prime}=G$ proves (3).

By (3), there exists a $\kappa$-connected path-complete graph $G^{\prime}$ of
order $n$ and size at least $m$ with $\rho(G)\leq\rho(G^{\prime})$. By the
definition of $PK_{n,m,\kappa}$ we have $m(G^{\prime})\geq
m(PK_{n,m,\kappa})$. By Lemma 3.1(a), we thus have
$\rho(G^{\prime})\leq\rho(PK_{n,m,\kappa})$. Hence

$\rho(G)\leq\rho(G^{\prime})\leq\rho(PK_{n,m,\kappa}),$

which proves (a).

(b) Now assume that equality holds in (2), i.e., that
$\rho(G)=\rho(PK_{n,m,\kappa})$, and furthermore that
$m\equiv\binom{n-1}{2}\pmod{\kappa}$ and
$\frac{1}{2}[n(3\kappa-1)-2\kappa^{2}-\kappa+1-b(\kappa-b)]\leq
m\leq\binom{n-1}{2}$, where $b$ is as defined above. It follows from Lemma
3.1(c) that the graph $PK_{n,m,\kappa}$ has exactly $m$ edges.

It follows from part (a) that $G$ has maximum remoteness among all
$\kappa$-connected $(n,m)$-graphs. We claim that $G$ has maximum size among
all such graphs maximising the remoteness. Suppose not. Then there exists a
$\kappa$-connected $(n,m+1)$-graph $G^{\prime\prime}$ with
$\rho(G)=\rho(G^{\prime\prime})$. Applying (2) to $G^{\prime\prime}$ we get
that

$\rho(G)=\rho(G^{\prime\prime})\leq\rho(PK_{n,m+1,\kappa})<\rho(PK_{n,m,\kappa}),$

where the last inequality follows from Lemma 3.1 (b) and the fact that
$m(PK_{n,m,\kappa})=m<m(PK_{n,m+1,\kappa})$. Hence $G$ has maximum size among
all $\kappa$-connected graphs of order $n$ maximising the remoteness.

The proof of (a) shows that, if $G$ has maximum size among all
$\kappa$-connected path-complete $(n,m)$-graphs, then $G$ is a path-complete
graph. Hence $G=PK_{n,m^{\prime},\kappa}$ for some $m^{\prime}$ with
$m^{\prime}\geq m$. Since by Lemma 3.1 we have
$\rho(PK_{n,m^{\prime},\kappa})<\rho(PK_{n,m,\kappa})$ if $m^{\prime}>m$, we
have $m^{\prime}=m$, and thus $G=PK_{n,m,\kappa}$, as desired. ∎

Evaluating the remoteness of $PK_{n,m,\kappa}$ yields the following corollary.

######  Corollary 3.3.

Let $G$ be a $\kappa$-connected graph of order $n$ and size $m$, with
$\frac{1}{2}[n(3\kappa-1)-2\kappa^{2}-\kappa+1-b(\kappa-b)]\leq
m\leq\binom{n-1}{2}$, where $b$ is the integer in $\\{1,2,\ldots,\kappa\\}$
with $b\equiv n-1\pmod{\kappa}$. Let $m^{*}$ be the smallest integer with
$m^{*}\geq m$ and $m^{*}\equiv\binom{n-1}{2}\pmod{\kappa}$. Then

$\rho(G)\leq\frac{n}{2\kappa}+2-\frac{1}{\kappa}-\frac{\kappa-1}{n-1}-\frac{m^{*}}{\kappa(n-1)},$

and this bound is sharp.

###### Proof.

Let $m^{*}$ be as defined above. It follows from Lemma 3.1 that the graph
$PK_{n,m,\kappa}$ has size $m^{*}$. Recall that
$PK_{n,m,\kappa}=K_{1}+[K_{\kappa}]^{\ell}+K_{a}+K_{b}$ for some
$\kappa,\ell,a,b\in\mathbb{N}$. Then $a+b=n-\ell\kappa-1$. Let $v$ be the
vertex in $K_{1}$, so $v$ realizes the remoteness. Let
$H:=PK_{n,m,\kappa}-V(K_{a}\cup K_{b})$. Straightforward calculations show
that $n(H)=\ell\kappa+1$, $\sigma(v,H)=\frac{\kappa}{2}(\ell(\ell+1))$ and
$m(H)=\ell{\kappa\choose 2}+(\ell-1)\kappa^{2}+\kappa$. Hence

$\sigma(v,PK_{n,m,\kappa})=\sigma(v,H)+(\ell+1)(a+b)+b=\frac{\kappa}{2}(\ell(\ell+1))+(\ell+1)(a+b)+b,$

and, since $m(PK_{n,m,\kappa})=m^{*}$,

$\displaystyle m^{*}=$ $\displaystyle\;m(H)+{a+b+\kappa\choose
2}-b\kappa-{\kappa\choose 2}$ $\displaystyle=$
$\displaystyle\;\ell{\kappa\choose
2}+(\ell-1)\kappa^{2}+\kappa+{a+b+\kappa\choose 2}-b\kappa-{\kappa\choose
2}+x$ $\displaystyle=$
$\displaystyle\;\dfrac{\kappa(\ell-1)(3\kappa-1)}{2}+\kappa+{n-(\ell-1)\kappa+1\choose
2}-b\kappa.$

Define
$\epsilon=\rho(PK_{n,m,\kappa})-\left(\dfrac{n}{2\kappa}+2-\dfrac{1}{\kappa}-\dfrac{\kappa-1}{n-1}-\dfrac{m^{*}}{\kappa(n-1)}\right)$.
Substituting the above terms for $\rho(PK_{n,m,\kappa})$ and $m^{*}$, it is
straightforward to verify that $\epsilon=0$. This proves that
$\rho(PK_{n,m,\kappa})=\left(\dfrac{n}{2\kappa}+2-\dfrac{1}{\kappa}-\dfrac{\kappa-1}{n-1}-\dfrac{m^{*}}{\kappa(n-1)}\right)$,
and the corollary follows. ∎

For $\kappa=1$, Corollary 3.3 yields Theorem 1.2 and, in addition,
characterises the extremal graphs as follows. Note that for $\kappa=1$ we have
$m^{*}=m$.

######  Corollary 3.4.

Let $G$ be a connected graph of order $n$ and size $m$, where $n-1\leq
m\leq\binom{n-1}{2}$. Then

$\rho(G)\leq\frac{n+2}{2}-\frac{m}{n-1},$

with equality if and only if $G=PK_{n,m,1}$.

##  4 Maximum remoteness of a $\lambda$-edge-connected graph of given order
and size

In this section we determine the maximum remoteness of a $\lambda$-edge
connected graph of given order $n$ and size at least $m$. For $\lambda=1$, the
maximum remoteness was determined in Theorem 1.2 and Corollary 3.4. Our focus
here is on graphs with $\lambda=2,3$. The proof strategy we employ is similar
to that in the previous section. We first define $\lambda$-edge-connected
path-complete graphs, which play a similar role to the $\kappa$-connected
path-complete graphs in the previous section. Since the structure of
$\lambda$-edge-connected path-complete graphs is more varied than that of
$\kappa$-connected path-complete graphs, the proofs became a little more
elaborate.

######  Definition 4.1.

Let $\lambda\in\\{2,3\\}$. A graph $G$ is said to be a $\lambda$-edge-
connected path-complete graph if there exist $k\in\mathbb{N}\cup\\{0\\}$ and
$a,b\in\mathbb{N}$ with

$G=\left\\{\begin{array}[]{cc}\left[K_{1}+K_{\lambda}\right]^{k}+K_{a}+K_{b}&\textrm{if
$k\geq 1$ and $ab\geq\lambda$, or}\\\
\left[K_{1}+K_{\lambda}\right]^{k}+K_{1}+K_{a}+K_{b}&\textrm{if
$a\geq\lambda$, or}\\\
\left[K_{1}+K_{3}\right]^{k}+K_{2}+K_{a}+K_{1}&\textrm{if $\lambda=3$, $k\geq
1$ and $a\geq 3$.}\end{array}\right.$

Denote the graphs defined above by $G_{1}^{\lambda}(n,k,b)$,
$G_{2}^{\lambda}(n,k,b)$ and $G_{3}^{\lambda}(n,k)$, respectively, where in
each case $n$ is the order of the graph.

######  Lemma 4.1.

Let $\lambda\in\\{2,3\\}$ and let $H,H^{\prime}$ be $\lambda$-edge-connected
path-complete graph of order $n$.
(a) $\rho(H+e)<\rho(H)$ for all $e\in E(\overline{H})$.
(b) If $H\neq H^{\prime}$, then either $m(H)<m(H^{\prime})$ and
$\rho(H)\geq\rho(H^{\prime})$, or $m(H)>m(H^{\prime})$ and
$\rho(H)\leq\rho(H^{\prime})$.
(c) We have $\frac{5}{3}n-\varepsilon_{2}(n)\leq m(H)\leq\binom{n}{2}-1$ if
$\lambda=2$, where $\varepsilon_{2}(n)$ is defined as $2$ if $n\equiv
0\pmod{3}$, as $\frac{5}{3}$ if $n\equiv 1\pmod{3}$, and as $\frac{1}{3}$ if
$n\equiv 2\pmod{3}$. We have and $\frac{9}{4}n-\varepsilon_{3}(n)\leq
m(H)\leq\binom{n}{2}-1$ if $\lambda=3$, where $\varepsilon_{3}(n)$ is defined
as $3$ if $n\equiv 0\pmod{4}$, as $\frac{9}{4}$ if $n\equiv 1\pmod{4}$, as
$\frac{1}{2}$ if $n\equiv 2\pmod{4}$, and as $-\frac{9}{4}$ if $n\equiv
3\pmod{4}$.
For every integer $m$ between the smallest and largest size of a
$\lambda$-edge-connected path-complete graph of order $n$ there exists a
$\lambda$-edge-connected path-complete graph of order $n$ whose size is at
least $m$ and at most $m+\lambda-1$.

###### Proof.

Fix $n$ and $\lambda\in\\{2,3\\}$.
(a) The proof is almost identical to Lemma 3.1 and thus omitted.
(b) Denote by $A_{n}^{\lambda}$ the set of all $\lambda$-edge-connected path-
complete graphs of order $n$ that are of the form $G_{1}^{\lambda}(n,k,b)$ or
$G_{2}^{\lambda}(n,k,b)$. By considering the lexicographic ordering of the
triples $(k,i,b)$ arising from the graphs $G_{i}(n,k,b)$ for $i\in\\{1,2\\}$,
we show with arguments similar to those in the proof of Lemma 3.1 that

If $H,H^{\prime}\in A_{n}^{\lambda}$ with $H\neq H^{\prime}$, then either
$H\lneqq H^{\prime}$ or $H^{\prime}\lneqq H$. (4)

By (a) we conclude that we have either $m(H)<m(H^{\prime})$ and
$\rho(H)>\rho(H^{\prime})$, or $m(H^{\prime})<m(H)$ and
$\rho(H^{\prime})>\rho(H)$, and so (b) holds if $H,H^{\prime}\in
A_{n}^{\lambda}$. Since $A^{2}_{n}$ contains all $2$-edge-connected path-
complete graphs of order $n$, the lemma holds for $\lambda=2$.

To complete the proof of the lemma, it remains to show the statement if
$\lambda=3$ and at least one of the graphs $H,H^{\prime}$ is not in
$A_{n}^{3}$. First assume that both, $H$ and $H^{\prime}$ are not in
$A_{n}^{3}$. Then $H=G_{3}^{3}(n,k)$ and $H^{\prime}=G_{3}^{3}(n,k^{\prime})$
for some $k,k^{\prime}\in\mathbb{N}$. Since $H\neq H^{\prime}$ we have $k\neq
k^{\prime}$. If $k<k^{\prime}$, then arguments similar to those in the proof
of Lemma 3.1 show that $H^{\prime}\lneqq H$ and so $m(H^{\prime})<m(H)$, a
contradiction. If $k>k^{\prime}$, then arguments similar to those in the proof
of Lemma 3.1 show that $H\lneqq H^{\prime}$, which implies that
$\rho(H)>\rho(H^{\prime})$, and the lemma holds.

We now assume that exactly one of $H$ or $H^{\prime}$ is in $A_{n}^{3}$, so
either $H=G_{3}^{3}(n,k)$ or $H^{\prime}=G_{3}^{3}(n,k)$ for some $k$. We
compare $G_{3}^{3}(n,k)$ with the $3$-edge-connected path-complete graphs
$G_{1}^{3}(n,k,n-4k-1)$ and $G_{1}^{3}(n,k,n-4k-2)$. Simple calculations show
that $m(G_{1}^{3}(n,k,n-4k-1))<m(G_{3}^{3}(n,k))<m(G_{1}^{3}(n,k,n-4k-2))$ and
that $A_{n}^{3}$ contains no graphs whose size is between
$m(G_{1}^{3}(n,k,n-4k-1))$ and $m(G_{1}^{3}(n,k,n-4k-2))$. It is easy to
verify that
$\rho(G_{1}^{3}(n,k,n-4k-1))=\rho(G_{3}^{3}(n,k))>\rho(G_{1}^{3}(n,k,n-4k-2))$.

If now $H=G_{3}^{3}(n,k)$, then it follows by $m(H)\leq m(H^{\prime})$ and
$H^{\prime}\in A_{n}^{3}$ that $m(G_{1}^{3}(n,k,n-4k-2))\leq m(H^{\prime})$
and $\rho(H)>\rho(G_{1}^{3}(n,k,n-4k-2))\geq\rho(H^{\prime})$. If
$H^{\prime}=G_{3}^{3}(n,k)$, then it follows by $m(H)\leq m(H^{\prime})$ and
$H\in A_{n}^{3}$ that $m(H)\leq m(G_{1}(n,k,n-4k-1))$ and
$\rho(H)\geq\rho(G_{1}(n,k,n-4k-1))\geq\rho(H^{\prime})$. Part (b) now
follows.
(c) To determine the largest size of a $\lambda$-edge-connected path-complete
graph note that the graph $G_{2}^{\lambda}(n,0,1)$ has size $\binom{n}{2}-1$,
and the complete graph is not a $\lambda$-edge-connected path-complete graph.

It is easy to verify that the smallest size among $2$-edge-connected path-
complete graphs of order $n$ is attained by $G_{1}^{2}(n,\frac{n-3}{3},2)$ if
$n\equiv 0\pmod{3}$, by $G^{2}_{2}(n,\frac{n-4}{3},1)$ if $n\equiv 1\pmod{3}$,
and by $G^{2}_{2}(n,\frac{n-5}{3},2)$ if $n\equiv 2\pmod{3}$. Their sizes are
$\frac{5}{3}n-2$, $\frac{5}{3}n-\frac{5}{3}$ and $\frac{5}{3}n-\frac{1}{3}$ if
$n$ is congruent to $0$, $1$ or $2$, respectively, modulo $3$.

It is easy to verify that the smallest size among $3$-edge-connected path-
complete graphs of order $n$ is attained by $G_{1}^{3}(n,\frac{n-4}{4},3)$ if
$n\equiv 0\pmod{4}$, by $G_{1}^{3}(n,\frac{n-5}{4},1)$ if $n\equiv 1\pmod{4}$,
by $G^{2}_{3}(n,\frac{n-6}{4},2)$ if $n\equiv 2\pmod{4}$, and by
$G^{2}_{3}(n,\frac{n-7}{4},3)$ if $n\equiv 3\pmod{4}$. Their sizes are
$\frac{9}{4}n-3$, $\frac{9}{4}n-\frac{9}{4}$, $\frac{9}{4}n-\frac{1}{2}$ and
$\frac{9}{4}n+\frac{9}{4}$ if $n$ is congruent to $0$, $1$, $2$, or $3$,
respectively, modulo $4$.

Also, for $i\in\\{1,2\\}$ the difference between the sizes of
$G_{i}^{\lambda}(n,k,b)$ and $G^{\lambda}_{i}(n,k,b-1)$ is at most $\lambda$
if $b>1$, and the difference between the sizes of $G_{2}^{\lambda}(n,k,1)$ and
$G_{1}^{\lambda}(n,k,n-k(\lambda+1)-1)$ is $1$. Hence, the set of sizes of
$\lambda$-edge-connected path-complete graphs of order $n$ contains no gaps of
length $\lambda$ or more. Part (c) follows. ∎

The proof of Lemma 4.1 shows that for $\lambda\in\\{2,3\\}$ no two
$\lambda$-edge-connected path-complete graphs of order $n$ have the same size.
Hence, for any $n,m$ for which there exists a non-complete $\lambda$-edge-
connected graph of order $n$ and size $m$, there exists a unique
$\lambda$-edge-connected path-complete graph of order $n$ and size at least
$m$ that has minimum size among all such graphs. We denote this graph by
$PK_{n,m}^{\lambda}$.

######  Theorem 4.2.

Let $\lambda\in\\{2,3\\}$. Let $G$ be a $\lambda$-edge-connected graph of
order $n$ and size at least $m$ that is not complete. Then

$\rho(G)\leq\rho(PK^{\lambda}_{n,m}).$

###### Proof.

Let $G$ a $\lambda$-edge-connected graph of order $n$ and size at least $m$.
We first prove that there exists a $\lambda$-edge-connected path-complete
$(n,m)$-graph $G^{\prime}$ with

$\rho(G)\leq\rho(G^{\prime}).$ (5)

We may assume that $G$ is a $\lambda$-edge-connected $(n,m)$-graph such that
$\rho(G)$ is maximised among all $\lambda$-edge-connected $(n,m)$-graphs. We
may further assume that, among those graphs, $G$ is one of maximum size. Let
$v$ be a vertex of $G$ with $\overline{\sigma}(v)=\rho(G)$, let $d={\rm
ecc}(v,G)$. For $i=0,1,\ldots,d$ let $N_{i}$ be the set of vertices at
distance $i$ from $v$, and let $n_{i}=|N_{i}|$. As in the proof of Theorem
3.2, we have

$G=K_{n_{0}}+K_{n_{1}}+K_{n_{2}}+\cdots+K_{n_{d}}.$

Clearly, $n_{0}=1$. Let $j\in\\{0,1,\ldots,d\\}$. If $d\leq 2$, then the
statement of the lemma clearly holds, so we assume that $d\geq 3$. If the
values $n_{0},n_{1},\ldots,n_{j}$ alternate between $1$ and $\lambda$, i.e.,
if for $i\in\\{0,1,2,\ldots,j\\}$ we have $n_{i}=1$ if $i$ is even, and
$n_{i}=\lambda$ if $i$ is odd, then we say that $n_{0},n_{1},\ldots,n_{j}$ is
an initial $(1,\lambda)$-segment. We may assume that, among those graphs
maximising $\rho$ and $m$, our graph $G$ has an initial $(1,\lambda)$-segment
of maximum length, i.e., the value of $j$ is maximum.

If we have $j\geq d-2$, then $G$ is isomorphic to one of the first two graphs
in Definition 4.1, and the lemma holds in this case. Hence we assume from now
on that $j\leq d-3$.
Claim 1: $j$ is odd, i.e., $n_{j}=\lambda$.
Suppose to the contrary that $j$ is even, i.e., $n_{j}=1$. Since
$n_{j+1}\neq\lambda$, and since $n_{j}n_{j+1}\geq\lambda$ by the
$\lambda$-edge-connectivity of $G$, we have that $n_{j+1}\geq\lambda+1$. Then
the graph

$G^{\prime}=K_{n_{0}}+K_{n_{1}}+\cdots+K_{n_{j}}+K_{n_{j+1}-1}+K_{n_{j+2}+1}+K_{n_{j+3}}+K_{n_{j+4}}+\cdots+K_{n_{d}}$

is a $\lambda$-edge-connected $(n,m)$-graph since
$m(G^{\prime})=m(G)+n_{j+3}-n_{j}=m(G)+n_{j+3}-1\geq m(G)$, and has greater
remoteness than $G$. This contradiction to the choice of $G$ proves Claim 1.
Claim 2: $n_{j+3}=1$.
By the maximality of $j$ we have $n_{j+1}\geq 2$. We first show that
$n_{j+3}\leq\lambda-1$. Suppose not. Then $n_{j+3}\geq\lambda$, and the graph

$G^{\prime}=K_{n_{0}}+K_{n_{1}}+\cdots+K_{n_{j}}+K_{n_{j+1}-1}+K_{n_{j+2}+1}+K_{n_{j+3}}+K_{n_{j+4}}+\cdots+K_{n_{d}}$

is a $\lambda$-edge-connected $(n,m)$-graph since
$m(G^{\prime})=m(G)+n_{j+3}-n_{j}\geq m(G)$, and has greater remoteness than
$G$. This contradiction to the choice of $G$ proves that
$n_{j+3}\leq\lambda-1$. This proves Claim 2 if $\lambda=2$.
To complete the proof of the Claim 2, it suffices to show that $n_{j+3}\neq 2$
if $\lambda=3$. Suppose to the contrary that $\lambda=3$ and $n_{j+3}=2$. Let

$\displaystyle G^{\prime}=$ $\displaystyle
K_{n_{0}}+K_{n_{1}}+\cdots+K_{n_{j}}+K_{n_{j+1}-1}+K_{n_{j+2}+1}+K_{n_{j+3}}+K_{n_{j+4}}+\cdots$
$\displaystyle+K_{n_{d-2}}+K_{n_{d-1}+1}+K_{n_{d}-1},$

i.e., $G^{\prime}$ is obtained from $G$ by moving a vertex from $K_{n_{j+1}}$
to $K_{n_{j+2}}$, and moving another vertex from $K_{n_{d}}$ to $K_{n_{d-1}}$.
Clearly, $G^{\prime}$ is a $3$-edge-connected, $G^{\prime}$ is an
$(n,m)$-graph since
$m(G^{\prime})=m(G)+n_{j+3}-n_{j}+n_{d-2}=m(G)-1+n_{d-2}\geq m(G)$, and
$\rho(G^{\prime})=\rho(G)$. Repeating this process until there is only one
vertex in $N_{j+1}$, we eventually obtain a $3$-edge-connected graph with the
same order, size and remoteness as $G$, but with a greater value of $j$. This
contradiction to the maximality of $j$ proves that $n_{j+2}\neq 2$, and Claim
2 follows.
Claim 3: $j=d-3$.
Recall that $j\leq d-3$. Suppose to the contrary that $j\leq d-4$. Then
$n_{j+4}>0$. By Claim 2 and since $G$ is $\lambda$-edge-connected, we have
$n_{j+2}\geq\lambda$ and $n_{j+4}\geq\lambda$. Then the graph

$G^{\prime}=K_{n_{0}}+K_{n_{1}}+\cdots+K_{n_{j}}+K_{1}+K_{n_{j+2}}+K_{n_{j+3}+n_{j+1}-1}+K_{n_{j+4}}+\cdots+K_{n_{d}}$

is a $\lambda$-edge-connected $(n,m)$-graph since
$m(G^{\prime})=m(G)+(n_{j+1}-1)(n_{j+4}-n_{j})\geq m(G)$, and has greater
remoteness than $G$. This contradiction to the choice of $G$ proves Claim 3.
We are now ready to complete the proof of the lemma. By Claim 3 and Claim 2,
we have $n_{d}=1$. First assume that $n_{d-2}\geq\lambda$. Then the graph

$G^{\prime}=K_{n_{0}}+K_{n_{1}}+\cdots+K_{n_{d-3}}+K_{n_{d-2}-1}+K_{n_{d-1}+2}$

i.e., $G^{\prime}$ is obtained from $G$ by moving a vertex from $K_{n_{d-2}}$
to $K_{n_{d-1}}$, and moving another vertex from $K_{n_{d}}$ to $K_{n_{d-1}}$.
Clearly, $G^{\prime}$ is a $\lambda$-edge-connected $(n,m)$-graph since
$m(G^{\prime})=m(G)$, and has the same remoteness than $G$. Since $G^{\prime}$
is a $\lambda$-edge-connected path-complete graph, the lemma holds in this
case.

Now assume that $n_{d-2}\leq\lambda-1$. If $\lambda=2$, then we have
$n_{d-2}=1$ and thus $j\geq d-2$, a contradiction to Claim 3, and the lemma
holds in this case. Similarly, if $\lambda=3$ and $n_{d-2}=1$, then we obtain
$j\geq d-2$, again contradicting Claim 3. The only remaining case is
$\lambda=3$ and $n_{d-2}=2$. In this case, $G$ is the $3$-edge-connected path-
complete graph $G_{3}^{3}(n,k)$ for some $k\in\mathbb{N}$. This proves (5).

By (5), there exists a $\kappa$-connected path-complete graph $G^{\prime}$ of
order $n$ and size at least $m$ with $\rho(G)\leq\rho(G^{\prime})$. By the
definition of $PK_{n,m}^{\lambda}$ we have $m(G^{\prime})\geq
m(PK_{n,m}^{\lambda})$. By Lemma 4.1(b), we thus have
$\rho(G^{\prime})\leq\rho(PK_{n,m}^{\lambda})$. Hence

$\rho(G)\leq\rho(G^{\prime})\leq\rho(PK_{n,m}^{\lambda}),$

which proves the theorem.

∎

In the proof of Lemma 4.1(c), the $\lambda$-edge-connected path-complete
graphs of minimum size were determined. It follows from Theorem 4.2 and Lemma
4.1(b) that these graphs maximise the remoteness among all $\lambda$-edge-
connected graphs of order $n$. Evaluating the remoteness of these graphs
yields the following bound on remoteness for $2$\- and $3$-edge-connected
graphs. The bound for $2$-edge-connected graphs was proved originally by
Plesník [20].

######  Corollary 4.3.

(a) [20] If $G$ is a $2$-edge-connected graph of order $n$, then

$\rho(G)\leq\left\\{\begin{array}[]{cc}\frac{n}{3}&\textrm{ if $n\equiv
0\pmod{3}$ or $n\equiv 1\pmod{3}$, }\\\ \frac{n}{3}-\frac{2}{3(n-1)}&\textrm{
if $n\equiv 2\pmod{3}$. }\end{array}\right.$

(b) If $G$ is a $3$-edge-connected graph of order $n$, then

$\rho(G)\leq\left\\{\begin{array}[]{cc}\frac{n}{4}&\textrm{ if $n\equiv
0\pmod{4}$ or $n\equiv 1\pmod{4}$, }\\\ \frac{n}{4}-\frac{1}{2(n-1)}&\textrm{
if $n\equiv 2\pmod{4}$, }\\\ \frac{n}{4}-\frac{3}{2(n-1)}&\textrm{ if $n\equiv
3\pmod{4}$. }\end{array}\right.$

The above bounds are sharp.

Since evaluating the exact remoteness of $PK_{n,m}^{2}$ and $PK_{n,m}^{3}$
gives a rather unpleasant expression, we derive a good approximation below.
Recall that the minimum size of a $\lambda$-edge-connected path-complete graph
of order $n$ is $\frac{5}{3}n-\varepsilon_{2}(n)$ for $\lambda=2$ and
$\frac{9}{4}n-\varepsilon_{3}(n)$ for $\lambda=3$. For graphs of smaller size,
the bound in Corollary 4.3 can likely not be improved, even if size is taken
into account.

######  Proposition 4.4.

(a) Let $n,m\in\mathbb{N}$ with $\frac{5}{3}n-\varepsilon_{2}(n)\leq
m<\binom{n}{2}$, where $\varepsilon_{2}$ is as defined in Lemma 4.1(c). Then

$\rho(PK^{2}_{n,m})=\frac{n}{3}-\frac{2m}{3(n-1)}+\varepsilon.$

for some $\varepsilon\in\mathbb{R}$ with
$\frac{2}{3}<\varepsilon<\frac{5}{3}$.
(b) Let $n,m\in\mathbb{N}$ with $\frac{9}{4}n-\varepsilon_{3}(n)\leq
m<\binom{n}{2}$, where $\varepsilon_{3}$ is as defined in Lemma 4.1(c). Then

$\rho(PK^{3}_{n,m})=\frac{n}{4}-\frac{m}{2(n-1)}+\varepsilon.$

for some $\varepsilon\in\mathbb{R}$ with $1<\varepsilon<\frac{3}{2}$.

Proof: (a) Recall that $PK^{2}_{n,m}$ equals either
$[K_{1}+K_{2}]^{k}+K_{a}+K_{b}$ for some $k,a,b\in\mathbb{N}$ or
$[K_{1}+K_{2}]^{k}+K_{1}+K_{a}+K_{b}$ for some $k\in\mathbb{N}\cup\\{0\\}$,
$a,b\in\mathbb{N}$. We assume that the size of $PK_{n,m}^{2}$ is $m$; the case
that its size is $m+1$ is almost identical. Let $v$ be the vertex that
realises the remoteness, i.e., the vertex in the leftmost $K_{1}$, and let
$H:=PK_{n,m}-V(K_{a}\cup K_{b})$. Define
$\varepsilon:=\rho(PK^{2}_{n,m})-\big{(}\frac{n}{3}-\frac{2m}{3(n-1)}\big{)}$.
It suffices to show that

$\frac{2}{3}<\varepsilon<\frac{5}{3}.$ (6)

First consider the case that $PK^{2}_{n,m}=[K_{1}+K_{2}]^{k}+K_{a}+K_{b}$
where $k\in\mathbb{N}$. Then $|V(H)|=3k$. Simple calculations show that
$\sigma_{H}(v)=3k^{2}-k$, and $m(H)=5k-2$. Also $a+b=n-3k$. Hence

$\sigma(v,PK^{2}_{n,m})=\sigma_{H}(v)+2k(a+b)+b=3k^{2}-k+2k(n-3k)+b,$

and

$m(PK^{2}_{n,m})=m(H)+\binom{a+b+2}{2}-2b-1=5k-2+\frac{1}{2}(n-3k+2)(n-3k+1)-2b-1.$

Since $\rho(PK^{2}_{n,m})=\frac{\sigma(v,PK^{2}_{n,m})}{n-1}$ we have

$\displaystyle\varepsilon$ $\displaystyle=$
$\displaystyle\frac{3k^{2}-k+2k(n-3k)+b}{n-1}-\frac{n}{3}$
$\displaystyle+\frac{10k-4+(n-3k+2)(n-3k+1)-4b-2}{3(n-1)}$ $\displaystyle=$
$\displaystyle\frac{4}{3}-\frac{2k+b}{3(n-1)}.$

Since $n=3k+a+b$ we have $0<2k+b<n-1$, and thus $1<\varepsilon<\frac{4}{3}$.
and (6) holds.

Now consider the case that $PK^{2}_{n,m}=[K_{1}+K_{2}]^{k}+K_{1}+K_{a}+K_{b}$
where $k\in\mathbb{N}\cup\\{0\\}$. Then $|V(H)|=3k+1$,
$\sigma_{H}(v)=3k^{2}+k$, and $m(H)=5k$. Also $a+b=n-3k-1$. Calculations
similar to the above yield that

$\varepsilon=\frac{5}{3}-\frac{9k+b+2}{3(n-1)}.$

Since $0<9k+b+2<3(n-1)$, we have $\frac{2}{3}<\varepsilon<\frac{5}{3}$, and
(6) follows.
(b) The proof of (b) is similar to (a) and thus omitted. $\Box$

######  Corollary 4.5.

(a) Let $G$ be a $2$-edge-connected graph of order $n$ and size $m$. Then

$\rho(G)\leq\left\\{\begin{array}[]{cc}\frac{n}{3}&\textrm{if
$m<\lceil\frac{5}{3}n\rceil-2$,}\\\
\frac{n}{3}-\frac{2m}{3(n-1)}+\frac{5}{3}&\textrm{if
$m\geq\lceil\frac{5}{3}n\rceil-2$},\end{array}\right.$

and this bound is sharp apart from an additive constant.
(b) Let $G$ be a $3$-edge-connected graph of order $n$ and size $m$. Then

$\rho(G)\leq\left\\{\begin{array}[]{cc}\frac{n}{4}&\textrm{if
$m<\lceil\frac{9}{4}n\rceil-2$,}\\\
\frac{n}{4}-\frac{m}{2(n-1)}+\frac{3}{2}&\textrm{if
$m\geq\lceil\frac{9}{4}n\rceil-2$,}\end{array}\right.$

and this bound is sharp apart from an additive constant.

We note that the results in this section cannot easily be extended to values
of $\lambda$ with $\lambda\geq 4$. For example for $\lambda=4$, graphs of the
form $[K_{1}+K_{4}]^{\ell_{1}}+K_{a_{1}}+K_{b_{1}}$ do not necessarily have
maximum remoteness for graphs of their order and size. Indeed, if such a graph
has order $n$ and size $m$, then their remoteness is
$\frac{n}{5}-\frac{2m}{5(n-1)}+O(1)$, while a graph of the form
$K_{1}+K_{4}++[K_{2}]^{\ell_{2}}+K_{a_{2}}+K_{b_{2}}$ of order $n$ and size
$m$ has remoteness $\frac{n}{4}-\frac{m}{2(n-1)}+O(1)$. For $m=cn(n-1)$, where
$0<c<\frac{1}{2}$ the former graph has remoteness $\frac{(1-2c)n}{5}+O(1)$,
while the latter has remoteness $\frac{(1-2c)n}{4}+O(1)$.

##  5 Maximum remoteness of a triangle-free graph with given order and size

In this section we show that the bounds on the remoteness of graph order $n$
and size $m$ in Theorem 1.2 can be improved significantly for triangle-free
graphs.

######  Theorem 5.1.

Let $G$ be a connected, triangle-free graph of order $n$ and size $m$. Then

$\rho(G)\leq\frac{n}{2}+2-\frac{2m}{n-1}.$

###### Proof.

Let $G$ be a triangle-free graph of order $n$ and size $m$, where $n-1\leq
m\leq\lfloor\frac{n^{2}}{4}\rfloor$. It suffices to show that, for every $v\in
V(G)$,

$\sigma(v,G)\leq\;\dfrac{(n+4)(n-1)}{2}-2m.$ (7)

We proceed by induction on $m$. For $m=n-1$ the bound in 7 becomes

$\sigma(v,G)\leq\frac{(n+4)(n-1)}{2}-2(n-1)=\frac{n(n-1)}{2},$

which holds by Theorem 1.1.

Now assume that $m>n-1$. Then $G$ is not a tree, that is, $G$ contains a
cycle. Let $u$ be an arbitrary vertex on a cycle $C$ such that $d(v,u)$ is
minimum among all $u$ lying on a cycle ($u$ can be $v$). Let $w$ be a vertex
of $C$ adjacent to $u$. Consider the graph $G^{\prime}=G-uw$. We prove that

$d_{G^{\prime}}(v,w)\geq d_{G}(v,w)+2.$ (8)

Let $P_{1}$ be a shortest $(v,w)$ path in $G^{\prime}$, and let
$P_{2}:x_{0},x_{1},\ldots,x_{j}$ be a shortest $(v,u)$-path in $G$, where
$x_{0}=v$, $x_{j}=u$ and $d_{G}(v,u)=j$. We show that $u$ is on $P_{1}$.
Indeed, $x_{0}$ is on $P_{1}$, and we let $i$ be the largest value for which
$x_{i}$ is on $P_{1}$. Since $x_{i}$ is on a cycle, it follows by our choice
of $u$ that $x_{i}=u$, i.e., $i=j$. Hence $u$ is on $P_{1}$.

Now the $(u,w)$-section of $P_{1}$ has more than two edges, since otherwise,
if it had only two edges, then these two edges together with $uw$ would form a
triangle in $G$, a contradiction to $G$ being triangle-free. Hence
$d_{G^{\prime}}(v,w)\geq d_{G}(v,u)+3$. It is easy to see that
$d_{G^{\prime}}(v,u)=d_{G}(v,u)$. Also $d_{G}(v,u)\leq d_{G}(v,w)-1$, and (8)
follows.

The graph $G^{\prime}$ is, connected, triangle-free and has $m-1$ edges. Since
$d_{G}(v,x)\leq d_{G^{\prime}}(v,x)$ for $x\in V(G)-\\{w\\}$, and
$d_{G}(v,w)\leq d_{G^{\prime}}(v,w)-2$, we have
$\sigma(v,G)\leq\sigma(v,G^{\prime})-2$. Applying the induction hypothesis to
$G^{\prime}$ we obtain that

$\sigma(v,G)\leq\sigma(v,G^{\prime})-2\leq\frac{(n+4)(n-1)}{2}-2(m-1)-2=\frac{(n+4)(n-1)}{2}-2m,$

as desired. ∎

We now show that bound in Theorem 5.1 is sharp, even for bipartite graphs.

######  Example 5.1.

Let $n,m\in\mathbb{N}$ be given and let $t\in\mathbb{N}$ be the smallest value
for which $m-n\leq\left\lfloor\dfrac{t^{2}}{4}\right\rfloor-t-1$. We define
$f(t)=\left\lfloor\dfrac{t^{2}}{4}\right\rfloor-t-(m-n)$. Then clearly $1\leq
f(t)\leq\left\lfloor\dfrac{t}{2}\right\rfloor-1$. Define
$BPK_{n,m}=[K_{1}]^{n-t+1}+\overline{K}_{a}+\overline{K}_{b}+\overline{K}_{c}$,
where $a=\left\lfloor\dfrac{t}{2}\right\rfloor-f(t)$,
$b=\left\lceil\dfrac{t}{2}\right\rceil-1$ and $c=f(t)$.

Clearly, $BPK_{n,m}$ is a bipartite graph with $n$ vertices and
$n-t+\left\lfloor\dfrac{t^{2}}{4}\right\rfloor-f(t)=m$ edges. Let $v$ be the
vertex that realises the remoteness, i.e., the vertex in the leftmost $K_{1}$.

$\displaystyle\sigma(v,BPK_{n,m})=$
$\displaystyle\sum_{i=0}^{n-t}i+(n-t+1)\left(\left\lfloor\dfrac{t}{2}\right\rfloor-f(t)\right)+(n-t+2)\left(\left\lceil\dfrac{t}{2}\right\rceil-1\right)$
$\displaystyle\;+(n-t+3)(f(t)).$ (9)

Simplifying Equation (5.1) and substituting the value of $f(t)$ we get that

$\displaystyle\sigma(v,BPK_{n,m})=$
$\displaystyle\;\dfrac{(n+4)(n-1)}{2}-2m-\dfrac{t^{2}}{2}+\left\lfloor\dfrac{t}{2}\right\rfloor+2\left\lceil\dfrac{t}{2}\right\rceil-\dfrac{3t}{2}+2\left\lfloor\dfrac{t^{2}}{4}\right\rfloor$
$\displaystyle=$ $\displaystyle\;\dfrac{(n+4)(n-1)}{2}-2m.$

Hence $BPK_{n,m}$ attains the upper bounds in Theorem 5.1.

## References

  * [1] Ai, J.; Gerke, S.; Gutin, G.; Mafunda, S.; Proximity and Remoteness in Directed and Undirected Graphs. Discrete Math. 344 no. 3 (2021), 112252.
  * [2] Aouchiche, M.; Comparaison automatisée d’invariants en théorie des graphes, Ph.D. Thesis, École Polytechnique de Montréal, (2006).
  * [3] Aouchiche, M.; Caporossi, G.; Hansen, P.; Variable neighbourhood search for extremal graphs, 20. Automated comparison of graph invariants. MATCH Commun. Math. Comput. Chem. 58 (2007) 365–384.
  * [4] Aouchiche, M.; Hansen, P.; Proximity and remoteness in graphs: results and conjectures. Networks 58(no. 2) (2011), 95-102.
  * [5] Aouchiche, M.; Hansen, P.; Proximity, remoteness and girth in graphs. Discrete Appl. Math. 222 (2017), 31-39.
  * [6] Aouchiche, M.; Rather, B.A.; Proximity and remoteness in graphs: a survey. Discrete App. Math. 353 (2024), 94-120.
  * [7] Barefoot, C.A.; Entringer, R.C.; Székely, L.A.; Extremal values for ratios of distances in trees. Discrete Appl. Math. 80 (1997), 37-56.
  * [8] Czabarka, É.; Dankelmann, P.; Olsen,T.; Székely, L.A.; Wiener index and remoteness in triangulations and quadrangulations. Discrete Math. Theor. Comp. Sci. 23,1 no. 3 (2021).
  * [9] Dankelmann, P.; Proximity, remoteness, and minimum degree. Discrete Appl. Math. 184 (2015), 223-228.
  * [10] Dankelmann, P.; New bounds on proximity and remoteness in graphs. Communications in Combinatorics and Optimization 1 (2016) 28-40.
  * [11] Dankelmann, P.; Jonck, E.; Mafunda, S.; Proximity and remoteness in triangle-free and $C_{4}$-free graphs in terms of order and minimum degree. Discrete Math. 344 no. 9 (2021), 112513.
  * [12] Dankelmann, P.; Mafunda, S.; On the difference between proximity and other distance parameters in triangle-free graphs and $C_{4}$-free graphs. Discrete Appl. Math. 321 (2022), 295-307.
  * [13] Dankelmann, P.; Mafunda, S.; Mallu, S.; Proximity, remoteness and maximum degree in graphs. Discrete Math and Theoretical Computer Science. 24 no. 2 (2022).
  * [14] Entringer, R.C.; Jackson, D.E.; Snyder, D.A.; Distance in graphs. Czechoslovak Math. J. 26 (101) no. 2 (1976), 283-296.
  * [15] Hua, H.; Das, K.Ch.; Proof of conjectures on remoteness and proximity in graphs. Discrete Appl. Math. 171 (2014), 72-80.
  * [16] Hua, H.; Chen, Y.; Das, K.Ch.; The difference between remoteness and radius of a graph. Discrete Appl. Math. 187 (2015), 103-110.
  * [17] Ma, B.; Wu, B.; Zhang, W.; Proximity and average eccentricity of a graph. Inform. Process. Lett. 112(no. 10) (2012), 392-395.
  * [18] Mafunda, S.; Aspects of distance measures in graphs and digraphs. Ph.D. Thesis, University of Johannesburg, (2020).
  * [19] O. Ore. Diameters in graphs. J. Combin. Theory 5 (1968), 75-81.
  * [20] Plesník, J.; On the sum of all distances in a graph or digraph. J. Graph Theory 8 no. 1 (1984), 1-21.
  * [21] Rissner, R.; Burkard, R.E.; Bounds on the radius and status of graphs. Networks, 64 no. 2 (2014), 76-83.
  * [22] Sedlar, J.; Remoteness, proximity and few other distance invariants in graphs. Filomat 27 no. 8 (2013), 1425-1435.
  * [23] Soltés, L.; Transmission in graphs: A bound and vertex removing. Mathematica Slovaca 41 (1991), 11-16.
  * [24] Wu, B.; Zhang, W.; Average distance, radius and remoteness of a graph. Ars Math. Contemp. 7 no. 2 (2014), 441-452.
  * [25] Zelinka, B.; Medians and peripherians of trees. Arch. Math. (Brno) 4 (1968), 87-95.


# A Note on Terai’s Conjecture Concerning the Exponential Diophantine Equation
$x^{2}+b^{y}=c^{z}$

Refik Keskina and Zafer Şiarb $\ {}^{a}$Sakarya University, Mathematics
Department, Sakarya/Turkey  bBingöl University, Mathematics Department,
Bingöl/Turkey<EMAIL_ADDRESS><EMAIL_ADDRESS>
###### Abstract

Let $(a,b,c)$ be a primitive Pythagorean triple, i.e., $a^{2}+b^{2}=c^{2}$
with $\gcd(a,b,c)=1$, $a$ even and $b$ odd. Terai’s conjecture says that the
Diophantine equation

$x^{2}+b^{y}=c^{z}$

has only the positive integer solutions $(x,y,z)=(a,2,2)$. In this study, we
prove that Terai’s conjecture is true when $b$ is a product of two primes and
$c\equiv 5(\mathop{\mathrm{m}od}8)$.

##  1 Introduction

Let $(a,b,c)$ be a primitive Pythagorean triple, i.e., $a,b,c$ are positive
integers such that $a^{2}+b^{2}=c^{2}$ with $\gcd(a,b,c)=1$, $a$ even and $b$
odd. In [5], Terai conjecture that the Diophantine equation

$x^{2}+b^{y}=c^{z}$

has only the positive integer solutions $(x,y,z)=(a,2,2)$ and proved that the
conjecture is true if $b$ and $c$ are primes with $b^{2}+1=2c.$ Terai’s
conjecture is proved in the special cases. In [3], the authors proved that the
conjecture is true when $c\equiv 5(\mathop{\mathrm{m}od}8)$ and $b$ or $c$ is
a prime power. In [6], the authors showed that Terai’s conjecture is true if
$b\equiv\pm 5(\mathop{\mathrm{m}od}8)$ and $c$ is prime. Recently, in [7], the
authors have proved that Terai’s conjecture is true if

$(a,b,c)=(2^{r+1}s,2^{2r}s^{2}-1,2^{2r}s^{2}+1),$

where $r,s\in\mathbb{N},\gcd(2,s)=1,r\geq 2$, and$~{}s<2^{r-1}$. One can
consult [8] and [9] for more information about Terai’s conjecture.

It is well known that if $(a,b,c)$ is a primitive Pythagorean triple, then
there are positive integers $m$ and $n$ such that

$\gcd(m,n)=1,m>n,m\not\equiv
n(\mathop{\mathrm{m}od}2),a=2mn,b=m^{2}-n^{2},c=m^{2}+n^{2}.$

In this study, we prove that Terai’s conjecture is true when $b$ is a product
of two primes and $c\equiv 5(\mathop{\mathrm{m}od}8)$. That is, we prove that

###### Theorem 1

Let $m,n\in\mathbb{Z}^{+}$ such that $m>n,~{}\gcd(m,n)=1$ and $m\not\equiv
n(\mathop{\mathrm{m}od}2).$ If $m^{2}+n^{2}\equiv
5(\mathop{\mathrm{m}od}8),~{}m+n$ and $m-n$ are prime numbers, then the only
solution of the equation

$x^{2}+(m^{2}-n^{2})^{y}=(m^{2}+n^{2})^{z}$ (1)

is $(x,y,z)$ $=(2mn,2,2).$

##  2 Preliminaries

In this section, we give some lemmas which will be useful in proving our
theorem.

###### Lemma 2

([4]) Let $x,y,z\in\mathbb{Z},~{}z>0,~{}\gcd(x,y)=1$ and $2|y.$ Then every
solution $(x,y,z)$ of the equation

$x^{2}+y^{2}=z^{m}$

can be expressed as

$\displaystyle z$ $\displaystyle=$ $\displaystyle
u^{2}+v^{2},~{}u,v\in\mathbb{N},~{}\gcd(u,v)=1,~{}2|v,$ $\displaystyle x+iy$
$\displaystyle=$
$\displaystyle\lambda_{1}(u+\lambda_{2}iv)^{m},\lambda_{1},\lambda_{2}\in\left\\{-1,1\right\\}.$

In [2], the authors proved the following result (see Corollary $1.2)$.

###### Lemma 3

Let $p$ and $n>3$ be primes. If $y$ is not the sum of two consecutive squares,
then the equation

$x^{2}+p^{2m}=2y^{n}$

has no solution $(x,y,m,n)$ in positive integers $x,y,m$ with $\gcd(x,y)=1$ .

The following lemma is proved by Cohn in [1] .

###### Lemma 4

The Diophantine equation $2z^{k}=y^{2}+1$ with $k>2$ has only the solutions
$y=z=1$ and $y=239,z=13,k=4.$

Thus, we can give the following result.

###### Corollary 5

If $q\geq 3$ is odd, then the equation $y^{q}=a^{2}+(a+1)^{2}$ has no positive
integer solutions $y$ and $a.$

##  3 The proof of Theorem 1

Assume that $m^{2}+n^{2}\equiv 5(\mathop{\mathrm{m}od}8),~{}\gcd(m,n)=1$,
$m\not\equiv n(\mathop{\mathrm{m}od}2)$, and $m+n=p,$ $m-n=q$ with prime
integers $p,q.$ Let $(x,y,z)$ be a solution of the equation (1). In this case,

$x^{2}\equiv-(m^{2}-n^{2})^{y}\equiv-(2n^{2})^{y}\left(\mathop{\mathrm{m}od}m^{2}+n^{2}\right).$

This implies that

$1=\left(\frac{-(2n^{2})^{y}}{m^{2}+n^{2}}\right)=\left(\frac{2}{m^{2}+n^{2}}\right)^{y}=(-1)^{y}$

since $m^{2}+n^{2}\equiv 5(\mathop{\mathrm{m}od}8),$ where the symbol
$\left(\frac{\cdot}{\cdot}\right)$ denotes the Jacobi symbol. The last
equality gives that $y$ is even. Similarly, since

$x^{2}\equiv(m^{2}+n^{2})^{z}\equiv(2n^{2})^{z}\left(\mathop{\mathrm{m}od}m^{2}-n^{2}\right)$

and $m^{2}-n^{2}=m^{2}+n^{2}-2n^{2}\equiv\pm 5(\mathop{\mathrm{m}od}8),$ it
follows that

$1=\left(\frac{(2n^{2})^{z}}{m^{2}-n^{2}}\right)=\left(\frac{2}{m^{2}-n^{2}}\right)^{z}=(-1)^{z}.$

Thus, $z$ is also even. So, let $y=2r$ and $z=2k$ for some positive integers
$r$ and $k.$ In this case, we have

$x^{2}+(m^{2}-n^{2})^{2r}=(m^{2}+n^{2})^{2k}.$ (2)

Since $(m,n)=1$ and $m\not\equiv n(\mathop{\mathrm{m}od}2),$ it can be easily
seen that $\gcd(x,m^{2}-n^{2},m^{2}+n^{2})=1$ and so
$(x,\left(m^{2}-n^{2}\right)^{r},\left(m^{2}+n^{2}\right)^{k})$ is a primitive
Pythagorean triple. Therefore, there exist positive integers $u$ and $v$ such
that $x=2uv,~{}\left(m^{2}-n^{2}\right)^{r}=u^{2}-v^{2},$ and
$\left(m^{2}+n^{2}\right)^{k}=u^{2}+v^{2},$ where $u>v,~{}\gcd(u,v)=1$
and$~{}u\not\equiv v(\mathop{\mathrm{m}od}2).$ The equalities
$\left(m^{2}-n^{2}\right)^{r}=u^{2}-v^{2}$ and
$\left(m^{2}+n^{2}\right)^{k}=u^{2}+v^{2}$ yield to

$\displaystyle 2u^{2}$ $\displaystyle=$
$\displaystyle\left(m^{2}-n^{2}\right)^{r}+\left(m^{2}+n^{2}\right)^{k}$
$\displaystyle 2v^{2}$ $\displaystyle=$
$\displaystyle\left(m^{2}+n^{2}\right)^{k}-\left(m^{2}-n^{2}\right)^{r}.$

From here, we get

$2u^{2}\equiv(m^{2}-n^{2})^{r}\equiv-(2n^{2})^{r}\left(\mathop{\mathrm{m}od}m^{2}+n^{2}\right)$

and

$2v^{2}\equiv(m^{2}+n^{2})^{k}\equiv(2n^{2})^{k}\left(\mathop{\mathrm{m}od}m^{2}-n^{2}\right).$

These congruences, respectively, imply that

$-1=\left(\frac{2}{m^{2}+n^{2}}\right)=\left(\frac{-(2n^{2})^{r}}{m^{2}+n^{2}}\right)=-\left(\frac{2}{m^{2}+n^{2}}\right)^{r}=(-1)^{r}$

and

$-1=\left(\frac{2}{m^{2}-n^{2}}\right)=\left(\frac{(2n^{2})^{k}}{m^{2}-n^{2}}\right)=\left(\frac{2}{m^{2}-n^{2}}\right)^{k}=(-1)^{k}.$

Therefore, $r$ and $k$ are odd. On the other hand, we have

$u^{2}-v^{2}=(u-v)(u+v)=\left(m^{2}-n^{2}\right)^{r}=p^{r}q^{r}.$

Since $\gcd(u-v,u+v)=1,$ it follows that either $u+v=p^{r},~{}u-v=q^{r}$ or
$u-v=1$, $u+v=p^{r}q^{r}.$ Assume that $u-v=1$ and $u+v=p^{r}q^{r}.$ In this
case, we have

$2\left(m^{2}+n^{2}\right)^{k}=2(u^{2}+v^{2})=(pq)^{2r}+1.$

Since $k$ is odd, this is impossible by Lemma 4 if $k>1.$ Therefore $k=1.$
Hence, we get

$2\left(m^{2}+n^{2}\right)=(pq)^{2r}+1.$ (3)

As $m+n=p,$ $m-n=q,$ we see that $2\left(m^{2}+n^{2}\right)=p^{2}+q^{2}.$ It
follows that

$(pq)^{2r}+1=p^{2}+q^{2},$ (4)

which is impossible. Now assume that $u-v=q^{r}$ and$~{}u+v=p^{r}.$ Then, it
is seen that

$p^{2r}+q^{2r}=2(u^{2}+v^{2})=2\left(m^{2}+n^{2}\right)^{k}$ (5)

and from here, we get

$\left(\frac{p^{r}+q^{r}}{2}\right)^{2}+\left(\frac{p^{r}-q^{r}}{2}\right)^{2}=\left(m^{2}+n^{2}\right)^{k}.$

Now, taking

$x=\frac{p^{r}+q^{r}}{2},~{}y=\frac{p^{r}-q^{r}}{2},z=m^{2}+n^{2}$

in Lemma 2 and considering the fact that $k$ is odd, we can write

$m^{2}+n^{2}=z=c^{2}+d^{2},c,d\in\mathbb{Z},\gcd(c,d)=1,2|d,x+iy=(c+id)^{k}$

Thus, we can see that

$p^{r}=\frac{(c+di)^{k}+(c-di)^{k}}{2}+\frac{(c+di)^{k}-(c-di)^{k}}{2i}$

and

$q^{r}=\frac{(c+di)^{k}+(c-di)^{k}}{2}-\frac{(c+di)^{k}-(c-di)^{k}}{2i}.$

From the last equations, we get

$2p^{r}=(c+di)^{k}(1-i)+(c-di)^{k}(1+i)$ (6)

and

$2q^{r}=(c+di)^{k}(1+i)+(c-di)^{k}(1-i).$ (7)

Also, it can be seen that

$\displaystyle c+id$ $\displaystyle\equiv$ $\displaystyle-d+id\equiv
d(-1+i)(\mathop{\mathrm{m}od}c+d),$ (8) $\displaystyle c-id$
$\displaystyle\equiv$ $\displaystyle-d-
id\equiv-d(1+i)(\mathop{\mathrm{m}od}c+d),$ (9) $c+id\equiv d+id\equiv
d(1+i)(\mathop{\mathrm{m}od}c-d),$ (10)

and

$c-id\equiv d-id\equiv d(1-i)(\mathop{\mathrm{m}od}c-d).$ (11)

Since $k$ is odd, it follows that $k=4t+1$ or $k=4t+3$ for some nonegative
integer $t.$ Let $k=4t+1.$ Then, using the congruences (8)-(11), we obtain

$\displaystyle 2p^{r}$ $\displaystyle=$
$\displaystyle(c+di)^{k}(1-i)+(c-di)^{k}(1+i)$ $\displaystyle\equiv$
$\displaystyle
d^{k}(-1+i)^{k}(1-i)+(-d)^{k}(1+i)^{k+1}(\mathop{\mathrm{m}od}c+d)$
$\displaystyle\equiv$
$\displaystyle(-d)^{k}\left((1-i)^{k+1}+(1+i)^{k+1}\right)(\mathop{\mathrm{m}od}c+d)$
$\displaystyle\equiv$ $\displaystyle 0(\mathop{\mathrm{m}od}c+d)$

and

$\displaystyle 2q^{r}$ $\displaystyle=$
$\displaystyle(c+di)^{k}(1+i)+(c-di)^{k}(1-i)$ $\displaystyle\equiv$
$\displaystyle
d^{k}(1+i)^{k}(1+i)+d^{k}(1-i)^{k}(1-i)(\mathop{\mathrm{m}od}c-d)$
$\displaystyle\equiv$ $\displaystyle
d^{k}\left((1+i)^{k+1}+(1-i)^{k+1}\right)(\mathop{\mathrm{m}od}c-d)$
$\displaystyle\equiv$ $\displaystyle 0(\mathop{\mathrm{m}od}c-d).$

These imply that $c+d|2p^{r}$ and $c-d|2q^{r}.$ Since $c+d$ and $c-d$ are odd,
we see that $c+d|p^{r}$ and $c-d|q^{r}.~{}$Similarly, if $k=4t+3$, then it can
be seen that $c-d|p^{r}$ and $c+d|q^{r}$. Thus, we can write $\left|c+\epsilon
d\right|=p^{t_{1}}$ and $\left|c-\epsilon d\right|=q^{t_{2}}$ for some
nonnegative integers $t_{1}$ and $t_{2}$, where $\epsilon=\mp 1.$ Assume that
$t_{2}=0$. If $t_{1}=0$, then we get $2=c^{2}+d^{2}$, which is impossible
since

$c^{2}+d^{2}=m^{2}+n^{2}\geq 5.$

Let $t_{1}\geq 1$. Then

$p^{2}+q^{2}=2(m^{2}+n^{2})=2(c^{2}+d^{2})=\left|c-\epsilon
d\right|^{2}+\left|c+\epsilon d\right|^{2}=1+\left|c+\epsilon
d\right|^{2}=1+p^{2t_{1}},$

which is impossible if $t_{1}=1.$ If $t_{1}\geq 2$, then

$p^{2}+q^{2}=1+p^{2t_{1}}\geq 1+p^{4}>2p^{2},$

a contradiction. Let $t_{2}\geq 1$ and $t_{1}=0$. So we obtain

$p^{2}+q^{2}=1+q^{2t_{2}}.$

It is seen that

$(q^{t_{2}}-1)^{2}<q^{2t_{2}}-q^{2}+1=p^{2}<q^{2t_{2}},$

which implies that $q^{t_{2}}-1<p<q^{t_{2}}$. This is a contradiction. So,
$t_{1}\geq 1$ and $t_{2}\geq 1$. Assume that $t_{1}>1$ or $t_{2}>1$. Then we
get

$p^{2}+q^{2}<p^{2t_{1}}+q^{2t_{2}}=\left|c+\epsilon
d\right|^{2}+\left|c+\epsilon
d\right|^{2}=2(c^{2}+d^{2})=2(m^{2}+n^{2})=p^{2}+q^{2},$

a contradiction. Therefore $t_{1}=t_{2}=1.$ This yields to $\left|c+\epsilon
d\right|=p$ and $\left|c-\epsilon d\right|=q$ and so
$m^{2}-n^{2}=pq=|c^{2}-d^{2}|$. As $m^{2}-n^{2}=|c^{2}-d^{2}|$ and
$m^{2}+n^{2}=c^{2}+d^{2}$, it can be seen that $cd=\pm mn$. Now, let
$\alpha=(c+id)$ and $\beta=(c-id).$ Multiplying the equations (6) and (7) side
to side, we obtain

$4p^{r}q^{r}=4(m^{2}-n^{2})^{r}=2(\alpha^{2k}+\beta^{2k}).$ (12)

Now assume that $k>1$ and $r>1.$ Then, since $m^{2}-n^{2}=|c^{2}-d^{2}|,$ it
follows that

$\displaystyle 2(m^{2}-n^{2})^{r}$ $\displaystyle=$
$\displaystyle\alpha^{2k}+\beta^{2k}=(c+id)^{2k}+(c-id)^{2k}$ $\displaystyle=$
$\displaystyle\left((c+id)^{2}+(c-id)^{2}\right)\cdot A$ $\displaystyle=$
$\displaystyle 2\left(c^{2}-d^{2}\right)\cdot A=\mp(m^{2}-n^{2})A,$

which implies that $A=\pm(m^{2}-n^{2})^{r-1}$, where

$A=\mathop{\displaystyle\sum}\limits_{j=0}^{k-1}\left(\alpha^{2}\right)^{k-1-j}\left(-\beta^{2}\right)^{j}.$

Note that $\alpha^{2}+\beta^{2}=2(c^{2}-d^{2}).$ On the other hand, since
$2\left(m^{2}-n^{2}\right)=2\left|c^{2}-d^{2}\right|=\pm\left(\alpha^{2}+\beta^{2}\right),$
it is seen that

$\alpha^{2}\equiv-\beta^{2}(\mathop{\mathrm{m}od}m^{2}-n^{2}).$

Therefore,

$\displaystyle A$ $\displaystyle=$
$\displaystyle\mathop{\displaystyle\sum}\limits_{j=0}^{k-1}\left(\alpha^{2}\right)^{k-1-j}\left(-\beta^{2}\right)^{j}\equiv\mathop{\displaystyle\sum}\limits_{j=0}^{k-1}\left(-\beta^{2}\right)^{k-1-j}\left(-\beta^{2}\right)^{j}(\mathop{\mathrm{m}od}m^{2}-n^{2})$
$\displaystyle\equiv$
$\displaystyle\mathop{\displaystyle\sum}\limits_{j=0}^{k-1}\left(-\beta^{2}\right)^{k-1}(\mathop{\mathrm{m}od}m^{2}-n^{2})$
$\displaystyle\equiv$ $\displaystyle
k\cdot\left(\beta^{2}\right)^{k-1}(\mathop{\mathrm{m}od}m^{2}-n^{2}).$

Also, since $\beta^{2}=c^{2}-d^{2}-2cdi$ and $cd=\pm mn$, we see that

$\beta^{2}\equiv\mp 2mni(\mathop{\mathrm{m}od}m^{2}-n^{2})$

and thus, $\left(\beta^{2}\right)^{k-1}\equiv
2^{k-1}\cdot(mn)^{k-1}(\mathop{\mathrm{m}od}m^{2}-n^{2}),$ where we used the
fact that that $k-1$ is even. Hence,

$A\equiv k\cdot 2^{k-1}\cdot(mn)^{k-1}(\mathop{\mathrm{m}od}m^{2}-n^{2}).$

As $r>1$, and $A=\pm(m^{2}-n^{2})^{r-1}$, it is seen that $m^{2}-n^{2}|A.$ So
it follows that $m^{2}-n^{2}|k\cdot(mn)^{k-1}$ since $m^{2}-n^{2}$ is odd. It
can be easily seen that

$\gcd((mn)^{k-1},m^{2}-n^{2})=1.$

Thus, we get $m^{2}-n^{2}|k.$ Then,

$k=(m^{2}-n^{2})a=pqa$

for some odd positive integer $a.$ Let rearrange the equation (5) as

$2\left(\left(m^{2}+n^{2}\right)^{qa}\right)^{p}=p^{2r}+q^{2r}.$ (13)

Since $q\geq 3$, it is seen that $\left(m^{2}+n^{2}\right)^{qa}$ is not the
sum of two consecutive squares by Corollary 5. Then by Lemma 3, the equation
(13) has no solutions since $p>3.$

Consequently, $k=1$ or $r=1.$ If $k=1$, then (5) implies that

$p^{2r}+q^{2r}=2(u^{2}+v^{2})=2\left(m^{2}+n^{2}\right)^{k}=2(m^{2}+n^{2})=p^{2}+q^{2}.$
(14)

This yields to $r=1.$ If $r=1$, then (5) shows that

$2\left(m^{2}+n^{2}\right)=p^{2}+q^{2}=p^{2r}+q^{2r}=2(u^{2}+v^{2})=2(m^{2}+n^{2})^{k}$

and therefore $k=1.$ Thus $y=2r=2,z=2k=2$ and so the only solution is
$(x,y,z)$ $=(2mn,2,2)$.

## References

  * [1] Cohn, J. H. E. _Perfect Pell Powers_ , Glasgow Math. J. 38 (1996), no. 1, 19–20
  * [2] Zhu, Huilin; Le, Maohua; Togbé, Alain, _On the exponential Diophantine equation_ $x^{2}+p^{2m}=2y^{n}$. Bull. Aust. Math. Soc. 86 (2012), no. 2, 303–314.
  * [3] Cao, Zhenfu; Dong, Xiaolei _On Terai’s conjecture_. Proc. Japan Acad. Ser. A Math. Sci. 74 (1998), no. 8, 127–129
  * [4] L. J. Mordell, _Diophantine Equations_ , Academic Press, London, 1969.
  * [5] Terai, N., _The Diophantine equation_ $x^{2}+q^{m}=p^{n}$, Acta Arith. 63 (1993), no. 4, 351–358.
  * [6] Yuan, P., Wang, J. _On theDiophantine equation_ $x^{2}+b^{y}=c^{z}$. Acta Arith. 84 (1998), no. 2, 145–147.
  * [7] Le, M., Soydan, G., _A note on Terai’s conjecture concerning primitive Pythagorean triples_ , Hacet. J. Math. Stat., https://doi.org/10.15672/hujms.795889.
  * [8] Le, M., Soydan, G. _A brief survey on the generalized Lebesgue-Ramanujan-Nagell equation_ , Surv. Math. Appl. 15 (2020), 473-523.
  * [9] Le, M., Scott, R., Styer, R.,_A survey on the ternary purely exponential Diophantine equation_ $a^{x}+b^{y}=c^{z}$, Surv. Math. Appl. 14 (2019), 109 – 140.


# CompuMat: A Computational Composite Material for Tangible Interaction

Xinyi Yang<EMAIL_ADDRESS>Harvard UniversityCambridgeMAUSA ,
Martin Nisser  Massachusetts Institute of TechnologyCambridgeMAUSA and
Stefanie Mueller  Massachusetts Institute of TechnologyCambridgeMAUSA

(2023)

###### Abstract.

This paper introduces a computational composite material comprising layers for
actuation, computation and energy storage. Key to its design is inexpensive
materials assembled from traditionally available fabrication machines to
support the rapid exploration of applications from computational composites.
The actuation layer is a soft magnetic sheet that is programmed to either
bond, repel, or remain agnostic to other areas of the sheet. The computation
layer is a flexible PCB made from copper-clad kapton engraved by a fiber
laser, powered by a third energy-storage layer comprised of 0.4mm-thin lithium
polymer batteries. We present the material layup and an accompanying digital
fabrication process enabling users to rapidly prototype their own untethered,
interactive and tangible prototypes. The material is low-profile, inexpensive,
and fully untethered, capable of being used for a variety of applications in
HCI and robotics including structural origami and proprioception.

Digital fabrication, Flexible electronics, Rapid prototyping

††journalyear: 2023††copyright: rightsretained††conference: TEI ’23:
Proceedings of the Seventeenth International Conference on Tangible, Embedded,
and Embodied Interaction; February 26-March 1, 2023; Warsaw,
Poland††booktitle: TEI ’23: Proceedings of the Seventeenth International
Conference on Tangible, Embedded, and Embodied Interaction (TEI ’23), February
26-March 1, 2023, Warsaw, Poland††doi: 10.1145/3569009.3573120††isbn:
978-1-4503-9977-7/23/02††ccs: Human-centered computing Human computer
interaction (HCI) Figure 1. Layup The layup of our composite sheet includes a
structural support layer, a programmable magnetic sheet that selectively bonds
to other sheets, a flexible PCB layer and a 0.4mm-thin lithium polymer battery
layer to power it, and an optional layer to convey desired affordances or
aesthetics. Mechanism overview A circuit is divided into two parts, and bonded
to two magnetic sheets coded with opposite magnetic patterns. The sheets will
only bond in one configuration, closing the circuit. Applications A
fabrication sample shows a composite square with exposed pads for electronic
components can be soldered to achieve specific applications when mated to a
complementary square.

##  1\. Introduction & Overview

Since the vision of Digital Bits proposed in Ishii’s 1997 paper (Ishii and
Ullmer, 1997), tangible user interfaces have been explored in a wide range of
forms. In exploring how to transition from interacting with bits on desktop
digital devices to interacting with digital bits embedded in physical objects,
researchers have explored creating objects that controlled digitally using
electromagnets (Nisser et al., 2021) or that shape-change predictably via
linearly actuated pistons (Follmer et al., 2013) or soluble support material
(Nisser et al., 2019). Moving to increase portability and inspired in many
ways by papercraft, growing communities of researchers turned to fabricating
interactive material sheets. This work is strongly informed by seminal
research on proposed Computational Composites (Vallgårda and Redström, 2007)
or Robotic Materials (McEvoy and Correll, 2015) that combine sensing,
actuation and computation in single composite material. For example,
Printscreen (Olberding et al., 2014) developed thin film sheets embedded with
both capacitive touch and display capabilities and Foldio (Olberding et al.,
2015) built on this work to enable self-foldability via embedded material
actuators. Such laminate composite materials capable of both sensing and
actuation have more recently been developed using actively controlled shape
memory polymer (Nisser et al., 2016). As these actuators suffer from power-
inefficiencies and required offboard energy storage, more recent techniques
have leveraged programmable magnetic sheets to enable both physical actuation
and interaction (Nisser et al., 2022a). However, these new materials have
proven challenging to manufacture as composite sheets capable of sensing,
computation, actuation and energy storage in an untethered, portable manner.
While foundational work has been done to design materials fitting these
criteria, an under-explored area has been the design of such a computational
composite that leverages inexpensive, commercially available materials that
can be manufactured using traditionally available fabrication machines.

In this paper, we design such a composite from readily available materials and
manufacturing platforms with the aim to accelerate experimentation and
prototyping of applications for computational composite materials. We leverage
sheets of programmable magnetic sheet to build on prior technologies and
propose an inexpensive material layup (Figure 1) that can be fabricated using
typical makerspace machines (Figure 2) that combines sensing, actuation and
energy storage for general purpose use. We use the Mixels interface (Nisser et
al., 2022a) to produce pairs of magnetic sheet that attract or repel in one
configuration, but remain agnostic in all others. The desired functionality is
given to the accompanying UI, which produces the required magnetic pixel
patterns and plots them using a magnetic plotter. We then use a fiber laser to
rapidly engrave custom PCB pairs whose circuits close electrically only when
superimposed in their correct configuration. By bonding these PCB pairs to
magnetic sheet pairs and battery layers, we produce a magnetically actuated
electronic sheet that only bonds in a particular, self-aligning orientation,
which closes its circuit to become electronically functional (Figure 2). We
use the sheet for applications including tangible interactions and origami-
inspired self-folding.

##  2\. Background and Related Work

In this section, we outline related work in smart laminate materials and
methods that have leveraged magnetism to imbue objects with interactive
capabilities.

###  2.1. Computational Composite Materials

Computational Composites (Vallgårda and Redström, 2007) or Robotic Materials
(McEvoy and Correll, 2015) that combine sensing, actuation and computation in
single composite material, or portable sheets capable of interacting with the
user, have been explored by researchers across a variety of communities in the
form of tangible devices, papercraft, and foldable robots. Researchers have
used printed circuits to create lightweight and portable interfaces that
harvest energy from human interaction (Karagozler et al., 2014), enable paper-
based computing through interactive pop-up books (Qi and Buechley, 2010; Zhao
et al., 2017) and that leverage thin film displays to create paper-based
sheets capable of dynamic visual feedback for educational tool-kits (Klamka
and Dachselt, 2017).

By adhering together structural layers, embedded electronics, actuators and
flexural hinges, roboticists have developed robots that can be manufactured as
smart laminate sheets before self-folding into their target geometries. Using
paper and carbon fiber as structural backing to flexible PCBs, researchers
have embedded actuators in the form of shape memory alloys (Firouzeh and Paik,
2015), shape memory polymers (Nisser et al., 2016), and pneumatically
activated polymer pouches (Niiyama et al., 2015). However these actuators
typically suffer from power-inefficiencies and require offboard energy from a
dedicated supply to actuate them, reducing portability.

In this work, we substitute away energy-intensive material actuators in favor
of reprogrammable magnetic materials capable of exerting near-field forces
without any online power. These materials are instead programmed to exert
particular forces before use, simplifying force control, and reducing both the
cost and thickness of the sheet.

###  2.2. Magnetically actuated interactive objects

Magnets have been widely used to create actuated interfaces by manipulating
the magnetic fields surrounding an object. Researchers have used digitally
controlled electromagnets to move objects across desks (Pangaro et al., 2002),
fabricated paper-based media that enable both movement and dynamic
interaction(Ogata and Fukumoto, 2015), utilized magnets to develop VR
interaction tool-kits (Zhao et al., 2017), and invented portable displays by
embedding shielded magnetic designs (Liang et al., 2014). In recent years,
researchers have explored the feasibility of using magnetic sheet by
programming patterns onto them for both haptic and other novel interactive
applications (Yasu, 2017, 2019). In particular, Mixels (Nisser et al., 2022a)
built upon work on orthonormal magnetic codes (Nisser et al., 2022b) to
develop a magnetic plotter and accompanying user interface that could be used
to plot magnetic patterns that were selectively attractive and agnostic to
other patterns.

In this paper, we build on Mixels by integrating their sheet into a material
stack of PCBs and battery layers to develop a portable smart laminate
material, and develop a digital fabrication pipeline to support its creation.
The programmed magnetic sheets allows the material stack to bond selectively
to only particular parts of other sheets, creating opportunities in snappable
PCBs and error-correcting folding of origami-inspired structures.

##  3\. Design and fabrication pipeline for programmable composite materials

This section introduces the design and fabrication procedure for making
magnetically programmable composite materials. We begin by introducing the
material layup and detail the software and hardware involved in fabricating
the finished laminate.

###  3.1. Material layup

Our smart composite material is comprised of three key layers to enable
actuation, computation and energy storage, respectively, and costs
approximately $6 USD per 50mm square.

Actuation layer The actuation layer is a soft magnetic sheet that is
programmed using the Mixels interface to either bond, repel, or remain
agnostic to other areas of the sheet. We use flexible, inexpensive off-the-
shelf fridge magnet that is traditionally used as stickers refrigerators and
white boards. Thicker sheet is capable of supporting stronger magnetic
attraction, while thinner sheet is more lightweight and amenable to bending.
We sampled four material thicknesses (0.1mm, 0.55mm, 0.76mm and 1mm) of
generic magnetic sheet and chose 0.76mm sheet as a trade-off between these
desirable criteria.

Computation layer The computation layer is a flexible PCB made from copper-
clad kapton engraved by a fiber laser. We use sheet with a copper trace
thickness of 0.3mm which gives high conductivity with insignificant voltage
drops and retaining sufficient rigidity to prevent breakage during handling,
while remaining flexible enough to allow rolling of the sheet. Copper traces
permit electronic components to be soldered directly onto the copper pads
during fabrication.

Energy storage layer The computation layer is powered by a third, energy-
storage layer, which is comprised of a 0.4mm-thin flexible lithium polymer
battery (Powerstream). These batteries are rechargeable, flexible and exhibit
an operating voltage up to 3.6V which supports interfacing with COTS
electronic components.

Optional layers Two additional, optional layers introduced in Figure 1 are
designated as a structural layer, to give further support to the sheet for
load-bearing applications, and an aesthetic layer, to give the sheet a desired
texture or color; in future work, this could be augmented with thin film
displays (Olberding et al., 2014).

Figure 2. Design and fabrication pipeline: We use copper-clad kapton and soft
magnetic sheet to encode with circuits and magnetic codes, respectively; We
design circuits and code the magnetic patterns using our own user interface,
outputting dxf files for the fiber laser and magnetic plotter to cut and plot;
These produce pairs of flexible PCBs and magnetic sheets with desired
patterns; We populate the PCBs with components and assemble the material
layups into sheet A and sheet B; The sheet becomes electrically functional
when sheets A and B are properly aligned, in which orientation they bond
magnetically. Figure 3. Designing (left) circuits for the fiber laser,
(middle) magnetic programs using the Mixels user interface, and (right)
magnetic sheets for cutting on a vinyl cutter.

###  3.2. Fabrication pipeline

The design and fabrication pipeline for fabricating our smart composite
material is illustrated in Figure 2. These produce pairs of flexible PCBs and
magnetic sheets with desired patterns; We populate the PCBs with components
and assemble the material layups into sheet A and sheet B; The sheet becomes
electrically functional when sheets A and B are properly aligned, in which
orientation they bond magnetically.

Materials: The process begins with selecting sheets of the copper-clad kapton
and soft magnetic sheet described in the materials section above.

Design: We design our circuit pad layouts in Adobe Illustrator and output dxf
files for the fiber laser software (zCAD) to execute on the copper-clad kapton
(Figure 3). We design square magnetic sheet geometries for simplicity and use
the Mixels user interface to design selectively attractive patterns to plot
onto these sheets using the magnetic plotter. By convention we refer to two
mating magnetic sheets as A and B, where Mixels ensures that A and B will only
bond attractively in one configuration while remaining magnetically agnostic
in all other translations and rotations.

Fabrication: We execute the circuit pattern on the copper clad kapton using
the fiber laser, upload a desired interface design into the vinyl cutter
software (Silhouette Studio) to cut desired sizes of magnetic sheet (for
simplicity, we use squares), and encode the magnetic programs onto the soft
magnetic sheets using the Mixels magnetic plotter. This plotter consists of a
Snapmaker 3-in-1 augmented with an add-on supporting an Arduino Nano micro-
controller, an electromagnet, an H-bridge, and a hall effect sensor encased in
a 3D-printed housing.

Assembly: After soldering any required electronic components onto the finished
PCB, we adhere the PCB layer and a battery layer onto each magnetically
programmed sheet (A and B) using CA glue.

Testing: Once each individual laminate is assembled, we superimpose the two
sheets in their correct mating configuration and confirm magnetic attraction
and a strong electrical connection (Figure 4A,B,C,D). The sheets will not bond
readily in any other configuration, helping the user find the correct
orientation and avoiding shorting the circuit.

Figure 4. Electronic magnetic sheet: (A). Exposed PCBs of sheets A and B (B)
Display and battery sides. (C) When the complementary sheets A and B combine,
the LEDs light up and blink every second. (D) The thickness of the electronic
magnetic sheet is 3mm. (E) Application: Authentication User Interface. Two
PCBs, here labeled Tom and Jerry, will selectively pair in different
configurations on the larger bottom PCB, lighting up different LEDs with Tom
and Jerry IDs. (F) Application: Object classification. Three magnetically-
folded boxes of equal size contain different contents. A classifier that
couples the magnetic interactions to a force transducer communicates the
contents of the boxes via LEDs without opening them. (G) Tangible Interface
for learning the Scratch language. Scratch components will only bond in
locations where they form correct semantic meanings, and light up an LED when
placed there to communicate this to the student.

##  4\. Applications

We illustrate use cases of our composite material and fabrication process
through applications in physical authentication, classification, tangible
interfaces and foldable structures.

###  4.1. Double-authentication user interface

We can leverage the selectivity of the magnetic codes together with the
closing of the electrical circuit for aligned PCBs as a double-authentication
method, as both magnetic bonding and electrical connection are required to
verify correct bonding. Using PCBs populated with LEDs to communicate this
authentication visually, we can enrich the feedback to the user in a way that
is tailored to the application (Figure 4E).

###  4.2. Object detection, classification and tracking

Object detection, classification, and tracking are critical features to
logistics, transportation, and warehousing management, and ways to do so
unobtrusively are particularly salient in HCI. With our technique, we leverage
magnetic codes to build a sheet that bonds to itself when folded to form a
cube. We fill the cubes with contents before folding the last side, it’s lid.
Outward-facing magnetic codes on each cube allow each cubic ”package” to be
identified and sorted without opening it (Figure 4F).

###  4.3. Tangible interface for learning Scratch for K12 student

Scratch is a visual programming language aimed primarily for children as an
educational tool for programming. Using our rapid fabrication technique, we
can physically instantiate these visual programs as interactive physical
coding blocks for students to learn and play with. These blocks can be
magnetically coded to only bond to create a particular ”program”, and designed
electrically to visually confirm correct ”compilation” using LEDs (Figure 4G).

###  4.4. Interactive, foldable structures

Folding is an efficient method to develop bistable and dynamic surfaces (Huang
and Eisenberg, 2012). Using our technique, we fabricate 2D sheets and fold
them into 3D geometries, embedding circuits onto sides of what becomes
different folded solids (Figure 5). In Figure 5A, An unfolded cube is colored
with white on one side and black on the other. It can be folded in either
direction to create either a white or black cube as seen by the user, and a
different LED will light up to confirm correct folding on completion. In
Figure 5B, a more exotic shape has multiple stable configurations, and the LED
only lights up on folding into the particular desired shape.

Figure 5. Conveying successful deployment of folded structures. (A) An
unfolded cube can be folded in two directions to create either a black or
white cube, with different LEDs signaling correct target acquisition. (B) This
mechanism can similarly be used in multistable structures to signal that a
particular geometry has been acquired by the object.

##  5\. Limitations and future work

In this section, we discuss the limitations of our fabrication process and
propose directions for future work.

###  5.1. Fabrication streamlining

Our existing fabrication procedure involves three separate user interfaces and
three different machines, resulting in several disaparate steps in both the
design and fabrication procedures. To unburden user attention and decrease the
risk for human error, future work will streamline file conversion and material
alignment between these procedures.

###  5.2. Magnetic sheet thickness

Increasing the magnetic sheet thickness increases the bonding force available
between mating pairs. While our design trade-off weighed inexpensive,
commercially available alternatives against each other to select our sheet,
materials exhibiting higher flux densities, such as high-purity iron
particulate cast in silicone matrices, could be explored to raise bond
strength while retaining low material thicknesses.

###  5.3. Integrating origami mechanisms

Origami is a traditional Japanese art that has received widespread used in
engineering (Peraza-Hernandez et al., 2014). It has been shown that single
single sheets can be constructed to acquire multiple different target
configurations once folded in order to adapt the sheet to diverse or changing
needs (Reis et al., 2015). Future work should explore leveraging these
capabilities using our approach to develop more exotic applications in self-
folding structures.

##  6\. Conclusion

In this paper, we introduced a computational composite sheet comprised of
actuation, energy and computation layers and developed a fabrication process
for its construction. We leveraged inexpensive materials and readily available
fabrication machines to support the rapid exploration of applications from
computational composites. We illustrated how this sheet can be used to build
new applications for physical authentication, classification, tangible
interfaces and foldable structures. In particular, at a sheet price of $6 per
50mm square, it supports the inexpensive creation of novel interactive devices
that can be assembled rapidly and are capable of communicating its state to
the user via onboard LEDs. Finally, we surveyed the limitations to our
approach and highlighted avenues for future work for continuing the
improvement of portable, computational composite materials for interactive
applications.

## References

  * (1)
  * Firouzeh and Paik (2015) Amir Firouzeh and Jamie Paik. 2015.  Robogami: A fully integrated low-profile robotic origami.  _Journal of Mechanisms and Robotics_ 7, 2 (2015), 021009\.
  * Follmer et al. (2013) Sean Follmer, Daniel Leithinger, Alex Olwal, Akimitsu Hogge, and Hiroshi Ishii. 2013.  inFORM: dynamic physical affordances and constraints through shape and object actuation.. In _Uist_ , Vol. 13. 2501–988.
  * Huang and Eisenberg (2012) Yingdan Huang and Michael Eisenberg. 2012.  Easigami: virtual creation by physical folding. In _Proceedings of the Sixth International Conference on Tangible, Embedded and Embodied Interaction_. 41–48.
  * Ishii and Ullmer (1997) Hiroshi Ishii and Brygg Ullmer. 1997.  Tangible bits: towards seamless interfaces between people, bits and atoms. In _Proceedings of the ACM SIGCHI Conference on Human factors in computing systems_. 234–241.
  * Karagozler et al. (2014) Mustafa Emre Karagozler, Ivan Poupyrev, Gary K Fedder, and Yuri Suzuki. 2014.  Paper generators: harvesting energy from touching, rubbing and sliding. In _Proc. 26th Ann. ACM Symp. User Interface Software and Technology (UIST)_. Citeseer, 161–162.
  * Klamka and Dachselt (2017) Konstantin Klamka and Raimund Dachselt. 2017.  IllumiPaper: Illuminated interactive paper. In _Proceedings of the 2017 CHI Conference on Human Factors in Computing Systems_. 5605–5618.
  * Liang et al. (2014) Rong-Hao Liang, Han-Chih Kuo, Liwei Chan, De-Nian Yang, and Bing-Yu Chen. 2014.  GaussStones: shielded magnetic tangibles for multi-token interactions on portable displays. In _Proceedings of the 27th annual ACM symposium on User interface software and technology_. 365–372.
  * McEvoy and Correll (2015) Michael Andrew McEvoy and Nikolaus Correll. 2015.  Materials that couple sensing, actuation, computation, and communication.  _Science_ 347, 6228 (2015), 1261689.
  * Niiyama et al. (2015) Ryuma Niiyama, Xu Sun, Cynthia Sung, Byoungkwon An, Daniela Rus, and Sangbae Kim. 2015\.  Pouch motors: Printable soft actuators integrated with computational design.  _Soft Robotics_ 2, 2 (2015), 59–70.
  * Nisser et al. (2021) Martin Nisser, Leon Cheng, Yashaswini Makaram, Ryo Suzuki, and Stefanie Mueller. 2021.  Programmable Polarities: Actuating Interactive Prototypes with Programmable Electromagnets. In _The Adjunct Publication of the 34th Annual ACM Symposium on User Interface Software and Technology_. 121–123.
  * Nisser et al. (2022a) Martin Nisser, Yashaswini Makaram, Lucian Covarrubias, Amadou Bah, Faraz Faruqi, Ryo Suzuki, and Stefanie Mueller. 2022a.  Mixels: Fabricating Interfaces using Programmable Magnetic Pixels.  _arXiv preprint arXiv:2208.03804_ (2022).
  * Nisser et al. (2022b) Martin Nisser, Yashaswini Makaram, Faraz Faruqi, Ryo Suzuki, and Stefanie Mueller. 2022b.  Selective Self-Assembly using Re-Programmable Magnetic Pixels.  _arXiv preprint arXiv:2208.03799_ (2022).
  * Nisser et al. (2019) Martin Nisser, Junyi Zhu, Tianye Chen, Katarina Bulovic, Parinya Punpongsanon, and Stefanie Mueller. 2019.  Sequential support: 3d printing dissolvable support material for Time-Dependent mechanisms. In _Proceedings of the Thirteenth International Conference on Tangible, Embedded, and Embodied Interaction_. 669–676.
  * Nisser et al. (2016) Martin EW Nisser, Samuel M Felton, Michael T Tolley, Michael Rubenstein, and Robert J Wood. 2016\.  Feedback-controlled self-folding of autonomous robot collectives. In _2016 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS)_. IEEE, 1254–1261.
  * Ogata and Fukumoto (2015) Masa Ogata and Masaaki Fukumoto. 2015.  FluxPaper: reinventing paper with dynamic actuation powered by magnetic flux. In _Proceedings of the 33rd Annual ACM Conference on Human Factors in Computing Systems_. 29–38.
  * Olberding et al. (2015) Simon Olberding, Sergio Soto Ortega, Klaus Hildebrandt, and Jürgen Steimle. 2015.  Foldio: Digital fabrication of interactive and shape-changing objects with foldable printed electronics. In _Proceedings of the 28th Annual ACM Symposium on User Interface Software & Technology_. 223–232.
  * Olberding et al. (2014) Simon Olberding, Michael Wessely, and Jürgen Steimle. 2014\.  PrintScreen: fabricating highly customizable thin-film touch-displays. In _Proceedings of the 27th annual ACM symposium on User interface software and technology_. 281–290.
  * Pangaro et al. (2002) Gian Pangaro, Dan Maynes-Aminzade, and Hiroshi Ishii. 2002\.  The actuated workbench: computer-controlled actuation in tabletop tangible interfaces. In _Proceedings of the 15th annual ACM symposium on User interface software and technology_. 181–190.
  * Peraza-Hernandez et al. (2014) Edwin A Peraza-Hernandez, Darren J Hartl, Richard J Malak Jr, and Dimitris C Lagoudas. 2014.  Origami-inspired active structures: a synthesis and review.  _Smart Materials and Structures_ 23, 9 (2014), 094001\.
  * Qi and Buechley (2010) Jie Qi and Leah Buechley. 2010.  Electronic popables: exploring paper-based computing through an interactive pop-up book. In _Proceedings of the fourth international conference on Tangible, embedded, and embodied interaction_. 121–128.
  * Reis et al. (2015) Pedro M Reis, Francisco López Jiménez, and Joel Marthelot. 2015\.  Transforming architectures inspired by origami.  _Proceedings of the National Academy of Sciences_ 112, 40 (2015), 12234–12235.
  * Vallgårda and Redström (2007) Anna Vallgårda and Johan Redström. 2007.  Computational composites. In _Proceedings of the SIGCHI conference on Human factors in computing systems_. 513–522.
  * Yasu (2017) Kentaro Yasu. 2017\.  Magnetic plotter: a macrotexture design method using magnetic rubber sheets. In _Proceedings of the 2017 CHI Conference on Human Factors in Computing Systems_. 4983–4993.
  * Yasu (2019) Kentaro Yasu. 2019\.  Magnetact: magnetic-sheet-based haptic interfaces for touch devices. In _Proceedings of the 2019 CHI Conference on Human Factors in Computing Systems_. 1–8.
  * Zhao et al. (2017) Yan Zhao, Yuta Sugiura, Mitsunori Tada, and Jun Mitani. 2017\.  InsTangible: A Tangible User Interface Combining Pop-up Cards with Conductive Ink Printing. In _International Conference on Entertainment Computing_. Springer, 72–80.