\documentclass[12pt]{article} \usepackage{e-jc} \specs{P18}{20(3)}{2013} %\usepackage{amsmath}%amssymb,psfig,latexsym,graphicx}%,graphs} \usepackage{latexsym} \usepackage{amsfonts} \usepackage{amsthm,amsmath,amssymb} % we recommend the graphicx package for importing figures \usepackage{graphicx} % use this command to create hyperlinks (optional and recommended) \usepackage[colorlinks=true,citecolor=black,linkcolor=black,urlcolor=blue]{hyperref} % use these commands for typesetting doi and arXiv references in the bibliography \newcommand{\doi}[1]{\href{http://dx.doi.org/#1}{\texttt{doi:#1}}} \newcommand{\arxiv}[1]{\href{http://arxiv.org/abs/#1}{\texttt{arXiv:#1}}} \theoremstyle{plain} \newtheorem{theorem}{Theorem} \newtheorem{lemma}[theorem]{Lemma} \newtheorem{corollary}[theorem]{Corollary} \newtheorem{proposition}[theorem]{Proposition} \newtheorem{fact}[theorem]{Fact} \newtheorem{observation}[theorem]{Observation} \newtheorem{claim}[theorem]{Claim} \newtheorem{result}[theorem]{Result} \theoremstyle{definition} \newtheorem{definition}[theorem]{Definition} \newtheorem{example}[theorem]{Example} \newtheorem{conjecture}[theorem]{Conjecture} \newtheorem{open}[theorem]{Open Problem} \newtheorem{problem}[theorem]{Problem} \newtheorem{question}[theorem]{Question} \theoremstyle{remark} \newtheorem{remark}[theorem]{Remark} \newtheorem{note}[theorem]{Note} \newtheorem{examples}{Examples} \newtheorem{exercise}{Exercise} \newcommand{\aut}{\mbox{\rm Aut}} \newcommand{\paut}{\mbox{\rm PAut}} \newcommand{\rank}{\mbox{\rm rank}} \newcommand{\hull}{\mbox{\rm Hull}} \newcommand{\wt}{\mbox{\rm wt}} \newcommand{\supp}{\mbox{\rm Supp}} \newcommand{\hd}{\mbox{\rm d}} \newcounter{unnumber} \renewcommand{\theunnumber}{} %\newtheorem{question}[unnumber]{Question} %\newcommand{\done}{\mbox{${\blacksquare}$ }} %\newcommand{\pf}{\noindent{\bf Proof:}} \newcommand{\eg}{\noindent{\bf Example:}} \newcommand{\egs}{\noindent{\bf Examples:}} \newcommand{\rk}{\noindent{\bf Remark:}} \newcommand{\rks}{\noindent{\bf Remarks:}} %\newcommand{\bmi}[1]{\mbox{\boldmath $ #1$}} %\newcommand{\bbar}[1]{\mbox{${\bar{\bar{#1}}}$}} %\newcommand{\bbar}[1]{\mbox{${\overline{\overline{#1}}}$}} %how to use \bmi: to get bold math ital R, type \bmi{R} %NEWCOMMANDS \newcommand{\jmod}[2]{\mbox{ $\equiv #1$}\mbox{ \rm (mod $#2$)}} %HOW TO USE: for ``5 equiv 2 (mod 7)'' type $5 \jmod{2}{7}$ %\newcommand{\done}{\begin{flushright}{\mbox{\large {\boldmath $\Box$}}}\end{flushright}} \newcommand{\njmod}[2]{\mbox{ $\not \equiv #1$}\mbox{ \rm (mod $#2$)}} %for 5 NOT equiv 0 mod p use \njmod \newcommand{\nonres}{\mbox{$\not \! \! \raisebox{-.2ex}{\mbox{$\Box$}}$}} \newcommand{\res}{\raisebox{-.2ex}{\mbox{$\Box$}}} \newcommand{\jvec}{\mbox{\boldmath $\jmath$}} %\newcommand{\bpf}{\noindent {\bf Proof:} $\mbox{}$} % comand to end proof ( open box) \newcommand{\epf}{\hfill \hbox{\raisebox{.5ex}{\fbox}$\phantom{.}$}} %CAL-commands \newcommand{\CAL}[1]{\mbox{$\mathcal{#1}$}} \newcommand{\R}{\mbox{$\mathbb{R}$}} \newcommand{\Z}{\mbox{$\mathbb{Z}$}} \newcommand{\N}{\mbox{$\mathbb{N}$}} \newcommand{\Q}{\mbox{$\mathbb{Q}$}} \newcommand{\C}{\mbox{$\mathbb{C}$}} \newcommand{\F}{\mbox{$\mathbb{F}$}} %HYPHENATION \hyphenation{col-linea-tion} \hyphenation{Wed-der-burn} %\newcommand{\dsum}{\displaystyle\sum} %\newcommand{\Colon}{\:\mathbin{:}\:} \title{\bf A characterization of graphs by codes\\ from their incidence matrices} \author{Peter~Dankelmann\\ \small Department of Mathematics\\[-0.8ex] \small University of Johannesburg\\[-0.8ex] \small P.O. Box 524\\[-0.8ex] \small Auckland Park 2006, South Africa\\ \small\tt pdankelmann@uj.ac.za\\ \and Jennifer~D.~Key \quad Bernardo~G. Rodrigues\\ \small School of Mathematical Sciences\\[-0.8ex] \small University of KwaZulu-Natal\\[-0.8ex] \small Durban 4041, South Africa\\ \small\tt keyj@clemson.edu\\ [-0.8ex] \small\tt rodrigues@ukzn.ac.za } % \date{\dateline{submission date}{acceptance date}\\ % \small Mathematics Subject Classifications: comma separated list of % MSC codes available from http://www.ams.org/mathscinet/freeTools.html} \date{\dateline{Oct 3, 2012}{Aug 4, 2013}{Aug 16, 2013}\\ \small Mathematics Subject Classifications: 05B05, 94B05} \begin{document} \maketitle \begin{abstract} We continue our earlier investigation of properties of linear codes generated by the rows of incidence matrices of $k$-regular connected graphs on $n$ vertices. The notion of edge connectivity is used to show that, for a wide range of such graphs, the $p$-ary code, for all primes $p$, from an $n \times \frac{1}{2}nk$ incidence matrix has dimension $n$ or $n-1$, minimum weight $k$, the minimum words are the scalar multiples of the rows, there is a gap in the weight enumerator between $k$ and $2k-2$, and the words of weight $2k-2$ are the scalar multiples of the differences of intersecting rows of the matrix. For such graphs, the graph can thus be retrieved from the code. \bigskip\noindent \textbf{Keywords:} codes; graphs; edge-connectivity \end{abstract} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \section{Introduction}\label{sec_intro} Linear codes generated by $|V| \times |E|$ incidence matrices for several classes of regular graphs $\Gamma=(V,E)$ were examined in, for example,~\cite{fikemw5,fikemw6,kemoro8,kero1,ghikey}, and shown to have certain important common properties. In order to establish this common property more generally, in~\cite{dakero1} it was shown that several properties of these codes for regular connected graphs can be derived from properties of the graph involving edge cuts, i.e.\ the removal of a set $S$ of edges of the graph $\Gamma$ and the ensuing properties of the graph $\Gamma-S$ that excludes these edges. For a prime $p$, denote by $C_p(G)$ the $p$-ary code generated by the rows of a $|V|\times |E|$ incidence matrix $G$ of a regular connected graph $\Gamma$. It was shown in \cite{dakero1} that if $\Gamma$ satisfies any of an extensive list of conditions, the minimum distance of $C_2(G)$ equals the edge-connectivity $\lambda(\Gamma)$ of $\Gamma$, i.e., the smallest number of edges whose removal renders $\Gamma$ disconnected, and there are no words whose weight is strictly between $\lambda(\Gamma)$ and $\lambda'(\Gamma)$, where the restricted edge-connectivity $\lambda'(\Gamma)$ is defined as the smallest number of edges whose removal results in a graph that is disconnected, and in which every component has at least two vertices. The analogous results for $p$-ary codes, for $p$ an odd prime, in that paper included a much smaller class of graphs, even though it had been shown, by different methods (in~\cite{fikemw5,fikemw6,kemoro8,kero1,ghikey}, for example) that the same results hold for all primes for all the classes studied. Thus we continue our study here to broaden our results for the $p$-ary case where $p$ is odd. The dimension of $C_p(G)$ is well-known to be $|V|$ or $|V|-1$: see Result~\ref{prop_dim}. In addition it has also been observed for several classes of connected $k$-regular graphs that the words of weight $2k-2$ in $C_p(G)$, for any prime $p$, are the scalar multiples of the difference of two intersecting rows of the incidence matrix $G$. Using edge cuts we are able to prove this generally for a wide class of graphs. These properties of the codes (the minimum weight, the nature of the minimum words, the gap in the weight enumerator, the nature of the words of the second smallest weight) from an incidence matrix of a graph are reminiscent of the properties of the codes from incidence matrices of desarguesian projective planes, except that in that case only a prime dividing the order of the plane will produce such properties: see, for example,~\cite[Chapter~5]{ak:book}. We note also that although the minimum weight and the nature of the minimum words for the $p$-ary codes from arbitrary finite projective planes of order divisible by $p$ have this property, the existence of the gap and the nature of the words of weight the same as that from the difference of two rows of an incidence matrix, is not necessarily achieved for non-desarguesian planes: see~\cite{ghireskey} for some counter-examples. Our main results for the codes are then Theorem~\ref{thm_binwords} (in Section~\ref{sec_binary}) for the binary codes, Theorem~\ref{thm_bippwords} (in Section~\ref{sec_parywords}) for the bipartite $p$-ary case, $p$ odd, and Corollaries~\ref{coro:summary},~\ref{cor_more} (in Section~\ref{sec_parywords}) for the non-bipartite $p$-ary case, $p$ odd. These results are established in the sections that follow. Background definitions and previous results are given in Section~\ref{sec_ban}. In Section~\ref{sec_end} we give a short summary of what we have broadly achieved. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \section{Background and notation}\label{sec_ban} \subsection{Codes from designs}\label{subsec_codes} For notation on designs and codes we refer to~\cite{ak:book}. An incidence structure $\CAL{D} =( \CAL{P},\CAL{B},\CAL{J})$, with point set \CAL{P}, block set \CAL{B}\ and incidence \CAL{J}\ is a $t$-$(v,k,\lambda)$ design, if $|\CAL{P}|=v$, every block $B \in \CAL{B}$ is incident with precisely $k$ points, and every $t$ distinct points are together incident with precisely $\lambda$ blocks. The {\em code { $C_F(\CAL{D})$} of the design} \CAL{D}\ over the finite field $F$ is the space spanned by the incidence vectors of the blocks over $F$. %If \CAL{Q}\ is any subset of \CAL{P}, then we will denote the {\em incidence %vector} of \CAL{Q}\ by { $v^{\mathcal Q}$}, and % if $\CAL{Q}=\{P\}$ where $P \in %\CAL{P}$, then we will write $v^P$ instead of %$v^{\{P\}}$. % Thus $C_F(\CAL{D}) = \left< v^B \,| \, B \in \CAL{B} \right>$, %and is a subspace of $F^{\mathcal P}$, the full vector space of functions from %\CAL{P}\ to $F$. For any $w \in F^{\mathcal P}$ and $P \in \CAL{P}$, %$w(P)$ or $w_P$ will denote the value of $w$ at $P$. If $F=\F_p$ then we write $C_p(\CAL{D})$ for $C_F(\CAL{D})$. All the codes here are {\em linear codes}, and the notation $[n,k,d]_q$ will be used for a code $C$ over $\F_q$ of length $n$, dimension $k$, and minimum weight $d$, where the {\em weight $\wt(v)$} of a vector $v$ is the number of non-zero coordinate entries. The {\em support}, $\supp(v)$, of a vector $v$ is the set of coordinate positions where the entry in $v$ is non-zero. So $|\supp(v)|=\wt(v)$. The vector all of whose entries are $1$ is the {\em all-one vector}, denoted by $\jvec$. A {\em generator matrix} for a code $C$ is a $k\times n$ matrix made up of a basis for $C$. We call two codes {\em isomorphic} if they can be obtained from one another by permuting the coordinate positions. %%%%%%%%%%%%%%%%%%%%%%%%%% \subsection{Graphs and codes}\label{subsec_graphs} The {\em graphs}, $\Gamma=(V,E)$ with vertex set $V$, or $V(\Gamma)$, and edge set $E$, or $E(\Gamma)$, discussed here are undirected with no loops and no multiple edges. The {\em order} of $\Gamma$ is $|V|$. If $x,y \in V$ and $x$ and $y$ are adjacent, we write $x \sim y$, and $xy$ for the edge in $E$ that they define. The {\em set of neighbours} of $u\in V$ is denoted by $N(u)$, and the {\em valency} or {\em degree} of $u$ is $|N(u)|$, which we denote by ${\rm deg}_{\Gamma}(u)$. The {\em minimum} and {\em maximum} degrees of the vertices of $\Gamma$ are denoted by $\delta(\Gamma)$ and $\Delta(\Gamma)$, respectively. The graph is {\em $k$-regular}, where $k\in \mathbb{N}_0$, if all its vertices have degree $k$, and $\Gamma$ is said to be {\em regular} if it is $k$-regular for some $k$. If $S\subseteq E$ then $\Gamma-S =(V,E-S)$, and $\Gamma[S]$ is the {\em subgraph induced by $S$}, i.e.\ the subgraph of $\Gamma$ whose vertex set consists of the vertices of $\Gamma$ that are incident with an edge in $S$, and whose edge set is $S$. If for some $r \ge 2$, $x_ix_{i+1}$ for $i=1$ to $r-1$, are all edges of $\Gamma$, and the $x_i$ are all distinct, then the sequence written $(x_1,\ldots,x_r)$ will be called a {\em path} in $\Gamma$. If also $x_rx_1$ is an edge, then this is a {\em closed path}, {\em circuit} or {\em cycle}, of length $r$, also written $C_r$. If for every pair of vertices there is a path connecting them, the graph is {\em connected}. A {\em {perfect matching}} is a set $S$ of disjoint edges such that every vertex is on exactly one member of $S$. The {\em girth} $g(\Gamma)$ of $\Gamma$ is the length of a shortest cycle in $\Gamma$. %If $\Gamma$ has a cycle of %even length, then the {\em even girth} $g_e(\Gamma)$ is the length of a %shortest even cycle. The {\em distance} $d(u,v)$ between two vertices $u$ and $v$ of a graph $\Gamma$ is the minimum length of a path from $u$ to $v$. The {\em diameter} of $\Gamma$, denoted by ${\rm diam}(\Gamma)$ is the largest of all distances between vertices of $\Gamma$, i.e., ${\rm diam}(\Gamma) = \max_{u,v \in V(\Gamma)} d(u,v)$. A subgraph $\Gamma'$ of a graph $\Gamma$ is {\em isometric} if for any two vertices of $\Gamma'$ their distance apart in $\Gamma'$ is the same as that in $\Gamma$. A {\em{strongly regular graph}} $\Gamma $ of type $(n,k,\lambda ,\mu )$ is a regular graph on $n=|V|$ vertices, with valency $k$ which is such that any two adjacent vertices are together adjacent to $\lambda $ vertices and any two non-adjacent vertices are together adjacent to $\mu $ vertices. If $\Gamma$ is strongly regular of type $(n,k,\lambda,\mu)$ then the complement $\Gamma^c$ is strongly regular of type $(n,n -k-1,n-2k+\mu-2,n-2k+\lambda)$. The parameters for $\Gamma$ are linked by the equation \begin{equation}\label{eqn_params} (n - k - 1)\mu = k(k - \lambda - 1). \end{equation} %See~\cite[Chapter~2]{camvl2}, for example, for proof of these properties. To avoid trivial cases, we require that a strongly regular graph and its complement are both connected, and so $0< \mu k$. Let $W_i$ be the number of codewords of weight $i$ in $C_2(G)$. Then $W_i=0$ for $k+1 \le i \le \lambda'(\Gamma)-1$, and $W_{\lambda'(\Gamma)} \neq 0$ if $\lambda'(\Gamma)>k+1$. \end{result} %%%%%%%%%%%%%%%%% We had similar results for bipartite connected graphs for $p$ odd: %%%%%%%%%%%%%%%%%%%% \begin{result}~\label{theo:bipartite} {\rm \cite[Theorem~2]{dakero1}} Let $\Gamma=(V,E)$ be a connected bipartite graph, $G$ a $|V|\times|E|$ incidence matrix for $\Gamma$, and $p$ an odd prime. Then \begin{enumerate} \item $C_p(G)$ is a $[|E|,|V|-1,\lambda(\Gamma)]_p$ code; \item if $\Gamma$ is super-$\lambda$, then $C_p(G)=[|E|,|V|-1,\delta(\Gamma)]_p$, and the minimum words are the non-zero scalar multiples of the rows of $G$ of weight $\delta(\Gamma)$. \end{enumerate} \end{result} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \begin{result}\label{res_gapp} {\rm \cite[Theorem~5]{dakero1}} Let $\Gamma=(V,E)$ be a connected bipartite $k$-regular graph with $|V| \ge 4$, $G$ an incidence matrix for $\Gamma$, $\lambda(\Gamma)=k$ and $\lambda'(\Gamma)>k$. Let $W_i$ be the number of codewords of weight $i$ in $C_p(G)$ where $p$ is odd. Then $W_i=0$ for $k+1 \le i \le \lambda'(\Gamma)-1$, and $W_{\lambda'(\Gamma)} \neq 0$ if $\lambda'(\Gamma)>k+1$. \end{result} For non-bipartite graphs for the $p$-ary case to match Result~\ref{theo:lambda} we had: %%%%%%%%%%%%%%% \begin{result}\label{res_theorem-3} {\rm \cite[Theorem~3]{dakero1}} Let $\Gamma=(V,E)$ be a connected graph that is not bipartite, $p$ be an odd prime, and $G$ be an incidence matrix for $\Gamma$. Then \begin{enumerate} \item[1.] $C_p(G)$ is a $ [ |E|, |V|, \lambda_{bip}(\Gamma)]_p$ code; \item[2.] if $\Gamma$ is super-$\lambda_{bip}$ then $C_p(G) = [ |E|, |V|, \delta(\Gamma) ]_p$, and the minimum words are the non-zero scalar multiples of the rows of $G$ of weight $\delta(\Gamma)$. \end{enumerate} \end{result} %%%%%%%%%%%%%%%%%% For the previous result we used the following result, which we will use again in this paper in order to extend Result~\ref{cor_lambdabip} below: %%%%%%%%%%%%%%%%%%%%%%%%% \begin{result}\label{prop:lambda-bip} {\rm \cite[Proposition~1]{dakero1}} Let $\Gamma=(V,E)$ be a connected graph that is not bipartite. Then \[ \lambda_{bip}(\Gamma) \geq \min\{ \lambda(\Gamma), b(\Gamma) \}. \] \begin{enumerate} \item If $\Gamma$ is $k$-regular, $b(\Gamma) \geq k$ and $\lambda(\Gamma) =k$, then $\lambda_{bip}(\Gamma)=k$. \item If $\Gamma$ is $k$-regular and super-$\lambda$, and if $b(\Gamma)>k$ then $\Gamma$ is super-$\lambda_{bip}$. \end{enumerate} \end{result} %%%%%%%%%%%%%%%%%%%%%%%% Using the two previous results, for the non-bipartite $p$-ary case we had: %%%%%%%%%%%%%%% \begin{result}\label{cor_lambdabip} {\rm\cite[Corollary~3]{dakero1}} Let $\Gamma=(V,E)$ be a connected $k$-regular graph that is not bipartite on $|V|=n$ vertices, $G$ an $n \times \frac{nk}{2}$ incidence matrix for $\Gamma$, and $p$ an odd prime. If \begin{enumerate} \item $k\geq (n+3)/2$ and $n \ge 6$, or \item $\Gamma$ is strongly regular with parameters $(n,k,\lambda,\mu)$, where \\ $(a)$ $n\geq 7$, $\mu \geq 1$, $1 \leq \lambda \leq k-3$, or $(b)$ $n \geq 11$, $\mu \ge 1$, $\lambda=0$, \end{enumerate} then the code $C_p(G)$ has minimum weight $k$, and the minimum words are the non-zero scalar multiples of the rows of $G$. \end{result} In~\cite{dakero1} we did not consider the nature of the words of weight $2k-2$, thus all cases for that consideration are new to this paper. The following conditions for a connected $k$-regular graph $\Gamma$ to be super-$\lambda'$ can be found in the literature. Firstly we state the results for non-bipartite graphs, but note that in many cases the original paper contains more general statements. %%%%%%%%%%%%%%%%% \begin{result}\label{res_list} Let $\Gamma=(V,E)$ be a $k$-regular connected graph on $|V|=n$ vertices which is not bipartite. \\ $(a)$ $\Gamma$ is super-$\lambda$ if one of the following holds: \begin{enumerate} \item[$1$.] $\Gamma$ is vertex-transitive and has no complete subgraph of order $k$ (Tindell \cite{Tin}); \item[$2$.] $\Gamma$ is edge-transitive and not a cycle (Tindell \cite{Tin}); \item[$3$.] $\Gamma$ has diameter at most $2$, and in addition $\Gamma$ has no complete subgraph of order $k$ (Fiol \cite{Fio}); \item[$4a$.] $\Gamma$ is strongly regular with parameters $(n,k,\lambda,\mu)$ with $\lambda\leq k-3$, $\mu\geq 1$ (from $3$ above); \item[$4b$.] $\Gamma$ is distance regular and $k>2$ (Brouwer and Haemers \cite{BH}); \item[$5$.] $\Gamma$ is $k$-regular and $k\geq \frac{n+1}{2}$ (Kelmans \cite{Kel}); % (Wang and Li \cite{WL}); \item[$6$.] $\Gamma$ has girth $g$, ${\rm diam}(\Gamma) \leq g-1$ if $g$ is odd and ${\rm diam}(\Gamma) \leq g-2$ if $g$ is even. (F\`abrega and Fiol \cite{FF}). \end{enumerate} $(b)$ $\Gamma$ is super-$\lambda'$ if one of the following holds: \begin{enumerate} \item[$1a'$.] $\Gamma$ is vertex-transitive, has girth at least $5$, and is not a cycle (Wang, \cite{Wan}); \item[$1b'$.] $\Gamma$ is vertex-transitive and \begin{enumerate} \item[$(i)$] not contained in $\{K_n,C_n, C_m[K_2], C_m \times K_2,C_{2m}^2, M_m\}$ where $m=\frac{n}{2}$; \item[$(ii)$] not a $4$-regular vertex-transitive graph in which every vertex is contained in exactly two triangles; \item[$(iii)$] does not contain a $(k-1)$-regular subgraph with $\ell$ vertices where $k \le \ell \le 2k-3$; \item[$(iv)$] does not contain a $(k-1)$-regular subgraph with $2k-2$ vertices and $n\ge 2k+1$; \item[$(v)$] does not contain a $(k-1)$-clique and is not isomorphic to a $(k + 1)$-clique. \end{enumerate} (Yang et al.\ \cite{YZQG}); \item[$2'$.] $\Gamma$ is edge-transitive, $\Gamma\notin \{K_6-M, C_n\}$ and $\Gamma$ is not the line graph of a triangle-free $3$-regular edge-transitive graph (Tian and Meng~\cite{TM}); \item[$3a'$.] any two non-adjacent vertices of $\Gamma$ have at least three neighbours in common, and $|V|\geq 13$ (Wang et al.\ \cite{WLWL}); \item[$3b'$.] any two non-adjacent vertices of $\Gamma$ have at least two neighbours in common, any two adjacent vertices have at most one neighbour in common, and $|V|\geq 10$ (Wang et al.\ \cite{WLWL}); \item[$4'$.] $\Gamma$ is strongly regular with parameters $(n,k,\lambda,\mu)$ with either $\mu\geq 3$ and $n\geq 13$, or with $\lambda \leq 1$, $\mu\geq 2$ and $n\geq 10$ (from $3a',b'$ above); \item[$5'$.] $\Gamma$ is $k$-regular and $k\geq \frac{1}{2}n+1$ (Ou and Zhang \cite{JZ}); \item[$6'$.] $\Gamma$ has girth $g$, and ${\rm diam}(\Gamma) \leq g-3$ (Balbuena, Lin, Miller \cite{BLM}). \end{enumerate} \end{result} The similar results for bipartite graphs: %The following conditions for a $k$-regular bipartite graph $\Gamma$ to be %maximally restricted edge-connected or super-$\lambda'$ %can be found in the literature. We state the results for regular, bipartite graphs, %but in many cases the original paper contains more general statements. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \begin{result}\label{res_biplist} Let $\Gamma=(V,E)$ be a $k$-regular connected bipartite graph on $n$ vertices. \\ $(a)$ $\Gamma$ is super-$\lambda$ if one of the following holds: \begin{enumerate} \item[$1$.] $\Gamma$ is half-vertex-transitive, i.e., its automorphism group acts transitively on each partite set (Tian, Meng and Liang, \cite{TML}); \item[$2.$] $\Gamma$ is edge-transitive and not a cycle (Tindell \cite{Tin}); \item[$3.$] $\Gamma$ has diameter $3$ (or equivalently, any two vertices in the same partite set have a neighbour in common) and $k<\frac{n}{4}$ (Balbuena, Carmona, F\`abrega and Fiol \cite{BCFF}); \item[$4.$] $\Gamma$ is $k$-regular and $k\geq \lfloor \frac{n+2}{4}\rfloor +1$ (Fiol \cite{Fio}). \end{enumerate} $(b)$ $\Gamma$ is super-$\lambda'$ if one of the following holds: \begin{enumerate} \item[$1'$.] $\Gamma$ is half-vertex-transitive, $\Gamma \notin \{C_n, C_{n/2} \times K_2, M_{n/2}\}$, and $\Gamma$ contains no $K_{k-1,k-1}$ (Tian, Meng, and Liang \cite{TML}); \item[$2'$.] $\Gamma$ is edge-transitive, $\Gamma\neq Q_3$ (hypercube with $n=8, k=3$), and $\Gamma$ is not of girth $3$ with $k=4$ and $n\geq 6$ (J.-X.\ Zhou \cite{Zho}); \item[$3'$.] $\Gamma$ has a perfect matching and any two vertices in the same partite set have at least three common neighbours (Yuan et al.\ \cite{YLW}); \item[$4'$.] $4(k-1)^2 \geq k(n-4)-2$ if $n$ is odd, $4(k-1)^2 \geq k(n-4)-1$ if $n$ is even, and $n\geq 22$ (Meierling and Volkmann \cite{MV}); \item[$5'$.] $\Gamma$ has girth $g$, and ${\rm diam}(\Gamma) \leq g-3$ (Balbuena, Lin, Miller \cite{BLM}). \end{enumerate} \end{result} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \section{\boldmath Words of weight $2k-2$ in the binary codes}\label{sec_binary} Results~\ref{theo:lambda} and~\ref{res_restricted-lambda} tell us about the minimum weight, the nature of the minimum words and the gap in the weight enumerator, in the binary codes $C_2(G)$. We now establish the nature of the words of the next weight, i.e.\ $2k-2$, for the $k$-regular connected graphs that are super-$\lambda'$. We take $k\ge 3$ to avoid trivial cases. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \begin{theorem}\label{thm_binwords} Let $\Gamma=(V,E)$ be a $k$-regular, connected, super-$\lambda'$ graph. Let $G$ be an incidence matrix for $\Gamma$. Let $W_i$ be the number of codewords of $C_2(G)$ of weight $i$. Then $W_i=0$ for $i\in \{1,2,\ldots,k-1\} \cup \{k+1, k+2,\ldots, 2k-3\}$. Moreover, \begin{itemize} \item[$(i)$] $W_k=|V|$ and the words of weight $k$ are the rows of $G$; \item[$(ii)$] $W_{2k-2}=|E|$ and every word of weight $2k-2$ is a difference of two rows of $G$ corresponding to two adjacent vertices. \end{itemize} \end{theorem} \begin{proof} The nature of the minimum words and the gap in the weight enumerator follow from Results~\ref{theo:lambda} and~\ref{res_restricted-lambda}, since $\Gamma$ is also super-$\lambda$, as noted in Section~\ref{subsec_ECCG}. Now let $w$ be a word of weight $2k-2$, and $S=\supp(w)$. Then, as shown in~\cite[Theorem~1]{dakero1}, $\Gamma-S$ is disconnected, so $S$ is an edge-cut. Suppose the components are $W$ and $V-W$. All the edges in $S$ are between $W$ and $V-W$, and since $|S|=2k-2$, $W$, and $V-W$ must have at least two vertices, and thus $S$ is a restricted edge-cut. Since its size is $\lambda'(\Gamma)$ and $\Gamma$ is super-$\lambda'$, $S$ must consist of all the edges through a pair of adjacent vertices, $x$ and $y$, excluding the edge $xy$. Thus $w=G_x-G_y$. \end{proof}%~\done \medskip Now the list of regular connected super-$\lambda'$ graphs in Result~\ref{res_list} can be consulted to see which graphs this result applies to. %, or~\cite[Result~4]{dakero1}, which includes bipartite graphs, can be used. \begin{example}\label{eg_USG}%{\rm In~\cite{fikemw10} uniform subset graphs were looked at and some properties deduced that we can use here. For $n>k>r\ge 0$, define $\Gamma=G(n,k,r)$ to be the graph with vertex set $\Omega^{\{k\}}$, the set of $k$-subsets of a set $\Omega$ of size $n$, and adjacency defined by the rule that $a,b \in \Omega^{\{k\}}$ are adjacent if $|a \cap b| =r$. The valency is $\nu=\binom{k}{r}\binom{n-k}{k-r}$. The graphs are edge-transitive (see, for example,~\cite{fikemw10}) and hence by a result quoted in~\cite[Result~4(2)]{dakero1}, for them $\lambda'(\Gamma)=2\nu -2$. If they are super-$\lambda'$ then they will satisfy Theorem~\ref{thm_binwords}. By Result~\ref{res_list}($2'$), this will be so if $\nu \ne 2,4$. The graphs with $\nu=2,4$ are: $L(K_3)=T(3)=G(3,2,1)$, $L(K_4)=T(4)=G(4,2,1)=K_6-M$, i.e.\ triangular graphs, and the odd graph $\CAL{O}_3=G(7,3,0)$\footnote{Frequently denoted $O_4$ in the literature.}. Of these, $T(3)$ has valency 2, so we exclude it; $T(4)$ has more words of weight 6 in $C_2(G)$; $\CAL{O}_3$ does satisfy the conclusions of the theorem, as does $\CAL{O}_2$, the Petersen graph. Computations are with Magma~\cite{magma1,magmaHB}. %T(m)=G(m,2,1)$ %} \end{example} \begin{example}\label{eg_SRG}%{\rm For strongly regular graphs, Result~\ref{res_list}~$(4')$ can be applied. For the Paley graphs $P(q)$ Theorem~\ref{thm_binwords} will apply for $q >9$. For $q=9$, $P(9)$ has parameters $(9,4,1,2)$ and thus is not covered by that result, although it is covered by Result~\ref{theo:lambda} for the minimum words and the gap in the weight enumerator. In fact there are six words of weight $2k-2=6$ in $C_2(G)$ (where $G$ is an incidence matrix for $P(9)$) that are not from the difference of two intersecting rows. These are the words $\sum_{x \in \Delta}G_x$ where $\Delta$ is any of the six triangles of points in $P(9)$.%} \end{example} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \section{\boldmath Gap in the weight enumerator for $p$ odd}\label{sec_gap} Notice that from Result~\ref{res_gapp}, we need only establish the gap in the weight enumerator for the non-bipartite graphs for the $p$ odd case. In analogy to Results~\ref{res_restricted-lambda} and~\ref{res_gapp} we now have the following: %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \begin{theorem} \label{theo:p-odd-gap1} Let $\Gamma=(V,E)$ be a connected $k$-regular graph with $\lambda(\Gamma)=k$ which is not bipartite, $G$ an incidence matrix for $\Gamma$, $\lambda_{bip}(\Gamma)=k$ and $\lambda_{bip}'(\Gamma)>k$. Let $p$ be an odd prime, and let $W_i$ be the number of codewords of $C_p(G)$ of weight $i$. Then $W_i=0$ for $i=k+1, k+2,\ldots, \lambda_{bip}'(\Gamma)-1$, and $W_i>0$ for $i=\lambda_{bip}'(\Gamma)$. \end{theorem} \begin{proof} Let $d$ be the minimum weight of $C_p(G)$. By Result~\ref{res_theorem-3} we have $d=k$. It suffices to show that for every nonzero word $x\in C_p(G)$ we have $\wt(x)=k$ or $\wt(x) \geq \lambda_{bip}'(\Gamma)$, and that $C_p(G)$ contains a word of weight $\lambda_{bip}'(\Gamma)$. Fix a nonzero word $x=\sum_{v\in V} \mu_vG_v$, and for any scalar $\alpha$ define $V_{\alpha}$ to be the set of all vertices $v$ with $\mu_v=\alpha$. Let $\Gamma_x=\Gamma(V, E -\supp(x))$. Consider a vertex $v\in V_{\alpha}$ where $\alpha\neq 0$. For every neighbour $w$ of $v$ in $\Gamma_x$ we have $vw\notin \supp(x)$, and so $\mu_v+\mu_w=0$, i.e., $\mu_w=-\alpha$. For every neighbour $u$ of a neighbour $w$ of $v$ in $\Gamma_x$, we have $uw\notin \supp(x)$ and so $\mu_w+\mu_u=0$, i.e., $\mu_u=\alpha$. Repeating this argument we obtain that the component of $\Gamma_x$ containing $v$ is bipartite, where the partite set containing $v$ is contained in $V_{\alpha}$, and the partite set not containing $v$ is contained in $V_{-\alpha}$. So each component of $\Gamma_x$ is either fully contained in $V_{\alpha}\cup V_{-\alpha}$ for some $\alpha\neq 0$ and bipartite, or is contained in $V_0$. \\[2mm] %--- {\sc Case 1:} Every nontrivial component of $\Gamma_x$ is contained in $V_0$. \\[2mm] Since $x$ is not the zero-word, we have $V-V_{0}\neq \emptyset$. If $V-V_{0}$ contains only one vertex, $v$ say, then $x$ has weight $k$ and is a multiple of $G_v$. If $V-V_{0}$ contains at least two vertices, $v$ and $w$ say, then each of these vertices forms a component of $\Gamma_x$, and so every edge incident with $v$ or $w$ is in $\supp(x)$. Since at most one edge is incident with both, $v$ and $w$, we have $|\supp(x)| \geq 2k-1> \lambda_{bip}'(\Gamma)$, and so $\wt(x) > \lambda_{bip}'(\Gamma)$, as desired. \\[2mm] %--- {\sc Case 2:} $\Gamma_x$ contains a nontrivial component which is not contained in $V_0$. \\[2mm] Then $S=\supp(x)$ is a restricted bipartition set and so $\wt(x) =|S| \geq \lambda_{bip}'(\Gamma)$, as desired. To see that there exists a word of weight $\lambda_{bip}'(\Gamma)$ consider a minimum restricted bipartition set $S$, and let $\Gamma_1$ be a non-trivial bipartite component of $\Gamma-S$, and let $V_1$ and $V_2$ be the partite sets of $\Gamma_1$. Let $x=\sum_{v\in V} \alpha_v G_v$, where $\alpha_v$ is defined as follows: \[ \alpha_v = \left\{ \begin{array}{cc} 1 & \textrm{if $v\in V_1$}, \\ -1 & \textrm{if $v\in V_2$}, \\ 0 & \textrm{if $v\in V-(V_1 \cup V_2)$}. \end{array} \right. \] Since no proper subset of $S$ is a bipartition set, $S$ contains exactly those edges that join either two vertices of $\Gamma_1$ in the same partite set, or a vertex in $\Gamma_1$ to a vertex not in $\Gamma_1$. Hence $S=\supp(x)$, and so $\wt(x) = |S| = \lambda_{bip}'(\Gamma)$. \end{proof} \medskip Recall that it has been shown by Hellwig and Volkmann \cite{HV1} that if a graph is super-$\lambda'$, then it is also super-$\lambda$. The following lemma shows that a similar statement holds for super-$\lambda_{bip}'$ graphs. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \begin{lemma}\label{lem_lambdas} Let $\Gamma$ be a connected, non-bipartite, $k$-regular graph, where $k \ge 3$. \begin{enumerate} \item[$(i)$] If $\lambda_{bip}'(\Gamma) \geq k$ then $\lambda_{bip}(\Gamma)=k$. \item[$(ii)$] If $\lambda_{bip}'(\Gamma) > k$ then $\Gamma$ is super-$\lambda_{bip}$. \item[$(iii)$] If $\Gamma$ is super-$\lambda_{bip}'$, then $\Gamma$ is also super-$\lambda_{bip}$. \end{enumerate} \end{lemma} \begin{proof} Let $S\subset E(\Gamma)$ be a minimum bipartition set and let $\Gamma_1$ be a bipartite component of $\Gamma-S$ of largest order. We first note that if $\Gamma-S$ is connected, then $S$ is a restricted bipartition set, and so $\lambda_{bip}'(\Gamma) = |S| = \lambda_{bip}(\Gamma) \leq k$. \\ (i) Let $\lambda_{bip}'(\Gamma) \geq k$. If $\Gamma-S$ is connected, then it follows from the above that $\lambda_{bip}(\Gamma) =k$, so we may assume that $\Gamma-S$ is disconnected. If $\Gamma_1$ consists of a single vertex, then $S$ contains the edges incident with this vertex, and so we have $\lambda_{bip}(\Gamma) = |S| \geq k$, and if $\Gamma_1$ is a nontrivial component, then $S$ is a restricted bipartition set, and so $|S| \geq \lambda_{bip}'(\Gamma)\geq k$. Since always $\lambda_{bip}(\Gamma) \leq k$, we have $\lambda_{bip}(\Gamma)=k$ in all cases. \\ (ii) Since $\lambda_{bip}'(\Gamma)>k$, it follows from the above that $\Gamma-S$ is disconnected. Then $\Gamma_1$ consists of a single vertex, since otherwise $S$ is a restricted bipartition set and we obtain $\lambda_{bip}(\Gamma) =|S|\geq \lambda_{bip}'(\Gamma) >k$, contradicting $\lambda_{bip}(\Gamma)\leq k$. Let $v$ be the vertex in $\Gamma_1$. Then since $S$ is a minimal bipartition set, it follows that only the edges incident with $v$ are in $S$. Since $S$ is an arbitrary minimal bipartition set, this implies that $\Gamma$ is super-$\lambda_{bip}$. \\ (iii) This statement is a direct consequence of (ii), since for every $k$-regular super-$\lambda_{bip}'$ graph with $k\geq 3$ we have $\lambda_{bip}'(\Gamma)>k$.\end{proof} \medskip %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \section{\boldmath Words of weight $2k-2$ for $p$ odd}\label{sec_parywords} Now we show that the words of weight $2k-2$ in the $p$-ary case for $p$ odd are also, for a wide variety of connected regular graphs, as expected. Notice that in the bipartite case we can prove the following in precisely the same way as in Theorem~\ref{thm_binwords} for the binary case: %%%%%%%%%%%%%%%%%%% \begin{theorem}\label{thm_bippwords} Let $\Gamma=(V,E)$ be a $k$-regular, bipartite, connected, super-$\lambda'$ graph. Let $G$ be an incidence matrix for $\Gamma$, $p$ an odd prime. Let $W_i$ be the number of codewords of $C_p(G)$ of weight $i$. Then $W_i=0$ for $i\in \{1,2,\ldots,k-1\} \cup \{k+1, k+2,\ldots, 2k-3\}$. Moreover, \begin{itemize} \item[$(i)$] $W_k=(p-1)|V|$ and the words of weight $k$ are the scalar multiples of the rows of $G$; %and \item[$(ii)$] $W_{2k-2}=(p-1)|E|$ and every word of weight $2k-2$ is a scalar multiple of the difference of two rows of $G$ corresponding to two adjacent vertices. \end{itemize} \end{theorem} Consulting the list of families of graphs that are $k$-regular, bipartite, connected, and super-$\lambda'$, will tell us which families satisfy the theorem. Some of these can be found in Result~\ref{res_biplist}. %Since the conditions are the same as for the binary codes %(Theorem~\ref{thm_binwords}), the two examples, Example~\ref{eg_USG} %and Example~\ref{eg_SRG}, will be applicable. Thus from now on we concentrate on the non-bipartite, $p$ odd, case. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \begin{lemma} \label{lem_one-component} Let $\Gamma$ be a connected non-bipartite graph and let $S$ be a minimum restricted bipartition set. Then $\Gamma-S$ contains exactly one bipartite component. \end{lemma} \begin{proof} Let $\Gamma_1$ be a non-trivial bipartite component of $\Gamma-S$. Suppose by way of contradiction that $\Gamma-S$ has another bipartite component, $\Gamma_2$ say. Since $S$ is minimal, every edge of $S$ is incident with a vertex $\Gamma_1$. Since $\Gamma$ is connected it follows that there exists an edge $e\in S$ joining a vertex in $\Gamma_1$ to a vertex in $\Gamma_2$. We claim that $S'=S-\{e\}$ is a restricted bipartition set. Clearly, $(\Gamma_1\cup \Gamma_2)+e$ is a nontrivial component of $\Gamma-S'$. This component does not contain an odd cycle since neither $\Gamma_1$ nor $\Gamma_2$ contain an odd cycle, and there is no cycle containing $e$ since $e$ is a bridge of $(\Gamma_1\cup \Gamma_2)+e$. Hence it is also bipartite, and so $S'$ is a smaller restricted bipartition set, a contradiction to the minimality of $S$.\end{proof} \medskip %%%%%%%%%%%%%%%%% \begin{theorem}\label{thm_pwords} Let $\Gamma=(V,E)$ be a $k$-regular, connected, non-bipartite, super-$\lambda_{bip}'$ graph. Let $G$ be an incidence matrix for $\Gamma$. Let $p$ be an odd prime, and let $W_i$ be the number of codewords of $C_p(G)$ of weight $i$. Then $W_i=0$ for $i\in \{1,2,\ldots,k-1\} \cup \{k+1, k+2,\ldots, 2k-3\}$. Moreover, \begin{enumerate} \item[$(i)$] $W_k=(p-1)|V|$ and the words of weight $k$ are the scalar multiples of the rows of $G$; \item[$(ii)$] $W_{2k-2}=(p-1)|E|$, and every word of weight $2k-2$ is a scalar multiple of a difference of two rows of $G$ corresponding to two adjacent vertices. \end{enumerate} \end{theorem} \begin{proof} (i) It follows from \cite[Theorem~3]{dakero1} that $W_1=W_2=\ldots=W_{k-1}=0$ and the words of weight $k$ are the scalar multiples of rows of $G$. Hence we have $W_k=(p-1)n$. (ii) It follows from Theorem~\ref{theo:p-odd-gap1} and the fact that $\lambda_{bip}'(\Gamma)=2k-2$ that $W_{k+1}=W_{k+2}=\ldots=W_{2k-3}=0$ and $W_{2k-2}>0$. Consider a word $x\in C_{p}(G)$ of weight $2k-2$. We use the same notation as in the proof of Theorem \ref{theo:p-odd-gap1}. If every nontrivial component of $\Gamma_x$ is contained in $V_0$, then, as in the proof of Theorem \ref{theo:p-odd-gap1}, $w(x)$ either equals $k$ or is at least $2k-1$, so this case cannot occur. Hence $\Gamma_x$ has a nontrivial component $\Gamma_1$ not contained in $V_0$. As in the proof of Theorem~\ref{theo:p-odd-gap1}, $\Gamma_1$ is bipartite, i.e., $\supp(x)$ is a restricted bipartition set of cardinality $\wt(x)=2k-2$. Since $\Gamma$ is super-$\lambda_{bip}'$, this implies that $\supp(x)$ consists of the edges incident with the vertices of an edge $uv$, except the edge $uv$ itself, and that $\Gamma_1$ contains only the vertices $u$ and $v$. By Lemma \ref{lem_one-component}, $\Gamma_1$ is the only bipartite component of $\Gamma_x$. Therefore, $\mu_w=0$ for all vertices $w$ not in $\Gamma_1$, and furthermore $\mu_u=-\mu_v$. Hence $x=\alpha G_u - \alpha G_v$ for some scalar $\alpha\neq 0$, and so $x$ is a scalar multiple of the difference of two rows of $G$ corresponding to adjacent vertices.\end{proof} \medskip We will frequently make use of the following proposition in order to show that a graph is super-$\lambda_{bip}$. \begin{proposition}\label{prop:main-tool} Let $\Gamma$ be a connected, $k$-regular graph that is not bipartite. Then \begin{enumerate} \item[$(a)$] $\lambda_{bip}'(\Gamma) \geq \min \{ \lambda'(\Gamma), b(\Gamma)\}$. \item[$(b)$] If $\lambda'(\Gamma)=2k-2$ and $b(\Gamma) \geq 2k-2$, then $\lambda_{bip}'(\Gamma)=2k-2$. \item[$(c)$] If $\Gamma$ is super-$\lambda'$ and $b(\Gamma)>2k-2$, then $\Gamma$ is super-$\lambda_{bip}'$. \end{enumerate} \end{proposition} \begin{proof} (a) Let $S$ be a set of cardinality $\lambda_{bip}'(\Gamma)$ such that $\Gamma-S$ contains a nontrivial bipartite component $\Gamma_1$. If $\Gamma_1$ contains all vertices of $\Gamma$, then $\Gamma-S$ is bipartite, and so $|S| \geq b(\Gamma) \geq \min \{ \lambda'(\Gamma), b(\Gamma)\}$. Hence we may assume that $\Gamma_1$ does not contain all vertices of $\Gamma$. By Lemma~\ref{lem_one-component}, $\Gamma-S$ contains no bipartite component other than $\Gamma_1$, and in particular no trivial component. Hence every component of $\Gamma-S$ is non-trivial, and so $S$ is a restricted edge-cut, implying that $|S| \geq \lambda'(\Gamma)$. Hence (a) follows. \noindent (b) The statement in (b) is a direct consequence of (a). \noindent (c) Let $S$ be as in (a). Since $|S| = \lambda'_{bip}(\Gamma) \le 2k - 2 < b(\Gamma)$, as above, $S$ is a restricted edge-cut, and $S$ contains at most $2k-2$ edges. Since $\Gamma$ is super-$\lambda'$, we have $|S|=2k-2$, and $S$ consists of the edges incident with an edge of $\Gamma$. Hence $\Gamma$ is super-$\lambda_{bip}'$.\end{proof} \medskip We now give sufficient conditions for a graph to be super-$\lambda_{bip}'$ or super-$\lambda_{bip}$. We first consider conditions on the vertex degrees. In \cite[Corollary~3]{dakero1} it was shown that for a $k$-regular non-bipartite graph on $n\ge 6$ vertices with $k\geq \frac{n+3}{2}$ we always have $\lambda_{bip}(\Gamma) = k$. Below we show that $k\geq \frac{n+5}{2}$ guarantees the non-bipartite graph to be super-$\lambda_{bip}'$. In the proof we use the well-known fact that a bipartite graph on $n$ vertices has at most $\frac{n^2}{4}$ edges. %%%%%%%%%%%%%%%%%% \begin{proposition}\label{prop_kbound} Let $\Gamma=(V,E)$ be a connected non-bipartite $k$-regular graph with $|V|=n$ and $k\geq \frac{n+5}{2}$ and $n\geq 13$. Then $\Gamma$ is super-$\lambda_{bip}'$. \end{proposition} \begin{proof} We note that $\Gamma$ is super-$\lambda'$ by Result~\ref{res_list}($3a'$), so, by Proposition~\ref{prop:main-tool}(c) it suffices to show that $b(\Gamma) > 2k-2$. Since a bipartite graph on $n$ vertices has at most $\frac{n^2}{4}$ edges, we have \[ b(\Gamma)\geq |E(\Gamma)|-\frac{1}{4}n^2 = \frac{1}{2}kn - \frac{1}{4}n^2 > 2k-2. \] It is easy to verify that the last inequality holds provided $k\geq \frac{n+5}{2}$ and $n\geq 13$.\end{proof} \medskip Note that the condition $k\geq \frac{n+5}{2}$ is best possible to guarantee that $\Gamma$ is super-$\lambda'_{bip}$. To see this let $n$ be even and let $\Gamma$ be the graph obtained from a complete bipartite graph $K_{n/2,n/2}$ with partite sets $U$ and $W$ by adding the edges of two cycles, one through the vertices of $U$, and the other through the vertices of $W$. Then $\Gamma$ is $k$-regular with $k=\frac{n+4}{2}$. It is easy to verify that $\lambda_{bip}'(\Gamma) = b(\Gamma) = n = 2k-4$. We note further that the condition $k\geq \frac{n+3}{2}$ given in \cite{dakero1} is best possible to guarantee that $\lambda_{bip}(\Gamma)=k$. To see this let $n\equiv 0 \pmod{4}$ and let $\Gamma$ be the graph obtained from a complete bipartite graph $K_{n/2,n/2}$ by adding the edges of a perfect matching. Then $\Gamma$ is $k$-regular with $k=\frac{n+2}{2}$. It is easy to verify that $\lambda_{bip}'(\Gamma) = b(\Gamma) = \frac{n}{2} = k-1$. \medskip We now give lower bounds on $b(\Gamma)$ which will be needed when we consider strongly regular graph, edge-transitive graphs and vertex transitive graphs. While several results for upper bounds on $b(\Gamma)$ are known (usually stated as lower bounds on the maximal number of edges in a bipartite subgraph of $\Gamma$), little appears to be known regarding lower bounds on $b(\Gamma)$. %%%%%%%%%%%%%%%%%%%%% \begin{lemma} \label{la:lower-bound-for-b} Let $a\ge 3$ be odd, and let $\Gamma$ be a graph of order $n$ containing a cycle of length $a$. \begin{enumerate} \item[$(i)$] If $\Gamma$ is $k$-regular graph and every edge of $\Gamma$ is on the same number of cycles of length $a$, then $ b(\Gamma) \geq \frac{nk}{2a}. $ \item[$(ii)$] If every vertex of $\Gamma$ is on the same number of cycles of length $a$, then $ b(\Gamma) \geq \frac{n}{a}. $ \end{enumerate} \end{lemma} \begin{proof} (i) Let each edge of $\Gamma$ be contained in $t$ cycles $C_a$, where $t>0$. Then the total number of cycles $C_a$ in $\Gamma$ equals $\frac{|E|t}{a}=\frac{nkt}{2a}$. Now removing an edge destroys at most $t$ cycles $C_a$. Hence, if $S\subseteq E$ is a set of $b(\Gamma)$ edges such that $\Gamma-S$ is bipartite, $|S|t$ is at least the total number of cycles $C_a$. Hence $ |S|t \geq \frac{nkt}{2a} $ and thus $ b(\Gamma) = |S| \geq \frac{nk}{2a}. $ (ii) Let each vertex of $\Gamma$ be contained in $t$ cycles of length $a$, where $t>0$. Then the total number of cycles $C_a$ in $\Gamma$ equals $\frac{nt}{a}$. Consider an arbitrary edge $uv$. Each cycle through $uv$ also goes through $u$, so there are at most $t$ cycles through $uv$, i.e., removing $uv$ destroys at most $t$ cycles $C_a$. As above, $|S|t \geq \frac{nt}{a} $ and thus $b(\Gamma) = |S| \geq \frac{n}{a}. $\end{proof} \medskip Now consider strongly regular graphs. %%%%%%%%%%%%%%%%%%%%% \begin{theorem} \label{theo:strongly-regular} Let $\Gamma=(V,E)$ be a strongly regular graph with parameters $(n,k,\lambda,\mu)$ that is not bipartite. Then $\Gamma$ is super-$\lambda_{bip}'$ if one of the following conditions hold: \\ $(i)$ $\lambda \ge 1$, $\mu\geq 3$, $n\geq 13$;\, $(ii)$ $\lambda = 1$, $\mu\geq 2$, $n\geq 10$; \, $(iii)$ $\lambda =0$, $\mu \geq 2$, $n\geq 19$. \end{theorem} \begin{proof} Under the conditions given in the statement $\Gamma$ is super-$\lambda'$ by Result~\ref{res_list}($4'$). Hence, by Proposition~\ref{prop:main-tool} it suffices to show that $b(\Gamma)>2k-2$. First suppose $\lambda\geq 1$. Then every edge is on exactly $\lambda \ge 1$ triangles. Applying Lemma~\ref{la:lower-bound-for-b}~(i) with $a=3$, we get that $b(\Gamma) \geq \frac{nk}{6}>2k-2$, i.e.\ $nk >12k-12$, which is true for $n\geq 11$, and thus for $n \ge 13$ to give $(i)$. % if also $\mu \ge 3$. If $\lambda=1$ and $\mu \ge 2$, then $\Gamma$ still has triangles, so if $n \ge 11$ the conditions are satisfied. If $n=10$ then by Equation~$(\ref{eqn_params})$, $(9-k)\mu=k(k-2)$ and there are no solutions with $0<\mu2k-2$, i.e.\ $nk>20k-20$ true for $n\geq 19$, and thus %with $\mu \ge 2$, $(iii)$ is proved.\end{proof} \medskip It was noted in \cite{dakero1} that for vertex transitive graphs $\lambda_{bip}(\Gamma)$ does not necessarily equal $k$, and the same holds true for edge-transitive and arc-transitive graphs. Below we show that under very mild additional assumptions vertex- or edge-transitive graphs do not only satisfy $\lambda_{bip}(\Gamma)=k$, but are also super-$\lambda_{bip}'$. We first consider edge-transitive graphs. In the proof of the following theorem we make use of the well known fact that a shortest odd cycle in a graph is always a {\em geodesic subgraph}, i.e., the distance between two vertices in such a cycle is equal to the distance between the two vertices in the graph $\Gamma$. We further use bounds on the radius of graphs. The {\em radius}, $ {\rm rad}(\Gamma)$, is defined as the smallest among the eccentricities of the vertices, where the {\em eccentricity} of a vertex $v$ is the largest of the distances between $v$ and all other vertices in $\Gamma$. %The first bound in the result below is a slight improvement of a bound by Erd\"{o}s et al.\ %\cite{EPPT}: see~\cite{dank:pc}. The following bound can be found in \cite{EPPT}. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \begin{result} \label{prop:radius} Let $\Gamma$ be a connected graph of order $n$ and minimum degree $\delta$. If $\Gamma$ contains no $4$-cycle, then $ {\rm rad}(\Gamma) \leq 5n/2(\delta^2 - 2\lfloor \delta/2 \rfloor +1). $ \end{result} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \begin{lemma}~\label{la:edge-transitive} Let $\Gamma$ be a connected $k$-regular, edge-transitive, triangle-free graph which is not bipartite. Then\\ $(a)$ if $k\geq 5$ then $b(\Gamma) > k$; \,\, $(b)$ if $k\geq 7$ then $b(\Gamma) > 2k-2$. \end{lemma} \begin{proof} Let $C$ be an odd cycle of shortest length, $g_0\geq 5$. We first derive a lower bound on $n$ in terms of $g_0$ and $k$. Let $S= \cup_{v \in V(C)} N(v)$. Every vertex of $\Gamma$ is adjacent to at most two vertices of $C$ since a vertex adjacent to three or more vertices of $C$ would produce a triangle or a shorter odd cycle. Hence no vertex of $\Gamma$ is in more than two sets $N(v)$, $v\in V(C)$, and so \[ n \geq |S| \ge \frac{1}{2} \sum_{v \in V(C)} |N(v)| = \frac{1}{2}g_0k. \] Applying Lemma 3 we get \[ b(\Gamma) \geq \frac{nk}{2g_o} \geq \frac{k^2}{4}. \] The right hand side of the last inequality is greater than $k$ if $k\geq 5$, and greater than $2k-2$ if $k\geq 7$.\end{proof} \medskip %%%%%%%%%%%%%%%%%%%%%%%%%%%% \begin{theorem}\label{thm_triangles} Let $\Gamma=(V,E)$ be a connected $k$-regular ($k\ge 3$), edge-transitive graph which is not bipartite, nor a line graph of a $3$-regular, triangle-free, edge-transitive, $2$-path-transitive graph. Let $|V|=n$. \begin{enumerate} \item If $\Gamma$ contains triangles then \\ $(i)$ if $n\geq 7$ then $\Gamma$ is super-$\lambda_{bip}$; \,\, $(ii)$ if $n\geq 11$ then $\Gamma$ is super-$\lambda_{bip}'$. \item If $\Gamma$ is triangle-free, then \\ $(iii)$ if $k\geq 5$ then $\Gamma$ is super-$\lambda_{bip}$; \, \, $(iv)$ if $k\geq 7$ then $\Gamma$ is super-$\lambda_{bip}'$. \end{enumerate} \end{theorem} \begin{proof} First use Result~\ref{res_list}($2'$) to show that $\Gamma$ is super-$\lambda'$: if $\Gamma$ is triangle-free then it cannot be $K_6-M$, nor a line graph, since for $k\ge 3$ the line graph will have triangles; if $\Gamma$ has triangles and $n \ge 7$ then $\Gamma$ is not $K_6-M$, and is not the line graph of a $3$-regular graph as described in Result~\ref{res_list}($2'$), in which case $k= 4$. Since this family is excluded, Result~\ref{res_list}($2'$) is satisfied, and so by Result~\ref{prop:lambda-bip} and Proposition~\ref{prop:main-tool} it suffices to show that $b(\Gamma)>k$ for $(i)$ and $(iii)$, and $b(\Gamma)>2k-2$ for $(ii)$ and $(iv)$. If $\Gamma$ contains triangles, then every edge is on the same number of triangles. Hence, by Lemma \ref{la:lower-bound-for-b} we have $b(\Gamma)\geq \frac{nk}{6}$, and thus $b(\Gamma)>k$ for $n>6$ and $b(\Gamma)>2k-2$ for $n\geq 11$, implying (i) and (ii). If $\Gamma$ is triangle-free, that $b(\Gamma)>k$ and $b(\Gamma)>2k-2$ for the stated values of $k$ follows from Lemma~\ref{la:edge-transitive}.\end{proof} \medskip The above theorem shows that regular edge-transitive graphs of sufficiently large vertex-degree are always super-$\lambda_{bip}'$. That this is not necessarily the case for edge-transitive graphs with small vertex-degrees, even if we assume arc-transitivity, can be seen from the following examples of $4$- and $6$-regular arc-transitive graphs for which $\lambda_{bip}'(\Gamma)<2k-2$. \begin{example}\label{eg_arctr}%{\rm Let $n\geq 3$ be an odd integer, and let $a\in \{2,3\}$. Consider the graph $\Gamma=C_n[\overline{K_a}]$, i.e., the graph with vertex set $\bigcup_{i=1}^n U_i$, where the $U_i$ are disjoint sets of cardinality $a$, with all $a^2$ edges between $U_i$ and $U_{i+1}$, where the indices are taken modulo $n$. Hence $\Gamma$ is edge-transitive and $k$-regular with $k=2a$. It is easy to verify that the set of all edges between $U_n$ and $U_1$ is a minimum bipartition set, so $\lambda_{bip}'(\Gamma)=a^2<2k-2=4a-2$ for $a\in \{2,3\}$. %} \end{example} We now consider vertex-transitive graphs. %%%%%%%%%%%%%%%%%%%%%%% \begin{lemma}~\label{la:vertex-transitive} Let $\Gamma$ be a connected $k$-regular, vertex-transitive graph with no $4$-cycles, that is not bipartite. Then\\ $(a)$ if $k\geq 7$ then $b(\Gamma) > k$; \,\, $(b)$ if $k\geq 12$ then $b(\Gamma) > 2k-2$. \end{lemma} \begin{proof} Let $C$ be an odd cycle of shortest length, $g_o$, and let $v$ be a vertex on $C$. Since $\Gamma$ is vertex-transitive, the eccentricity of $v$ equals the radius of $\Gamma$. Then the two vertices, $u$ and $w$, opposite $v$ in $C$ are at distance $\frac{g_o-1}{2}$ from $v$ in $C$. Since $C$ is an isometric subgraph of $\Gamma$, we have \[ \frac{g_o-1}{2}= d_C(v,w) = d_{\Gamma}(v,w) \leq {\rm rad}(\Gamma) \leq \frac{5n}{2(\delta^2 - 2\lfloor \delta/2 \rfloor +1)} \] where the last inequality follows from Proposition \ref{prop:radius}. Dropping the floors in the last fraction, we obtain that \[ g_o\leq \frac{5n+k^2-k+1}{k^2-k+1}. \] Applying Lemma~\ref{la:lower-bound-for-b}, we get \[ b(\Gamma) \geq \frac{n}{g_o} \geq \frac{n(k^2-k+1)}{5n+k^2-k+1}. \] The right hand side of the last inequality is increasing in $n$ for fixed $k$. Since $\Gamma$ has no $4$-cycles, we have $n\geq k^2 - 2\lfloor k/2 \rfloor +1$. (This well-known inequality follows from the fact that a vertex of $\Gamma$, $v$ say, has $k$ neighbours, and the neighbourhoods of any two neighbours of $v$ have no vertex in common other than $v$, since otherwise $v$ would be on a $4$-cycle. Note that a neighbour of $v$ may be adjacent to at most one other neighbour of $v$, which means that at most $2\lfloor k/2 \rfloor$ neighbours of $v$ are adjacent to another neighbour of $v$.) Substituting this for $n$ yields, after a simple calculation, that $b(\Gamma) > k$ for $k\geq 7$, and $b(\Gamma)>2k-2$ for $k\geq 12$. \end{proof} \medskip %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \begin{theorem}\label{thm_verttran} Let $\Gamma$ be a connected $k$-regular, vertex-transitive graph with no $4$-cycles, that is not bipartite. Then\\ $(i)$ if $k\geq 7$ then $\Gamma$ is super-$\lambda_{bip}$; \,\, $(ii)$ if $k\geq 12$ then $\Gamma$ is super-$\lambda_{bip}'$. \end{theorem} \begin{proof} For $(i)$, from Result~\ref{res_list}($1$), $\Gamma$ is super-$\lambda$ since $\Gamma$ does not contain $K_7$ as a subgraph. By Lemma~\ref{la:vertex-transitive}$(a)$, if $k\geq 7$ then $b(\Gamma)>k$. Hence, by Result~\ref{prop:lambda-bip}, $\Gamma$ is super-$\lambda_{bip}$. For $(ii)$, take $k\ge 12$ so that by Lemma~\ref{la:vertex-transitive}$(b)$, $b(\Gamma) >2k-2$. If $\Gamma$ has no triangles then by Result~\ref{res_list}($1a'$), $\Gamma$ is super-$\lambda'$. Since $b(\Gamma)>2k-2$, it follows by Proposition~\ref{prop:main-tool}(c) that $\Gamma$ is super-$\lambda_{bip}'$. If $\Gamma$ has triangles, we must use Result~\ref{res_list}($1b'$). Since $k \ge 12$, and $\Gamma$ has no 4-cycles, $\Gamma$ is not in $(i)$ or $(ii)$ of Result~\ref{res_list}($1b'$). Suppose Result~\ref{res_list}($1b'$)$(iii)$ or $(iv)$ that $\Gamma$ has a $(k-1)$-regular subgraph $\Delta=(W,F)$ on $\ell$ vertices where $k \le \ell \le 2k-2$. Let $u \in W$ and $N$ be the set of $k-1$ neighbours of $u$. If $U=W - (N \cup \{u\})$, then $|U|=\ell -k \le k-2$. Clearly $\ell=k$ would imply $\Delta=K_k$, which we cannot have. So $U \not = \emptyset$. Any $v \in U$ has $k-1$ neighbours in $\Delta$, at most $k-3$ of which can be in $U$; $uv$ is not an edge, so $v$ has at least two neighbours $x,y \in N$. Then $(u,x,v,y)$ is a 4-cycle in $\Gamma$, which we have excluded. Thus $\Gamma$ is not of this type. That $\Gamma$ cannot be of type Result~\ref{res_list}($1b'$)$(v)$ is immediate since a $(k-1)$-clique where $k \ge 12$ would have $4$-cycles. Hence $\Gamma$ is super-$\lambda'$, and thus super-$\lambda_{bip}'$ since $b(\Gamma) >2k-2$.\end{proof} \medskip We note that for $k$-regular vertex-transitive graphs the inequality $\lambda_{bip}(\Gamma) \geq k$ does not hold in general if $4$-cycles are present, even for arbitrarily large vertex degrees. To see this consider the following example. \begin{example}\label{eg_4cycles}{\rm Let $a,b$ be integers greater than $1$, $a$ even and $b$ odd, and let $\Gamma^1, \Gamma^2,\ldots,\Gamma^b$ be disjoint copies of the complete bipartite graph $K_{a,a}$. Let $U_i=\{u^i_1, u^i_2,\ldots,u^i_a\}$ and $W_i=\{w^i_1, w^i_2,\ldots,w^i_a\}$ be the partite sets of $\Gamma^i$. Let $\Gamma$ be the graph obtained from the union of the $\Gamma^i$ by adding the edges $u^i_{a/2+j}w^{i+1}_j$ and $w^i_{a/2+j}u^{i+1}_j$, $j=1,2,\ldots,a/2$, between $\Gamma^i$ and $\Gamma^{i+1}$ for $i=1,2,\ldots,b-1$, and the edges $u^b_{a/2+j}u^{1}_j$ and $w^b_{a/2+j}w^{1}_j$, $j=1,2,\ldots,a/2$ between $\Gamma^b$ and $\Gamma^{1}$. It is easy to verify that $\Gamma$ is $(a+1)$-regular and vertex-transitive. Clearly, the graph $\Gamma-\{u^b_{a/2+j}u^{1}_j, w^b_{a/2+j}w^{1}_j \mid j=1,2,\ldots,a/2\}$ is bipartite with partite sets $\bigcup U_i$ and $\bigcup W_i$, but $\Gamma$ is not bipartite. Since removing the set $\{u^b_{a/2+j}u^{1}_j, w^b_{a/2+j}w^{1}_j \mid j=1,2,\ldots,a/2\}$ renders $\Gamma$ bipartite, we have $b(\Gamma) \leq |\{u^b_{a/2+j}u^{1}_j, w^b_{a/2+j}w^{1}_j \mid j=1,\ldots,a/2\}| = a$. Hence $\Gamma$ is $(a+1)$-regular, but $\lambda_{bip}(\Gamma)\leq b(\Gamma) \leq a$.} \end{example} %%%%%%%%%%%%%%%%%%%%%%%% \begin{corollary}\label{coro:summary} Let $\Gamma$ be a connected, $k$-regular graph on $n$ vertices that is not bipartite, and let $p$ be an odd prime. Let $G$ be an incidence matrix for $\Gamma$. Then $\dim(C_p(G))=n$ and if any one of the following holds: \begin{itemize} \item[1.] $k\geq \frac{n+5}{2}$ and $n \ge 13$; \item[2.] $\Gamma$ is strongly regular with parameters $(n,k,\lambda,\mu)$ with\\ $(i)$ $\lambda \ge 1$,$\mu \geq 3$, $n\geq 13$; or $(ii)$ $\lambda=1$, $\mu \geq 2$, $n\geq 10$; or $(iii)$ $\lambda=0$, $\mu\geq 2$, $n\geq 19$; \item[3.] $\Gamma$ is edge-transitive, $k\geq 3$ and \\ $(i)$ $\Gamma$ contains triangles and $n\geq 11$, or $(ii)$ $\Gamma$ is triangle-free and $k\geq 9$; \item[4.] $\Gamma$ is vertex-transitive, contains no $4$-cycles, and $k\geq 12$, \end{itemize} then the minimum weight of $C_p(G)$ is $k$, the words of weight $k$ are precisely the scalar multiples of the rows of $G$, there are no words of weight $i$ such that $k k$ then we will have $\Gamma$ super-$\lambda_{bip}$ and hence we can use Result~\ref{res_theorem-3}. From Lemma~\ref{la:edge-transitive} we see this is true if $k \ge 5$. For $(4)$, if $\Gamma$ is vertex-transitive, with no complete subgraph of order $k$, then by Result~\ref{res_list}~($1$), it is super-$\lambda$, so using Result~\ref{prop:lambda-bip}, if we can show that $b(\Gamma) >k$ then we will have $\Gamma$ super-$\lambda_{bip}$ and hence we can use Result~\ref{res_theorem-3}. From Lemma~\ref{la:vertex-transitive} this is true for $k \ge 7$.\end{proof} \medskip \begin{example}\label{eg_ham}{\rm The Hamming graph $H(d,q)$, where $q,d\geq 2$, has for vertices the $q^d$ words of length $d$ over an alphabet of $q$ elements, and where two vertices are adjacent if their words differ in exactly one position. For all $d,q$ $H(d,q)$ is $k$-regular with $k=d(q-1)$, and it is edge-transitive. It is bipartite if $q=2$, and for $d \ge 4$ $H(d,2)=Q_d$ will satisfy Theorem~\ref{thm_bippwords}, using Result~\ref{res_biplist}($2'$). For $d=3$, $H(3,2)=Q_3$ and for all $p$ there are words of weight 4 that are not from the difference of two intersecting rows. For $q\geq 3$, $H(d,q)$ contains triangles, and so the conclusion of Corollary \ref{coro:summary}(3) holds for $H(d,q)$ for $p$ odd if $q^d \ge 11$, i.e.\ all $d \ge 2$ and $q \ge 3$ apart from $d=2,q=3$. Using Magma $H(2,3)$ was shown not to satisfy the conclusion for all $p$. Note that for the binary case it is excluded by Result~\ref{res_list}($2'$) since $H(2,3)=L(K_{3,3})$. } \end{example} \begin{example}\label{eg_lat}{\rm The square lattice graph $L_2(m)$ and the triangular graph $T(m)$ ($G(m,2,1)$ in the notation of Example~\ref{eg_USG}) are edge-transitive, both are line graphs and thus contain triangles, and so the conclusion of Corollary~\ref{coro:summary}(3) holds for these graphs if they have at least $11$ vertices, i.e., for $L_2(m)$ if $m\geq 4$, and for $T(m)$ if $m \geq 6$. Both graphs are also strongly regular: $L_2(m)$ is an $(m^2,2(m-1),m-2,2)$ and $T(m)$ is $(\binom{m}{2},2(m-2),m-2,4)$, and neither $L_2(3)$ nor $T(5)$ satisfy the requirements of Corollary~\ref{coro:summary}(2). Notice that for $G$ an incidence matrix for $T(5)$, $C_p(G)$, for any $p$ odd, has words of weight 10 that are not the difference of two rows. These can be constructed from two disjoint 5-cycles, for example $c_1=( \{1,2\}, \{2,3\}, \{3,4\}, \{4,5\}, \{5,1\} )$ and $c_2=(\{1,3\}, \{3,5\}, \{5,2\}, \{2,4\}, \{4,1\} )$, and then $w=\sum_{u \in c_1}G_u -\sum_{u \in c_2}G_u$ has weight 10 but is not a scalar multiple of the difference of two rows of $G$. There are six words of this type, not counting scalar multiples. Similarly, for $G$ an incidence matrix of $L_2(3)$, $C_p(G)$ has words of weight 6 that are not scalar multiples of the difference of two rows of $G$. If the bipartite sets of $K_{3,3}$ are $\{1,2,3\},\{4,5,6\}$ then if $s_1=\{\{1,4\},\{1,5\},\{2,4\},\{3,6\}\}$, $s_2=\{\{1,6\},\{2,5\},\{2,6\},\{3,4\},\{3,5\}\}$, $w=\sum_{u \in s_1}G_u -\sum_{u \in s_2}G_u$ has weight 6 and is not a scalar multiple of the difference of two rows of $G$. There are 36 words of this type, modulo scalar multiples.} \end{example} %{\bf Example} Johnson graphs and Kneser graphs are edge-transitive, so.... \begin{example}\label{eg_USGp}{\rm For the uniform subset graphs $G(n,k,r)$ (see Example~\ref{eg_USG}), since they are edge-transitive, Corollary~\ref{coro:summary}(3), is applicable. In~\cite{fikemw10} it was shown that $G(n,1,0)$ (i.e.\ $K_n$), which contains triangles for $n\ge 3$, satisfies the conclusions of Corollary~\ref{coro:summary} for $n\ge 9$ for $p$ odd, a slight improvement on Corollary~\ref{coro:summary}(3)(i). } \end{example} \begin{example}\label{eg_SRGp}{\rm For $P(9)$ (see Example~\ref{eg_SRG}), strongly regular of type $(9,4,1,2)$, $C_2(G)$ (where $G$ is an incidence matrix) has words of weight 6 that are not differences of rows of $G$. Similarly $C_p(G)$ is covered by Corollary~\ref{cor_more}(2) but not by Corollary~\ref{coro:summary}(2), and it has words of weight 6 that are not differences of rows of $G$. These can be obtained from a $6$-cycle $(x_1,\ldots,x_6)$ that is an isometric subgraph of $P(9)$, in which case %, where there are no edges in the cycle other than the edges of the cycle itself, $w=\sum_{i=1}^6 G_{x_i} -\jvec$ has weight $6$ and $\supp(w)=\{x_1x_2,x_2x_3,x_3x_4,x_4x_5,x_5x_6,x_6x_1\}$. An example of such a cycle is $(1,w^5,w^6,w^2,w,w^4)$ where $w$ is a primitive root of the polynomial $X^2+2X+2$ over $\F_3$. }\end{example} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \section{Conclusion}\label{sec_end} In this paper we have used the notion of edge-connectivity, and related concepts, and the vast literature devoted to the study of classes of graphs that have the various connectivity properties, to show that for a wide range of classes of $k$-regular connected graphs $\Gamma=(V,E)$, the $p$-ary code, for any prime $p$, generated by the row span over $\F_p$ of a $|V|\times |E|$ incidence matrix $G$ for $\Gamma$ has dimension $|V|$ or $|V|-1$ and the properties: \begin{itemize} \item the minimum weight is $k$ and the vectors of weight $k$ are the scalar multiples of the rows of $G$, i.e.\ up to scalar multiples, there are $|V|$ words of weight $k$; \item there are no words of weight $i$ such that $k