%\def\func#1{{\rm #1\,}}
\documentclass[12pt]{article}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%TCIDATA{OutputFilter=LATEX.DLL}
%TCIDATA{Version=4.00.0.2312}
%TCIDATA{Created=Friday, June 27, 2003 00:49:57}
%TCIDATA{LastRevised=Friday, August 01, 2003 12:50:35}
%TCIDATA{}
%TCIDATA{}
%TCIDATA{CSTFile=40 LaTeX article.cst}
\newtheorem{theorem}{Theorem}
\newtheorem{acknowledgement}[theorem]{Acknowledgement}
\newtheorem{algorithm}[theorem]{Algorithm}
\newtheorem{axiom}[theorem]{Axiom}
\newtheorem{case}[theorem]{Case}
\newtheorem{claim}[theorem]{Claim}
\newtheorem{conclusion}[theorem]{Conclusion}
\newtheorem{condition}[theorem]{Condition}
\newtheorem{conjecture}[theorem]{Conjecture}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{criterion}[theorem]{Criterion}
\newtheorem{definition}[theorem]{Definition}
\newtheorem{example}[theorem]{Example}
\newtheorem{exercise}[theorem]{Exercise}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{notation}[theorem]{Notation}
\newtheorem{problem}[theorem]{Problem}
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{remark}[theorem]{Remark}
\newtheorem{solution}[theorem]{Solution}
\newtheorem{summary}[theorem]{Summary}
\newenvironment{proof}[1][Proof]{\noindent\textbf{#1.} }{\ \rule{0.5em}{0.5em}}
\textwidth= 6.25in
\textheight= 9.0in
\topmargin = -10pt
\evensidemargin=10pt
\oddsidemargin=10pt
\headsep=25pt
\parskip=10pt
\font\smallit=cmti10
\font\smalltt=cmtt10
\font\smallrm=cmr9
%\input{tcilatex}
\def\gcd{{\rm gcd\,}}
\def\rep{{\rm rep\,}}
\def\pdim{{\rm pdim\,}}
\begin{document}
%\title{AN UPPER BOUND FOR THE REPRESENTATION NUMBER OF GRAPHS WITH FIXED
%ORDER}
%\author{\textbf{Darren A. Narayan} \\
%EndAName
%TCIMACRO{%
%\TeXButton{TeX field}{{\smallit Department of Mathematics and Statistics, Rochester Institute of Technology, Rochester, NY 14623, USA}\\ }}%
%BeginExpansion
%{\smallit Department of Mathematics and Statistics, Rochester Institute of Technology, Rochester, NY
%14623, USA}\\ %
%EndExpansion
%\texttt{dansma@rit.edu}\\
%\date{}
%\maketitle
\begin{center}
{\bf AN UPPER BOUND FOR THE REPRESENTATION NUMBER OF GRAPHS WITH FIXED
ORDER}
\vskip 20pt
{\bf Darren A. Narayan}\\
{\smallit Department of Mathematics and Statistics, Rochester Institute of Technology, Rochester, NY
14623}\\ {\tt dansma@rit.edu}\\
\end{center}
\vskip 30pt
\centerline{\smallit Received: 4/30/03, Revised: 7/17/03, Accepted: 7/31/03, Published: 8/7/03}
\vskip 30pt
\centerline{\bf Abstract}
\noindent A graph has a \emph{representation modulo} $n$ if there exists
an
injective map $f\colon \;\{V(G)\}\rightarrow \{0,1,\ldots ,n-1\}$ such
that vertices $u$ and $v$ are adjacent if and only if $\left\vert
f(u)-f(v)\right\vert $ is relatively prime to $n$. \ The \textit{%
representation number} is the smallest $n$ such that $G$ has a
representation modulo $n$. We seek the maximum value for the
representation number over graphs of a fixed order. \ Erd\H{o}s and Evans
provided an upper
bound in their proof that every finite graph can be represented modulo
some positive integer. \ In this note we improve this bound and show that
the new
bound is best possible.
\pagestyle{myheadings}
\markright{\smalltt INTEGERS: \smallrm ELECTRONIC
JOURNAL OF COMBINATORIAL NUMBER THEORY \smalltt 3 (2003), \#A12\hfill} %
\thispagestyle{empty} \baselineskip=15pt \vskip 30pt
\section*{\normalsize 1. Introduction}
Let $G$ be a finite graph with vertices $\{v_{1},\ldots ,v_{r}\}$. A \textit{%
representation of $G$ modulo $n$} is an assignment of distinct labels to the
vertices such that the label $a_{i}$ assigned to vertex $v_{i}$ is in $%
\{0,1,\ldots ,n-1\}$ and such that $\left\vert a_{i}-a_{j}\right\vert $ and $%
n$ are relatively prime if and only if $(v_{i},v_{j})\in E(G)$. Erd\H{o}s
and Evans \cite{1} showed that every finite graph can be represented modulo
some positive integer. The representation number of a graph $G$, denoted $%
\mathrm{rep\,}(G),$ is the smallest $n$ such that $G$ has a representation
modulo $n$.
Modular representations have received considerable attention in recent years
as a source of open problems (see \cite{4} and \cite{7}). Representation
numbers for various classes of graphs were determined in \cite{2} and \cite%
{3}, but little is known for many families of graphs, including bipartite
graphs and trees.
The existence proof in \cite{1} is elegant but gives an unnecessarily large
upper bound for the representation number. For a graph of order $r$, the
value $n$ is the product of $r$ primes, each greater than $3^{{r}\choose{2}}$%
. Our bound is the product of the first $r-1$ primes greater than or equal
to $r-1$.\ In fact we show that this significantly smaller bound is best
possible over all graphs of order $r$.
We also mention a connection to a result involving orthogonal latin square
graphs. An \emph{orthogonal latin square graph} is one whose vertices can be
labeled with latin squares of the same order and same symbols such that two
vertices are adjacent if and only if the corresponding latin squares are
orthogonal. Lindner, E. Mendelsohn, N. S. Mendelsohn, and Wolk \cite{5}
showed that every finite graph is an orthogonal latin square graph. A
shorter proof of this result was given by Erd\H{o}s and Evans \cite{1} after
establishing that every finite graph can be represented modulo some positive
integer. An even more simple proof of the theorem from \cite{5} can be
obtained using the upper bound found in this note.
\section*{\normalsize 2. Dimensions and representations}
\ \ \ \ \ \ A \textit{product representation }of \textit{length\ }$t$\textit{%
\ }assigns distinct vectors of length $t$ to each vertex so that vertices $u$
and $v$ are adjacent if and only if their vectors differ in every position.
\ The \textit{product dimension} of a\textit{\ }graph, denoted $\mathrm{%
pdim\,}G$, is the minimum length of such a representation of $G$.
As developed in \cite{2} and \cite{3}, there is a close correspondence
between product representation and modular representation. From a
representation of a graph $G$ modulo a product of primes $q_{1},\ldots
,q_{t} $, we obtain a product representation of length $t$ as follows. The
vector for vertex $v$ is $(v_{1},\ldots ,v_{t})$, where $v_{i}\equiv a
(\mathrm{mod}\,
q_{i})$ and $v_{i}\in \{0,\ldots ,q_{i-1}\}$ for $1\leq i\leq t$. If $u$
has vector $(u_{1},\ldots ,u_{t})$ and $v$ has vector $(v_{1},\ldots ,v_{t})$%
, then the modular representation implies that $u$ and $v$ are adjacent if
and only if $u_{i}\neq v_{i}$ for all $i$, making this assignment a product
representation.
Conversely, given a product representation, a modular representation can be
obtained by choosing distinct primes for the coordinates, provided that the
prime for each coordinate is larger than the number of values used in that
coordinate. The numbers assigned to the vertices can then be obtained using
the Chinese Remainder Theorem. The resulting modular representation
generated from the product representation is called the \textit{coordinate
representation}.
We use $p_{i}$ to denote the $i$th prime, and for any prime $p_{i}$ we use $%
p_{i+1},p_{i+2},\ldots ,p_{i+k}$ to denote the next $k$ primes larger than $%
p_{i}$. The seminal work on product dimension was done by Lov\'{a}sz, Ne\v{s}%
et\v{r}il, and Pultr \cite{6}. We first restate one of their results and
then a result from \cite{3} as Lemmas \ref{1} and \ref{2}. The graph $%
K_{r-1}+K_{1}$ is the disjoint union of $K_{r-1}$ and $K_{1}$.
\begin{lemma}
\label{1} For $r\geq3,$ the maximum product dimension of an $r-$vertex graph
is $r-1$, achieved by $K_{r-1}+K_1$.
\end{lemma}
\begin{lemma}
\label{2} Let $p_{s}$ be the smallest prime that is at least $r-1$. Then $%
\mathrm{rep\,}(K_{r-1}+K_{1})=p_{s}p_{s+1}\cdots p_{s+r-2}$.
\end{lemma}
By converting from product representations to modular representations, we
show that for all $r\geq 3,$ $K_{r-1}+K_{1}$ is the $r$-vertex graph with
largest representation number. For graphs with at most two vertices, it is
straightforward to show that $\mathrm{rep\,}(K_{1})=1$, $\mathrm{rep\,}%
(K_{2})=2$, and $\mathrm{rep\,}(2K_{1})=4$.
\begin{theorem}
\label{3}For $r\geq 3$, the maximum of $\mathrm{rep\,}(G)$ over graphs of
order $r$ is $p_{s}p_{s+1}\cdots p_{s+r-2}$, where $p_{s}$ is the smallest
prime that is at least $r-1$.
\end{theorem}
\begin{proof}
The sharpness of the upper bound follows from Lemma~\ref{2}. To prove the
upper bound, let $G$ have order $r$, and begin with a product representation
of length $r-1$ provided by Lemma~\ref{1}. By relabeling if necessary, we
may assume that the values used in coordinate $i$ are $\{0,1,\ldots
,c_{i}-1\}$ for some positive integer $c_{i}$ and that coordinates are
indexed such that $c_{1}\leq \cdots \leq c_{r-1}$.
If $G$ is not complete, then $c_{1}\leq r-1$. Thus we may associate $%
p_{s+i-1}$ with the $i$th coordinate and the corresponding coordinate
representation of $G$ is a representation modulo $p_{s}\cdots p_{s+r-2}$. If
$G$ is complete, then $\mathrm{rep\,}(G)$ is the smallest prime that is at
least $r$, which is smaller than the claimed upper bound.
\end{proof}
\
\section*{\normalsize 3. Conclusion}
\qquad We note that the construction given in the proof of Theorem \ref{3}
will not always give the representation number, since the representation
number need not be a product of distinct primes. The case mentioned earlier,
$\mathrm{rep}(2K_{1})=4$, is one of infinitely many examples. Therefore, finding the
representation number of a graph is a different problem from finding the
product dimension of a graph. \ Since the representation number of a graph
depends upon the distribution of primes and prime powers, tools from number
theory may be valuable for future studies. There are many open problems
involving modular repesentations. \ Representation numbers have been
determined for only a few graph families (see \cite{2} and \cite{3}). \
Little is known about representation numbers for some multipartite graphs,
including the most basic cases involving trees and complete bipartite
graphs.\
\noindent
\textbf{Acknowledgements}
The author is indebted to a referee for many valuable suggestions,
including an improved presentation of the proof of Theorem 3. This work was
partially supported by a RIT College of Science Dean's Summer Research
Fellowship Grant and a Reidler Foundation Grant. Thanks to Anthony Evans
and\ Garth Isaak for useful discussions. Finally the author thanks Dustin
Sheffield, now an undergraduate at Virginia Tech, for preliminary computer
simulations.
%\medskip \textbf{MSC\ Classification:} \textbf{05C78}
\begin{thebibliography}{9}
\footnotesize
\bibitem{1} P. Erd\H{o}s and A. B. Evans, Representations of graphs and
orthogonal latin square graphs, J. Graph Theory \textbf{13} (1989) 593-595.
\bibitem{2} A. B. Evans, G. H. Fricke, C. C. Maneri, T. A. McKee and M.
Perkel, Representations of graphs modulo $n,$ J. Graph Theory \textbf{18}
(1994) 801-815.
\bibitem{3} A. B. Evans, G. Isaak and D. A. Narayan, Representations of
graphs modulo $n.$ Discrete Math \textbf{223} (2000) 109-123.
\bibitem{4} J. A. Gallian, A dynamic survey of graph labeling, Electronic.
J. Combin. \textbf{5} (2002), 1-106.
\bibitem{5} C. C. Lindner, E. Mendelsohn, N. S. Mendelsohn, and B. Wolk,
Orthogonal latin square graphs, J. Graph Theory \textbf{3} (1979) 325-338.
\bibitem{6} L. Lov\'{a}sz, J. Ne\v{s}et\v{r}il, and A. Pultr. On a product
dimension of graphs, J. Combin. Theory B \textbf{29} (1980), 47-67.
\bibitem{7} D. B. West, (ed.) Research Problems, Discrete Math \textbf{257}
(2002) 599-624.
\end{thebibliography}
\end{document}