\documentclass[12pt]{article} \usepackage{amsmath,mathrsfs,bbm} \usepackage{amssymb} \textwidth=4.825in \overfullrule=0pt \thispagestyle{empty} \begin{document} \noindent % % {\bf Dustin A. Cartwright, Mar\'ia Ang\'elica Cueto and Enrique A. Tobis} % % \medskip \noindent % % {\bf The Maximum Independent Sets of de Bruijn Graphs of Diameter 3} % % \vskip 5mm \noindent % % % % The nodes of the de Bruijn graph $B(d,3)$ consist of all strings of length $3$, taken from an alphabet of size $d$, with edges between words which are distinct substrings of a word of length~$4$. We give an inductive characterization of the maximum independent sets of the de Bruijn graphs $B(d,3)$ and for the de Bruijn graph of diameter three with loops removed, for arbitrary alphabet size. We derive a recurrence relation and an exponential generating function for their number. This recurrence allows us to construct exponentially many comma-free codes of length~3 with maximal cardinality. \end{document} .