% EJC papers *must* begin with the following two lines. \documentclass[12pt]{article} \usepackage{e-jc} % 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{amsthm,amsmath,amssymb} % 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 \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\\[-0.8ex] \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 \\[-0.8ex] \small\tt andersyeo@gmail.com } \date{\dateline{xxx}{yyy}\\ \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 edges 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 \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+})} 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} \label{thmKeven} \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+})} 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)}. \] \label{p:Gkr} \end{proposition} \begin{theorem}{\rm (\cite{HeYe16+})} 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)}. \] \label{thmKodd} \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+})} 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)}. \] \label{p:Hkr} \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})} For $k \ge 2$, the hypergraph $L_k$ is the unique $k$-uniform, $2$-regular, linear, intersecting hypergraph. \label{t:intersect} \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} If $H \in \cH_k$ and $G_H$ is the dual graph of $H$, then $\alpha'(G_H) = \alpha_2(H)$. \label{ob1} \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} If $H \in \cH_k$ and $G_H$ is the dual graph of $H$, then $\alpha'(G_H) = |E(H)| - \tau(H)$. \label{p:dual} \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} 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} \label{alpha1} \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} 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)}. \] \label{p:Hkreven} \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} 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)}. \] \label{alpha1odd} \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} 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)}. \] \label{p:Hkreven} \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})} 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$. \label{lem:useful} \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} 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} \label{mainAlpha} \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{array}{rcl} \vspace{0.2cm} \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{array} \] } 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} 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)}. \] \label{p:Rkreven} \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{array}{rcl} \vspace{0.2cm} \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) } \\ \vspace{0.2cm} & & \displaystyle{ \hspace*{0.5cm} - \left( \frac{k-1}{k(k+1)} \right) \left( m(H^k_G) + n_1(H^k_G) \right) } \\ \vspace{0.5cm} & & \displaystyle{ \hspace*{1cm} - \, \, \frac{1}{k(k+1)} } \\ \vspace{0.2cm} & = & \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) } \\ \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} + n_1(H^k_G) \right) } \\ \vspace{0.5cm} & & \displaystyle{ \hspace*{1cm} - \, \, \frac{1}{k(k+1)} } \\ \vspace{0.2cm} & = & \displaystyle{ \left( \frac{k(k+2) - k}{k(k+1)} \right) \ell_1 } \\ \vspace{0.2cm} & & \displaystyle{ \hspace*{0.5cm} + \left( \frac{k^3 + k^2 + 4k + 4}{2k(k+1)} \right) \ell_2 } \\ \vspace{0.5cm} & & \displaystyle{ \hspace*{1cm} + \left( \frac{k^2 - 1}{k(k+1)} \right) n_1(H^k_G) } \\ \vspace{0.3cm} & = & \displaystyle{ \ell_1 + \left( \frac{k^2 + 4}{2k} \right) \ell_2 + \left( \frac{k-1}{k} \right) n_1(H^k_G) } \\ \vspace{0.2cm} & = & \displaystyle{ (\ell_{1,1} + \ell_{1,2}) + \left( \frac{k^2 + 4}{2k} \right) (\ell_{2,1} + \ell_{2,2}) } \\ \vspace{0.5cm} & & \displaystyle{ \hspace*{0.5cm} + \left( \frac{k-1}{k} \right) \left( (k-1)\ell_{1,1} + (k-2)\ell_{1,2} + \ell_{2,1} \right) } \\ \vspace{0.2cm} & = & \displaystyle{ \left( \frac{k^2 - k + 1}{k} \right) \ell_{1,1} + \left( \frac{k^2 -2k + 2}{2} \right) \ell_{1,2} } \\ \vspace{0.2cm} & & \displaystyle{ \hspace*{0.5cm} + \left( \frac{k^2 + 2k + 2}{2k} \right) \ell_{2,1} + \left( \frac{k^2 + 4}{2k} \right) \ell_{2,1} } \\ \vspace{0.2cm} & = & \displaystyle{ (k-1)\ell_{1,1} + (k-2)\ell_{1,2} + \ell_{2,1} } \\ \vspace{0.2cm} & & \displaystyle{ \hspace*{0.5cm} + \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}) } \\ \vspace{0.2cm} & = & \displaystyle{ n_1(H^k_G) + r + \frac{1}{2} k \ell } \\ \vspace{0.2cm} & = & \displaystyle{ n_1(H^k_G) + \alpha'(G) } \\ \vspace{0.2cm} & = & \alpha(H). \end{array} \] } \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{array}{rcl} \multicolumn{3}{l}{\vspace{0.2cm} k^2(k^2 - 3) \alpha(H) } \\ \vspace{0.2cm} & \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') \\ \vspace{0.2cm} & = & 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') \\ \vspace{0.05cm} & = & k^2(k^2 - 3)|S| + (-k^3 + k^2 + k + 1) n_1(H') \\ \vspace{0.2cm} & & \hspace*{0.5cm} + \, (k^3 - k^2 - 2)n_2(H) - (k^3 - k^2 - 2)r - k(k-1) c(H') \\ \vspace{0.05cm} & = & k^2(k^2 - 3)|S| + (-k^3 + k^2 + k + 1) (k|S| - n_1(H) - 2r) \\ \vspace{0.2cm} & & \hspace*{0.5cm} + \, (k^3 - k^2 - 2)n_2(H) - (k^3 - k^2 - 2)r - k(k-1) c(H') \\ \vspace{0.05cm} & = & (k^4 - 3k^2 - k^4 + k^3 + k^2 + k)|S| + (k^3 - k^2 - k - 1) n_1(H) \\ \vspace{0.2cm} & & \hspace*{0.5cm} + \, (k^3 - k^2 - 2)n_2(H) + (k^3 - k^2 - 2k)r - k(k-1) c(H') \\ \vspace{0.05cm} & = & k(k - 1)^2|S| + (k^3 - k^2 - k - 1) n_1(H) \\ \vspace{0.2cm} & & \hspace*{0.5cm} + \, (k^3 - k^2 - 2)n_2(H) + (k^3 - k^2 - 2k)r - k(k-1) c(H') \\ \vspace{0.05cm} & = & k(k - 1)( (k-1)|S| - c(H') - r + t_0 + 1 ) \\ \vspace{0.05cm} & & \hspace*{0.5cm} - \, k(k-1)t_0 - k(k-1) + (k^3 - k^2 - k - 1) n_1(H) \\ \vspace{0.2cm} & & \hspace*{1cm} + \, (k^3 - k^2 - 2)n_2(H) + (k^3 - 3k )r \\ \vspace{0.05cm} & \ge & k(k - 1) n_1(H) - \, k(k-1)t_0 - k(k-1) + (k^3 - k^2 - k - 1) n_1(H) \\ \vspace{0.2cm} & & \hspace*{1cm} + \, (k^3 - k^2 - 2)n_2(H) + k(k^2 - 3)r \\ \vspace{0.05cm} & = & (k^3 - 2k - 1) n_1(H) + \, (k^3 - k^2 - 2)n_2(H) \\ \vspace{0.2cm} & & \hspace*{0.5cm} + \, k(k^2 - 3)r - \, k(k-1)t_0 - k(k-1) \\ \vspace{0.05cm} & = & k(k^2 + k - 4) (n_1(H) + n_2(H)) - (k-1)^2(n_1(H) + 2n_2(H)) \\ \vspace{0.2cm} & & \hspace*{0.5cm} + \, 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{array} \] } 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{array}{rcl} \vspace{0.05cm} k(k^2 - 3) \alpha(H) & \ge & (k^2 + k - 4) n(H) - (k-1)^2 m(H) \\ \vspace{0.2cm} & & \hspace*{0.5cm} + \, (k^2 - 3)r - \, (k-1)^2r - (k-1) \\ \vspace{0.2cm} & = & (k^2 + k - 4) n(H) - (k-1)^2 m(H) + 2(k-2)r - (k-1) \\ \vspace{0.2cm} & \ge & k(k^2 + k - 4) n(H) - (k-1)^2 m(H) + k-3 \\ \vspace{0.2cm} & \ge & k(k^2 + k - 4) n(H) - (k-1)^2 m(H) \\ \vspace{0.2cm} & > & k(k^2 + k - 4) n(H) - (k-1)^2 m(H) - (k-1). \end{array} \] } 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} 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)}. \] \label{p:Rkrodd} \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{array}{rcl} \multicolumn{3}{l}{\vspace{0.2cm} \displaystyle{ \frac{(k^2 + k - 4) n - (k-1)^2 m - (k-1)}{k(k^2 - 3)}}} \\ \vspace{0.15cm} & = & \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) } \\ \vspace{0.15cm} & & \hspace*{0.5cm} \displaystyle{ - \, \left( \frac{(k-1)^2}{k(k^2 - 3)} \right) \left( m(H^k_G) + n_1(H^k_G) \right) } \\ \vspace{0.3cm} & & \hspace*{1.25cm} \displaystyle{ - \, \frac{k-1}{k(k^2 - 3)} } \\ \vspace{0.15cm} & = & \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) + (k-1)n_1(H^k_G) \right) } \\ \vspace{0.15cm} & & \hspace*{0.5cm} \displaystyle{ - \, \left( \frac{(k-1)^2}{k(k^2 - 3)} \right) \left( (k^2 + k - 1)|V_2| - (k+1)|V_1| + (k+2) + n_1(H^k_G) \right) } \\ \vspace{0.3cm} & & \hspace*{1.25cm} \displaystyle{ - \, \frac{k-1}{k(k^2 - 3)} } \\ \vspace{0.15cm} & = & \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} & & \hspace*{0.75cm} \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)} } \\ \vspace{0.3cm} & = & \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} } \\ \vspace{0.3cm} & = & \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) \, + \, \frac{k^2 + k + 2}{2k} } \\ \vspace{0.3cm} & = & \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) \\ \vspace{0.3cm} & = & \alpha(H). \end{array} \] } \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} } %\begin{center} %\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. \medskip \begin{thebibliography}{10} \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{org/abs/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}