% Template article for preprint document class `elsart'
% SP 2001/01/05

% Modified 2007/01/09 for CTW 2010
% Please find the original file at http://www.elsevier.com/

\documentclass{ctwart}
%\documentclass{letter}
% Use the option doublespacing or reviewcopy to obtain double line spacing
% \documentclass[doublespacing]{elsart}

% if you use PostScript figures in your article
% use the graphics package for simple commands
% \usepackage{graphics}
% or use the graphicx package for more complicated commands
% \usepackage{graphicx}
% or use the epsfig package if you prefer to use the old commands
% \usepackage{epsfig}
\newtheorem{pro}{Proposition}
\newtheorem{problem}{Problem}
\newcommand\proof{\noindent {\bf Proof:\hspace{.05in}}}
\newtheorem{con}{Conjecture}
% The amssymb package provides various useful mathematical symbols
\usepackage{amssymb}

\begin{document}

\begin{frontmatter}

% Title, authors and addresses

% use the thanksref command within \title, \author or \address for footnotes;
% use the corauthref command within \author for corresponding author footnotes;
% use the ead command for the email address,
% and the form \ead[url] for the home page:
% \title{Title\thanksref{label1}}
% \thanks[label1]{}
% \author{Name\corauthref{cor1}\thanksref{label2}}
% \ead{email address}
% \ead[url]{home page}
% \thanks[label2]{}
% \corauth[cor1]{}
% \address{Address\thanksref{label3}}
% \thanks[label3]{}

\title{Progress on rainbow connection}

% use optional labels to link authors explicitly to addresses:
% \author[label1,label2]{}
% \address[label1]{}
% \address[label2]{}

\author{Ingo Schiermeyer}

\address{Institut f\"ur Diskrete Mathematik und Algebra, Technische
Universit\"at Bergakademie Freiberg, 09596 Freiberg, Germany,
Ingo.Schiermeyer@tu-freiberg.de}

\begin{keyword}
Rainbow colouring, rainbow connectivity, extremal problem
\end{keyword}

\end{frontmatter}

% main text

\section{Introduction}

We use \cite{BM} for terminology and notation not defined here and
consider finite and simple graphs only.

An edge-coloured graph $G$ is called {\it rainbow-connected} if any
two vertices are connected by a path whose edges have different
colours. This concept of rainbow connection in graphs was recently
introduced by Chartrand et al. in \cite{CJMZ}. The rainbow
connection number of a connected graph $G,$ denoted $rc(G),$ is the
smallest number of colours that are needed in order to make $G$
rainbow connected. An easy observation is that if $G$ has $n$
vertices then $rc(G) \leq n-1,$ since one may colour the edges of a
given spanning tree of $G$ with different colours, and colour the
remaining edges with one of the already used colours. Chartrand et
al. computed the precise rainbow connection number of several graph
classes including complete multipartite graphs \cite{CJMZ}. The
rainbow connection number has been studied for further graph classes
in \cite{CLRTY} and for graphs with fixed minimum degree in
(\cite{CLRTY}, \cite{KY}, \cite{S}).

\medskip

Rainbow connection has an interesting application for the secure
transfer of classified information between agencies (cf. \cite{E}).
While the information needs to be protected since it relates to
national security, there must also be procedures that permit access
between appropriate parties. This two-fold issue can be addressed by
assigning information transfer paths between agencies which may have
other agencies as intermediaries while requiring a large enough
number of passwords and firewalls that is prohibitive to intruders,
yet small enough to manage (that is, enough so that one or more
paths between every pair of agencies have no password repeated). An
immediate question arises: What is the minimum number of passwords
or firewalls needed that allows one or more secure paths between
every two agencies so that the passwords along each path are
distinct?

\medskip

The computational complexity of rainbow connectivity has been
studied in (\cite{CFMY}, \cite{LT}). It is proved that the
computation of $rc(G)$ is NP-hard (\cite{CFMY},\cite{LT}). In fact
it is already NP-complete to decide if $rc(G) = 2,$ and in fact it
is already NP-complete to decide whether a given edge-coloured (with
an unbounded number of colours) graph is rainbow connected
\cite{CFMY}. More generally it has been shown in \cite{LT}, that for
any fixed $k \geq 2,$ deciding if $rc(G) = k$ is NP-complete.
\medskip

For the rainbow connection numbers of graphs the following results
are known (and obvious).

%It is also known that $rc(G) = 1$ if and only if $G$ is a clique,
%that $rc(G) = n-1$ if and only if $G$ is a tree and that a cycle
%with $k \geq 3$ vertices has rainbow connection number $\lceil
%\frac{k}{2}\rceil.$ Also notice that $rc(G) \geq diam(G),$ where
%$diam(G)$ denotes the diameter of the graph $G.$

%Motivated by the fact that there are graphs with minimum degree $2$
%and with $rc(G) = n-3$ (just take two vertex-disjoint triangles and
%connect them by a path of length $n-5$), and by the fact that
%cliques have $rc(G) = 1,$ it is interesting to study the behaviour
%of $rc(G)$ with respect to the minimum degree $\delta(G).$ In
%\cite{CLRTY} Caro et al. have shown the following theorem.

\begin{pro}\label{p1} \ \\
Let $G$ be a connected graph of order $n.$ Then \\
1. $1 \leq rc(G) \leq n-1,$ \\
2. $rc(G) \geq diam(G),$ \\
3. $rc(G) = 1 \Leftrightarrow G \ \mbox{is complete},$\\
4. $rc(G) = n-1 \Leftrightarrow G \ \mbox{is a tree}.$\\
\end{pro}

\section{Rainbow connection and minimum degree}

Motivated by the fact that there are graphs with minimum degree $2$
and with $rc(G) = n-3$ (just take two vertex-disjoint triangles and
connect them by a path of length $n-5$), and by the fact that
cliques have $rc(G) = 1,$ it is interesting to study the behaviour
of $rc(G)$ with respect to the minimum degree $\delta(G).$ In
\cite{CLRTY} Caro et al. have shown the following theorem.

\begin{thm}\label{t1}
If $G$ is a connected graph with $n$ vertices and $\delta(G) \geq 3$
then $rc(G) < \frac{5n}{6}.$
\end{thm}

\noindent They also made the following conjecture.

\begin{con}\label{con}
If $G$ is a connected graph with $n$ vertices and $\delta(G) \geq 3$
then $rc(G) < \frac{3n}{4}.$
\end{con}

\noindent For 2-connected graphs Conjecture \ref{con} is true. This
follows from the following proposition in \cite{CLRTY}.

\begin{pro}\label{p1}
If $G$ is a 2-connected graph with $n$ vertices then $rc(G) \leq
\frac{2n}{3}.$
\end{pro}

\begin{cor}\label{c1}
If $G$ is a 2-connected graph with $n$ vertices then $rc(G) \leq
\frac{3n-1}{4}$ for $n \geq 3.$
\end{cor}

\noindent Conjecture \ref{con} has recently been proven in \cite{S}
by the following theorem.

\begin{thm}\label{t2}
If $G$ is a connected graph with $n$ vertices and $\delta(G) \geq 3$
then $rc(G) \leq \frac{3n-1}{4}.$
\end{thm}

The presented results motivate the following challenging problem.
\begin{problem}
For every $k \geq 2$ find a minimal constant $c_k$ with $0 < c_k
\leq 1$ such that $rc(G) \leq c_k \cdot n$ for all graphs $G$ with
minimum degree $\delta(G) \geq k.$ Is it true that $c_k =
\frac{3}{k+1}$ for all $k \geq 2$?
\end{problem}
This is true for $k = 2,3$ as shown before ($c_2 = 1$ and $c_3 =
\frac{3}{4}).$

\section{Rainbow connection and size of graphs}

Another approach for achieving upper bounds is based on the size
(number of edges) of the graph. Those type of sufficient conditions
are known as Erd\H{o}s-Gallai type results. Research on the
following Erd\H{o}s-Gallai type problem has been started in
\cite{KS}.

\begin{problem}
For every $k, 1 \leq k \leq n-1,$ compute and minimize the function
$f(n,k)$ with the following property: If $|E(G)| \geq f(n,k),$ then
$rc(G) \leq k.$
\end{problem}

First we can show a lower bound for $f(n,k).$

\begin{pro}\label{p2} \ \\
$f(n,k) \geq {n-k+1 \choose 2} + (k-1).$
\end{pro}

\proof We construct a graph $G_k$ as follows: Take a $K_{n-k+1}-e$
and denote the two vertices of degree $n-k-1$ with $u_1$ and $u_2.$
Now take a path $P_k$ with vertices labeled $w_1, w_2, \ldots, w_k$
and identify the vertices $u_2$ and $w_1.$ The resulting graph $G_k$
has order $n$ and size $|E(G)| = {n-k+1 \choose 2} + (k-2).$ For its
diameter we obtain $d(u_1, w_k) = diam(G) = k+1.$ Hence $f(n,k) \geq
{n-k+1 \choose 2} + (k-1).$ \qed

\medskip

\noindent Using Propositions \ref{p1} and \ref{p2} we can compute
$f(n,k)$ for $k \in \{1, n-2, n-1\}.$

\begin{pro} \ \\
$f(n,1) = {n \choose 2},$\\
$f(n,n-1) = n-1,$\\
$f(n,n-2) = n.$
\end{pro}

For $k = 2$ we obtain $f(n,2) = {n-1 \choose 2} + 1$ by the
following stronger result shown in \cite{KS}.

\begin{thm} \label{t1}
Let $G$ be a connected graph of order $n$ and size $m.$ If ${n-1
\choose 2} + 1 \leq m \leq {n \choose 2} - 1,$ then $rc(G) = 2.$
\end{thm}



%\label{}

%\section{}
%

\label{}

% The Appendices part is started with the command \appendix;
% appendix sections are then done as normal sections
% \appendix

% \section{}
% \label{}

\begin{thebibliography}{00}

\bibitem{BM} J. A. Bondy and U.S.R. Murty, {\it Graph Theory},
Springer, 2008.

\bibitem{CFMY} S. Chakraborty, E. Fischer, A. Matsliah, and R.
Yuster, {\it Hardness and algorithms for rainbow connectivity},
Proceedings STACS 2009, to appear in Journal of Combinatorial
Optimization.

\bibitem{CLRTY} Y. Caro, A. Lev, Y. Roditty, Z. Tuza, and R. Yuster
{\it On rainbow connection}, The Electronic Journal of Combinatorics
15 (2008), $\#57.$

\bibitem{CJMZ} G. Chartrand, G. L. Johns, K. A. McKeon, and P.
Zhang, {\it Rainbow connection in graphs}, Math. Bohemica 133 (2008)
85-98.

\bibitem{E} A. B. Ericksen, {\it A matter of security}, Graduating
Engineer \& Computer Careers (2007) 24-28.

\bibitem{KS} A. Kemnitz and I. Schiermeyer, {\it Graphs with rainbow connection number
two}, preprint 2009, submitted to Discussiones Mathematicae Graph
Theory.

\bibitem{KY} M. Krivelevich and R. Yuster, {\it The rainbow connection of a graph is (at most)
reciprocal to its minimum degree}, Preprint 2009.

\bibitem{LT} V. B. Le and Z. Tuza, {\it Finding optimal rainbow
connection is hard}, Preprint 2009.

\bibitem{S} I. Schiermeyer, {\it Rainbow connection in graphs with
minimum degree three}, IWOCA 2009, LNCS 5874 (2009) 432-437.

% \bibitem{label}
% Text of bibliographic item

% notes:
% \bibitem{label} \note

% subbibitems:
% \begin{subbibitems}{label}
% \bibitem{label1}
% \bibitem{label2}
% If there is a note, it should come last:
% \bibitem{label3} \note
% \end{subbibitems}

%\bibitem{}

\end{thebibliography}

\end{document}

