\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 <n-1$.
Furthermore, we exclude the complete and the null graphs.

 
An {\em{adjacency matrix}} $A=[a_{u,v}]$ of a graph $\Gamma=(V,E)$
 is a $|V|\times |V|$ matrix with entries $a_{u,v}$, $u,v \in V$,
such that $a_{u,v}=1$ if  $u \sim v$  and 
$a_{u,v}=0$ otherwise.
An {\em incidence matrix}  of $\Gamma$ is an $|V| \times |E|$ matrix $G=[g_{u,e}]$ with
$g_{u,e}=1$ if the vertex $u$ is on the edge $e$ and $g_{u,e}=0$
otherwise. 
 We denote the row of
$G$ corresponding to vertex $v$ by $G_v$.

If $\Gamma$ is regular with valency $k$, then the $1$-$(|E|,k,2)$  design with incidence matrix $G$ is called the {\em incidence design} of $\Gamma$.
It was proved in~\cite{fikemw5} that
if $\Gamma$ is regular  with  valency $k$ and $\CAL{G}$  the $1$-$(|E|,k,2)$ incidence design for $\Gamma$, then $\aut(\Gamma)= \aut(\CAL{G})$. 
The {\em neighbourhood design} of a regular graph is the 1-design formed
by taking the points to be the vertices of the graph and the blocks to
be the sets of neighbours of a vertex, for each vertex, i.e.\ regarding an adjacency matrix as an incidence matrix for the design.
The {\em line graph} of a graph 
$\Gamma=(V,E)$ is the graph $L(\Gamma)$ with $E$ as vertex set and where
adjacency is defined so that  $e$ and $f$ in $E$, as vertices,  are adjacent in $L(\Gamma)$ if $e$ and $f$ as edges of $\Gamma$ share a vertex in
$\Gamma$.


The {\em{code}} of a graph $\Gamma$ over a finite field $F$ is the row
span of an adjacency matrix $A$ over the field $F$,
denoted by $C_F(\Gamma)$ or $C_F(A)$. The dimension of the code
is the rank of the matrix over $F$, also written $\rank_p(A)$ if $F=\F_p$,
in which case we will speak of the {\em{$p$-rank}} of $A$ or $\Gamma$,
and write $C_p(\Gamma)$ or $C_p(A)$ for the code. It is also the code over $\F_p$ of the neighbourhood design. Similarly, if $G$ is an incidence matrix for $\Gamma$, $C_p(G)$  denotes the row span of $G$ over $\F_p$ and is the code of the design with blocks the rows of $G$, in the case that $\Gamma$ is regular. 
%If $M$ is an adjacency matrix for $L(\Gamma)$ where $\Gamma$
 %is regular of valency $k$, $|V|$ vertices, $|E|$ edges, then
%\begin{equation}\label{eqn_matrels}
% G^TG = M +2I_{|E|},
%\end{equation}
%where  $G$ is an incidence matrix for $\Gamma$.

A graph is {\em bipartite} if and only if it does not have
an odd cycle.

We denote the {\em complete graph} on $n$ vertices by $K_n$, the {\em complete
bipartite graph} on $n+m$ vertices whose partite sets have $n$ and $m$
vertices, respectively, by $K_{m,n}$, and the {\em cycle} on $n$ vertices by $C_n$.
A {\em triangle} is the graph $K_3$.
The graph obtained from $K_n$, where $n$ is even, by removing a 
perfect matching $M$,
is denoted by $K_{n}-M$.
We write $C_n \times K_2$ and $C_n[K_2]$ for the {\em{cartesian}} product and the {\em{lexicographic}}
product, respectively, of $C_n$ and $K_2$. These graphs are obtained from the disjoint
union of two cycles on $n$ vertices, $u_0, u_1,\ldots, u_{n-1}, u_0$ and
$v_0, v_1, \ldots, v_{n-1}, v_0$ by adding the set of edges
$\{u_iv_i| i=0,1,\ldots,n-1\}$  for $C_n\times K_2$ and
$\{u_iv_{i-1}, u_iv_i, u_iv_{i+1}| i=0,1,\ldots,n-1\}$ for $C_n[K_2]$.
We denote by $M_n$ the {\em Mobius ladder} with $n$ rungs, i.e., the graph obtained
from $C_n\times K_2$ as defined above by replacing the edges $u_{n-1}u_0$ and
$v_{n-1}v_0$ by $u_{n-1}v_0$ and $v_{n-1}u_0$. The {\em {square of the cycle $C_n$}},
denoted by $C_n^2$, is the graph obtained from  the cycle $u_0,u_1,\ldots, u_{n-1}, u_0$
by adding the edges $u_iu_{i+2}$ for $i=0,1,\ldots,n-1$. All subscripts are
to be taken modulo $n$.
A graph is said to be {\em triangle-free}  or {\em $C_4$-free} if it does not have a subgraph 
isomorphic to a $K_3$ or $C_4$, respectively. 

%%%%%%%%%%%
\subsection{Edge-cuts in graphs}\label{subsec_ECCG}

If $\Gamma=(V,E)$ is a connected
graph, then an {\em edge-cut} of $\Gamma$ is a subset $S\subseteq E$ such that removing
the edges in $S$ renders the new graph $\Gamma-S$ disconnected. The
{\em edge-connectivity} of $\Gamma$, denoted by $\lambda(\Gamma)$,
is the minimum cardinality of an edge-cut of $\Gamma$. 
A {\em bridge} of a connected graph is an edge whose removal disconnects
the graph.
So $\Gamma$ has a bridge if and only if $\lambda(\Gamma)=1$. 

If $\Gamma-S$
has only nontrivial components, i.e., components with at least two vertices,
then $S$ is a {\em restricted edge-cut}. The minimal cardinality of a
restricted edge-cut is the {\em restricted edge-connectivity}, denoted
by $\lambda'(\Gamma)$. 

Now assume that $\Gamma=(V,E)$ is connected $k$-regular, $k\geq 2$.%, and $S$ is an edge cut.
\begin{itemize}
\item 
For $x \in V$, if $S=\{xy\mid y \in N(x)\}$, then $S$ is an edge cut, so $ \lambda(\Gamma) \le k$.
\item
For
$xy \in E$, if $S=\{xz \mid z \in N(x)\} \cup \{yz \mid z \in N(y)\} -\{xy\}$, then
$S$
is a restricted edge-cut, so $\lambda'(\Gamma)\leq
2k-2$. 
\item
$\Gamma$ is {\em maximally edge-connected} if $\lambda(\Gamma)=k$,
and $\Gamma$ is {\em super-$\lambda$} if $\lambda(\Gamma)=k$ and every minimal edge-cut consists
of the edges incident with some vertex. 
\item $\Gamma$ is {\em maximally restricted
edge-connected} if $\lambda'(\Gamma)=2k-2$, and $\Gamma$ is {\em super-$\lambda'$} if
$\lambda'(\Gamma)=2k-2$ and every minimal restricted edge-cut  consists
of the edges incident with some  edge.
\item If a graph is
super-$\lambda'$, then it is also super-$\lambda$ (see Hellwig and Volkmann \cite{HV1}).
\end{itemize}


In \cite{dakero1},  a {\em bipartition set} of a non-bipartite graph
$\Gamma=(V,E)$ was defined to be a set $S\subseteq E$ such that $\Gamma-S$
contains a bipartite component. The minimum cardinality of a bipartition set of $\Gamma$ is denoted by
$\lambda_{bip}(\Gamma)$.


A {\em restricted bipartition set} is
 a bipartition set $S\subseteq E$ such that $\Gamma-S$ has a nontrivial bipartite
component, i.e., a component that is bipartite and contains more than one vertex.
So $\Gamma-S$ may contain isolated vertices, but at least one of the components of $\Gamma-S$
is a connected bipartite graph on at least two vertices. 
The minimum cardinality of a restricted bipartition set of $\Gamma$ is denoted 
by $\lambda_{bip}'(\Gamma)$.

Suppose $\Gamma$ is connected, non-bipartite,  $k$-regular $k\geq 2$.
\begin{itemize}
\item For $x \in V$, if $S=\{xy\mid y \in N(x)\}$, then $S$ is a bipartition set, so $ \lambda_{bip}(\Gamma)\le k$.
\item If $|V| \ge 3$ and
$xy \in E$, if $S=\{xz \mid z \in N(x)\} \cup \{yz \mid z \in N(y)\} -\{xy\}$, then
$S$
is a restricted bipartition set, so $ \lambda_{bip}'(\Gamma)\le 2k-2$.
\item $\Gamma$ is 
{\em super-$\lambda_{bip}$} if  $\lambda_{bip}(\Gamma)=k$ and
every  minimum  bipartition set consists
of the edges incident with some  vertex.
\item $\Gamma$ is 
{\em super-$\lambda_{bip}'$} if  $\lambda_{bip}'(\Gamma)=2k-2$ and
every  minimum restricted bipartition set consists
of the edges incident with some  edge.
\item The minimum number of edges of  $\Gamma$ whose removal
renders the graph bipartite is denoted by $b(\Gamma)$.
\end{itemize}





%%%%%Include the below if necessary
%If
%$W,X$ are non-empty disjoint sets of vertices of $\Gamma$, then $E(W,X)$ denotes the set
% of edges that have one end in $W$ and the other end in $X$, and
%we write $|E(W,X)|=q(W,X)$.
% The following well-known fact will be of
%use
%\begin{equation}\label{eq:lambda}
% \lambda(\Gamma) = \min_{\emptyset \neq W\subset V} q(W, V-W).
%\end{equation}



The concept of super edge-connectivity was first introduced by
Bauer, Suffel, Boesch, and Tindell \cite{BSBT} in 1981, and it has
been studied extensively since.
 For $G$  an incidence matrix of a connected graph $\Gamma$, $C_2(G)$ is
 also known as the {\em cut space} of $\Gamma$, and was examined for majority-logic decoding
 in~\cite{hakbre,hakfra}.
 
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\section{Previous results}\label{sec_results}

First we state the results from Dankelmann, Key, Rodrigues~\cite{dakero1} that give the first answers to the general questions about the codes from the incidence matrices of regular connected graphs.

The first result is well-known and
  quoted in~\cite[Result~1]{dakero1}:
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{result}\label{prop_dim}
Let $\Gamma=(V,E)$ be a connected graph, $G$ an incidence matrix for $\Gamma$,  and $C_p(G)$ the row-span of $G$ over $\F_p$.  Then $\dim(C_2(G))=|V|-1$. For odd $p$, $\dim(C_p(G))=|V|$ if $\Gamma$ is not bipartite, 
 and $\dim(C_p(G))=|V|-1$ if $\Gamma$  is
bipartite.
\end{result}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

The results from~\cite{dakero1}  for binary codes and that we now wish to extend to $p$-ary codes are as follows, starting with the minimum weight and words, and then referring to a list from the literature of such graphs that are super-$\lambda$, (see~\cite[Result~2]{dakero1}):
%%%%%%%%%%%%%%%%%%%
\begin{result}\label{theo:lambda}
{\rm (Dankelmann, Key, Rodrigues \cite[Theorem~1]{dakero1})}
Let $\Gamma=(V,E)$ be a connected graph, $G$ a $|V|\times|E|$ incidence matrix for $\Gamma$. Then
\begin{enumerate}
\item $C_2(G)$ is a $[|E|,|V|-1,\lambda(\Gamma)]_2$ code;
\item if $\Gamma$ is super-$\lambda$, then
$C_2(G)=[|E|,|V|-1,\delta(\Gamma)]_2$, and  the minimum words are the rows  of $G$ of weight $\delta(\Gamma)$.
\end{enumerate}
\end{result}

For the gap in the  weight-enumerator, and referring to the list in~\cite[Result~4]{dakero1}:
%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{result}\label{res_restricted-lambda}
{\rm  \cite[Theorem~4]{dakero1}}
Let $\Gamma=(V,E)$ be a connected $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_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<\mu<k<8$ of this, so $(ii)$ is proved.

If $\lambda=0$ then it is easy to show that $\Gamma$
 has $5$-cycles, and that every edge is on the same number of
$5$-cycles.  Hence, by Lemma~\ref{la:lower-bound-for-b} we have
$b(\Gamma) \geq \frac{nk}{10}>2k-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 <i <2k-2$, and the words of weight $2k-2$ are precisely the scalar multiples of
the differences of two rows of $G$ corresponding  to two adjacent vertices of $\Gamma$.
\end{corollary}
\begin{proof} Using Theorem~\ref{thm_pwords}: (1) follows from Proposition~\ref{prop_kbound}; (2) follows from Theorem~\ref{theo:strongly-regular}; (3) follows from Theorem~\ref{thm_triangles}; (4) follows from Theorem~\ref{thm_verttran}.\end{proof}
\medskip

These conditions can be weakened somewhat if only the minimum weight and the nature of the minimum words is required, so that Result~\ref{cor_lambdabip} could be extended to the following:
%%%%%%%%%%%%%%%%
\begin{corollary}\label{cor_more}
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+3}{2}$ and $n \ge 6$;
\item[2.] $\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$;
  \item[3.] $\Gamma$ is edge-transitive, $k\geq 5$; 
\item[4.] $\Gamma$ is vertex-transitive, $k\ge 7$, and $\Gamma$ contains no complete subgraph of order $k$,
\end{itemize}
then the minimum weight of  $C_p(G)$ is $k$ and the words of  weight $k$ are
precisely the scalar multiples of the rows of $G$.
\end{corollary}
\begin{proof} The first two cases are from Result~\ref{cor_lambdabip}. 

For $(3)$, if $\Gamma$ is edge-transitive, and $k \ge 3$ then by Result~\ref{res_list}~($2$) 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: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<i<2k-2$, and the words of weight $2k-2$ are the  scalar multiples of the differences of two rows of $G$ corresponding to adjacent vertices,
i.e.\ up to scalar multiples, there are $|E|$ words of weight $2k-2$.
\end{itemize}
In particular, for graphs satisfying these conditions, non-isomorphic graphs give non-isomorphic codes from their incidence matrices
since an incidence matrix of such a graph can be recovered from the words of minimum
weight of the code.
The work extends the results from~\cite{dakero1}. Furthermore, if the graph has an edge-transitive automorphism group, these codes  can be used for full error-correction using permutation decoding, as described in~\cite[Result~7]{dakero1}.

\SquashBibFurther

\begin{thebibliography}{10}

\bibitem{ak:book}
E.~F. Assmus, Jr and J.~D. Key.
\newblock {\em Designs and their Codes}.
\newblock Cambridge: Cambridge University Press, 1992.
\newblock Cambridge Tracts in Mathematics, Vol.~103 (Second printing with
  corrections, 1993).

\bibitem{BCFF}
C.\ Balbuena, A.\ Carmona, J.\ F\`{a}brega, and M. A. Fiol.
\newblock Superconnectivity of bipartite digraphs and graphs.
\newblock {\em Discrete Appl.\ Math.}, 197/198:61--75, 1999.

\bibitem{BLM}
C.\ Balbuena, Y.\ Lin, and M.\ Miller.
\newblock Diameter-sufficient conditions for a graph to be super-resricted
  connected.
\newblock {\em Discrete Appl.\ Math.}, 156:2827--2834, 2008.

\bibitem{BSBT}
D.\ Bauer, F.\ Boesch, C.\ Suffel, and R.\ Tindell.
\newblock Connectivity extremal problems and the design of reliable
  probabilistic networks.
\newblock In {\em The Theory and Applications of Graphs, Kalamazoo MI}, pages
  45--54. Wiley, New York, 1981.

\bibitem{magma1}
W.~Bosma, J.~Cannon, and C.~Playoust.
\newblock The {M}agma algebra system {I}: {T}he user language.
\newblock {\em J. Symbolic Comput.}, 24, 3/4:235--265, 1997.

\bibitem{BH}
A. E. Brouwer and W. H. Haemers.
\newblock Eigenvalues and perfect matchings.
\newblock {\em Linear Algebra Appl.}, 395:155--162, 2005.

\bibitem{magmaHB}
J.~Cannon, A.~Steel, and G.~White.
\newblock Linear codes over finite fields.
\newblock In J.~Cannon and W.~Bosma, editors, {\em Handbook of {M}agma
  {F}unctions}, pages 3951--4023. %Computational Algebra Group, 
  Department of
  Mathematics, Univ.\ of Sydney, 2006.
\newblock V2.13, \url{http://magma.maths.usyd.edu.au/}.

\bibitem{dakero1}
P.~Dankelmann, J.~D. Key, and B.~G. Rodrigues.
\newblock Codes from incidence matrices of graphs.
\newblock {\em Des. Codes Cryptogr.}, 68:373--393, 2013.
\newblock \doi{10.1007/s10623-011-9594-x}.

\bibitem{EPPT}
P.\ Erd\"{o}s, J.\ Pach, R.\ Pollack, and Z.\ Tuza.
\newblock Radius, diameter and minimum degree.
\newblock {\em J.\ Combin.\ Theory Ser. B}, 47(1):73--79, 1989.

\bibitem{FF}
J.\ F\`{a}brega and M. A. Fiol.
\newblock Bipartite graphs and digraphs with maximum connectivity.
\newblock {\em Discrete Appl.\ Math.}, 69:271--279, 1996.

\bibitem{Fio}
M. A. Fiol.
\newblock On super-edge-connected digraphs and bipartite digraphs.
\newblock {\em J.\ Graph Theory}, 16:545--555, 1992.

\bibitem{fikemw10}
W.~Fish, J.~D. Key, and E.~Mwambene.
\newblock Codes from uniform subset graphs and line graphs.
\newblock (In preparation).

\bibitem{fikemw5}
W.~Fish, J.~D. Key, and E.~Mwambene.
\newblock Codes from the incidence matrices and line graphs of {H}amming
  graphs.
\newblock {\em Discrete Math.}, 310:1884--1897, 2010.

\bibitem{ghireskey}
D. Ghinelli, M.~J. de~Resmini, and J.~D. Key.
\newblock Minimum words of codes from affine planes.
\newblock {\em J. Geom.}, 91:43--51, 2008.

\bibitem{ghikey}
D.~Ghinelli and J.~D. Key.
\newblock Codes from incidence matrices and line graphs of {P}aley graphs.
\newblock {\em Adv. Math. Commun.}, 5:93--108, 2011.
\newblock \doi{10.3934/amc.2011.5.93}.

\bibitem{hakbre}
S.~L. Hakimi and J.~G. Bredeson.
\newblock Graph theoretic error-correcting codes.
\newblock {\em IEEE Trans. Inform. Theory}, 14:584--591, 1968.

\bibitem{hakfra}
S.~L. Hakimi and H.~Frank.
\newblock Cut-set matrices and linear codes.
\newblock {\em IEEE Trans. Inform. Theory}, 11:457--458, 1965.

\bibitem{HV1}
A.\ Hellwig and L.\ Volkmann.
\newblock Sufficient conditions for graphs to be $\lambda'$-optimal,
  super-edge-connected and maximally edge-connected.
\newblock {\em J.\ Graph Theory}, 48:228--246, 2005.

\bibitem{Kel}
A.K.\ Kelmans.
\newblock Asymptotic formulas for the probability of $k$-connectedness of
  random graphs.
\newblock {\em Theory Probab.\ Appl.}, 17:243--254, 1972.

\bibitem{kemoro8}
J.~D. Key, J.~Moori, and B.~G. Rodrigues.
\newblock Codes associated with triangular graphs, and permutation decoding.
\newblock {\em Int. J. Inform. and Coding Theory}, 1, No.3:334--349, 2010.

\bibitem{kero1}
J.~D. Key and B.~G. Rodrigues.
\newblock Codes associated with lattice graphs, and permutation decoding.
\newblock {\em Discrete Appl. Math.}, 158:1807--1815, 2010.

\bibitem{fikemw6}
J.~D. Key, W. Fish, and E. Mwambene.
\newblock Codes from the incidence matrices and line graphs of {H}amming graphs
  ${H}^k(n,2)$ for $k \ge 2$.
\newblock {\em Adv. Math. Commun.}, 5:373--394, 2011.

\bibitem{MV}
D.\ Meierling and L.\ Volkmann.
\newblock Sufficient conditions for triangle-free graphs to be optimally
  restricted edge-connected.
\newblock {\em Discrete Appl.\ Math.}, 160:1775--1781, 2012.

\bibitem{JZ}
J.\ Ou and F.\ Zhang.
\newblock Super-restricted edge-connectivity of regular graphs.
\newblock {\em Graphs Combin.}, 21(4):459--467, 2005.

\bibitem{TM}
Y.\ Tian and J.\ Meng.
\newblock On super-restricted edge-connectivity of edge-transitive graphs.
\newblock {\em Discrete Math.}, 310:2273--2279, 2010.

\bibitem{TML}
Y.\ Tian, J.\ Meng, and X.\ Liang.
\newblock On super-restricted edge-connectivity of half vertex transitive
  graphs.
\newblock {\em Graphs Combin.}, 28:287--296, 2012.

\bibitem{Tin}
R.\ Tindell.
\newblock Edge-connectivity properties of symmetric graphs.
\newblock Preprint, Stevens Institute of Technology, Hoboken, NJ, 1982.

\bibitem{WLWL}
S. Wang, J. Li, L. Wu, and S. Lin.
\newblock Neighbourhood conditions for graphs to be super resricted edge
  connected.
\newblock {\em Networks}, 56(1):11--19, 2010.

\bibitem{Wan}
Y.Q.\ Wang.
\newblock Super-restricted edge-connectivity of vertex-transitive graphs.
\newblock {\em Discrete Math.}, 289:199--205, 2004.

\bibitem{YZQG}
W. Yang, Z. Zhang, C. Quin, and X. Guo.
\newblock On super $2$-restricted and $3$-restricted edge-connected vertex
  transitive graphs.
\newblock {\em Discrete Math.}, 311:2683--2689, 2011.

\bibitem{YLW}
J. Yuan, A.\ Liu, and S.\ Wang.
\newblock Sufficient condtitions for bipartite graphs to be
  super-$k$-restricted edge connected.
\newblock {\em Discrete Math.}, 309:2886--2896, 2009.

\bibitem{Zho}
J. X. Zhou.
\newblock Super-restricted edge-connectivity of regular edge-transitive graphs.
\newblock {\em Discrete Appl.\ Math.}, 160:1248--1252, 2012.
\newblock \doi{10.1016/j.dam.2011.12.004}.

 \end{thebibliography}
\end{document}

\end{thebibliography}

%\bibliographystyle{plain} 
%\bibliography{bib}

\end{document}


