% EJC papers *must* begin with the following two lines.
\documentclass[12pt]{article}
\usepackage{e-jc}
\specs{P2.50}{24(2)}{2017}

% Please remove all other commands that change parameters such as
% margins or pagesizes.

% only use standard LaTeX packages
% only include packages that you actually need

% we recommend these ams packages
\usepackage{amsmath,amssymb,amsthm}

% we recommend the graphicx package for importing figures
\usepackage{graphicx}
\usepackage{tikz}

% 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}}}

% all overfull boxes must be fixed;
% i.e. there must be no text protruding into the margins


% declare theorem-like environments
\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}

\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}


%\newcommand{\qed}{$\Box$}
\newcommand{\coro}{{\rm cor}}
\newcommand{\diam}{{\rm diam}}
\newcommand{\defic}{{\rm def}}
\newcommand{\pn}{{\rm pn}}
\newcommand{\odd}{{\rm odd}}
\newcommand{\even}{{\rm even}}


\newcommand{\gt}{\gamma_t}
\newcommand{\dbar}{{\overline{d}}}
\newcommand{\gbar}{{\overline{G}}}
\newcommand{\barG}{{\overline{G}}}
\newcommand{\Ebar}{{\overline{E}}}


\renewcommand{\labelenumi}{\rm(\alph{enumi})}
\let\oldenumerate\enumerate
\renewcommand{\enumerate}{
  \oldenumerate
  \setlength{\itemsep}{1.5pt}
  \setlength{\parskip}{0pt}
  \setlength{\parsep}{0pt}
}

%\newcommand{\smallqed}{{\tiny ($\Box$)}}

\newcommand{\TR}[1]{\mbox{$\tau(#1)$}}

\newcommand{\integers}{\mbox{\bf Z}}
\def\ZZ{Z\!\!\!Z}

%\newtheorem{definition}[fact]{Definition}
\newcommand{\pf}{\textbf{Proof:} }
\newcommand{\qe}{\mathop{\mathrm{qe}}}
\newcommand{\un}{\mathop{\mathrm{un}}}

\newcommand{\SC}{strongly connected}

\newcommand{\ClaimX}[1]{{\bf Claim #1:}}
\newcommand{\ProofClaimX}[1]{{\em Proof of Claim #1:}}
\newcommand{\ProofLemmaX}[1]{{\em Proof of Lemma~#1:}}
\newcommand{\CaseX}[1]{{\bf Case #1:}}
\newcommand{\ProofCaseX}[1]{{\em Proof of Case #1:}}
\newcommand{\SubCaseX}[1]{{\bf Subcase #1:}}
\newcommand{\ProofSubCaseX}[1]{{\em Proof of Subcase #1:}}

\newcommand{\cB}{{\cal B}}
\newcommand{\cC}{{\cal C}}
\newcommand{\cF}{{\cal F}}
\newcommand{\cT}{{\cal T}}
\newcommand{\cG}{{\cal G}}
\newcommand{\cH}{{\cal H}}
\newcommand{\cI}{{\cal I}}
\newcommand{\cK}{{\cal K}}
\newcommand{\cM}{{\cal M}}
\newcommand{\cR}{{\cal R}}
\newcommand{\cX}{{\cal X}}
\newcommand{\oc}{{\rm oc}}
\newcommand{\vc}{{\rm vc}}


\def \nH {n_{_H}}
\def \mH {m_{_H}}

\newenvironment{unnumbered}[1]{\trivlist \item [\hskip \labelsep {\bf
#1}]\ignorespaces\it}{\endtrivlist}



\def\vertex(#1){\put(#1){\circle*{2}}}
\def\vertexo(#1){\put(#1){\circle{2}}}
\def\vert(#1){\put(#1){\circle*{1.5}}}
\def\verto(#1){\put(#1){\circle{1.5}}}
\def\lab(#1)#2{\put(#1){\makebox(0,0)[c]{#2}}}
\setlength{\unitlength}{1mm}

\newcommand{\spec}[1]{\mbox{$#1$-special}}
%\newcommand{\proof}{\noindent\textbf{Proof. }}
\newcommand{\3}{ \vspace{0.3cm} }
\newcommand{\2}{ \vspace{0.2cm} }
\newcommand{\1}{ \vspace{0.1cm} }
\newcommand{\5}{ \vspace{0.05cm} }

\newcommand{\New}[1]{{\bf[#1]}}
%\newcommand{\ClaimX}[1]{\emph{Claim #1:}}
%\newcommand{\ClaimQED}{ \hfill {\tiny \mbox{($\Box$)}}}

%\newcommand{\PicTxt}[1]{{\scriptsize #1}}
\newcommand{\PicTxt}[1]{{\small #1}}
\newcommand{\PicTxtII}[1]{{\normalsize #1}}
\newcommand{\Vx}[1]{V(#1)}
%\newcommand{\Vx}[1]{#1}
\newcommand{\comment}[1]{{\bf TO MIKE: #1}}

\newcommand{\NEW}[1]{{\color{red} #1}}
\newcommand{\NEWX}[1]{{\color{blue} #1}}




\newcommand{\III}{1}
\newcommand{\IV}{2}
\newcommand{\IVx}{3}
\newcommand{\IVxx}{4}
\newcommand{\IVxxx}{5}
\newcommand{\V}{6}
\newcommand{\VI}{7}
\newcommand{\VII}{8}
\newcommand{\VIII}{9}
\newcommand{\IX}{10}
\newcommand{\X}{11}
\newcommand{\XI}{12}
\newcommand{\XII}{13}
\newcommand{\XIII}{14}
\newcommand{\XIV}{15}
\newcommand{\XV}{16}
\newcommand{\XVI}{17}
\newcommand{\XVII}{18}
\newcommand{\XVIII}{19}
\newcommand{\IXX}{20}
\newcommand{\XX}{21}




\newcommand{\hyperedgefive}[5]{
% { {x node 1}{y node 1}{radius node 1} }
% { {x node 2}{y node 2}{radius node 2} }
% { {x node 3}{y node 3}{radius node 3} }
% { {x node 4}{y node 4}{radius node 4} }
% { {x node 5}{y node 5}{radius node 5} } anti clockwise
	\hyperedgebig #1#2#3;
	\hyperedgebig #2#3#4;
	\hyperedgebig #3#4#5;
	\hyperedgebig #4#5#1;
	\hyperedgebig #5#1#2;
}

\newcommand{\hyperedgefour}[4]{
%{{x node 1}{y node 1}{radius node 1}}
%{{x node 2}{y node 2}{radius node 2}}
%{{x node 3}{y node 3}{radius node 3}}
%{{x node 4}{y node 4}{radius node 4}}anti clockwise
	\hyperedgebig #1#2#3;
	\hyperedgebig #2#3#4;
	\hyperedgebig #3#4#1;
	\hyperedgebig #4#1#2;
}

\newcommand{\hyperedgebig}[9]{%{x node 1}{y node 1}{radius node 1}{x node 2}{y node 2}{radius node 2}{x node 3}{y node 3}{radius node 3}anti clockwise
	\pgfmathsetmacro\Done{sqrt((#4-#1)^2+(#5-#2)^2)}
	\pgfmathsetmacro\angleone{(#2>#5)*(180+asin((#4-#1)/ \Done)-asin((#1-#4)/ \Done))+asin((#1-#4)/ \Done)+asin((#3-#6)/\Done)}
	\pgfmathsetmacro\angleone{\angleone-360*(\angleone>0)-360*(\angleone>360)}
	\pgfmathsetmacro\Dtwo{sqrt((#7-#4)^2+(#8-#5)^2)}
	\pgfmathsetmacro\angletwo{(#5>#8)*(180+asin((#7-#4)/ \Dtwo)-asin((#4-#7)/ \Dtwo))+asin((#4-#7)/ \Dtwo)+asin((#6-#9)/\Dtwo)}
	\pgfmathsetmacro\angletwo{\angletwo-360*(\angletwo>0)-360*(\angletwo>360)}
	\draw ([shift=(\angletwo:#6)] #4,#5)--([shift=(\angletwo:#9)]#7,#8);
	\draw (#4,#5)+(\angleone:#6) arc(\angleone:\angletwo+360*(\angletwo<\angleone):#6);
}

\newcommand{\hyperedgethree}[9]{%{x node 1}{y node 1}{radius node 1}{x node 2}{y node 2}{radius node 2}{x node 3}{y node 3}{radius node 3} anticlockwise!
	\pgfmathsetmacro\Done{sqrt((#4-#1)^2+(#5-#2)^2)}
	\pgfmathsetmacro\angleone{(#2>#5)*(180+asin((#4-#1)/ \Done)-asin((#1-#4)/ \Done))+asin((#1-#4)/ \Done)+asin((#3-#6)/\Done)}
	\pgfmathsetmacro\angleone{\angleone-360*(\angleone>0)-360*(\angleone>360)}
\draw ([shift=(\angleone:#3)] #1,#2)--([shift=(\angleone:#6)]#4,#5);
	\pgfmathsetmacro\Dtwo{sqrt((#7-#4)^2+(#8-#5)^2)}
	\pgfmathsetmacro\angletwo{(#5>#8)*(180+asin((#7-#4)/ \Dtwo)-asin((#4-#7)/ \Dtwo))+asin((#4-#7)/ \Dtwo)+asin((#6-#9)/\Dtwo)}
	\pgfmathsetmacro\angletwo{\angletwo-360*(\angletwo>0)-360*(\angletwo>360)}
	\draw ([shift=(\angletwo:#6)] #4,#5)--([shift=(\angletwo:#9)]#7,#8);
	\pgfmathsetmacro\Dthree{sqrt((#1-#7)^2+(#2-#8)^2)}
	\pgfmathsetmacro\anglethree{(#8>#2)*(180+asin((#1-#7)/ \Dthree)-asin((#7-#1)/ \Dthree))+asin((#7-#1)/ \Dthree)+asin((#9-#3)/\Dthree)}
	\pgfmathsetmacro\anglethree{\anglethree-360*(\anglethree>0)-360*(\anglethree>360)}
	\draw ([shift=(\anglethree:#9)] #7,#8)--([shift=(\anglethree:#3)]#1,#2);
	\draw (#1,#2)+(\anglethree:#3) arc(\anglethree:\angleone+360*(\angleone<\anglethree):#3);
	\draw (#4,#5)+(\angleone:#6) arc(\angleone:\angletwo+360*(\angletwo<\angleone):#6);
	\draw (#7,#8)+(\angletwo:#9) arc(\angletwo:\anglethree+360*(\anglethree<\angletwo):#9);
}

\newcommand{\hyperedgetwo}[6]{%{x node 1}{y node 1}{radius node 1}{x node 2}{y node 2}{radius node 2}
	\pgfmathsetmacro\Done{sqrt((#4-#1)^2+(#5-#2)^2)}
	\pgfmathsetmacro\angleone{(#2>#5)*(180+asin((#4-#1)/ \Done)-asin((#1-#4)/ \Done))+asin((#1-#4)/ \Done)+asin((#3-#6)/\Done)}
	\pgfmathsetmacro\angleone{\angleone-360*(\angleone>0)-360*(\angleone>360)}
	\draw ([shift=(\angleone:#3)] #1,#2)--([shift=(\angleone:#6)]#4,#5);
	\pgfmathsetmacro\Dtwo{sqrt((#1-#4)^2+(#2-#5)^2)}
	\pgfmathsetmacro\angletwo{(#5>#2)*(180+asin((#1-#4)/ \Dtwo)-asin((#4-#1)/ \Dtwo))+asin((#4-#1)/ \Dtwo)+asin((#6-#3)/\Dtwo)}
	\pgfmathsetmacro\angletwo{\angletwo-360*(\angletwo>0)-360*(\angletwo>360)}
	\draw ([shift=(\angletwo:#6)] #4,#5)--([shift=(\angletwo:#3)]#1,#2);
	\draw (#1,#2)+(\angletwo:#3) arc(\angletwo:\angleone+360*(\angleone<\angletwo):#3);
	\draw (#4,#5)+(\angleone:#6) arc(\angleone:\angletwo+360*(\angletwo<\angleone):#6);
}



%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

% if needed include a line break (\\) at an appropriate place in the title

\allowdisplaybreaks

\title{\bf Transversals and Independence in Linear Hypergraphs with Maximum Degree Two}




\author{Michael A. Henning${}^{1,}$\thanks{Research
supported in part by the South African
National Research Foundation and the University of Johannesburg} \qquad Anders Yeo${}^{1,2}$ \\
\small ${}^1$Department of Pure and Applied Mathematics\\[-0.8ex]
\small University of Johannesburg\\[-0.8ex]
\small Auckland Park, 2006 South Africa\\
\small\tt mahenning@uj.ac.za
\and
\small ${}^2$Department of Mathematics and Computer Science \\[-0.8ex]
\small University of Southern Denmark \\[-0.8ex]
\small Campusvej 55, 5230 Odense M, Denmark \\
\small\tt andersyeo@gmail.com
}



\date{\dateline{May 24, 2016}{Jun 22, 2017}{Jun 30, 2017}\\
\small Mathematics Subject Classifications: 05C65}



\begin{document}


\maketitle


\begin{abstract}
For $k \ge 2$, let $H$ be a $k$-uniform hypergraph on $n$ vertices and $m$ edges. Let $S$ be a set of vertices in a hypergraph $H$. The set $S$ is a transversal if $S$ intersects every edge of $H$, while the set $S$ is strongly independent if no two vertices in $S$ belong to a common edge. The transversal number, $\tau(H)$, of $H$ is the minimum cardinality of a transversal in $H$, and the strong independence number of $H$, $\alpha(H)$, is the maximum cardinality of a strongly independent set in $H$. The hypergraph $H$ is linear if every two distinct edges of $H$ intersect in at most one vertex. Let $\cH_k$ be the class of all connected, linear, $k$-uniform hypergraphs with maximum degree~$2$. It is known [European J. Combin. 36 (2014), 231--236] that if $H \in \cH_k$, then $(k+1)\tau(H) \le n+m$, and there are only two hypergraphs that achieve equality in the bound. In this paper, we prove a much more powerful result, and establish tight upper bounds on $\tau(H)$ and tight lower bounds on $\alpha(H)$ that are achieved for  infinite families of hypergraphs. More precisely, if $k \ge 3$ is odd and $H \in \cH_k$ has $n$ vertices and $m$ edges, then we prove that $k(k^2 - 3)\tau(H) \le (k-2)(k+1)n + (k - 1)^2m + k-1$ and $k(k^2 - 3)\alpha(H) \ge  (k^2 + k - 4)n  - (k-1)^2 m - (k-1)$. Similar bounds are proven in the case when $k \ge 2$ is even.







\bigskip\noindent \textbf{Keywords:} Transversal; Hypergraph; Linear hypergraph; Strong independence \\
\bigskip\noindent \textbf{AMS subject classification:} 05C65;05C69

\end{abstract}






\section{Introduction}

In this paper, we study transversals and independence in hypergraphs. Hypergraphs are systems of sets which are conceived as natural
extensions of graphs.  A \emph{hypergraph} $H = (V,E)$ is a finite
set $V = V(H)$ of elements, called \emph{vertices}, together with a
finite multiset $E = E(H)$ of subsets of $V$, called
\emph{hyperedges} or simply \emph{edges}. The \emph{order} of $H$ is
$n(H) = |V|$ and the \emph{size} of $H$ is $m(H) = |E|$. The hypergraph $H$
is said to be $k$-\emph{uniform} if every edge of $H$ is of size~$k$.
Every (simple) graph is a $2$-uniform hypergraph. Thus graphs are
special hypergraphs.  The \emph{degree} of a
vertex $v$ in $H$, denoted by $d_H(v)$, is the number of edges of $H$ which contain
$v$. A vertex of degree~$r$ in $H$ is called a \emph{degree}-$r$ \emph{vertex}.
The \emph{rank} of $H$ is the maximum size of an edge in $H$.
%
The hypergraph $H$ is $r$-regular if $d_H(v) = r$ for all $v \in V(H)$. The minimum and maximum degrees among the vertices of $H$ is denoted by $\delta(H)$ and $\Delta(H)$, respectively. We use the standard notation $[k] = \{1,2,\ldots,k\}$.


Two vertices $x$ and $y$ of $H$ are \emph{adjacent} if there is an
edge $e$ of $H$ such that $\{x,y\}\subseteq V(e)$. Two vertices $x$ and $y$ of $H$ are \emph{connected} if there is a
sequence $x=v_0,v_1,v_2\ldots,v_k=y$ of vertices of $H$ in which
$v_{i-1}$ is adjacent to $v_i$ for $i \in [k]$. A \emph{connected hypergraph} is a hypergraph in which every pair of vertices is connected. A maximal connected subhypergraph of $H$ is a
\emph{component} of $H$. Thus, no edge in $H$ contains vertices from different components.



For a subset $X \subseteq V(H)$ of vertices in $H$,  let $H[X]$ denote the hypergraph induced by the vertices in $X$, in the sense that $V(H[X])=X$ and $E(H[X]) = \{e \cap X \mid e \in E(H) \mbox{ and } |e \cap X| \ge 1\}$; that is,  $E(H[X])$ is obtained from $E(H)$ by shrinking edges $e \in E(H)$ that intersect $X$ to the edges $e \cap X$.
%
For a subset $X \subset V(H)$ of vertices in $H$, we define $H - X$ to be the hypergraph obtained from $H$ by deleting the vertices in $X$ and all edges incident with $X$, and deleting all isolated vertices, if any, from the resulting hypergraph.


A subset $T$ of vertices in a hypergraph $H$ is a \emph{transversal} (also called \emph{vertex cover} or \emph{hitting set} in many papers) if $T$ intersects every edge of $H$. Equivalently, a set of vertices $S$ is transversal in $H$ if and only if $V(H) \setminus S$ is a weakly independent set in $H$. That is, no edge lies completely within $V(H) \setminus S$. The \emph{transversal number} $\TR{H}$ of $H$ is the minimum size of a transversal in $H$. Transversals in hypergraphs are well studied in the literature (see,
for example,~\cite{ChMc92,CoHeSl79,HeLo14,HeYe08,LaCh90,ThYe07}).




A set $S$ of vertices in a hypergraph $H$ is \emph{strongly independent} if no two vertices in $S$ belong to a common edge. The \emph{strong independence number} of $H$, which we denote by $\alpha(H)$, is the maximum cardinality of a strongly independent set in $H$. The independence number is one of the most fundamental and well-studied graph and hypergraph parameters (see,
for example,~\cite{BeRa08,BGHR12,CaHa13,Fa84,Ha11,HaLo09,HaRa11,HeTh,HeLo16,HeLoRa12,HeLoSoYe14,Jo84,Jo90,JoTu09,KoMuVe14,LoPeRa11}).





A hypergraph $H$ is called an \emph{intersecting hypergraph} if every
two distinct edges of $H$ have a non-empty intersection, while $H$ is
called a \emph{linear hypergraph} if every two distinct edges of $H$
intersect in at most one vertex. Intersecting and linear hypergraphs are well
studied in the literature (see, for example,~\cite{ErKoRa61,HiMi67}).


Two edges in a graph $G$ are \emph{independent} if they are not adjacent in $G$. A set of pairwise independent edges of $G$ is called a \emph{matching} in $G$, while a matching of maximum cardinality is a \emph{maximum matching}. The number of edges in a maximum matching of $G$ is the \emph{matching number} of $G$ which we denote by $\alpha'(G)$. %
Matchings in graphs are extensively studied in the literature (see, for example, the classical book on matchings by Lov\'{a}sz and Plummer~\cite{LoPl86}, and the excellent
survey articles by Plummer~\cite{Pl03} and Pulleyblank~\cite{Pu95}).


Given a graph $G$,  we define a hypergraph $H_G$ as follows. Let the edges of $G$ become vertices in $H_G$ and the vertices of $G$ become hyperedges  in $H_G$, containing all edges that are incident with that vertex in the graph. Thus, $V(H_G) = E(G)$ and $E(H_G)$ contains a hyperedge for every vertex $v \in V(G)$ which consists of all elements of $V(H_G)$ that correspond with edges incident with $v$ in $G$. Therefore, $n(H_G) = m(G)$ and $m(H_G) = n(G)$. We call $H_G$ the \emph{dual hypergraph} of $G$.




\section{Known Matching Results}
\label{S:known}


We shall need the following results by the authors~\cite{HeYe16+} which establish a tight lower bound on the matching number of a graph in terms of its maximum degree, order, and size.

\begin{theorem}{\rm (\cite{HeYe16+})}
\label{thmKeven}
If $k \ge 2$ is an even integer and $G$ is a connected graph of order $n$, size $m$ and maximum degree $\Delta(G) \le k$, then
\[
\alpha'(G) \ge \frac{n}{k(k+1)} \, + \, \frac{m}{k+1} - \frac{1}{k(k+1)},
\]
unless the following holds.
\\[-24pt]
\begin{enumerate}
\item $G$ is $k$-regular and $n = k+1$, in which case $\alpha'(G) = \frac{n-1}{2} = \frac{n}{k(k+1)} \, + \, \frac{m}{k+1} - \frac{1}{k}$.
\item $G$ is $k$-regular and $n = k+3$, in which case $\alpha'(G) = \frac{n-1}{2} = \frac{n}{k(k+1)} \, + \, \frac{m}{k+1} - \frac{3}{k(k+1)}$.
\end{enumerate}
\end{theorem}





Let $k \ge 4$ be even and let $r \ge 1$ be arbitrary and let $\ell = r(k-1)+1$. Let $X_1,X_2,\ldots,X_\ell$ be a number of vertex disjoint graphs such that each $X_i$ where $i \in [\ell]$ is either a
single vertex or it is a $K_{k+1}$ where an arbitrary edge has been deleted.
Let $Y=\{y_1,y_2,\ldots,y_r\}$ and build the graph $G_{k,r}$ as follows. Let $G_{k,r}$ be obtained from the disjoint union of the graphs  $X_1,X_2,\ldots,X_\ell$ by adding to it the vertices in $Y$ and furthermore, for every $i \in [r]$, adding an edge from $y_i$ to a vertex in each graph $X_{(i-1)(k-1)+1}$, $X_{(i-1)(k-1)+2}$, $X_{(i-1)(k-1)+3}, \ldots, X_{(i-1)(k-1)+k}$ in such a way that no vertex degree becomes more than~$k$. Let $\cG_{k,r}$ be the family of all such graph $G_{k,r}$.
%
When $k=4$ and $r=2$, an example of a graph $G$ in the family $\cG_{k,r}$ is illustrated in Figure~\ref{graph1}, where $G$ has order~$n = 21$, size~$m = 35$ and matching number $\alpha'(G)=8$.



\begin{figure}[htb]
\begin{center}
\tikzstyle{vertexX}=[circle,draw, fill=black!90, minimum size=8pt, scale=0.5, inner sep=0.2pt]
\begin{tikzpicture}[scale=0.21]
 \node (a1) at (1.0,3.0) [vertexX] {};
\node (a2) at (2.0,6.0) [vertexX] {};
\node (a3) at (5.0,6.0) [vertexX] {};
\node (a4) at (6.0,3.0) [vertexX] {};
\node (a5) at (3.5,1.0) [vertexX] {};
\node (b1) at (9.0,4.0) [vertexX] {};
\node (c1) at (12.0,4.0) [vertexX] {};
\node (d1) at (15.0,3.0) [vertexX] {};
\node (d2) at (16.0,6.0) [vertexX] {};
\node (d3) at (19.0,6.0) [vertexX] {};
\node (d4) at (20.0,3.0) [vertexX] {};
\node (d5) at (17.5,1.0) [vertexX] {};
\node (e1) at (23.0,4.0) [vertexX] {};
\node (f1) at (26.0,3.0) [vertexX] {};
\node (f2) at (27.0,6.0) [vertexX] {};
\node (f3) at (30.0,6.0) [vertexX] {};
\node (f4) at (31.0,3.0) [vertexX] {};
\node (f5) at (28.5,1.0) [vertexX] {};
\node (g1) at (34.0,4.0) [vertexX] {};
\node (t1) at (10.5,12.0) [vertexX] {};
\node (t2) at (28.0,12.0) [vertexX] {};
\draw (a2) -- (a1) -- (a5) -- (a4) -- (a3) -- (a1) -- (a4) -- (a2) -- (a5) -- (a3);
\draw (d2) -- (d1) -- (d5) -- (d4) -- (d3) -- (d1) -- (d4) -- (d2) -- (d5) -- (d3);
\draw (f2) -- (f1) -- (f5) -- (f4) -- (f3) -- (f1) -- (f4) -- (f2) -- (f5) -- (f3);
\draw (a3) -- (t1) -- (b1);
 \draw (c1) -- (t1) -- (d2);
\draw (g1) -- (t2) -- (f3);
 \draw (e1) -- (t2) -- (d3);
 \end{tikzpicture}
\end{center}
\vskip -0.5 cm \caption{A graph $G$ in the family $\cG_{4,2}$}  \label{graph1}
\end{figure}

\begin{proposition}{\rm (\cite{HeYe16+})}
\label{p:Gkr}
For $k \ge 4$ an even integer and $r \ge 1$ arbitrary, if  $G \in \cG_{k,r}$ has order~$n$ and size~$m$, then \[
\alpha'(G) = \frac{n}{k(k+1)} \, + \, \frac{m}{k+1} - \frac{1}{k(k+1)}.
\]
\end{proposition}




\begin{theorem}{\rm (\cite{HeYe16+})}
\label{thmKodd}
If $k \ge 3$ is an odd integer and $G$ is a connected graph of order $n$, size $m$, and with maximum degree $\Delta(G) \le k$, then
\[
\alpha'(G) \ge \left( \frac{k-1}{k(k^2 - 3)} \right) n \, + \, \left( \frac{k^2 - k - 2}{k(k^2 - 3)} \right) m \, - \, \frac{k-1}{k(k^2 - 3)}.
\]
\end{theorem}

For $k \ge 3$ odd, let $H_{k+2}$ be the graph of (odd) order~$k+2$ whose complement $\overline{H_{k+2}}$ is isomorphic to $P_3 \cup  ( \frac{k-1}{2} )P_2$. We note that every vertex in $H_{k+2}$ has degree~$k$, except for exactly one vertex, which has degree~$k-1$. We call the vertex of degree~$k-1$ in $H_{k+2}$ the \emph{link vertex} of $H_{k+2}$.

For $k \ge 3$ odd and $r \ge 1$ arbitrary, let $T_{k,r}$ be a tree with maximum degree at most~$k$ and with partite sets $V_1$ and $V_2$, where $|V_2| = r$. Let $H_{k,r}$ be obtained from $T_{k,r}$ as follows: For every vertex $x$ in $V_2$ with $d_{T_{k,r}}(x) < k$, add $k-d_{T_{k,r}}(x)$ copies of the subgraph $H_{k+2}$ to $T_{k,r}$ and in each added copy of $H_{k+2}$, join the link vertex of $H_{k+2}$ to $x$. We note that every vertex in the resulting graph $H_{k,r}$ has degree~$k$, except possibly for vertices in the set $V_1$ whose degrees belong to the set $\{1,2,\ldots,k\}$. Let $\cF_{k,r}$ be the family of all such graphs $H_{k,r}$.
%


When $k=3$ and $r=4$, an example of a graph $G$ in the family $\cF_{k,r}$ is illustrated in Figure~\ref{H34}, where $G$ has order~$n = 29$, size~$m = 40$ and matching number $\alpha'(G)=12$.

\begin{figure}[htb]
\begin{center}
\tikzstyle{vertexX}=[circle,draw, fill=black!90, minimum size=8pt, scale=0.5, inner sep=0.2pt]
\begin{tikzpicture}[scale=0.21]
\node (a0) at (3,7.5) [vertexX] {};
\node (a1) at (1,3.0) [vertexX] {};
\node (a2) at (5,3.0) [vertexX] {};
\node (a3) at (3,5.0) [vertexX] {};
\node (a4) at (3,1.0) [vertexX] {};
\draw (a3) -- (a4) -- (a1) -- (a0) -- (a2) -- (a4);
\draw (a1) -- (a3) -- (a2);
\node (b0) at (9,7.5) [vertexX] {};
\node (b1) at (7,3.0) [vertexX] {};
\node (b2) at (11,3.0) [vertexX] {};
\node (b3) at (9,5.0) [vertexX] {};
\node (b4) at (9,1.0) [vertexX] {};
\draw (b3) -- (b4) -- (b1) -- (b0) -- (b2) -- (b4);
\draw (b1) -- (b3) -- (b2);
\node (c0) at (15,7.5) [vertexX] {};
\node (c1) at (13,3.0) [vertexX] {};
\node (c2) at (17,3.0) [vertexX] {};
\node (c3) at (15,5.0) [vertexX] {};
\node (c4) at (15,1.0) [vertexX] {};
\draw (c3) -- (c4) -- (c1) -- (c0) -- (c2) -- (c4);
\draw (c1) -- (c3) -- (c2);
\node (d0) at (27,7.5) [vertexX] {};
\node (d1) at (25,3.0) [vertexX] {};
\node (d2) at (29,3.0) [vertexX] {};
\node (d3) at (27,5.0) [vertexX] {};
\node (d4) at (27,1.0) [vertexX] {};
\draw (d3) -- (d4) -- (d1) -- (d0) -- (d2) -- (d4);
\draw (d1) -- (d3) -- (d2);
\node (x0) at (2.0,17) [vertexX] {};
\node (x1) at (8.5,17) [vertexX] {};
\node (x2) at (15.0,17) [vertexX] {};
\node (x3) at (21.5,17) [vertexX] {};
\node (x4) at (28.0,17) [vertexX] {};
\node (y0) at (3,12) [vertexX] {};
\node (y1) at (11,12) [vertexX] {};
\node (y2) at (19,12) [vertexX] {};
\node (y3) at (27,12) [vertexX] {};
\draw (y0) -- (a0);
\draw (y1) -- (b0);
\draw (y1) -- (c0);
\draw (y3) -- (d0);
\draw (x0) -- (y0) -- (x1) -- (y1);
\draw (x1) -- (y2) -- (x2);
\draw (y2) -- (x3) -- (y3) -- (x4);

 \draw (31.5,17) node {$V_1$};
 \draw (31,12) node {$V_2$};
 \draw [rounded corners] (0.5,16) rectangle (29.5,18);
 \draw [rounded corners] (1,11) rectangle (29,13);

\end{tikzpicture}
\end{center}
\vskip -0.5 cm \caption{A graph $G$ in the family $\cF_{3,4}$}  \label{H34}
\end{figure}


\begin{proposition}{\rm (\cite{HeYe16+})}
\label{p:Hkr}
For $k \ge 3$ an odd integer and $r \ge 1$ arbitrary, if  $G \in \cF_{k,r}$ has order~$n$ and size~$m$, then
\[
\alpha'(G) = \left( \frac{k-1}{k(k^2 - 3)} \right) n \, + \, \left( \frac{k^2 - k - 2}{k(k^2 - 3)} \right) m \, - \, \frac{k-1}{k(k^2 - 3)}.
\]
\end{proposition}





\section{Three Families of Hypergraphs}

In this section, we define three families of hypergraphs, $\cH_k$, $\cH_k'$ and $\cH_k''$. For a hypergraph $H$ with maximum degree at most~$2$ we let $V_1(H)$ and $V_2(H)$ denote the set of vertices in $H$ of degree~$1$ and~$2$, respectively. Further, we let $n_i(H) = |V_i(H)|$ for $i \in [2]$.

\subsection{The Family $\cH_k$}
\label{S:cHk}


\begin{definition}
Let $\cH_k$ be the class of all connected, linear, $k$-uniform hypergraphs with maximum degree~$2$.
\end{definition}



\vskip -0.15 cm
For a hypergraph $H \in \cH_k$ we define a graph $G_H$ as follows. Let the vertices of $G_H$ be the edges of $H$ and let the edges of $G_H$ correspond to the $n_2(H)$ vertices of degree~$2$ in $H$: if a vertex of $H$ is contained in the edges $e$ and $f$ of $H$, then the corresponding edge of the multigraph $G_H$ joins vertices $e$ and $f$ of $G_H$. Thus, $V(G_H) = E(H)$ and for every $v \in V_2(H)$, contained in the two edges $e$ and $f$, add an edge between $e$ and $f$ in $G_H$. By the linearity of $H$, the multigraph $G_H$ is indeed a graph, called the \emph{dual graph} of $H$. Since $H$ is $k$-uniform and $\Delta(H) = 2$, the maximum degree, $\Delta(G_H)$, in $G_H$ is at most~$k$. Since $H$ is connected, so too is $G_H$. By construction, $n(G_H) = m(H)$ and $m(G_H) = n_2(H)$.
%
We note that if $H \in \cH_k$ is $2$-regular, then the dual graph, $G_H$, of $H$ is $k$-regular.


\subsection{The Family $\cH_k'$}

In order to define the family $\cH_k'$, we first define a hypergraph, which we call $L_k$.

\medskip
\noindent
\textbf{The Hypergraph $L_k$.}
%
For $k \ge 2$, let $L_k$ be the $2$-regular, $k$-uniform hypergraph of size~$k+1$ and order $k(k+1)/2$ defined inductively as follows. We define $L_2 = K_3$ and we define $L_3$ to be the hypergraph with $V(L_3) = \{v_1,v_2,\ldots,v_6\}$ and let $E(L_3) = \{e_1,e_2,e_3,e_4\}$, where $e_1 = \{v_1,v_2,v_3\}$, $e_2 = \{v_1,v_4,v_5\}$, $e_3 = \{v_2,v_4,v_6\}$ and $e_4 = \{v_3,v_5,v_6\}$. For $k \ge 2$, suppose the hypergraph $L_k$ has been constructed and that $E(L_k) = \{e_1,e_2,\ldots,e_{k+1}\}$. Let $L_{k+2}$ be the hypergraph of order~$n(L_k) + 2k + 3$ with $V(L_{k+2}) = V(L_k) \cup \{v\} \cup \{u_1,u_2,\ldots,u_{k+1}\} \cup \{w_1,w_2,\ldots,w_{k+1}\}$ and with edge set $E(L_{k+2}) = \{f_1,f_2,\ldots,f_{k+3}\}$, where $f_i = e_i \cup \{u_i,w_i\}$ for $i \in [k+1]$ and where $f_{k+2} = \{v,u_1,\ldots,u_{k+1}\}$ and $f_{k+3} = \{v,w_1,\ldots,w_{k+1}\}$.
%
The hypergraphs $L_2$, $L_4$ and $L_6$ are illustrated in Figure~\ref{intersect}(a), \ref{intersect}(b), and \ref{intersect}(c), respectively.

\begin{figure}[htb]
\begin{center}
\tikzstyle{vertexX}=[circle,draw, fill=black!100, minimum size=8pt, scale=0.5, inner sep=0.1pt]
\begin{tikzpicture}[scale=0.25]
 \node (a1) at (1.0,4.0) [vertexX] {};
\node (a2) at (1.0,1.0) [vertexX] {};
\node (a3) at (4.0,1.0) [vertexX] {};
\node (a4) at (2.5,-2.0) {(a) $L_2$};
%------- EDGE 0------
\draw[color=black!90, thick,rounded corners=4pt] (1.9999433500235204,4.010644094312785) arc (0.6098731973394038:176.4869591045931:1.0); % Arc around vertex 1
\draw[color=black!90, thick,rounded corners=4pt] (0.0018791224802877649,0.9387242800182674) arc (183.5130408954069:359.3901268026606:1.0); % Arc around vertex 2
\draw[color=black!90, thick,rounded corners=4pt] (1.9999433500235204,4.010644094312785) -- (1.9999433500235204,0.989355905687214);
\draw[color=black!90, thick,rounded corners=4pt] (0.0018791224802877649,0.9387242800182674) -- (0.0,2.5) -- (0.0018791224802878759,4.061275719981733);
% ----------------
%------- EDGE 1------
\draw[color=black!90, thick,rounded corners=4pt] (0.992814465624922,4.899971315151625) arc (90.45745018578945:275.52564338823333:0.9); % Arc around vertex 0
\draw[color=black!90, thick,rounded corners=4pt] (4.899971315151625,4.007185534375078) arc (0.4574501857894546:89.54254981421053:0.9); % Arc around vertex 1
\draw[color=black!90, thick,rounded corners=4pt] (3.1041821183800913,1.0866621195795443) arc (174.47435661176667:359.54254981421053:0.9); % Arc around vertex 2
\draw[color=black!90, thick,rounded corners=4pt] (0.992814465624922,4.899971315151625) -- (4.007185534375078,4.899971315151625);
\draw[color=black!90, thick,rounded corners=4pt] (4.899971315151625,4.007185534375078) -- (4.899971315151625,0.9928144656249211);
\draw[color=black!90, thick,rounded corners=4pt] (3.1041821183800913,1.0866621195795443) -- (3.363603896932107,3.363603896932107) -- (1.086662119579544,3.1041821183800913);
% ----------------
%------- EDGE 2------
\draw[color=black!90, thick,rounded corners=4pt] (4.004601528639943,0.2000132339006001) arc (-89.6704379697801:87.9060302070261:0.8); % Arc around vertex 1
\draw[color=black!90, thick,rounded corners=4pt] (0.9707691742230907,1.7994657959064915) arc (92.09396979297392:269.6704379697801:0.8); % Arc around vertex 2
\draw[color=black!90, thick,rounded corners=4pt] (4.004601528639943,0.2000132339006001) -- (0.9953984713600572,0.2000132339006001);
\draw[color=black!90, thick,rounded corners=4pt] (0.9707691742230907,1.7994657959064915) -- (2.5,1.8) -- (4.029230825776909,1.7994657959064915);
% ----------------
 \end{tikzpicture}
 %\hfill
 \hspace*{2cm}
\tikzstyle{vertexX}=[circle,draw, fill=black!100, minimum size=8pt, scale=0.5, inner sep=0.1pt]
\begin{tikzpicture}[scale=0.25]
 \node (a1) at (1.0,10.0) [vertexX] {};
\node (a2) at (1.0,7.0) [vertexX] {};
\node (a3) at (1.0,4.0) [vertexX] {};
\node (a4) at (1.0,1.0) [vertexX] {};
\node (a5) at (4.0,7.0) [vertexX] {};
\node (a6) at (4.0,4.0) [vertexX] {};
\node (a7) at (4.0,1.0) [vertexX] {};
\node (a8) at (7.0,4.0) [vertexX] {};
\node (a9) at (7.0,1.0) [vertexX] {};
\node (a10) at (10.0,1.0) [vertexX] {};
\node (a11) at (4.5,-2.0) {(b) $L_4$};
%------- EDGE 0------
\draw[color=black!90, thick,rounded corners=4pt] (1.9999404314142877,4.010914834996838) arc (0.6253863972442666:11.376967106857592:1.0); % Arc around vertex 0
\draw[color=black!90, thick,rounded corners=4pt] (0.007769901048958916,1.1244163604017057) arc (172.85294740996648:359.3903323424423:1.0); % Arc around vertex 1
\draw[color=black!90, thick,rounded corners=4pt] (1.9999984825500685,9.99825790426205) arc (-0.09981478378023212:180.02328137121071:1.0); % Arc around vertex 2
\draw[color=black!90, thick,rounded corners=4pt] (1.9999404314142877,4.010914834996838) -- (1.9999433882011346,0.9893594928299944);
\draw[color=black!90, thick,rounded corners=4pt] (0.007769901048958916,1.1244163604017057) -- (0.0,9.999593663429177);
\draw[color=black!90, thick,rounded corners=4pt] (1.9999984825500685,9.99825790426205) -- (1.9803505536273511,4.197263255581333);
% ----------------
%------- EDGE 1------
\draw[color=black!90, thick,rounded corners=4pt] (0.9921968514540919,10.919966907487856) arc (90.48597047746559:275.5712207156533:0.92); % Arc around vertex 0
\draw[color=black!90, thick,rounded corners=4pt] (4.919999943253066,10.000323132102855) arc (0.020124028368887714:89.51402952253443:0.92); % Arc around vertex 1
\draw[color=black!90, thick,rounded corners=4pt] (3.0804763018984502,1.0296001457707613) arc (178.15624329998536:359.97987597163115:0.92); % Arc around vertex 2
\draw[color=black!90, thick,rounded corners=4pt] (0.9921968514540919,10.919966907487856) -- (4.007803148545908,10.919966907487856);
\draw[color=black!90, thick,rounded corners=4pt] (4.919999943253066,10.000323132102855) -- (4.919999943253066,0.9996768678971465);
\draw[color=black!90, thick,rounded corners=4pt] (3.0804763018984502,1.0296001457707613) -- (3.35191187357377,9.34702084230403) -- (1.0893163521310583,9.084345813507085);
% ----------------
%------- EDGE 2------
\draw[color=black!90, thick,rounded corners=4pt] (0.9992511434117376,7.83999966619863) arc (90.05107896148978:272.54430286561285:0.84); % Arc around vertex 0
\draw[color=black!90, thick,rounded corners=4pt] (7.83999966619863,7.000748856588262) arc (0.0510789614897762:89.9489210385102:0.84); % Arc around vertex 1
\draw[color=black!90, thick,rounded corners=4pt] (6.160828076141371,1.0372891701088522) arc (177.45569713438715:359.9489210385102:0.84); % Arc around vertex 2
\draw[color=black!90, thick,rounded corners=4pt] (0.9992511434117376,7.83999966619863) -- (7.000748856588263,7.83999966619863);
\draw[color=black!90, thick,rounded corners=4pt] (7.83999966619863,7.000748856588262) -- (7.83999966619863,0.9992511434117369);
\draw[color=black!90, thick,rounded corners=4pt] (6.160828076141371,1.0372891701088522) -- (6.4060303038033,6.4060303038033) -- (1.0372891701088518,6.160828076141371);
% ----------------
%------- EDGE 3------
\draw[color=black!90, thick,rounded corners=4pt] (0.9998488636842061,4.759999984972246) arc (90.01139404353056:271.5027608704118:0.76); % Arc around vertex 0
\draw[color=black!90, thick,rounded corners=4pt] (10.759990584449437,4.003783060692465) arc (0.28520303478334164:89.98860595646948:0.76); % Arc around vertex 1
\draw[color=black!90, thick,rounded corners=4pt] (9.24252962708978,1.061956712011301) arc (175.32394489703594:359.71479696521664:0.76); % Arc around vertex 2
\draw[color=black!90, thick,rounded corners=4pt] (0.9998488636842061,4.759999984972246) -- (10.000151136315793,4.759999984972246);
\draw[color=black!90, thick,rounded corners=4pt] (10.759990584449437,4.003783060692465) -- (10.759990584449437,0.9962169393075345);
\draw[color=black!90, thick,rounded corners=4pt] (9.24252962708978,1.061956712011301) -- (9.461451338116294,3.463748809993609) -- (1.0199310897135436,3.2402613925415986);
% ----------------
%------- EDGE 4------
\draw[color=black!90, thick,rounded corners=4pt] (10.00009704136856,0.32000000692428476) arc (-89.99182343988883:89.97264907846073:0.68); % Arc around vertex 1
\draw[color=black!90, thick,rounded corners=4pt] (0.997529417175017,1.679995511912031) arc (90.20816805916866:269.99182343988883:0.68); % Arc around vertex 2
\draw[color=black!90, thick,rounded corners=4pt] (10.00009704136856,0.32000000692428476) -- (0.9999029586314389,0.32000000692428476);
\draw[color=black!90, thick,rounded corners=4pt] (0.997529417175017,1.679995511912031) -- (4.001070993069664,1.6799991565978922) -- (10.000324607259005,1.679999922522148);
% ----------------
 \end{tikzpicture}
 %\hfill
 \hspace*{2cm}
\tikzstyle{vertexX}=[circle,draw, fill=black!100, minimum size=8pt, scale=0.5, inner sep=0.1pt]
\begin{tikzpicture}[scale=0.25]
 \node (a1) at (1.0,16.0) [vertexX] {};
\node (a2) at (1.0,13.0) [vertexX] {};
\node (a3) at (1.0,10.0) [vertexX] {};
\node (a4) at (1.0,7.0) [vertexX] {};
\node (a5) at (1.0,4.0) [vertexX] {};
\node (a6) at (1.0,1.0) [vertexX] {};
\node (a7) at (4.0,13.0) [vertexX] {};
\node (a8) at (4.0,10.0) [vertexX] {};
\node (a9) at (4.0,7.0) [vertexX] {};
\node (a10) at (4.0,4.0) [vertexX] {};
\node (a11) at (4.0,1.0) [vertexX] {};
\node (a12) at (7.0,10.0) [vertexX] {};
\node (a13) at (7.0,7.0) [vertexX] {};
\node (a14) at (7.0,4.0) [vertexX] {};
\node (a15) at (7.0,1.0) [vertexX] {};
\node (a16) at (10.0,7.0) [vertexX] {};
\node (a17) at (10.0,4.0) [vertexX] {};
\node (a18) at (10.0,1.0) [vertexX] {};
\node (a19) at (13.0,4.0) [vertexX] {};
\node (a20) at (13.0,1.0) [vertexX] {};
\node (a21) at (16.0,1.0) [vertexX] {};
\node (a22) at (7.5,-2.0) {(c) $L_6$};
%------- EDGE 0------
\draw[color=black!90, thick,rounded corners=4pt] (-0.09999999062676213,0.9998563994313584) arc (180.0074797332202:359.98554873389094:1.1); % Arc around vertex 1
\draw[color=black!90, thick,rounded corners=4pt] (2.099894574058543,16.015229115423313) arc (0.7932653786981447:179.99252065999448:1.1); % Arc around vertex 2
\draw[color=black!90, thick,rounded corners=4pt] (-0.09999999062676213,0.9998563994313584) -- (-0.09999999062774756,16.000143593019462);
\draw[color=black!90, thick,rounded corners=4pt] (2.099894574058543,16.015229115423313) -- (2.099973175188146,12.992317951672371) -- (2.099999965011186,0.9997225556107884);
% ----------------
%------- EDGE 1------
\draw[color=black!90, thick,rounded corners=4pt] (0.9881289814302683,17.029931589435975) arc (90.66036341868451:276.0927890800722:1.03); % Arc around vertex 0
\draw[color=black!90, thick,rounded corners=4pt] (5.029999994074748,16.000110480856918) arc (0.006145715369447746:89.33963658131552:1.03); % Arc around vertex 1
\draw[color=black!90, thick,rounded corners=4pt] (2.9702338531102006,1.0219472713505904) arc (178.7790473823493:359.9938542846306:1.03); % Arc around vertex 2
\draw[color=black!90, thick,rounded corners=4pt] (0.9881289814302683,17.029931589435975) -- (4.011871018569732,17.029931589435975);
\draw[color=black!90, thick,rounded corners=4pt] (5.029999994074748,16.000110480856918) -- (5.029999994074748,0.9998895191430828);
\draw[color=black!90, thick,rounded corners=4pt] (2.9702338531102006,1.0219472713505904) -- (3.27563501887429,15.2677463730928) -- (1.1093230966580256,14.975818150650433);
% ----------------
%------- EDGE 2------
\draw[color=black!90, thick,rounded corners=4pt] (0.9987325604876904,13.95999916333145) arc (90.07564474577082:272.9252626237068:0.96); % Arc around vertex 0
\draw[color=black!90, thick,rounded corners=4pt] (7.959999986250258,13.000162479244937) arc (0.009697265664371457:89.92435525422917:0.96); % Arc around vertex 1
\draw[color=black!90, thick,rounded corners=4pt] (6.040292490305415,1.0236959033551747) arc (178.58561129673907:359.9903027343356:0.96); % Arc around vertex 2
\draw[color=black!90, thick,rounded corners=4pt] (0.9987325604876904,13.95999916333145) -- (7.00126743951231,13.95999916333145);
\draw[color=black!90, thick,rounded corners=4pt] (7.959999986250258,13.000162479244937) -- (7.959999986250258,0.9998375207550625);
\draw[color=black!90, thick,rounded corners=4pt] (6.040292490305415,1.0236959033551747) -- (6.32151612792989,12.32083902104085) -- (1.0489919549921478,12.041250925243707);
% ----------------
%------- EDGE 3------
\draw[color=black!90, thick,rounded corners=4pt] (0.9997167498863231,10.889999954926614) arc (90.01823487228567:271.76384343879636:0.89); % Arc around vertex 0
\draw[color=black!90, thick,rounded corners=4pt] (10.889999954926614,10.000283250113677) arc (0.01823487228567444:89.98176512771431:0.89); % Arc around vertex 1
\draw[color=black!90, thick,rounded corners=4pt] (9.11042169700351,1.0273942117587707) arc (178.23615656120364:359.9817651277143:0.89); % Arc around vertex 2
\draw[color=black!90, thick,rounded corners=4pt] (0.9997167498863231,10.889999954926614) -- (10.000283250113677,10.889999954926614);
\draw[color=black!90, thick,rounded corners=4pt] (10.889999954926614,10.000283250113677) -- (10.889999954926614,0.9997167498863229);
\draw[color=black!90, thick,rounded corners=4pt] (9.11042169700351,1.0273942117587707) -- (9.370674964743973,9.370674964743973) -- (1.02739421175877,9.11042169700351);
% ----------------
%------- EDGE 4------
\draw[color=black!90, thick,rounded corners=4pt] (0.9999133139014178,7.819999995418) arc (90.00605700926887:271.1995742341041:0.82); % Arc around vertex 0
\draw[color=black!90, thick,rounded corners=4pt] (13.819999717326453,7.000680870425277) arc (0.04757439786133322:89.99394299073106:0.82); % Arc around vertex 1
\draw[color=black!90, thick,rounded corners=4pt] (12.180767029993872,1.0354590024526573) arc (177.52160378794775:359.95242560213865:0.82); % Arc around vertex 2
\draw[color=black!90, thick,rounded corners=4pt] (0.9999133139014178,7.819999995418) -- (13.000086686098584,7.819999995418);
\draw[color=black!90, thick,rounded corners=4pt] (13.819999717326453,7.000680870425277) -- (13.819999717326453,0.999319129574723);
\draw[color=black!90, thick,rounded corners=4pt] (12.180767029993872,1.0354590024526573) -- (12.41999110089589,6.420353834688749) -- (1.0171666922065539,6.1801797119620145);
% ----------------
%------- EDGE 5------
\draw[color=black!90, thick,rounded corners=4pt] (0.999968851494472,4.7499999993531805) arc (90.00237957054055:270.87197684650056:0.75); % Arc around vertex 0
\draw[color=black!90, thick,rounded corners=4pt] (16.74999137943768,4.003595937869617) arc (0.27471047027624174:89.99762042945946:0.75); % Arc around vertex 1
\draw[color=black!90, thick,rounded corners=4pt] (15.252432172122976,1.0603518245227674) arc (175.38446991750504:359.7252895297238:0.75); % Arc around vertex 2
\draw[color=black!90, thick,rounded corners=4pt] (0.999968851494472,4.7499999993531805) -- (16.000031148505528,4.7499999993531805);
\draw[color=black!90, thick,rounded corners=4pt] (16.74999137943768,4.003595937869617) -- (16.74999137943768,0.9964040621303832);
\draw[color=black!90, thick,rounded corners=4pt] (15.252432172122976,1.0603518245227674) -- (15.468546786708977,3.470795425111757) -- (1.0114137096218823,3.25008685354058);
% ----------------
%------- EDGE 6------
\draw[color=black!90, thick,rounded corners=4pt] (16.000021061175943,0.3200000003261566) arc (-89.99822541692174:89.99654338536715:0.68); % Arc around vertex 1
\draw[color=black!90, thick,rounded corners=4pt] (0.9975298247557323,1.6799955133927449) arc (90.20813371680264:269.9982254299629:0.68); % Arc around vertex 2
\draw[color=black!90, thick,rounded corners=4pt] (16.000021061175943,0.3200000003261566) -- (0.9999789389788338,0.32000000032615195);
\draw[color=black!90, thick,rounded corners=4pt] (0.9975298247557323,1.6799955133927449) -- (4.001219428243573,1.6799989066129142) -- (16.00004102392827,1.6799999987625274);
% ----------------
 \end{tikzpicture}
\end{center}
\vskip -0.75 cm \caption{The hypergraphs $L_2$, $L_4$ and $L_6$.} \label{intersect}
\end{figure}

We shall need the following result from~\cite{DoHe14}.

\begin{theorem}{\rm (\cite{DoHe14})}
 \label{t:intersect}
For $k \ge 2$, the hypergraph $L_k$ is the unique $k$-uniform, $2$-regular, linear, intersecting hypergraph.
\end{theorem}

\begin{definition}
Let $\cH_k' = \cH_k \setminus \{L_k\}$.
\end{definition}


\subsection{The Family $\cH_k''$}


For a hypergraph $H \in \cH_k$, let $\alpha_2(H)$ be the maximum cardinality of a strongly independent set in $H$ consisting only of degree-$2$ vertices in $H$. Every strongly independent set in $H$ corresponds to a matching in the dual graph $G_H$ of $H$. Conversely, every matching $M$ in the dual graph $G_H$ of $H$ corresponds to a strongly independent set $V_M \subseteq V_2(H)$ in $H$. This immediately implies the following observation.



\begin{observation}
\label{ob1}
If $H \in \cH_k$ and $G_H$ is the dual graph of $H$, then $\alpha'(G_H) = \alpha_2(H)$.
\end{observation}


The following result is well-known (see, for example,~\cite{DoHe14}). However, since it is central to our discussions, we give a short proof for completeness.

\begin{proposition}
\label{p:dual}
If $H \in \cH_k$ and $G_H$ is the dual graph of $H$, then $\alpha'(G_H) = |E(H)| - \tau(H)$.
\end{proposition}
\begin{proof} Let $H \in \cH_k$ and let $G_H$ be the dual graph of $H$. If $M$ is a maximum matching, then the corresponding set $V_M \subseteq V_2(H)$ is a maximum strong independent set in $V_2(H)$ by Observation~\ref{ob1}. Therefore, $V_M$ covers $2|V_M|$ distinct edges in $H$. Using an additional $|E(H)| - 2|V_M|$ vertices in $H$, one from each of the edges not covered by $V_H$, we can extend the set  $V_M$ to a transversal in $H$. Therefore, $\tau(H) \le |V_M| + (|E(H)|-2|V_M|) = |E(H)| - \alpha'(G_H)$, or, equivalently, $\alpha'(G_H) \le |E(H)| - \tau(H)$.
%


Conversely, let $T$ be a minimum transversal in $H$, and so, $\tau(H) = |T|$. If a vertex $x \in T$ covers only one hyperedge in $H$ that is not covered by $T \setminus \{x\}$, then delete this vertex from $T$ and the edge it covers from $H$. We continue this process removing $r$ vertices from $T$, resulting in a set $T'$, and $r$ associated edges from $H$, resulting in a hypergraph $H'$, until every vertex in $T'$  covers two distinct edges in $H'$ that are not covered by any other vertex of $T'$. Therefore, $T'$ corresponds to a matching in $G_H$, and $|E(H)| = |E(H')| + r = 2|T'| + r = 2|T'| + (|T| - |T'|) = |T'|+|T|$. Thus, $\alpha'(G_H) \ge |T'| = |E(H)| - |T| = |E(H)| - \tau(H)$. As observed earlier, $\alpha'(G_H) \le |E(H)| - \tau(H)$. Consequently, $\alpha'(G_H) = |E(H)| - \tau(H)$. \end{proof}


\medskip
\noindent
\textbf{The Family $\cM_k$.}
%
Let $\cM_k$ be the class of all connected, linear, $k$-uniform, $2$-regular hypergraphs $H$ with $k+3$ edges. We note that $\cM_k$ is a subclass of $\cH_k$. The dual graph, $G_H$, of a hypergraph $H \in \cM_k$ is a $k$-regular graph of order~$k+3$. We note that the complement $\overline{G_H}$ of $G_H$ is a $2$-regular graph on $k+3$ vertices. Thus, $G_H$ can be constructed from $K_{k+3}$ by removing the edges of a cycle factor of $K_{k+3}$. Using this approach, we observe that the number of non-isomporphic hypergraphs
in $\cM_k$ is equal to the number of non-isomorphic cycle factors in $K_{k+3}$. For example, $|\cM_4| = 2$ (the cycle factors in $K_7$ are either a Hamilton cycle or the union of a $3$-cycle and a $4$-cycle) and $|\cM_6| = 4$ (consider cycle factors with cycle lengths $(9)$, $(6,3)$, $(5,4)$ and $(3,3,3)$). We state this formally as follows.

\begin{observation}
\label{o:Mk}
The following holds.
\\[-24pt]
\begin{enumerate}
\item If $H \in \cM_k$, then the dual graph of $H$ is a $k$-regular graph of order~$k+3$.
\item If $G$ is a $k$-regular graph of order~$k+3$, then the dual hypergraph of $G$ belongs to $\cM_k$ and has order~$k(k+3)/2$.
\end{enumerate}
\end{observation}


\begin{definition}
Let $\cH_k'' = \cH_k' \setminus \cM_k  = \cH_k \setminus (\cM_k \cup \{L_k\})$.
\end{definition}






\section{Main Results}

In what follows, we adopt the following notation. If $H \in \cH_k$, we let $H$ have order~$n$ and size~$m$, and so $n = n(H)$ and $m = m(H)$. Further, we let $n_i = n_i(H)$ for $i \in [2]$, and so $n_1$ and $n_2$ denote the number of vertices of degree~$1$ and~$2$, respectively, in $H$. We note that $km = n_1 + 2n_2$. We denote the number of components of a hypergraph $H$ by $c(H)$.

\subsection{Transversal Number}

Our first result establishes an upper bound on the transversal number of a connected, linear, $k$-uniform hypergraph with maximum degree~$2$ for $k \ge 2$ even.

\begin{theorem}
\label{alpha1}
For all even $k \ge 2$ the following holds.
\\ [-22pt]
\begin{enumerate}
\item If $H \in \cH_k$, then $\tau(H) \le \frac{k n + (k-1) m + k+1}{k(k+1)}$.
\item If $H \in \cH_k'$, then $\tau(H) \le \frac{k n + (k-1) m + 3}{k(k+1)}$.
\item If $H \in \cH_k''$, then $\tau(H) \le \frac{k n + (k-1) m + 1}{k(k+1)}$.
\end{enumerate}
\end{theorem}
\begin{proof}
Let $k \ge 2$ be even and let $H \in \cH_k$. Let $G_H$ be the dual graph of $H$. If $H = L_k$, then, by Theorem~\ref{t:intersect}, we note that $m = k+1$ and $G_H$ is a $k$-regular graph of order~$k+1$.
%and size $m(G_H) = n_2 = k(k+1)/2$.
If $H \in \cM_k$, then $m = k+3$ and, by Observation~\ref{o:Mk}, the graph $G_H$ is a $k$-regular graph of order~$k+3$.
%and size $m(G_H) = k(k+3)/2$.
If $H \in \cH_k''$, then $G_H$ has maximum degree $\Delta(G) \le k$. Further, if $G_H$ is $k$-regular (and still $H \in \cH_k''$), then $n(G_H) \notin \{k+1,k+3\}$. In all cases, we note that $G_H$ is a connected graph of order $n(G_H) = m$ and size~$m(G_H) = n_2$. Let
{\small
\[
\theta = \left\{
\begin{array}{cl}
1 & \mbox{if $H \in \cH_k''$} \1 \\
3 & \mbox{if $H \in \cM_k$} \1 \\
k+1 & \mbox{if $H = L_k$.} \\
\end{array}
\right.
\]
}

By Theorem~\ref{thmKeven} and our definition of $\theta$, the following holds.

{\small
\[
\alpha'(G_H) \ge
\frac{m}{k(k+1)} \, + \, \frac{n_2}{k+1} - \frac{\theta}{k(k+1)}.
\]
}

By Proposition~\ref{p:dual}, we note that the following therefore holds.
%Recall that $m = m(H)$ and $km = n_1 + 2n_2$.

{\small
\[
\begin{array}{rcl} \vspace{0.2cm}
\tau(H) & = & m - \alpha'(G_H) \\ \vspace{0.2cm}
& \le &  \displaystyle{ m - \left( \frac{m}{k(k+1)} + \frac{n_2}{k+1} - \frac{\theta}{k(k+1)} \right) } \\ \vspace{0.3cm}
& = & \displaystyle{ \left( 1 - \frac{1}{k(k+1)} \right) \left(\frac{n_1 + 2n_2}{k}\right)  - \frac{n_2}{k+1} + \frac{\theta}{k(k+1)} } \\ \vspace{0.2cm}
& = & \displaystyle{ \left(\frac{k(k+1)-1}{k^2(k+1)} \right) n_1  + \left( \frac{2(k(k+1)-1) - k^2}{k^2(k+1)} \right) n_2  + \frac{\theta}{k(k+1)}.} \\
\end{array}
\]
}

Simplifying and multiplying through with $k^2(k+1)$ we obtain the following.

{\small
\[
\begin{array}{rcl} \vspace{0.2cm}
k^2(k+1) \tau(H) & \le & (k^2+k-1) n_1  + (k^2 +2k -2) n_2  + k\theta \\ \vspace{0.2cm}
& = & k^2 (n_1 + n_2) + (k-1)(n_1+2n_2) + k\theta \\
& = & k^2 n + (k-1) (km) + k\theta. \\
\end{array}
\]
}
This implies the desired result.
\end{proof}


\medskip
We discuss next the hypergraphs $H \in \cH_k$ for $k \ge 4$ even that achieve the upper bound for the transversal number in the statement of Theorem~\ref{alpha1}.
%
If $H = L_k$, then $m(H) = k+1$ and $n(H) = k(k+1)/2$, and the dual graph of $H$ is the graph $K_{k+1}$. Therefore, by Proposition~\ref{p:dual},
{\small
\[
\tau(H) = m(H) - \alpha'(K_{k+1}) = (k+1) - \frac{k}{2} = \frac{k+2}{2} = \frac{k n + (k-1) m + k+1}{k(k+1)},
\]
}
and equality holds in the statement of Theorem~\ref{alpha1}(a).
%
If $H \in \cM_k$, then $m(H) = k+3$ and $n(H) = k(k+3)/2$. By Observation~\ref{o:Mk}, the dual graph, $G_H$, of $H$ is a $k$-regular graph of order~$k+3$. Therefore, by Proposition~\ref{p:dual},
{\small
\[
\tau(H) = m(H) - \alpha'(G_H) = (k+3) - \frac{k+2}{2} = \frac{k+4}{2} = \frac{k n + (k-1) m + 3}{k(k+1)},
\]
}
and equality holds in the statement of Theorem~\ref{alpha1}(b).
%
We show next that there is an infinite family of hypergraphs $H \in \cH_k''$ that satisfy
{\small
\[
\tau(H) = \frac{k n + (k-1) m + 1}{k(k+1)}.
\]
}


For $k \ge 4$ an even integer and $r \ge 1$, let $G$ be an arbitrary graph in the family~$\cG_{k,r}$.
%, and let $G$ have order~$n$ and size~$m$.
%
We show that associated with the graph $G$, there exists a hypergraph $H \in \cH_k'' $ for which equality holds in the statement of Theorem~\ref{alpha1}(c), constructed as follows. Let $H_G$ be the dual hypergraph of $G$, and so the edges of $G$ become vertices in $H_G$ and the vertices of $G$ become hyperedges in $H_G$, containing all edges that are incident with that vertex in the graph. We note that $n(H_G) = m(G)$ and $m(H_G) = n(G)$.


Since $\Delta(G) = k$, we note that the rank of $H_G$ is $k$. We note further that the edges of size~$1$ in $H_G$, if any, correspond to the pendant edges in $G$ (that are incident with a vertex of degree~$1$). The edges of size~$2$ in $H_G$, if any, correspond to vertices of degree~$2$ in $G$ (that have both neighbors in $Y$). All other edges in $H_G$ have size~$k-1$ or~$k$.

We now expand all edges of $H_G$ of size less than~$k$ to edges of size~$k$ by adding new vertices of degree~$1$ to each such edge. For example, if $e_v$ is an edge of size~$1$ in $H_G$ containing the vertex $v$, then we add $k-1$ new vertices and expand the edge $e_v$ to an edge of size~$k$ that contains these new vertices and the vertex $v$. Let $H_G^k$ denote the resulting hypergraph, and let $\cH_{k,r}^{\even}$ be the family of all such hypergraphs $H_G^k$.  For example, given the graph $G \in \cG_{4,2}$ shown in Figure~\ref{graph1} we obtain the associated hypergraph $H \in \cH_{4,2}^{\even}$ shown in Figure~\ref{hyp1}.





\begin{figure}[htb]
\begin{center}
\tikzstyle{vertexX}=[circle,draw, fill=black!90, minimum size=8pt, scale=0.5, inner sep=0.2pt]
\begin{tikzpicture}[scale=0.21]
 \node (a1) at (1.0,10.0) [vertexX] {};
\node (a2) at (1.0,7.0) [vertexX] {};
\node (a3) at (1.0,4.0) [vertexX] {};
\node (a4) at (1.0,1.0) [vertexX] {};
\node (a5) at (4.0,7.0) [vertexX] {};
\node (a6) at (4.0,4.0) [vertexX] {};
\node (a7) at (4.0,1.0) [vertexX] {};
\node (a8) at (7.0,4.0) [vertexX] {};
\node (a9) at (7.0,1.0) [vertexX] {};
\node (a10) at (10.0,1.0) [vertexX] {};
\node (a11) at (4.0,10.0) [vertexX] {};
\node (a1) at (14.0,10.0) [vertexX] {};
\node (a2) at (14.0,7.0) [vertexX] {};
\node (a3) at (14.0,4.0) [vertexX] {};
\node (a4) at (14.0,1.0) [vertexX] {};
\node (a1) at (18.0,10.0) [vertexX] {};
\node (a2) at (18.0,7.0) [vertexX] {};
\node (a3) at (18.0,4.0) [vertexX] {};
\node (a4) at (18.0,1.0) [vertexX] {};
\node (a1) at (22.0,10.0) [vertexX] {};
\node (a2) at (22.0,7.0) [vertexX] {};
\node (a3) at (22.0,4.0) [vertexX] {};
\node (a4) at (22.0,1.0) [vertexX] {};
\node (a5) at (25.0,7.0) [vertexX] {};
\node (a6) at (25.0,4.0) [vertexX] {};
\node (a7) at (25.0,1.0) [vertexX] {};
\node (a8) at (28.0,4.0) [vertexX] {};
\node (a9) at (28.0,1.0) [vertexX] {};
\node (a10) at (31.0,1.0) [vertexX] {};
\node (a11) at (25.0,12.0) [vertexX] {};
\node (a1) at (35.0,12.0) [vertexX] {};
\node (a2) at (35.0,7.0) [vertexX] {};
\node (a3) at (35.0,4.0) [vertexX] {};
\node (a4) at (35.0,1.0) [vertexX] {};
\node (a1) at (39.0,10.0) [vertexX] {};
\node (a2) at (39.0,7.0) [vertexX] {};
\node (a3) at (39.0,4.0) [vertexX] {};
\node (a4) at (39.0,1.0) [vertexX] {};
\node (a5) at (42.0,7.0) [vertexX] {};
\node (a6) at (42.0,4.0) [vertexX] {};
\node (a7) at (42.0,1.0) [vertexX] {};
\node (a8) at (45.0,4.0) [vertexX] {};
\node (a9) at (45.0,1.0) [vertexX] {};
\node (a10) at (48.0,1.0) [vertexX] {};
\node (a11) at (42.0,12.0) [vertexX] {};
\node (a1) at (52.0,12.0) [vertexX] {};
\node (a2) at (52.0,7.0) [vertexX] {};
\node (a3) at (52.0,4.0) [vertexX] {};
\node (a4) at (52.0,1.0) [vertexX] {};
%------- EDGE 0------
\draw[color=black!90, thick,rounded corners=4pt] (1.9999404314142877,4.010914834996838) arc (0.6253863972442666:11.376967106857592:1.0); % Arc around vertex 0
\draw[color=black!90, thick,rounded corners=4pt] (0.007769901048958916,1.1244163604017057) arc (172.85294740996648:359.3903323424423:1.0); % Arc around vertex 1
\draw[color=black!90, thick,rounded corners=4pt] (1.9999984825500685,9.99825790426205) arc (-0.09981478378023212:180.02328137121071:1.0); % Arc around vertex 2
\draw[color=black!90, thick,rounded corners=4pt] (1.9999404314142877,4.010914834996838) -- (1.9999433882011346,0.9893594928299944);
\draw[color=black!90, thick,rounded corners=4pt] (0.007769901048958916,1.1244163604017057) -- (0.0,9.999593663429177);
\draw[color=black!90, thick,rounded corners=4pt] (1.9999984825500685,9.99825790426205) -- (1.9803505536273511,4.197263255581333);
% ----------------
%------- EDGE 1------
\draw[color=black!90, thick,rounded corners=4pt] (4.999940431414288,4.010914834996838) arc (0.625386397244263:11.376967106857592:1.0); % Arc around vertex 0
\draw[color=black!90, thick,rounded corners=4pt] (3.0077699010489587,1.1244163604017057) arc (172.85294740996648:359.3903323424423:1.0); % Arc around vertex 1
\draw[color=black!90, thick,rounded corners=4pt] (4.999998482550069,9.99825790426205) arc (-0.09981478378023212:180.02328137121071:1.0); % Arc around vertex 2
\draw[color=black!90, thick,rounded corners=4pt] (4.999940431414288,4.010914834996838) -- (4.999943388201134,0.9893594928299944);
\draw[color=black!90, thick,rounded corners=4pt] (3.0077699010489587,1.1244163604017057) -- (3.000000082554708,9.999593663429177);
\draw[color=black!90, thick,rounded corners=4pt] (4.999998482550069,9.99825790426205) -- (4.980350553627351,4.197263255581333);
% ----------------
%------- EDGE 2------
\draw[color=black!90, thick,rounded corners=4pt] (0.9992511434117376,7.83999966619863) arc (90.05107896148978:272.54430286561285:0.84); % Arc around vertex 0
\draw[color=black!90, thick,rounded corners=4pt] (7.83999966619863,7.000748856588262) arc (0.0510789614897762:89.9489210385102:0.84); % Arc around vertex 1
\draw[color=black!90, thick,rounded corners=4pt] (6.160828076141371,1.0372891701088522) arc (177.45569713438715:359.9489210385102:0.84); % Arc around vertex 2
\draw[color=black!90, thick,rounded corners=4pt] (0.9992511434117376,7.83999966619863) -- (7.000748856588263,7.83999966619863);
\draw[color=black!90, thick,rounded corners=4pt] (7.83999966619863,7.000748856588262) -- (7.83999966619863,0.9992511434117369);
\draw[color=black!90, thick,rounded corners=4pt] (6.160828076141371,1.0372891701088522) -- (6.4060303038033,6.4060303038033) -- (1.0372891701088518,6.160828076141371);
% ----------------
%------- EDGE 3------
\draw[color=black!90, thick,rounded corners=4pt] (0.9998488636842061,4.759999984972246) arc (90.01139404353056:271.5027608704118:0.76); % Arc around vertex 0
\draw[color=black!90, thick,rounded corners=4pt] (10.759990584449437,4.003783060692465) arc (0.28520303478334164:89.98860595646948:0.76); % Arc around vertex 1
\draw[color=black!90, thick,rounded corners=4pt] (9.24252962708978,1.061956712011301) arc (175.32394489703594:359.71479696521664:0.76); % Arc around vertex 2
\draw[color=black!90, thick,rounded corners=4pt] (0.9998488636842061,4.759999984972246) -- (10.000151136315793,4.759999984972246);
\draw[color=black!90, thick,rounded corners=4pt] (10.759990584449437,4.003783060692465) -- (10.759990584449437,0.9962169393075345);
\draw[color=black!90, thick,rounded corners=4pt] (9.24252962708978,1.061956712011301) -- (9.461451338116294,3.463748809993609) -- (1.0199310897135436,3.2402613925415986);
% ----------------
%------- EDGE 4------
\draw[color=black!90, thick,rounded corners=4pt] (10.00009704136856,0.32000000692428476) arc (-89.99182343988883:89.97264907846073:0.68); % Arc around vertex 1
\draw[color=black!90, thick,rounded corners=4pt] (0.997529417175017,1.679995511912031) arc (90.20816805916866:269.99182343988883:0.68); % Arc around vertex 2
\draw[color=black!90, thick,rounded corners=4pt] (10.00009704136856,0.32000000692428476) -- (0.9999029586314389,0.32000000692428476);
\draw[color=black!90, thick,rounded corners=4pt] (0.997529417175017,1.679995511912031) -- (4.001070993069664,1.6799991565978922) -- (10.000324607259005,1.679999922522148);
% ----------------
%------- EDGE 5------
\draw[color=black!90, thick,rounded corners=4pt] (15.119874929612019,4.016737443845316) arc (0.8562683842671959:13.02523564058481:1.12); % Arc around vertex 0
\draw[color=black!90, thick,rounded corners=4pt] (12.891234288144895,1.15823588788402) arc (171.87796067783682:359.17586240395644:1.12); % Arc around vertex 1
\draw[color=black!90, thick,rounded corners=4pt] (15.119996038777831,9.997021221396668) arc (-0.15238539579075905:180.0347638583396:1.12); % Arc around vertex 2
\draw[color=black!90, thick,rounded corners=4pt] (15.119874929612019,4.016737443845316) -- (15.119884139679014,0.9838905712268662);
\draw[color=black!90, thick,rounded corners=4pt] (12.891234288144895,1.15823588788402) -- (12.880000206157288,9.999320446998325);
\draw[color=black!90, thick,rounded corners=4pt] (15.119996038777831,9.997021221396668) -- (15.091183398712474,4.252425811624516);
% ----------------
%------- EDGE 6------
\draw[color=black!90, thick,rounded corners=4pt] (19.11987492961202,4.016737443845315) arc (0.8562683842671817:13.02523564058481:1.12); % Arc around vertex 0
\draw[color=black!90, thick,rounded corners=4pt] (16.891234288144897,1.15823588788402) arc (171.87796067783682:359.17586240395644:1.12); % Arc around vertex 1
\draw[color=black!90, thick,rounded corners=4pt] (19.11999603877783,9.997021221396668) arc (-0.15238539579075905:180.0347638583396:1.12); % Arc around vertex 2
\draw[color=black!90, thick,rounded corners=4pt] (19.11987492961202,4.016737443845315) -- (19.119884139679012,0.9838905712268662);
\draw[color=black!90, thick,rounded corners=4pt] (16.891234288144897,1.15823588788402) -- (16.880000206157288,9.999320446998325);
\draw[color=black!90, thick,rounded corners=4pt] (19.11999603877783,9.997021221396668) -- (19.091183398712474,4.252425811624516);
% ----------------
%------- EDGE 7------
\draw[color=black!90, thick,rounded corners=4pt] (22.999940431414288,4.010914834996839) arc (0.6253863972442915:11.376967106857592:1.0); % Arc around vertex 0
\draw[color=black!90, thick,rounded corners=4pt] (21.00776990104896,1.1244163604017057) arc (172.85294740996648:359.3903323424423:1.0); % Arc around vertex 1
\draw[color=black!90, thick,rounded corners=4pt] (22.99999848255007,9.99825790426205) arc (-0.09981478378023212:180.02328137121071:1.0); % Arc around vertex 2
\draw[color=black!90, thick,rounded corners=4pt] (22.999940431414288,4.010914834996839) -- (22.999943388201135,0.9893594928299944);
\draw[color=black!90, thick,rounded corners=4pt] (21.00776990104896,1.1244163604017057) -- (21.000000082554706,9.999593663429177);
\draw[color=black!90, thick,rounded corners=4pt] (22.99999848255007,9.99825790426205) -- (22.98035055362735,4.197263255581333);
% ----------------
%------- EDGE 8------
\draw[color=black!90, thick,rounded corners=4pt] (25.999943350025227,4.010644094152619) arc (0.6098731881620303:8.155702612127584:1.0); % Arc around vertex 0
\draw[color=black!90, thick,rounded corners=4pt] (24.004981162245436,1.099687072951082) arc (174.27884896244777:359.3901268025394:1.0); % Arc around vertex 1
\draw[color=black!90, thick,rounded corners=4pt] (25.99999981145267,11.999385919695156) arc (-0.035184211960995526:180.01159485839582:1.0); % Arc around vertex 2
\draw[color=black!90, thick,rounded corners=4pt] (25.999943350025227,4.010644094152619) -- (25.999943350023496,0.9893559056850985);
\draw[color=black!90, thick,rounded corners=4pt] (24.004981162245436,1.099687072951082) -- (24.000000020476495,11.999797631546071);
\draw[color=black!90, thick,rounded corners=4pt] (25.99999981145267,11.999385919695156) -- (25.98988620654226,4.141863660242426);
% ----------------
%------- EDGE 9------
\draw[color=black!90, thick,rounded corners=4pt] (21.999251143411737,7.83999966619863) arc (90.05107896148978:272.54430286561285:0.84); % Arc around vertex 0
\draw[color=black!90, thick,rounded corners=4pt] (28.83999966619863,7.000748856588262) arc (0.05107896148975932:89.9489210385102:0.84); % Arc around vertex 1
\draw[color=black!90, thick,rounded corners=4pt] (27.16082807614137,1.0372891701088522) arc (177.45569713438715:359.9489210385102:0.84); % Arc around vertex 2
\draw[color=black!90, thick,rounded corners=4pt] (21.999251143411737,7.83999966619863) -- (28.000748856588263,7.83999966619863);
\draw[color=black!90, thick,rounded corners=4pt] (28.83999966619863,7.000748856588262) -- (28.83999966619863,0.9992511434117369);
\draw[color=black!90, thick,rounded corners=4pt] (27.16082807614137,1.0372891701088522) -- (27.4060303038033,6.4060303038033) -- (22.037289170108853,6.160828076141371);
% ----------------
%------- EDGE 10------
\draw[color=black!90, thick,rounded corners=4pt] (21.999848863684207,4.759999984972246) arc (90.01139404353056:271.5027608704118:0.76); % Arc around vertex 0
\draw[color=black!90, thick,rounded corners=4pt] (31.759990584449437,4.003783060692465) arc (0.28520303478334164:89.98860595646948:0.76); % Arc around vertex 1
\draw[color=black!90, thick,rounded corners=4pt] (30.24252962708978,1.061956712011301) arc (175.32394489703594:359.71479696521664:0.76); % Arc around vertex 2
\draw[color=black!90, thick,rounded corners=4pt] (21.999848863684207,4.759999984972246) -- (31.000151136315793,4.759999984972246);
\draw[color=black!90, thick,rounded corners=4pt] (31.759990584449437,4.003783060692465) -- (31.759990584449437,0.9962169393075345);
\draw[color=black!90, thick,rounded corners=4pt] (30.24252962708978,1.061956712011301) -- (30.461451338116294,3.463748809993609) -- (22.019931089713545,3.2402613925415986);
% ----------------
%------- EDGE 11------
\draw[color=black!90, thick,rounded corners=4pt] (31.000097041368562,0.32000000692428476) arc (-89.99182343988883:89.97264907846073:0.68); % Arc around vertex 1
\draw[color=black!90, thick,rounded corners=4pt] (21.997529417175016,1.679995511912031) arc (90.20816805916866:269.99182343988883:0.68); % Arc around vertex 2
\draw[color=black!90, thick,rounded corners=4pt] (31.000097041368562,0.32000000692428476) -- (21.999902958631438,0.32000000692428476);
\draw[color=black!90, thick,rounded corners=4pt] (21.997529417175016,1.679995511912031) -- (25.001070993069664,1.6799991565978922) -- (31.000324607259007,1.679999922522148);
% ----------------
%------- EDGE 12------
\draw[color=black!90, thick,rounded corners=4pt] (36.119883964739145,4.01612158553403) arc (0.8247595631932612:9.283539167327575:1.12); % Arc around vertex 0
\draw[color=black!90, thick,rounded corners=4pt] (33.8871618063824,1.12645613795275) arc (173.5170659714414:359.1752403746548:1.12); % Arc around vertex 1
\draw[color=black!90, thick,rounded corners=4pt] (36.11999952442327,11.998967870333997) arc (-0.05280060905579376:180.01714812901855:1.12); % Arc around vertex 2
\draw[color=black!90, thick,rounded corners=4pt] (36.119883964739145,4.01612158553403) -- (36.11988396472166,0.9838784132511685);
\draw[color=black!90, thick,rounded corners=4pt] (33.8871618063824,1.12645613795275) -- (33.88000005016216,11.999664793735642);
\draw[color=black!90, thick,rounded corners=4pt] (36.11999952442327,11.998967870333997) -- (36.105330356218595,4.180678730407541);
% ----------------
%------- EDGE 13------
\draw[color=black!90, thick,rounded corners=4pt] (39.99994043141429,4.0109148349968375) arc (0.6253863972442204:11.376967106857592:1.0); % Arc around vertex 0
\draw[color=black!90, thick,rounded corners=4pt] (38.00776990104896,1.1244163604017057) arc (172.85294740996648:359.3903323424423:1.0); % Arc around vertex 1
\draw[color=black!90, thick,rounded corners=4pt] (39.99999848255007,9.99825790426205) arc (-0.09981478378017528:180.02328137121071:1.0); % Arc around vertex 2
\draw[color=black!90, thick,rounded corners=4pt] (39.99994043141429,4.0109148349968375) -- (39.99994338820113,0.9893594928299944);
\draw[color=black!90, thick,rounded corners=4pt] (38.00776990104896,1.1244163604017057) -- (38.000000082554706,9.999593663429177);
\draw[color=black!90, thick,rounded corners=4pt] (39.99999848255007,9.99825790426205) -- (39.98035055362735,4.197263255581333);
% ----------------
%------- EDGE 14------
\draw[color=black!90, thick,rounded corners=4pt] (42.99994335002523,4.010644094152618) arc (0.6098731881619734:8.155702612127584:1.0); % Arc around vertex 0
\draw[color=black!90, thick,rounded corners=4pt] (41.004981162245436,1.099687072951082) arc (174.27884896244774:359.3901268025394:1.0); % Arc around vertex 1
\draw[color=black!90, thick,rounded corners=4pt] (42.999999811452675,11.999385919695156) arc (-0.035184211960995526:180.01159485839582:1.0); % Arc around vertex 2
\draw[color=black!90, thick,rounded corners=4pt] (42.99994335002523,4.010644094152618) -- (42.9999433500235,0.9893559056850985);
\draw[color=black!90, thick,rounded corners=4pt] (41.004981162245436,1.099687072951082) -- (41.0000000204765,11.999797631546071);
\draw[color=black!90, thick,rounded corners=4pt] (42.999999811452675,11.999385919695156) -- (42.98988620654226,4.141863660242426);
% ----------------
%------- EDGE 15------
\draw[color=black!90, thick,rounded corners=4pt] (38.99925114341174,7.83999966619863) arc (90.05107896148976:272.54430286561285:0.84); % Arc around vertex 0
\draw[color=black!90, thick,rounded corners=4pt] (45.83999966619863,7.000748856588262) arc (0.05107896148975932:89.9489210385102:0.84); % Arc around vertex 1
\draw[color=black!90, thick,rounded corners=4pt] (44.16082807614137,1.0372891701088522) arc (177.45569713438715:359.9489210385102:0.84); % Arc around vertex 2
\draw[color=black!90, thick,rounded corners=4pt] (38.99925114341174,7.83999966619863) -- (45.00074885658826,7.83999966619863);
\draw[color=black!90, thick,rounded corners=4pt] (45.83999966619863,7.000748856588262) -- (45.83999966619863,0.9992511434117369);
\draw[color=black!90, thick,rounded corners=4pt] (44.16082807614137,1.0372891701088522) -- (44.4060303038033,6.4060303038033) -- (39.03728917010885,6.160828076141371);
% ----------------
%------- EDGE 16------
\draw[color=black!90, thick,rounded corners=4pt] (38.99984886368421,4.759999984972246) arc (90.01139404353056:271.5027608704118:0.76); % Arc around vertex 0
\draw[color=black!90, thick,rounded corners=4pt] (48.75999058444944,4.003783060692466) arc (0.2852030347834038:89.98860595646948:0.76); % Arc around vertex 1
\draw[color=black!90, thick,rounded corners=4pt] (47.24252962708978,1.0619567120113016) arc (175.3239448970359:359.7147969652166:0.76); % Arc around vertex 2
\draw[color=black!90, thick,rounded corners=4pt] (38.99984886368421,4.759999984972246) -- (48.00015113631579,4.759999984972246);
\draw[color=black!90, thick,rounded corners=4pt] (48.75999058444944,4.003783060692466) -- (48.75999058444944,0.9962169393075339);
\draw[color=black!90, thick,rounded corners=4pt] (47.24252962708978,1.0619567120113016) -- (47.4614513381163,3.463748809993609) -- (39.019931089713545,3.2402613925415986);
% ----------------
%------- EDGE 17------
\draw[color=black!90, thick,rounded corners=4pt] (48.00009704136856,0.32000000692428476) arc (-89.99182343988883:89.97264907846073:0.68); % Arc around vertex 1
\draw[color=black!90, thick,rounded corners=4pt] (38.997529417175016,1.679995511912031) arc (90.20816805916866:269.99182343988883:0.68); % Arc around vertex 2
\draw[color=black!90, thick,rounded corners=4pt] (48.00009704136856,0.32000000692428476) -- (38.99990295863144,0.32000000692428476);
\draw[color=black!90, thick,rounded corners=4pt] (38.997529417175016,1.679995511912031) -- (42.00107099306967,1.6799991565978922) -- (48.000324607259,1.679999922522148);
% ----------------
%------- EDGE 18------
\draw[color=black!90, thick,rounded corners=4pt] (53.119883964739145,4.01612158553403) arc (0.8247595631932612:9.283539167327575:1.12); % Arc around vertex 0
\draw[color=black!90, thick,rounded corners=4pt] (50.8871618063824,1.12645613795275) arc (173.5170659714414:359.1752403746548:1.12); % Arc around vertex 1
\draw[color=black!90, thick,rounded corners=4pt] (53.11999952442327,11.998967870333997) arc (-0.05280060905579376:180.01714812901855:1.12); % Arc around vertex 2
\draw[color=black!90, thick,rounded corners=4pt] (53.119883964739145,4.01612158553403) -- (53.11988396472166,0.9838784132511685);
\draw[color=black!90, thick,rounded corners=4pt] (50.8871618063824,1.12645613795275) -- (50.88000005016216,11.999664793735642);
\draw[color=black!90, thick,rounded corners=4pt] (53.11999952442327,11.998967870333997) -- (53.105330356218595,4.180678730407541);
% ----------------
%------- EDGE 19------
\draw[color=black!90, thick,rounded corners=4pt] (22.000007396710977,9.400000000045592) arc (-89.99929366613128:89.9373955445227:0.6); % Arc around vertex 1
\draw[color=black!90, thick,rounded corners=4pt] (3.9999842966500543,10.599999999794504) arc (90.00149955946034:269.9992936661313:0.6); % Arc around vertex 2
\draw[color=black!90, thick,rounded corners=4pt] (22.000007396710977,9.400000000045592) -- (3.9999926032890234,9.400000000045592);
\draw[color=black!90, thick,rounded corners=4pt] (3.9999842966500543,10.599999999794504) -- (17.999680158193474,10.59999991475101) -- (22.000655592194246,10.599999641832289);
% ----------------
%------- EDGE 20------
\draw[color=black!90, thick,rounded corners=4pt] (25.013634479710568,12.599845064131582) arc (88.69789101295719:269.99916168981747:0.6); % Arc around vertex 0
\draw[color=black!90, thick,rounded corners=4pt] (51.999970006879366,11.400000000749657) arc (-90.0028641320456:90.00011918040178:0.6); % Arc around vertex 1
\draw[color=black!90, thick,rounded corners=4pt] (25.013634479710568,12.599845064131582) -- (51.99999875194575,12.599999999998701);
\draw[color=black!90, thick,rounded corners=4pt] (51.999970006879366,11.400000000749657) -- (41.99998288987862,11.400000000243963) -- (24.999991221236296,11.400000000064223);
% ----------------
 \end{tikzpicture}
\end{center}
\vskip -0.15 cm \caption{The hypergraph $H \in \cH_{4,2}^{\even}$ associated with the graph $G \in \cG_{4,2}$ shown in Figure~\ref{graph1}.}  \label{hyp1}
% ($|V(H)|=49$, $|E(G)|=21$ and $\tau(H)=13$).
\end{figure}

\begin{proposition}
\label{p:Hkreven}
For $k \ge 4$ an even integer and $r \ge 1$ arbitrary, if  $H \in \cH_{k,r}^{\even}$ has order~$n$ and size~$m$, then
\[
\tau(H) = \frac{k n + (k-1) m + 1}{k(k+1)}.
\]
\end{proposition}
\begin{proof} We consider the graph $G \in \cG_{k,r}$ used to construct the hypergraph $H \in \cH_{k,r}^{\even}$, and so $H = H_G^k$. Assume that when building the graph $G$, we have $\ell_1$ single vertices and $\ell_2$ copies of $K_{k+1}$'s minus an edge in $X_1,X_2,\ldots,X_\ell$. We note that $\ell_1 + \ell_2 = \ell = r(k-1)+1$ and $n(G) = r + \ell_1 + \ell_2(k+1)$. Further,
{\small
\[
\alpha'(G) = r + \left( \frac{k}{2} \right) \ell_2 = \frac{\ell_1 + \ell_2 - 1}{k-1} + \left( \frac{k}{2} \right) \ell_2 = \frac{2\ell_1 + (k^2 - k + 2)\ell_2 - 2}{2(k-1)}.
\]
}
The order of $H_G^k$ is
{\small
\[
n(H_G^k) = k\ell_ 1 + \left( \frac{k^2 + k + 2}{2} \right) \ell_2.
\]
}

Further, $m(H_G^k) = m(H_G) = n(G) = r + \ell_1 + \ell_2(k+1)$, implying that the size of $H_G^k$ is
{\small
\[
m(H_G^k) = \left( \frac{k}{k-1} \right) \ell_1 + \left( \frac{k^2}{k-1} \right) \ell_2 - \frac{1}{k-1}.
\]
}

We remark that the graph $G \in \cG_{k,r}$ used to construct the hypergraph $H_G^k \in \cH_{k,r}^{\even}$ is in fact the dual graph (see Section~\ref{S:cHk}) of $H_G^k$. Therefore, letting $H = H_G^k$, $n = n(H_G^k)$ and $m = m(H_G^k)$, and applying Proposition~\ref{p:dual} to $H$ and its dual graph $G$, we have

{\small
\[
\begin{array}{rcl} \vspace{0.2cm}
\tau(H) & = &  m - \alpha'(G) \\   \vspace{0.2cm}
& = &  \displaystyle{ \left( \left( \frac{k}{k-1} \right) \ell_1 + \left( \frac{k^2}{k-1} \right) \ell_2 - \frac{1}{k-1} \right)  } \\   \vspace{0.2cm}
&  &  \displaystyle{
\hspace*{0.5cm} -  \left(
\left( \frac{1}{k-1} \right) \ell_1 +
\left( \frac{k^2 - k + 2}{2(k-1)} \right) \ell_2 - \frac{1}{k-1} \right) } \\
\vspace{0.2cm}
& = &  \displaystyle{ \ell_1 + \left( \frac{k^2 + k - 2}{2(k-1)} \right) \ell_2  } \\
\vspace{0.2cm}
& = &  \displaystyle{ \ell_1 + \left( \frac{k + 2}{2} \right) \ell_2  }
\end{array}
\]
}
and
{\small
\[
\begin{array}{rcl} \vspace{0.2cm}
\displaystyle{  \frac{k n + (k-1) m + 1}{k(k+1)} }
& = &
\displaystyle{
\left( \frac{k}{k(k+1)} \right)
\left(
k\ell_ 1 + \left( \frac{k^2 + k + 2}{2} \right) \ell_2
\right) } \\   \vspace{0.2cm}
&  &  \displaystyle{
\hspace*{0.5cm}
+
\left( \frac{k-1}{k(k+1)} \right)
\left(
\left( \frac{k}{k-1} \right) \ell_1 +
\left( \frac{k^2}{k-1} \right) \ell_2 - \frac{1}{k-1}
\right) } \\   \vspace{0.2cm}
&  &  \displaystyle{
\hspace*{1cm}
+ \, \,
\frac{1}{k(k+1)}  } \\
\vspace{0.2cm}
& = &  \displaystyle{ \ell_1 + \left( \frac{k + 2}{2} \right) \ell_2.  } \\
\end{array}
\]
}
Equality therefore holds in the statement of Theorem~\ref{alpha1}(c).
\end{proof}

\medskip
Next we consider the case when $k \ge 3$ is odd.


\begin{theorem}
\label{alpha1odd}
For $k \ge 3$ an odd integer, if $H \in \cH_k$, then
\[
\tau(H) \le \frac{(k-2)(k+1)n + (k - 1)^2m + k-1}{k(k^2 - 3)}.
\]
\end{theorem}
\begin{proof}
Let $k \ge 3$ be odd and let $H \in \cH_k$. Let $G_H$ be the dual graph of $H$ and note that $G_H$ has maximum degree $\Delta(G) \le k$.  Further, we note that $G_H$ is a connected graph of order $n(G_H) = m$ and size~$m(G_H) = n_2$. By Theorem~\ref{thmKodd}, the following holds.
{\small
\[
\alpha'(G_H) \ge
\left( \frac{k-1}{k(k^2 - 3)} \right) m \, + \, \left( \frac{k^2 - k - 2}{k(k^2 - 3)} \right) n_2 \, - \, \frac{k-1}{k(k^2 - 3)}.
\]
}

By Proposition~\ref{p:dual}, we note that the following therefore holds.

{\small
\[
\begin{array}{rcl} \vspace{0.2cm}
\tau(H) & = & m - \alpha'(G_H) \\ \vspace{0.2cm}
& \le &  \displaystyle{ m - \left( \left( \frac{k-1}{k(k^2 - 3)} \right) m \, + \, \left( \frac{k^2 - k - 2}{k(k^2 - 3)} \right) n_2 \, - \, \frac{k-1}{k(k^2 - 3)} \right) } \\ \vspace{0.3cm}
& = & \displaystyle{ \left( 1 - \frac{k-1}{k(k^2 - 3)} \right) \left(\frac{n_1 + 2n_2}{k}\right)  - \left( \frac{k^2 - k - 2}{k(k^2 - 3)} \right) n_2 + \, \frac{k-1}{k(k^2 - 3)} } \\ \vspace{0.2cm}
& = & \displaystyle{
\left( \frac{k^3 - 4k + 1}{k^2(k^2 - 3)} \right) n_1  +
\left( \frac{2(k^3 - 4k + 1) - k(k^2 - k - 2)}{k^2(k^2 - 3)} \right) n_2 + \, \frac{k-1}{k(k^2 - 3)}. } \\
\end{array}
\]
}

Simplifying and multiplying through with $k^2(k^2 - 3)$ we obtain the following.

{\small
\[
\begin{array}{rcl} \vspace{0.2cm}
k^2(k^2 - 3) \tau(H) & \le & (k^3 - 4k + 1) n_1  + (k^3 + k^2 - 6k + 2) n_2  + k(k-1) \\ \vspace{0.2cm}
& = & (k^3 - 2k)(n_1 + n_2) - (2k-1)(n_1+2n_2) + k^2 \cdot n_2 + k(k-1) \\
\vspace{0.2cm}
& = & (k^3 - 2k)n - (2k-1)(k m) + k^2 \cdot n_2 + k(k-1) \\
\vspace{0.2cm}
& = & (k^3 - 2k)n - (2k-1)(k m) + k^2 (km - n) + k(k-1) \\
\vspace{0.2cm}
& = & k(k-2)(k+1)n + k (k - 1)^2m + k(k-1).
\end{array}
\]
}
This implies the desired result.
\end{proof}

\medskip
We discuss next the hypergraphs $H \in \cH_k$ for $k \ge 3$ odd that achieve the upper bound for the transversal number in the statement of Theorem~\ref{alpha1odd}. For $k \ge 3$ an even integer and $r \ge 1$, let $G$ be an arbitrary graph in the family~$\cF_{k,r}$. Analogously as with the case when $k$ is even, we let $H_G$ be the dual hypergraph of $G$, and we let $H_G^k$ be the hypergraph obtained from $H_G$ by expanding all edges of $H_G$ of size less than~$k$ to edges of size~$k$ by adding new vertices of degree~$1$ to each such edge. Let $H_G^k$ denote the resulting hypergraph, and let $\cH_{k,r}^{\odd}$ be the family of all such hypergraphs $H_G^k$. For example, given the graph $G \in \cF_{3,2}$ shown in Figure~\ref{hyp2}(a) we obtain the associated hypergraph $H \in \cH_{3,2}^{\odd}$ shown in Figure~\ref{hyp2}(b).



\begin{figure}[htb]
\begin{center}
\tikzstyle{vertexX}=[circle,draw, fill=black!90, minimum size=8pt, scale=0.5, inner sep=0.2pt]
\begin{tikzpicture}[scale=0.37]
\node (a0) at (3,7.5) [vertexX] {};
\node (a1) at (1,3.0) [vertexX] {};
\node (a2) at (5,3.0) [vertexX] {};
\node (a3) at (3,5.0) [vertexX] {};
\node (a4) at (3,1.0) [vertexX] {};
\draw (a3) -- (a4) -- (a1) -- (a0) -- (a2) -- (a4);
\draw (a1) -- (a3) -- (a2);
% ------------------
\node (b0) at (9,7.5) [vertexX] {};
\node (b1) at (7,3.0) [vertexX] {};
\node (b2) at (11,3.0) [vertexX] {};
\node (b3) at (9,5.0) [vertexX] {};
\node (b4) at (9,1.0) [vertexX] {};
\draw (b3) -- (b4) -- (b1) -- (b0) -- (b2) -- (b4);
\draw (b1) -- (b3) -- (b2);
% ------------------
\node (x0) at (1.0,12.5) [vertexX] {};
\node (x1) at (6.0,12.5) [vertexX] {};
\node (x2) at (11.0,12.5) [vertexX] {};
\node (y0) at (3.0,10) [vertexX] {};
\node (y1) at (9.0,10) [vertexX] {};
\draw (x0) -- (y0) -- (x1) -- (y1) -- (x2);
\draw (y0) -- (a0);
\draw (y1) -- (b0);
 \draw (12.5,12.5) node {$V_1$};
 \draw (11,10) node {$V_2$};
 \draw [rounded corners] (0.5,12) rectangle (11.5,13);
 \draw [rounded corners] (2,9.5) rectangle (10,10.5);
 \draw (6,-1) node {(a) $G \in \cF_{3,2}$};
\end{tikzpicture}
\hspace*{2cm}
\tikzstyle{vertexX}=[circle,draw, fill=black!90, minimum size=8pt, scale=0.5, inner sep=0.2pt]
%\tikzstyle{vertexX}=[circle,draw, fill=gray!30, minimum size=6pt, scale=0.5, inner sep=0.1pt]
%\tikzstyle{vertexY}=[circle,draw, fill=black!40, minimum size=14pt, scale=0.5, inner sep=0.1pt]
%========= HERE tikz
\begin{tikzpicture}[scale=0.37]
 \node (a1) at (1.0,1.0) [vertexX] {};
\node (a2) at (1.0,3.0) [vertexX] {};
\node (a3) at (1.0,5.0) [vertexX] {};
\node (a4) at (5.0,5.0) [vertexX] {};
\node (a5) at (5.0,3.0) [vertexX] {};
\node (a6) at (5.0,1.0) [vertexX] {};
\node (a7) at (3.0,2.0) [vertexX] {};
\node (a8) at (3.0,7.0) [vertexX] {};
\node (b1) at (7.0,1.0) [vertexX] {};
\node (b2) at (7.0,3.0) [vertexX] {};
\node (b3) at (7.0,5.0) [vertexX] {};
\node (b4) at (11.0,5.0) [vertexX] {};
\node (b5) at (11.0,3.0) [vertexX] {};
\node (b6) at (11.0,1.0) [vertexX] {};
\node (b7) at (9.0,2.0) [vertexX] {};
\node (b8) at (9.0,7.0) [vertexX] {};
\node (c1) at (1.0,9.0) [vertexX] {};
\node (c2) at (5.0,9.0) [vertexX] {};
\node (c3) at (7.0,9.0) [vertexX] {};
\node (c4) at (11.0,9.0) [vertexX] {};
\node (c5) at (6.0,11.0) [vertexX] {};
\node (c6) at (1.0,11.0) [vertexX] {};
\node (c7) at (1.0,13.0) [vertexX] {};
\node (c8) at (11.0,11.0) [vertexX] {};
\node (c9) at (11.0,13.0) [vertexX] {};
%------- EDGE 0------
\draw[color=black!90, thick,rounded corners=4pt] (1.5999996420537173,5.000655389511118) arc (0.06258510065257994:179.538944044518:0.6); % Arc around vertex 1
\draw[color=black!90, thick,rounded corners=4pt] (0.40001942588971373,0.9951718854310111) arc (180.461055955482:359.93741489934746:0.6); % Arc around vertex 2
\draw[color=black!90, thick,rounded corners=4pt] (1.5999996420537173,5.000655389511118) -- (1.5999996420537173,0.9993446104888825);
\draw[color=black!90, thick,rounded corners=4pt] (0.40001942588971373,0.9951718854310111) -- (0.4,3.0) -- (0.40001942588971373,5.00482811456899);
% ----------------
%------- EDGE 1------
\draw[color=black!90, thick,rounded corners=4pt] (5.599999642053717,5.000655389511118) arc (0.06258510065257994:179.538944044518:0.6); % Arc around vertex 1
\draw[color=black!90, thick,rounded corners=4pt] (4.400019425889714,0.9951718854310111) arc (180.461055955482:359.93741489934746:0.6); % Arc around vertex 2
\draw[color=black!90, thick,rounded corners=4pt] (5.599999642053717,5.000655389511118) -- (5.599999642053717,0.9993446104888825);
\draw[color=black!90, thick,rounded corners=4pt] (4.400019425889714,0.9951718854310111) -- (4.4,3.0) -- (4.400019425889714,5.00482811456899);
% ----------------
%------- EDGE 2------
\draw[color=black!90, thick,rounded corners=4pt] (0.9999134390963681,3.359999989593347) arc (90.01377659582427:243.3579139148:0.36); % Arc around vertex 0
\draw[color=black!90, thick,rounded corners=4pt] (5.161429673497256,2.6782229645941626) arc (-63.35791391480001:89.98622340417575:0.36); % Arc around vertex 1
\draw[color=black!90, thick,rounded corners=4pt] (2.8394361757736837,1.6777900399586931) arc (243.51198373104404:296.48801626895596:0.36); % Arc around vertex 2
\draw[color=black!90, thick,rounded corners=4pt] (0.9999134390963681,3.359999989593347) -- (5.000086560903632,3.359999989593347);
\draw[color=black!90, thick,rounded corners=4pt] (5.161429673497256,2.6782229645941626) -- (3.160563824226316,1.677790039958693);
\draw[color=black!90, thick,rounded corners=4pt] (2.8394361757736837,1.6777900399586931) -- (0.838570326502744,2.678222964594163);
% ----------------
%------- EDGE 3------
\draw[color=black!90, thick,rounded corners=4pt] (0.8385703265027442,1.3217770354058371) arc (116.64208608519999:269.98622340417575:0.36); % Arc around vertex 0
\draw[color=black!90, thick,rounded corners=4pt] (3.1605638242263163,2.322209960041307) arc (63.51198373104401:116.48801626895596:0.36); % Arc around vertex 1
\draw[color=black!90, thick,rounded corners=4pt] (5.000086560903632,0.640000010406653) arc (-89.98622340417575:63.35791391480001:0.36); % Arc around vertex 2
\draw[color=black!90, thick,rounded corners=4pt] (0.8385703265027442,1.3217770354058371) -- (2.8394361757736837,2.322209960041307);
\draw[color=black!90, thick,rounded corners=4pt] (3.1605638242263163,2.322209960041307) -- (5.161429673497256,1.3217770354058371);
\draw[color=black!90, thick,rounded corners=4pt] (5.000086560903632,0.640000010406653) -- (0.999913439096368,0.640000010406653);
% ----------------
%------- EDGE 4------
\draw[color=black!90, thick,rounded corners=4pt] (0.7452703237417542,5.2543870909330295) arc (135.0385543976556:269.98622340417575:0.36); % Arc around vertex 0
\draw[color=black!90, thick,rounded corners=4pt] (3.2543870909330295,7.254729676258246) arc (45.0385543976556:134.96144560234438:0.36); % Arc around vertex 1
\draw[color=black!90, thick,rounded corners=4pt] (5.000086560903632,4.640000010406653) arc (-89.98622340417575:44.961445602344384:0.36); % Arc around vertex 2
\draw[color=black!90, thick,rounded corners=4pt] (0.7452703237417542,5.2543870909330295) -- (2.745612909066971,7.254729676258246);
\draw[color=black!90, thick,rounded corners=4pt] (3.2543870909330295,7.254729676258246) -- (5.254729676258246,5.2543870909330295);
\draw[color=black!90, thick,rounded corners=4pt] (5.000086560903632,4.640000010406653) -- (0.999913439096368,4.640000010406653);
% ----------------
%------- EDGE 5------
\draw[color=black!90, thick,rounded corners=4pt] (7.599999642053717,5.000655389511118) arc (0.06258510065257994:179.538944044518:0.6); % Arc around vertex 1
\draw[color=black!90, thick,rounded corners=4pt] (6.400019425889714,0.9951718854310111) arc (180.461055955482:359.93741489934746:0.6); % Arc around vertex 2
\draw[color=black!90, thick,rounded corners=4pt] (7.599999642053717,5.000655389511118) -- (7.599999642053717,0.9993446104888825);
\draw[color=black!90, thick,rounded corners=4pt] (6.400019425889714,0.9951718854310111) -- (6.4,3.0) -- (6.400019425889714,5.00482811456899);
% ----------------
%------- EDGE 6------
\draw[color=black!90, thick,rounded corners=4pt] (11.599999642053717,5.000655389511118) arc (0.06258510065257994:179.538944044518:0.6); % Arc around vertex 1
\draw[color=black!90, thick,rounded corners=4pt] (10.400019425889713,0.9951718854310111) arc (180.461055955482:359.93741489934746:0.6); % Arc around vertex 2
\draw[color=black!90, thick,rounded corners=4pt] (11.599999642053717,5.000655389511118) -- (11.599999642053717,0.9993446104888825);
\draw[color=black!90, thick,rounded corners=4pt] (10.400019425889713,0.9951718854310111) -- (10.4,3.0) -- (10.400019425889713,5.00482811456899);
% ----------------
%------- EDGE 7------
\draw[color=black!90, thick,rounded corners=4pt] (6.999913439096368,3.359999989593347) arc (90.01377659582427:243.3579139148:0.36); % Arc around vertex 0
\draw[color=black!90, thick,rounded corners=4pt] (11.161429673497256,2.6782229645941626) arc (-63.35791391480001:89.98622340417575:0.36); % Arc around vertex 1
\draw[color=black!90, thick,rounded corners=4pt] (8.839436175773685,1.6777900399586931) arc (243.51198373104404:296.48801626895596:0.36); % Arc around vertex 2
\draw[color=black!90, thick,rounded corners=4pt] (6.999913439096368,3.359999989593347) -- (11.000086560903632,3.359999989593347);
\draw[color=black!90, thick,rounded corners=4pt] (11.161429673497256,2.6782229645941626) -- (9.160563824226315,1.677790039958693);
\draw[color=black!90, thick,rounded corners=4pt] (8.839436175773685,1.6777900399586931) -- (6.838570326502744,2.678222964594163);
% ----------------
%------- EDGE 8------
\draw[color=black!90, thick,rounded corners=4pt] (6.838570326502745,1.3217770354058371) arc (116.64208608519998:269.98622340417575:0.36); % Arc around vertex 0
\draw[color=black!90, thick,rounded corners=4pt] (9.160563824226315,2.322209960041307) arc (63.51198373104401:116.48801626895596:0.36); % Arc around vertex 1
\draw[color=black!90, thick,rounded corners=4pt] (11.000086560903632,0.640000010406653) arc (-89.98622340417575:63.35791391480001:0.36); % Arc around vertex 2
\draw[color=black!90, thick,rounded corners=4pt] (6.838570326502745,1.3217770354058371) -- (8.839436175773685,2.322209960041307);
\draw[color=black!90, thick,rounded corners=4pt] (9.160563824226315,2.322209960041307) -- (11.161429673497256,1.3217770354058371);
\draw[color=black!90, thick,rounded corners=4pt] (11.000086560903632,0.640000010406653) -- (6.999913439096368,0.640000010406653);
% ----------------
%------- EDGE 9------
\draw[color=black!90, thick,rounded corners=4pt] (6.745270323741754,5.2543870909330295) arc (135.0385543976556:269.98622340417575:0.36); % Arc around vertex 0
\draw[color=black!90, thick,rounded corners=4pt] (9.25438709093303,7.254729676258246) arc (45.038554397655595:134.96144560234438:0.36); % Arc around vertex 1
\draw[color=black!90, thick,rounded corners=4pt] (11.000086560903632,4.640000010406653) arc (-89.98622340417575:44.961445602344384:0.36); % Arc around vertex 2
\draw[color=black!90, thick,rounded corners=4pt] (6.745270323741754,5.2543870909330295) -- (8.74561290906697,7.254729676258246);
\draw[color=black!90, thick,rounded corners=4pt] (9.25438709093303,7.254729676258246) -- (11.254729676258245,5.2543870909330295);
\draw[color=black!90, thick,rounded corners=4pt] (11.000086560903632,4.640000010406653) -- (6.999913439096368,4.640000010406653);
% ----------------
%------- EDGE 10------
\draw[color=black!90, thick,rounded corners=4pt] (0.9999134390963681,9.359999989593348) arc (90.01377659582428:224.96144560234438:0.36); % Arc around vertex 0
\draw[color=black!90, thick,rounded corners=4pt] (5.254729676258246,8.74561290906697) arc (-44.961445602344384:89.98622340417575:0.36); % Arc around vertex 1
\draw[color=black!90, thick,rounded corners=4pt] (2.745612909066971,6.745270323741754) arc (225.03855439765562:314.9614456023444:0.36); % Arc around vertex 2
\draw[color=black!90, thick,rounded corners=4pt] (0.9999134390963681,9.359999989593348) -- (5.000086560903632,9.359999989593348);
\draw[color=black!90, thick,rounded corners=4pt] (5.254729676258246,8.74561290906697) -- (3.254387090933029,6.745270323741754);
\draw[color=black!90, thick,rounded corners=4pt] (2.745612909066971,6.745270323741754) -- (0.7452703237417542,8.74561290906697);
% ----------------
%------- EDGE 11------
\draw[color=black!90, thick,rounded corners=4pt] (6.999913439096368,9.359999989593348) arc (90.01377659582428:224.96144560234438:0.36); % Arc around vertex 0
\draw[color=black!90, thick,rounded corners=4pt] (11.254729676258245,8.74561290906697) arc (-44.961445602344384:89.98622340417575:0.36); % Arc around vertex 1
\draw[color=black!90, thick,rounded corners=4pt] (8.74561290906697,6.745270323741754) arc (225.03855439765562:314.9614456023444:0.36); % Arc around vertex 2
\draw[color=black!90, thick,rounded corners=4pt] (6.999913439096368,9.359999989593348) -- (11.000086560903632,9.359999989593348);
\draw[color=black!90, thick,rounded corners=4pt] (11.254729676258245,8.74561290906697) -- (9.25438709093303,6.745270323741754);
\draw[color=black!90, thick,rounded corners=4pt] (8.74561290906697,6.745270323741754) -- (6.745270323741754,8.74561290906697);
% ----------------
%------- EDGE 12------
\draw[color=black!90, thick,rounded corners=4pt] (4.677790039958693,9.160563824226315) arc (153.51198373104404:269.89326053021284:0.36); % Arc around vertex 0
\draw[color=black!90, thick,rounded corners=4pt] (6.321777035405837,11.161429673497256) arc (26.64208608519998:153.3579139148:0.36); % Arc around vertex 1
\draw[color=black!90, thick,rounded corners=4pt] (7.000670663480328,8.640000624708186) arc (-89.89326053021284:26.488016268956017:0.36); % Arc around vertex 2
\draw[color=black!90, thick,rounded corners=4pt] (4.677790039958693,9.160563824226315) -- (5.678222964594163,11.161429673497256);
\draw[color=black!90, thick,rounded corners=4pt] (6.321777035405837,11.161429673497256) -- (7.322209960041307,9.160563824226315);
\draw[color=black!90, thick,rounded corners=4pt] (7.000670663480328,8.640000624708186) -- (4.999329336519672,8.640000624708186);
% ----------------
%------- EDGE 13------
\draw[color=black!90, thick,rounded corners=4pt] (1.359999989593347,13.000086560903632) arc (0.013776595824253057:179.89313814430324:0.36); % Arc around vertex 1
\draw[color=black!90, thick,rounded corners=4pt] (0.6400006261415696,8.999328567547659) arc (180.10686185569676:359.98622340417575:0.36); % Arc around vertex 2
\draw[color=black!90, thick,rounded corners=4pt] (1.359999989593347,13.000086560903632) -- (1.359999989593347,8.999913439096368);
\draw[color=black!90, thick,rounded corners=4pt] (0.6400006261415696,8.999328567547659) -- (0.64,11.0) -- (0.6400006261415696,13.000671432452341);
% ----------------
%------- EDGE 14------
\draw[color=black!90, thick,rounded corners=4pt] (11.359999989593348,13.000086560903632) arc (0.013776595824267268:179.89313814430326:0.36); % Arc around vertex 1
\draw[color=black!90, thick,rounded corners=4pt] (10.64000062614157,8.999328567547659) arc (180.10686185569674:359.98622340417575:0.36); % Arc around vertex 2
\draw[color=black!90, thick,rounded corners=4pt] (11.359999989593348,13.000086560903632) -- (11.359999989593348,8.999913439096368);
\draw[color=black!90, thick,rounded corners=4pt] (10.64000062614157,8.999328567547659) -- (10.64,11.0) -- (10.64000062614157,13.000671432452341);
% ----------------
 \draw (6,-1) node {(b) $H \in \cH_{3,2}^{\odd}$};

\end{tikzpicture}
\end{center}
\vskip -0.5 cm \caption{The hypergraph $H \in \cH_{3,2}^{\odd}$ associated with the graph $G \in \cF_{3,2}$.}  \label{hyp2}
\end{figure}



\begin{proposition}
\label{p:Hkrodd}
For $k \ge 3$ an odd integer and $r \ge 1$ arbitrary, if  $H \in \cH_{k,r}^{\odd}$ has order~$n$
%, with $n_2$ vertices of degree~$2$,
and size~$m$, then
\[
\tau(H) = \frac{(k-2)(k+1)n + (k - 1)^2m + k-1}{k(k^2 - 3)}.
\]
\end{proposition}
\begin{proof} We consider the graph $G \in \cF_{k,r}$ used to construct the hypergraph $H \in \cH_{k,r}^{\odd}$, and so $H = H_G^k$. Assume that $\ell$ copies of the graph $H_{k+2}$ were added when constructing the graph $G$. Thus, as observed in~\cite{HeYe16+},
\[
\ell = (k-1)|V_2| - |V_1| + 1.
\]
Further, the order, size and matching number of $G$ are as follows.
{\small
\[
\begin{array}{lcl}
n(G) & = & (k^2 + k - 1)|V_2| - (k+1)|V_1| + (k+2) \2 \\
2m(G) & = & (k^3 + k^2 - k + 1)|V_2| - (k^2 + 2k - 1) |V_1| + (k^2 + 2k - 1) \2 \\
2\alpha'(G) & = &  (k^2 + 1)|V_2| - (k+1)|V_1| + (k + 1).
\end{array}
\]
}

For $i \in [k]$, let $n_{1,i}$ be the number of vertices in $V_1$ that have degree~$i$ in $G$. Thus, if $[V_1,V_2]$ denotes the set of edges between $V_1$ and $V_2$ in $G$, then
{\small
\[
\sum_{i = 1}^k n_{1,i} = |V_1| \hspace*{0.5cm} \mbox{and} \hspace*{0.5cm} \sum_{i = 1}^k i \cdot n_{1,i} = |[V_1,V_2]| = k|V_2| - \ell = |V_1| + |V_2| - 1.
\]
}

Recall that  $H = H_G^k$, $n = n(H_G^k)$ and $m = m(H_G^k)$. The order of $H$ is
{\small
\[
\begin{array}{lcl}
n & = & \displaystyle{ m(G) + \sum_{i = 1}^k (k - i) \cdot n_{1,i} } \3 \\
& = & \displaystyle{ m(G) + k \left( \sum_{i = 1}^k n_{1,i} \right) \, - \, \left( \sum_{i = 1}^k i \cdot n_{1,i} \right) } \3 \\
& = & \displaystyle{ m(G) + (k-1)|V_1| - |V_2| + 1 } \3 \\
& = & \displaystyle{ \left( \frac{k^3 + k^2 - k - 1}{2} \right) |V_2| \, - \,  \left( \frac{k^2 + 1}{2} \right) |V_1| \, + \,  \left( \frac{k^2 + 2k + 1}{2} \right)}.
\end{array}
\]
}



Further, $H$ has size $m = m(H_G^k) = m(H_G) = n(G)$, and so
{\small
\[
m = (k^2 + k - 1)|V_2| - (k+1)|V_1| + (k+2).
\]
}

We remark that the graph $G \in \cF_{k,r}$ used to construct the hypergraph $H_G^k \in \cH_{k,r}^{\odd}$ is in fact the dual graph (see Section~\ref{S:cHk}) of $H_G^k$. Therefore, applying Proposition~\ref{p:dual} to $H$ and its dual graph $G$, we have

{\small
\[
\begin{array}{rcl} \vspace{0.2cm}
\tau(H) & = &  m - \alpha'(G) \\   \vspace{0.2cm}
& = &  \displaystyle{ \left( (k^2 + k - 1)|V_2| - (k+1)|V_1| + (k+2) \right)  } \\   \vspace{0.2cm}
&  &  \displaystyle{
\hspace*{0.5cm} -  \frac{1}{2} \left(
(k^2 + 1)|V_2| - (k+1)|V_1| + (k + 1) \right) } \\
\vspace{0.2cm}
& = &  \displaystyle{ \left( \frac{k^2 + 2k - 3}{2} \right) |V_2| \, - \, \left( \frac{k + 1}{2} \right) |V_1| \, + \, \frac{k + 3}{2} }
\end{array}
\]
}
and

{\small
\[
\begin{array}{rcl}
\multicolumn{3}{l}{\vspace{0.2cm} \displaystyle{  \frac{(k-2)(k+1)n + (k - 1)^2m + k-1}{k(k^2 - 3)} }   }
\\   \vspace{0.3cm}
& = &
\displaystyle{
\left( \frac{(k-2)(k+1)}{k(k^2 - 3)} \right)
\left(
\left( \frac{k^3 + k^2 - k - 1}{2} \right) |V_2| \, - \,  \left( \frac{k^2 + 1}{2} \right) |V_1| \, + \,  \left( \frac{k^2 + 2k + 1}{2} \right)
\right) } \\   \vspace{0.3cm}
&  &  \displaystyle{
\hspace*{0.5cm}
+
\left( \frac{(k - 1)^2}{k(k^2 - 3)} \right)
\left(
(k^2 + k - 1)|V_2| - (k+1)|V_1| + (k+2)
\right) } \\   \vspace{0.3cm}
&  &  \displaystyle{
\hspace*{1cm}
+ \, \frac{k-1}{k(k^2 - 3)}   } \\
\vspace{0.2cm}
& = &  \displaystyle{ \left( \frac{k^2 + 2k - 3}{2} \right) |V_2| \, - \, \left( \frac{k + 1}{2} \right) |V_1| \, + \, \frac{k + 3}{2}. }
\end{array}
\]
}
Equality therefore holds in the statement of Theorem~\ref{alpha1odd}.
\end{proof}



\subsection{Strong Independence Number}

In this section we establish a lower bound on the strong independence number of a connected, linear, $k$-uniform hypergraph $H$ with maximum degree~$2$ for $k \ge 2$. For this purpose, we first establish a lower bound on a maximum strong independent set consisting only of degree-$2$ vertices in $H$.


\begin{theorem} \label{alpha2}
For all even $k \ge 2$ the following holds.
\\ [-20pt]
\begin{enumerate}
\item If $H \in \cH_k$, then $\alpha_2(H) \ge  \frac{n_1 + (k^2+2) n_2 - k(k+1)}{k^2(k+1)}$.
\item If $H \in \cH_k'$, then $\alpha_2(H) \ge  \frac{n_1 + (k^2+2) n_2 - 3k}{k^2(k+1)}$.
\item If $H \in \cH_k''$, then $\alpha_2(H) \ge  \frac{n_1 + (k^2+2) n_2 - k}{k^2(k+1)}$.
\end{enumerate}
\end{theorem}
\begin{proof}
Let $k \ge 2$ be even and let $H \in \cH_k$, and let $G_H$ be the dual graph of $H$. We adopt the notation in the proof of Theorem~\ref{alpha1}. Analogously as in the proof of Theorem~\ref{alpha1},
{\small
\[
\alpha'(G_H) \ge
\frac{m}{k(k+1)} \, + \, \frac{n_2}{k+1} - \frac{\theta}{k(k+1)}.
\]
}

By Observation~\ref{ob1}, we note that the following therefore holds.

{\small
\[
\begin{array}{rcl} \vspace{0.2cm}
\alpha_2(H) & = & \alpha'(G_H) \\ \vspace{0.2cm}
& \ge &  \displaystyle{ \frac{m}{k(k+1)} + \frac{n_2}{k+1} - \frac{\theta}{k(k+1)} } \\ \vspace{0.2cm}
& = & \displaystyle{ \left( \frac{1}{k(k+1)} \right) \left(\frac{n_1 + 2n_2}{k} \right)  + \frac{n_2}{k+1} - \frac{\theta}{k(k+1)}.}
\end{array}
\]
}

Multiplying through with $k^2 (k+1)$ we obtain the following.
{\small
\[
k^2(k+1) \alpha_2(H)  \ge  n_1  + (k^2+2) n_2  - k\theta.
\]
}
This implies the desired result.
\end{proof}

\medskip
We proceed further with the following simple lemma.\footnote{We have not been able to find the original source of this lemma, but as remarked in~\cite{BuHeTu12}, ``it definitely seems to have been known already at least in the early 1960's." For completeness, we provide the short proof given in~\cite{BuHeTu12}.}


\begin{lemma}{\rm (\cite{BuHeTu12})}
\label{lem:useful}
If $H$ is a $k$-uniform hypergraph of order $n$ and size $m$ with $\delta(H) \ge 1$ and with $c$ components, then $(k-1)m + c \ge n$. 
\end{lemma}
\begin{proof} Replace each hyperedge $e \in E(H)$ by a star of $k-1$ edges on the vertex set of $e$ to produce a graph $G$. If $H$ has $c$ components, then so too does $G$. Since $G$ has $(k-1)m$ edges, $n$ vertices and $c$ components, we have that $(k-1)m + c \ge n$.
\end{proof}

\medskip
As a special case of Lemma~\ref{lem:useful}, we note that if $H$ is a connected $k$-uniform hypergraph of order $n$ and size $m$, then $(k-1)m + 1 \ge n$.




\begin{theorem}
\label{mainAlpha}
For all even $k \ge 2$ the following holds.
\\ [-22pt]
\begin{enumerate}
\item If $H \in \cH_k$, then $\alpha(H) \ge \frac{(k+2)n - (k-1)m - (k+1)}{k(k+1)}$.
\item If $H \in \cH_k'$, then $\alpha(H) \ge  \frac{(k+2)n - (k-1)m - 3}{k(k+1)}$.
\item If $H \in \cH_k''$, then $\alpha(H) \ge  \frac{(k+2)n - (k-1)m - 1}{k(k+1)}$.
\end{enumerate}
\end{theorem}
\begin{proof}
Let $k \ge 2$ be even and let $H \in \cH_k''$ be arbitrary. Let $V_1(H)$ denote the set of all vertices of degree~$1$ in $H$, and let $S$ be the set of all edges of $H$ that contain at least one vertex in $V_1(H)$. Let $R$ be the vertices in $H$ which belong to two edges of $S$, and let $r = |R|$. Let $X = V(H) \setminus (V_1(H) \cup R)$ and consider the hypergraph $H[X]$ induced by the vertices in $X$. Let $S'$ be the set of edges in $H[X]$ of size less than~$k$. We note that each edge in $S'$ was obtained by shrinking an edge in $S$ by removing from it vertices in $V_1(H) \cup R$. We note that $H[X]$ contains at most~$r + 1$ components; that is, $c(H[X]) \le r+1$.



%
Let $H'$ be obtained from $H[X]$ by removing all edges in $H[X]$ of size less than~$k$. Equivalently, $H'$ is obtained from $H$ be removing all edges in $S$ and all resulting isolated vertices. We note that $H'$ has order
{\small
\[
  n(H') = n(H) - n_1(H) - r
\]
}
and may possibly be the empty hypergraph. For every $i= \{0\} \cup [k-1]$, let $T_i$ denote the subset of edges of $S$ which contain vertices from exactly $i$ different components in $H'$ and let $t_i = |T_i|$. We note that for $i \in [k-1] \setminus \{1\}$, the removal of all edges in $T_i$ from $H[X]$ gives rise to at most~$(i-1)t_i$ additional components. Thus,
{\small
\[
c(H') \le c(H[X]) + \sum_{i=2}^{k-1} (i-1)t_i.
\]
}
As observed earlier, $c(H[X]) \le r+1$, implying that
{\small
\[
\sum_{i=2}^{k-1} (i-1)t_i \ge c(H') - r -1.
\]
}


Every edge in $T_i$ contains at most $k-i$ vertices of degree~$1$ in $H$, and at least $i$ vertices from different components of $H'$, in addition to possibly some vertices of $R$. Thus,

{\small
\[
\begin{array}{rcl} \vspace{0.2cm}
 n_1(H) & \le & k|S| - \displaystyle{  \left(\sum_{i=1}^{k-1} i \cdot t_i \right) - 2r } \\   \vspace{0.2cm}
  & = & k|S| - \displaystyle{  \left(\sum_{i=0}^{k-1} t_i \right) - \left(\sum_{i=2}^{k-1} (i-1)t_i \right) - 2r } + t_0 \\  \vspace{0.2cm}
  & \le & k|S| - |S| - (c(H') - r -1) - 2r + t_0 \\
  & = & (k-1)|S|  - c(H') - r + t_0 + 1. \\
\end{array}
\]
}

We now obtain a strong independent set in $H$ by taking a maximum strong independent set of degree-$2$ vertices in $H'$ and adding to this set a vertex of degree one from each edge in $S$. Therefore the following holds by Theorem~\ref{alpha2}, as no component belongs to $\{L_k\} \cup \cM_k$ (recall that $H \in \cH_k''$).
{\small
\[
\alpha(H) \ge |S| + \alpha_2(H')  \ge |S| + \frac{n_1(H') + (k^2+2) n_2(H') - k \cdot c(H')}{k^2(k+1)}.
\]
}

As $n_1(H')+n_2(H')= n(H') = n(H) -n_1(H)-r$, we note that
{\small
\[
n_2(H') = n_2(H) - n_1(H') - r.
\]
}
Furthermore,
{\small
\[
n_1(H') = k|S| - n_1(H) - 2r,
\]
}
as the $|S|$ edges in $S$ each have $k$ vertices and every vertex with degree~$1$ in $H'$ belongs to an edge in $S$ and does not have degree~$1$ in $H$ and does not belong to $R$, and every vertex in $R$ counts two in $k|S|-n_1(S)$ but does not belong to $H'$.
The following now holds by the above observations.

{\small
\[
\begin{array}{rcl}
\multicolumn{3}{l}{\vspace{0.2cm} k^2(k+1) \alpha(H) } \\   \vspace{0.2cm}
& \ge &  k^2(k+1)|S| + n_1(H') + (k^2+2) n_2(H') - k \cdot c(H')  \\   \vspace{0.2cm}
& = & k^2(k+1)|S| + n_1(H') + (k^2+2)(n_2(H) - r - n_1(H'))  - k \cdot c(H')  \\   \vspace{0.2cm}
& = & k^2(k+1)|S| + n_1(H')(1-(k^2+2)) + (k^2+2)n_2(H) - (k^2+2)r  - k \cdot c(H')  \\   \vspace{0.2cm}
& = & k^2(k+1)|S| + (k|S|-n_1(H)-2r)(-k^2-1) + (k^2+2)n_2(H) - (k^2+2)r  - k \cdot c(H')  \\   \vspace{0.2cm}
& = & (k^3+k^2-k^3-k)|S| + n_1(H)(k^2+1) + (k^2+2)n_2(H) + k^2r  - k \cdot c(H')  \\   \1
& = & \left( k(k-1)|S|  - k \cdot c(H') - kr + k t_0 + k \right) \\
& & \hspace*{0.5cm} - k t_0 + n_1(H)(k^2+1) + (k^2+2)n_2(H) + (k^2+k)r - k  \2 \\
& \ge & \left( k \cdot n_1(H) \right) - k t_0 + n_1(H)(k^2+1) + (k^2+2)n_2(H) + (k^2+k)r - k \2 \\
& = & (k^2+k+1)n_1(H) + (k^2+2) n_2(H) + (k^2+k)r -k t_0 - k \2 \\
& = & (k^2+2k)(n_1(H)+n_2(H)) - (k-1)(n_1(H)+2n_2(H)) + (k^2+k)r -k t_0 - k \2 \\
& = & (k^2+2k)n(H) - (k-1)(k \cdot m(H)) + (k^2+k)r - k t_0 - k. \\  % \vspace{0.2cm}
\end{array}
\]
}

Note that every edge in $T_0$ must contain a vertex from $R$. In particular, if $r = 0$, then $t_0 = 0$. In this case, dividing though by $k$ the above simplifies to the following.
{\small
\[
k(k+1) \alpha(H) \ge (k+2)n(H) - (k-1)m(H) - 1.
\]
}
Suppose that $r \ge 1$. We note that every edge in $T_0$ contains at most~$k-1$ vertices from $R$, and so $t_0 \le (k-1)r$. Dividing though by $k$ above we get the following.

{\small
\[
\begin{array}{rcl} \vspace{0.2cm}
k(k+1) \alpha(H)  & \ge &  (k+2)n(H) - (k-1)m(H) + (k+1)r - t_0 - 1 \\  \vspace{0.2cm}
& \ge &  (k+2)n(H) - (k-1)m(H) + (k+1)r - (k-1)r - 1 \\  \vspace{0.2cm}
& = &  (k+2)n(H) - (k-1)m(H) + 2r - 1  \\ \vspace{0.2cm}
& \ge &  (k+2)n(H) - (k-1)m(H) - 1.
\end{array}
\]
}
This implies the theorem in the case when $H \in \cH_k''$.

Suppose next that $H \in \cH_k'$. If $H \notin \cM_k$, then as shown above we have $k(k+1) \alpha(H) \ge (k+2)n(H) - (k-1)m(H) - 1$. Suppose, therefore, that $H \in \cM_k$. We note that, by Theorem~\ref{alpha2},
{\small
\[
\alpha_2(H) \ge  \frac{n_1(H) + (k^2+2) n_2(H) - 3k}{k^2(k+1)}.
\]
}

As $H$ is $2$-regular, we have $\alpha(H)=\alpha_2(H)$ and $n_1(H)=0$, and therefore $n(H) = n_2(H) = k(k+3)/2$ and $k \cdot m(H) = 2n_2(H) = k(k+3)$.
Therefore,

%{\small
%\[
\begin{align*}
\alpha(H) & \ge   \displaystyle{ \frac{(k^2+2) n_2(H) - 3k}{k^2(k+1)} } \\% \vspace{0.2cm}
& =  \displaystyle{ \frac{k(k+2)n_2(H) - 2(k-1) n_2(H) - 3k}{k^2(k+1)} } \\ %\vspace{0.2cm}
& =  \displaystyle{ \frac{k(k+2)n(H) - (k-1) (k \cdot m(H)) - 3k}{k^2(k+1)} } \\
& =  \displaystyle{ \frac{(k+2)n(H)| - (k-1) m(H) - 3}{k(k+1)}. }
\end{align*}
%\]


This implies the theorem in the case when $H \in \cH_k'$.

Suppose finally that $H \in \cH_k$. From the above, it remains for us to consider the case when $H = L_k$. In this case Theorem~\ref{alpha2} implies that
{\small
\[
\alpha_2(H) \ge \frac{n_1(H) + (k^2+2) n_2(H) - k(k+1)}{k^2(k+1)}.
\]
}

As $H$ is $2$-regular, we have $\alpha(H)=\alpha_2(H)$ and $n_1(H)=0$, and therefore $n(H) = n_2(H) = k(k+1)/2$ and $k \cdot m(H) = 2n_2(H) = k(k+1)$. Analogous to the discussion in the previous argument,
{\small
\[
\alpha(H)  \ge  \frac{(k+2)n(H) - (k-1) m(H) - (k+1)}{k(k+1)},
\]
}

This implies the theorem in the case when $H \in \cH_k$.
\end{proof}

\medskip
We discuss next the hypergraphs $H \in \cH_k$ for $k \ge 2$ even that achieve the lower bound for the strong independence number in the statement of Theorem~\ref{mainAlpha}.
%
If $H = L_k$, then, by Observation~\ref{ob1} and Theorem~\ref{thmKeven}(a), equality holds in the statement of Theorem~\ref{mainAlpha}(a).
%
If $H \in \cM_k$, then, by Observation~\ref{o:Mk} and Theorem~\ref{thmKeven}(b), equality holds in the statement of Theorem~\ref{mainAlpha}(b).


We show next that there is an infinite family of hypergraphs $H \in \cH_k''$ for which equality holds in the statement of Theorem~\ref{mainAlpha}(c).
%
For $k \ge 4$ an even integer and $r \ge 1$, let $G$ be an arbitrary graph in the family~$\cG_{k,r}$, and let $H_G^k$ be the associated hypergraph in the family~$\cH_{k,r}^{\even}$. For each vertex $v$ of degree~$1$ in $H_G^k$, we add $k-1$ new vertices and an edge (of size~$k$) containing $v$ and these new vertices. Let $R_G^k$ denote the resulting hypergraph, and let $\cR_{k,r}$ be the family of all such hypergraphs $R_G^k$.


\begin{proposition}
\label{p:Rkreven}
For $k \ge 4$ an even integer and $r \ge 1$ arbitrary, if  $H \in \cR_{k,r}^{\even}$ has order~$n$ and size~$m$, then
\[
\alpha(H) = \frac{(k+2)n - (k-1)m - 1}{k(k+1)}.
\]
\end{proposition}
\begin{proof} Let $G \in \cG_{k,r}$ be the graph and $H_G^k \in \cH_{k,r}^{\even}$ the associated hypergraph used to construct the hypergraph $H \in \cR_{k,r}^{\even}$, and so $H = R_G^k$.


We show firstly that $\alpha(R^k_G) = n_1(H^k_G) + \alpha'(G)$. Let $S$ be a maximum independent set in $H = R_G^k$ that contains the maximum number of vertices of degree~$1$ in $H$. For each vertex $v$ of degree~$1$ in $H_G^k$, let $e_v$ be the associated edge containing $v$ that was added to $H_G^k$ when constructing $H$. We note that every vertex in $e_v$ different from $v$ has degree~$1$ in $H$. Let $v'$ be an arbitrary vertex in $e_v$ different from $v$. If $v \in S$ or if $S$ contains no vertex from $e_v$, then the set $(S \setminus \{v\}) \cup \{v'\}$ is a maximum independent set containing more vertices of degree~$1$ than does $S$, a contradiction. Hence, the set $S$ contains $n_1(H_G^k)$ vertices of degree~$1$, one from each edge added to $H_G^k$ when constructing $H$. The remaining vertices of $S$ belong to $V(H_G)$ and have degree~$2$ in $H_G^k$, and so $\alpha(H) \le n_1(H_G^k) + \alpha_2(H_G^k)$. Conversely, every maximum independent set of degree-$2$ vertices in $H_G^k$ can be extended to an independent set in $H$ by adding to it $n_1(H_G^k)$ vertices of degree~$1$, one vertex from each edge added to $H_G^k$ when constructing $H$, implying that $\alpha(H) \ge n_1(H_G^k) + \alpha_2(H_G^k)$. Consequently, $\alpha(H) = n_1(H_G^k) + \alpha_2(H_G^k)$. We note that $G$ is the dual graph of the hypergraph $H_G^k \in \cH_k$, and so, by Observation~\ref{ob1}, $\alpha_2(H_G^k) = \alpha'(G)$. Therefore, $\alpha(R^k_G) = n_1(H^k_G) + \alpha'(G)$.

Let $G$ be constructed from $\ell_1$ single vertices and $\ell_2$ copies of $K_{k+1} - e$. Further, let $\ell_{1,1}$ and $\ell_{1,2}$ be the number of single vertices of degree~$1$ and degree~$2$ in $G$, and let $\ell_{2,1}$ and $\ell_{2,2}$ be the number of copies of $K_{k+1} - e$ joined to one or two vertices in $Y$, respectively. We note that $(\ell_{1,1} + \ell_{1,2}) + (\ell_{2,1} + \ell_{2,2}) = \ell_1 + \ell_2 = \ell = r(k-1)+1$ and $n(G) = r + \ell_1 + \ell_2(k+1)$.
%
Recall that $n = n(H)$ and $m = m(H)$. We note that
{\small
\[
\begin{array}{ccl}
n & = & n(H^k_G) + (k-1)n_1(H^k_G) \2 \\
m & = & m(H^k_G) + n_1(H^k_G) \2 \\
n_1(H^k_G) & = & (k-1)\ell_{1,1} + (k-2)\ell_{1,2} + \ell_{2,1} \2 \\
r & = & \ell_{1,2} + \ell_{2,2} + 1
\end{array}
\]
}
Recall (see the proof of Proposition~\ref{p:Hkreven}) that

{\small
\[
\begin{array}{ccl}
n(H_G^k) & = & k\ell_ 1 + \frac{1}{2}(k^2 + k + 2) \ell_2 \3 \\
m(H_G^k) & = & \frac{1}{k-1} \left( k \ell_1 + k^2 \ell_2 - 1 \right) \3 \\
\alpha'(G) & = &  r + \frac{1}{2} k \ell_2.
\end{array}
\]
}
We note that
{\small
\[
\begin{array}{rcl}
%\frac{1}{k}( \ell_{1,1} + 2\ell_{1,2} + \ell_{2,1} + 2\ell_{2,2} )
\multicolumn{3}{l}{\vspace{0.2cm} \frac{1}{k}( \ell_{1,1} + 2\ell_{1,2} + \ell_{2,1} + \ell_{2,2} ) } \\   \vspace{0.2cm}
& = &  \frac{1}{k}( \ell + \ell_{1,2} + 2\ell_{2,2}) \\   \vspace{0.2cm}
& = &  \frac{1}{k}( \ell + r - 1) \\   \vspace{0.2cm}
& = &  \frac{1}{k}( (r(k-1) + 1) + r - 1) \\
\vspace{0.2cm}
& = & r.
\end{array}
\]
}
Thus,

{\small
%\[
\begin{align*} %array}{rcl} 
\displaystyle{  \frac{(k+2)n - (k-1)m - 1}{k(k+1)} }
= & 
\displaystyle{
\left( \frac{k+2}{k(k+1)} \right)
\left(
n(H^k_G) + (k-1)n_1(H^k_G)
\right) } \\   
&   \displaystyle{
%\hspace*{0.5cm}
-
\left( \frac{k-1}{k(k+1)} \right)
\left(
m(H^k_G) + n_1(H^k_G)
\right) } \\   
&    \displaystyle{- 
\frac{1}{k(k+1)}  } \\
= & 
\displaystyle{
\left( \frac{k+2}{k(k+1)} \right)
\left(
k\ell_ 1 + \left( \frac{k^2 + k + 2}{2} \right) \ell_2 + (k-1)n_1(H^k_G)
\right) } \\   
&    \displaystyle{
-
\left( \frac{k-1}{k(k+1)} \right)
\left(
\left( \frac{k}{k-1} \right) \ell_1 +
\left( \frac{k^2}{k-1} \right) \ell_2 - \frac{1}{k-1} + n_1(H^k_G)
\right) } \\   
&    \displaystyle{
- \frac{1}{k(k+1)}  } \\
= & 
\displaystyle{
\left( \frac{k(k+2) - k}{k(k+1)} \right) \ell_1
} \\
&    \displaystyle{
+ \left( \frac{k^3 + k^2 + 4k + 4}{2k(k+1)} \right) \ell_2 } \\
&    \displaystyle{
+ \left( \frac{k^2 - 1}{k(k+1)} \right) n_1(H^k_G) }\\ 
= & 
\displaystyle{
\ell_1 + \left( \frac{k^2 + 4}{2k} \right) \ell_2  +
\left( \frac{k-1}{k} \right) n_1(H^k_G)  }  \\ 
= & 
\displaystyle{
(\ell_{1,1} + \ell_{1,2}) + \left( \frac{k^2 + 4}{2k} \right) (\ell_{2,1} + \ell_{2,2}) } \\
&    \displaystyle{
+ \left( \frac{k-1}{k} \right) \left( (k-1)\ell_{1,1} + (k-2)\ell_{1,2} + \ell_{2,1} \right)  }
\\
= & 
\displaystyle{
\left( \frac{k^2 - k + 1}{k} \right) \ell_{1,1} +
\left( \frac{k^2 -2k + 2}{2} \right) \ell_{1,2}  } \\   
&    \displaystyle{
+
\left( \frac{k^2 + 2k + 2}{2k} \right) \ell_{2,1} +
\left( \frac{k^2 + 4}{2k} \right) \ell_{2,1} } \\
= & 
\displaystyle{ (k-1)\ell_{1,1} + (k-2)\ell_{1,2} + \ell_{2,1}  } \\   
&    \displaystyle{
+ \frac{1}{k} \left( \ell_{1,1} + 2\ell_{1,2} + \ell_{2,1} + 2\ell_{2,2} \right) + \frac{1}{2} k (\ell_{2,1} + \ell_{2,2}) } \\
= & 
\displaystyle{ n_1(H^k_G) + r + \frac{1}{2} k  \ell } \\
= & 
\displaystyle{ n_1(H^k_G) + \alpha'(G) } \\
= &  \alpha(H).\qedhere
\end{align*}%
}
\end{proof}

\medskip
Next we consider the case when $k \ge 3$ is odd.

\begin{theorem} \label{alpha2odd}
For $k \ge 3$ odd, if $H \in \cH_k$, then
\[
\alpha_2(H) \ge  \frac{(k-1)n_1  + (k^3 - k^2 - 2) n_2  - k(k-1)}{k^2(k^2 - 3)}.
\]
\end{theorem}
\begin{proof}
Let $k \ge 3$ be odd and let $H \in \cH_k$. Let $G_H$ be the dual graph of $H$ and note that $G_H$ has maximum degree $\Delta(G) \le k$.  Further, we note that $G_H$ is a connected graph of order $n(G_H) = m$ and size~$m(G_H) = n_2$. By Theorem~\ref{thmKodd}, the following holds.
{\small
\[
\alpha'(G_H) \ge
\left( \frac{k-1}{k(k^2 - 3)} \right) m \, + \, \left( \frac{k^2 - k - 2}{k(k^2 - 3)} \right) n_2 \, - \, \frac{k-1}{k(k^2 - 3)}.
\]
}

By Observation~\ref{ob1}, and noting that $km = n_1 + 2n_2$, the following therefore holds.
{\small
\[
\alpha_2(H) = \alpha'(G_H) \ge \left( \frac{k-1}{k(k^2 - 3)} \right) \left(\frac{n_1 + 2n_2}{k} \right) \, + \, \left( \frac{k^2 - k - 2}{k(k^2 - 3)} \right) n_2 \, - \, \frac{k-1}{k(k^2 - 3)}.
\]
}

Multiplying through with $k^2 (k^2 - 3)$, and simplifying, we obtain the following.
{\small
\[
k^2(k^2 - 3) \alpha_2(H)  \ge  (k-1)n_1  + (k^3 - k^2 - 2) n_2  - k(k-1).
\]
}
This implies the desired result.
\end{proof}


\begin{theorem} \label{alpha3odd}
For $k \ge 3$ odd, if $H \in \cH_k$, then
\[
\alpha(H) \ge  \frac{(k^2 + k - 4) n(H)  - (k-1)^2 m(H) - (k-1)}{k(k^2 - 3)}.
\]
\end{theorem}
\begin{proof}
Let $k \ge 3$ be odd and let $H \in \cH_k$. We follow the same notation as introduced in the proof of Theorem~\ref{mainAlpha}. Proceeding exactly as in the proof of Theorem~\ref{mainAlpha}, we have
{\small
\[
\begin{array}{lcl}
n_1(H) & \le & (k-1)|S|  - c(H') - r + t_0 + 1 \\
n_1(H') & = & k|S| - n_1(H) - 2r \\
n_2(H') & = & n_2(H) - n_1(H') - r \\
\end{array}
\]
}

The following holds by Theorem~\ref{alpha2odd}.
{\small
\[
\alpha(H) \ge |S| + \alpha_2(H')  \ge |S| + \frac{(k-1)n_1(H')  + (k^3 - k^2 - 2) n_2(H')  - k(k-1)c(H')}{k^2(k^2 - 3)}.
\]
}
Therefore,

{\small
\begin{align*}
%\multicolumn{3}{l}{\vspace{0.2cm} 
k^2(k^2 - 3) \alpha(H)   
 \ge &   k^2(k^2 - 3)|S| + (k-1)n_1(H')  + (k^3 - k^2 - 2) n_2(H')  - k(k-1)c(H') \\   
 = &  k^2(k^2 - 3)|S| + (k-1)n_1(H')  + (k^3 - k^2 - 2) (n_2(H) - n_1(H') - r)\\
 &  - k(k-1)c(H')  \\   
 = &  k^2(k^2 - 3)|S| + (-k^3 + k^2 + k + 1) n_1(H') \\   
&   +   (k^3 - k^2 - 2)n_2(H) - (k^3 - k^2 - 2)r   - k(k-1) c(H')  \\   
 = & k^2(k^2 - 3)|S| + (-k^3 + k^2 + k + 1) (k|S| - n_1(H) - 2r) \\   
&   +   (k^3 - k^2 - 2)n_2(H) - (k^3 - k^2 - 2)r   - k(k-1) c(H')  \\   
= & (k^4 - 3k^2 - k^4 + k^3 + k^2 + k)|S| + (k^3 - k^2 - k - 1) n_1(H) \\   
&   +   (k^3 - k^2 - 2)n_2(H) + (k^3 - k^2 - 2k)r   - k(k-1) c(H')  \\ 
= & k(k - 1)^2|S| + (k^3 - k^2 - k - 1) n_1(H) \\   
&   +   (k^3 - k^2 - 2)n_2(H) + (k^3 - k^2 - 2k)r   - k(k-1) c(H')  \\  
= & k(k - 1)( (k-1)|S| - c(H') - r + t_0 + 1 ) \\   
&   -   k(k-1)t_0 - k(k-1) + (k^3 - k^2 - k - 1) n_1(H) \\ 
& +   (k^3 - k^2 - 2)n_2(H) + (k^3 - 3k )r  \\ 
 \ge & k(k - 1) n_1(H) -   k(k-1)t_0 - k(k-1) + (k^3 - k^2 - k - 1) n_1(H) \\ 
&   +   (k^3 - k^2 - 2)n_2(H) + k(k^2 - 3)r  \\ 
= & (k^3 - 2k - 1) n_1(H)  +   (k^3 - k^2 - 2)n_2(H) \\ 
&   +   k(k^2 - 3)r -   k(k-1)t_0 - k(k-1)  \\ 
= & k(k^2 + k - 4) (n_1(H) + n_2(H))  - (k-1)^2(n_1(H) + 2n_2(H)) \\ 
&   +   k(k^2 - 3)r -   k(k-1)t_0 - k(k-1)  \\
= & k(k^2 + k - 4) n(H)  - k(k-1)^2 m(H) +   k(k^2 - 3)r -   k(k-1)t_0 - k(k-1).
\end{align*}
}
Dividing through by $k$, the above simplifies to
{\small
\[
k(k^2 - 3) \alpha(H) \ge (k^2 + k - 4) n(H)  - (k-1)^2 m(H) + \, (k^2 - 3)r - \, (k-1)t_0 - (k-1).
\]
}
As observed in the proof of Theorem~\ref{mainAlpha}, if $r = 0$, then $t_0 = 0$, while if $r \ge 1$, then $t_0 \le (k-1)r$. If $r= 0$, then the above simplifies to the following.
{\small
\[
k(k^2 - 3) \alpha(H) \ge (k^2 + k - 4) n(H)  - (k-1)^2 m(H) - (k-1).
\]
}
If $r \ge 1$, then the above simplifies to the following.
{\small
\begin{align*}
k(k^2 - 3) \alpha(H)   \ge &  (k^2 + k - 4) n(H)  - (k-1)^2 m(H) \\ 
  &  +  (k^2 - 3)r -  (k-1)^2r - (k-1)  \\  
 = &  (k^2 + k - 4) n(H)  - (k-1)^2 m(H) + 2(k-2)r - (k-1)  \\
 \ge & k(k^2 + k - 4) n(H)  - (k-1)^2 m(H) + k-3 \\
 \ge & k(k^2 + k - 4) n(H)  - (k-1)^2 m(H) \\
  > & k(k^2 + k - 4) n(H)  - (k-1)^2 m(H) - (k-1).
\end{align*}}
This completes the proof of Theorem~\ref{alpha3odd}.
\end{proof}


\medskip
We show next that there is an infinite family of hypergraphs $H \in \cH_k$ for which equality holds in the statement of Theorem~\ref{alpha3odd}.
%
For $k \ge 3$ an odd integer and $r \ge 1$, let $G$ be an arbitrary graph in the family~$\cF_{k,r}$, and let $H_G^k$ be the associated hypergraph in the family~$\cH_{k,r}^{\odd}$. For each vertex $v$ of degree~$1$ in $H_G^k$, we add $k-1$ new vertices and an edge (of size~$k$) containing $v$ and these new vertices. Let $R_G^k$ denote the resulting hypergraph, and let $\cR_{k,r}^{\odd}$ be the family of all such hypergraphs $R_G^k$.


\begin{proposition}
\label{p:Rkrodd}
For $k \ge 3$ an odd integer and $r \ge 1$ arbitrary, if  $H \in \cR_{k,r}^{\odd}$ has order~$n$ and size~$m$, then
\[
\alpha(H) = \frac{(k^2 + k - 4) n(H)  - (k-1)^2 m(H) - (k-1)}{k(k^2 - 3)}.
\]
\end{proposition}
\begin{proof} Let $G \in \cF_{k,r}$ be the graph and $H_G^k \in \cH_{k,r}^{\odd}$ the associated hypergraph used to construct the hypergraph $H \in \cR_{k,r}^{\odd}$, and so $H = R_G^k$.
%
Analogous to the proof of Proposition~\ref{p:Rkreven}, we have that
{\small
\[
\alpha(H) = n_1(H^k_G) + \alpha'(G).
\]
}
%
\medskip
For $i \in [k]$, let $n_{1,i}$ be the number of vertices in $V_1$ that have degree~$i$ in $G$. As shown in the proof of Proposition~\ref{p:Hkreven},
{\small
\[
\sum_{i = 1}^k n_{1,i} = |V_1| \hspace*{0.5cm} \mbox{and} \hspace*{0.5cm} \sum_{i = 1}^k i \cdot n_{1,i} = |V_1| + |V_2| - 1,
\]
}
implying that
{\small
\[
n_1(H^k_G) = \sum_{i=1}^{k} (k-i)n_{1,i} = k \sum_{i = 1}^k n_{1,i} - \sum_{i = 1}^k i \cdot n_{1,i}
= (k-1)|V_1| - |V_2| + 1.
\]
}

Recall that $n = n(H)$ and $m = m(H)$. We note that
{\small
\[
\begin{array}{ccl}
n & = & n(H^k_G) + (k-1)n_1(H^k_G) \2 \\
m & = & m(H^k_G) + n_1(H^k_G)
\end{array}
\]
}

Recall (see the proof of Proposition~\ref{p:Hkreven}) that

{\small
\[
\begin{array}{ccl}
n(H_G^k) & = & \displaystyle{ {\small \left( \frac{k^3 + k^2 - k - 1}{2} \right) |V_2| \, - \,  \left( \frac{k^2 + 1}{2} \right) |V_1| \, + \,  \left( \frac{k^2 + 2k + 1}{2} \right) }} \3 \\
m(H_G^k) & = & (k^2 + k - 1)|V_2| - (k+1)|V_1| + (k+2) \3 \\
\alpha'(G) & = &  \frac{1}{2}\left(  (k^2 + 1)|V_2| - (k+1)|V_1| + (k + 1) \right)
\end{array}
\]
}
Therefore,
{\small
\begin{align*}
 &\displaystyle{  \frac{(k^2 + k - 4) n  - (k-1)^2 m - (k-1)}{k(k^2 - 3)}}\\
 = &
\displaystyle{
\left( \frac{k^2 + k - 4}{k(k^2 - 3)} \right)
\left(
n(H^k_G) + (k-1)n_1(H^k_G)
\right) } \\   
& \displaystyle{ -  \left( \frac{(k-1)^2}{k(k^2 - 3)} \right)
\left(
m(H^k_G) + n_1(H^k_G)
\right) } \\   
&  \displaystyle{ -  \frac{k-1}{k(k^2 - 3)} } \\ 
= &
\displaystyle{
\left( \frac{k^2 + k - 4}{k(k^2 - 3)} \right)
\left(
\left( \frac{k^3 + k^2 - k - 1}{2} \right) |V_2|  -  \left( \frac{k^2 + 1}{2} \right) |V_1|  +   \left( \frac{k^2 + 2k + 1}{2} \right) \right. } \\   
& \displaystyle{ \left. 
+ (k-1)n_1(H^k_G)
\right) -  \left( \frac{(k-1)^2}{k(k^2 - 3)} \right)
\left(
(k^2 + k - 1)|V_2| - (k+1)|V_1|  \right. } \\  
&  \displaystyle{ \left. + 
(k+2) + n_1(H^k_G)
\right) -  \frac{k-1}{k(k^2 - 3)} } \\ 
= &
\displaystyle{
\left( \frac{k^5 - 2k^3 - 2k^2 - 3k + 6}{2k(k^2 - 3)} \right) |V_2|   -  \left( \frac{k^4 - k^3 - k^2 + 3k - 6}{2k(k^2 - 3)} \right) |V_1| } \\   \vspace{0.3cm}
&
\displaystyle{ + 
\left( \frac{k^3 - k^2 - 3k + 3}{k(k^2 - 3)} \right) n_1(H^k_G)  +  \frac{k^4 + k^3 - k^2 - 3k - 6}{2k(k^2 - 3)}
} \\ 
= &
\displaystyle{
\left( \frac{k^3 + k - 2}{2k} \right) |V_2|   -  \left( \frac{k^2 - k + 2}{2k} \right) |V_1|  + 
\left( \frac{k-1}{k} \right) n_1(H^k_G)  +  \frac{k^2 + k + 2}{2k}
} \\ 
= &
\displaystyle{
\left( \frac{k^3 + k - 2}{2k} \right) |V_2|   -  \left( \frac{k^2 - k + 2}{2k} \right) |V_1|  +  n_1(H^k_G)   -  \frac{1}{k} \left( (k-1)|V_1| - |V_2| + 1 \right) } \\   
& \displaystyle{   +  \frac{k^2 + k + 2}{2k}
} \\ 
= &
\displaystyle{
n_1(H^k_G)  +  \left( \frac{k^2 + 1}{2} \right) |V_2|   -  \left( \frac{k+1}{2} \right) |V_1|  +  \frac{k+1}{2}
}  \\ \vspace{0.2cm}
= &
n_1(H^k_G)  +  \alpha'(G)  \\ 
= &
\alpha(H).
\end{align*}
}
This completes the proof of Proposition~\ref{p:Rkrodd}. 
\end{proof}




\section{Summary}



For small values of $k \ge 3$, the results in this paper are summarized in Table~1 and Table~2 below.

{\small
\begin{center}
\begin{tabular}{|c||c|c|c|} \hline
$k$ even & \multicolumn{3}{|c|}{ $H$ has order $n$ and size $m$.} \\ \cline{2-4}
       &  $H \in \cH_k$               &  $H \in \cH_k'$                        &  $H \in \cH_k''$ \\ \hline \hline
$k=4$  &  $20\tau(H)   \le 4n  + 3m + 5$  &  $20\tau(H)   \le  4n + 3m + 3$  &  $20\tau(H)   \le  4n + 3m + 1$ \\
       &  $20\alpha(H) \ge 6n  - 3m - 5$  &  $20\alpha(H) \ge  6n - 3m - 3$  &  $20\alpha(H) \ge  6n - 3m - 1$  \\ \hline
$k=6$  &  $42\tau(H)   \le 6n  + 5m + 7$  &  $42\tau(H)   \le  6n + 5m + 3$  &  $42\tau(H)   \le  6n + 5m + 1$ \\
       &  $42\alpha(H) \ge 8n  - 5m - 7$  &  $42\alpha(H) \ge  8n - 5m - 3$  &  $42\alpha(H) \ge  8n - 5m - 1$  \\ \hline
$k=8$  &  $72\tau(H)   \le 8n  + 7m + 9$  &  $72\tau(H)   \le  8n + 7m + 3$  &  $72\tau(H)   \le  8n + 7m + 1$ \\
       &  $72\alpha(H) \ge 10n - 7m - 9$  &  $72\alpha(H) \ge 10n - 7m - 3$  &  $72\alpha(H) \ge 10n - 7m - 1$  \\ \hline
\end{tabular} \\
\2
\textbf{Table~1.} Results for small values of even $k \ge 4$
\end{center}
}


\bigskip
{\small
\begin{center}
\begin{tabular}{|c||c|} \hline
$k$ odd & $H \in \cH_k$ has order $n$ and size $m$. \\ \hline \hline
$k=3$  &  $9\tau(H)   \le 2n  + 2m + 1$  \\
       &  $9\alpha(H) \ge 4n  - 2m - 1$  \\ \hline
$k=5$  &  $55\tau(H)   \le 9n  + 8m + 2$  \\
       &  $55\alpha(H) \ge 13n  - 8m - 2$  \\ \hline
$k=7$  &  $161\tau(H)   \le 20n  + 18m + 3$  \\
       &  $161\alpha(H) \ge 26n  - 18m - 3$  \\ \hline
\end{tabular} \\
\2
\textbf{Table~2.} Results for small values of odd $k \ge 3$
\end{center}
}


We have further shown that in each of the inequality statements involving the transversal number or the independence number, there is an infinite family of hypergraphs $H \in \cH_k$ for which equality holds, implying that all the bounds are tight.




\begin{thebibliography}{99}


\bibitem{BeRa08} E. Berger and Z. Ran, A note on the edge cover number and independence number in hypergraphs. \textit{Discrete Math.} 308:2649--2654, 2008.

\bibitem{BGHR12} P. Borowiecki, F. G\"{o}ring, J. Harant, and D. Rautenbach. The potential of greed for independence. \textit{J. Graph Theory} 71(3):245--259, 2012.

\bibitem{BuHeTu12} Cs. Bujt\'{a}s, M. A. Henning and Zs. Tuza, Transversals and domination in uniform hypergraphs. \textit{European J. Combin.} 33:62--71, 2012.


\bibitem{CaHa13} Y. Caro and A. Hansberg. New approach  to the $k$-independence number of a graph. \textit{Electron.\ J.\ Combin.}\ 20(1):\#P33, 2013.


\bibitem{ChMc92} V. Chv\'{a}tal and C. McDiarmid, Small transversals in hypergraphs. \textit{Combinatorica} 12:19--26, 1992.

\bibitem{CoHeSl79} E. J. Cockayne, S. T. Hedetniemi and P. J. Slater. Matchings and transversals in hypergraphs, domination and independence-in trees. \textit{J. Combin. Theory B} 27:78--80, 1979.

\bibitem{DoHe14} M. Dorfling and M. A. Henning, Linear hypergraphs with large transversal number and maximum degree two. \textit{European J. Combin.} 36:231--236, 2014.


\bibitem{ErKoRa61} P. Erd\H{o}s, C. Ko, and R. Rado, Intersection theorems for systems of finite sets. \textit{Quart. J. Math. Oxford} 12(2):313--320, 1961.



\bibitem{Fa84} S. Fajtlowicz, Independence, clique size and maximum degree. \textit{Combinatorica} 4:35--38, 1984.

\bibitem{HaLo09} M. M. Halld\'{o}rsson and E. Losievskaja, Independent sets in bounded-degree hypergraphs. \textit{Discrete Applied Math.} 157(8):1773--1786, 2009.

\bibitem{Ha11} J. Harant, A lower bound on independence in terms of degrees. \textit{Discrete Applied Math.}
    159(10):966--970, 2011.

\bibitem{HaRa11} J. Harant and D. Rautenbach, Independence in connected graphs. \textit{Discrete Applied Math.} 159(1):79--86, 2011.

\bibitem{HeTh} C. C. Heckman and R. Thomas, Independent sets in triangle-free cubic planar graphs. \textit{J. Combin. Theory B} 96:253--275, 2006.


\bibitem{HeLo14} M. A. Henning and C. L\"{o}wenstein, A characterization of the hypergraphs that achieve equality in the Chv\'{a}tal-McDiarmid Theorem. \textit{Discrete Math.} 323:69--75, 2014.

\bibitem{HeLo16} M. A. Henning and C. L\"{o}wenstein, The Fano plane and the strong independence ratio in hypergraphs of maximum degree three. \textit{J. Graph Theory} 82(3):196--208, 2016.

\bibitem{HeLoRa12} M. A. Henning, C. L\"{o}wenstein, and D. Rautenbach, Independent sets and matchings in subcubic graphs. \textit{Discrete Math.} 312(11): 1900--1910, 2012.

\bibitem{HeLoSoYe14} M. A. Henning, C. L\"{o}wenstein, J. Southey, and A. Yeo, A new lower bound on the independence number of a graph and applications. \textit{Electron.\ J.\ Combin.}\ 21(1):\#P1.38, 2014. 

\bibitem{HeYe08} M. A. Henning and A. Yeo, Hypergraphs with large transversal number and with edge sizes at least three. \textit{J. Graph Theory} 59:326--348, 2008.

\bibitem{HeYe16+} M. A. Henning and A. Yeo, Tight lower bounds on the matching number in a graph with given maximum degree, manuscript. \arxiv{1604.05020}.

\bibitem{HiMi67} A. J. W. Hilton and E. C. Milner, Some intersection theorems for systems of finite sets. \textit{Quart. J. Math. Oxford} 18:369--384, 1967.


\bibitem{Jo84} K. F. Jones, Independence in graphs with maximum degree four. \textit{J. Combin. Theory B} 37:254--269, 1984.

\bibitem{Jo90} K. F. Jones, Size and independence in triangle-free graphs with maximum degree three. \textit{J. Graph Theory} 14:525--535, 1990.


\bibitem{JoTu09} B. K. Jose and Z. Tuza, Hypergraph domination and strong independence. \textit{Applicable Analysis \& Discrete Math.} 3(2):347--358, 2009.


\bibitem{LoPl86} L. Lov\'{a}sz and M. D. Plummer, \textit{Matching Theory}, North-Holland Mathematics Studies, vol. 121, \textit{Ann. Discrete Math.}, vol. 29, North-Holland, 1986.



\bibitem{KoMuVe14} A. Kostochka, D. Mubayi, and J. Verstra\"{e}te, On independent sets in hypergraphs. \textit{Random Struct. Alg.} 44:224--239, 2014.

\bibitem{LaCh90} F. C. Lai and G. J. Chang. An upper bound for the transversal numbers of $4$-uniform hypergraphs. \textit{J. Combin. Theory Ser. B} 50:129--133, 1990.

\bibitem{LoPeRa11} C. L\"{o}wenstein,  A. S. Pedersen, D. Rautenbach, and F. Regen, Independence, odd girth, and average degree. \textit{J. Graph Theory} 67(2):96--111, 2011.

\bibitem{Pl03} M. Plummer, Factors and Factorization. 403--430. {\em Handbook of Graph Theory} {\em ed.} J. L. Gross and J. Yellen. CRC Press, 2003, ISBN: 1-58488-092-2.

\bibitem{Pu95} W. R. Pulleyblank, Matchings and Extension. 179--232. {\em Handbook of Combinatorics} {\em ed.} R. L. Graham, M. Gr\"{o}tschel, L. Lov\'{a}sz. Elsevier Science B.V. 1995, ISBN 0-444-82346-8.


\bibitem{ThYe07} S. Thomass\'{e} and A. Yeo, Total domination of graphs and small transversals of hypergraphs. \textit{Combinatorica} 27:473--487, 2007.


\bibitem{ZhLi04} G. Zhou and Y. Li, Independence numbers of hypergraphs with sparse neighborhoods. \textit{European J. Combin.} 25:355--362, 2004.


\end{thebibliography}

\end{document}
