% EJC papers *must* begin with the following two lines. 
\documentclass[12pt]{article}
\usepackage{e-jc}

% Please remove all commands that change parameters such as
%    margins or page sizes.

% Packages amssymb and amsthm are already loaded. 
% We recommend these AMS packages:
\usepackage{amsmath,amssymb}
% We recommend the graphicx package for importing figures:
\usepackage{graphicx}
% Use this command to create hyperlinks (optional and recommended):
\usepackage[colorlinks=true,citecolor=black,linkcolor=black,urlcolor=blue]{hyperref}

% Theorem-like environments that are declared in the style file are:
% theorem, lemma, corollary, proposition, fact, observation, claim,
% definition, example, conjecture, open, problem, question, remark, note

%%%%%%%%%%%%%METADATA%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

% Give the submission and acceptance dates in the format shown.
% The editors will insert the publication date in the third argument.
\dateline{Jan 1, 2018}{Jan 2, 2018}{TBD}

% Give one or more subject codes separated by commas.
% Codes are available from http://www.ams.org/mathscinet/freeTools.html
\MSC{05C88, 05C89}

% Uncomment exactly one of the following copyright statements.  Alternatively,
% you can write your own copyright statement subject to the approval of the journal.
% See https://creativecommons.org/licenses/ for a full explanation of the 
% Creative Commons licenses.
%
% We strongly recommend CC BY-ND or CC BY. Both these licenses allow others
% to freely distribute your work while giving credit to you. The difference between
% them is that CC BY-ND only allows distribution unchanged and in whole, while
% CC BY also allows remixing, tweaking and building upon your work.  
%
%    One author:
%\Copyright{The author.}
%\Copyright{The author. Released under the CC BY license (International 4.0).}
%\Copyright{The author. Released under the CC BY-ND license (International 4.0).}
%    More than one author:
%\Copyright{The authors.}
%\Copyright{The authors. Released under the CC BY license (International 4.0).}
\Copyright{  The authors. Released under the CC BY-ND license (International 4.0).}

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


\def \nG {n_{_G}}
\def \mG {m_{_G}}
\def \nH {n_{_H}}
\def \mH {m_{_H}}
\def \nHp {n_{_{H'}}}
\def \mHp {m_{_{H'}}}
\def \nF {n_{_F}}
\def \mF {m_{_F}}

\newcommand{\3}{ \vspace{0.3cm} }
\newcommand{\2}{ \vspace{0.2cm} }
\newcommand{\1}{ \vspace{0.1cm} }

\newcommand{\cI}{{\cal I}}
\newcommand{\cH}{{\cal H}}

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

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

% If needed, include a line break (\\) at an appropriate place in the title.
\title{On upper transversals in $3$-uniform hypergraphs}

% Input author, affiliation, address and support information as follows;
% The address should include the country, but does not have to include
%    the street address. Give at least one email address.

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

\begin{document}

\maketitle

% E-JC papers must include an abstract. The abstract should consist of a
% succinct statement of background followed by a listing of the
% principal new results that are to be found in the paper. The abstract
% should be informative, clear, and as complete as possible. Phrases
% like "we investigate..." or "we study..." should be kept to a minimum
% in favor of "we prove that..."  or "we show that...".  Do not
% include equation numbers, unexpanded citations (such as "[23]"), or
% any other references to things in the paper that are not defined in
% the abstract. The abstract may be distributed without the rest of the
% paper so it must be entirely self-contained.  Try to include all words
% and phrases that someone might search for when looking for your paper.

\begin{abstract}
A set $S$ of vertices in a hypergraph $H$ is a transversal if it has a nonempty intersection with every edge of $H$. The upper transversal number $\Upsilon(H)$ of $H$ is the maximum cardinality of a minimal transversal in $H$. We show that if $H$ is a connected $3$-uniform hypergraph of order~$n$, then $\Upsilon(H) > 1.4855 \sqrt[3]{n} - 2$. For $n$ sufficiently large, we construct infinitely many connected $3$-uniform hypergraphs, $H$, of order~$n$ satisfying $\Upsilon(H) < 2.5199 \sqrt[3]{n}$. We conjecture that $\displaystyle{
\sup_{n \to \infty}  \, \left( \inf  \frac{ \Upsilon(H) }{ \sqrt[3]{n} } \right) = \sqrt[3]{16} }$, where the infimum is taken over all connected $3$-uniform hypergraphs $H$ of order~$n$.
\end{abstract}

\section{Introduction}

In this paper, we continue the study of transversals in hypergraphs. Hypergraphs are systems of sets which are conceived as natural extensions of graphs.  A \emph{hypergraph} $H = (V(H),E(H))$ is a
finite set $V(H)$ of elements, called \emph{vertices}, together with a finite multiset $E(H)$ of nonempty subsets of $V(H)$, called \emph{hyperedges} or simply \emph{edges}.
%
A $k$-\emph{edge} in $H$ is an edge of size~$k$. The hypergraph $H$ is $k$-\emph{uniform} if every edge of $H$ is a $k$-edge. Every $2$-uniform hypergraph is a graph. 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$. The minimum and maximum degrees among the vertices of $H$ is denoted by $\delta(H)$ and $\Delta(H)$, respectively.


A subset $T$ of vertices in a hypergraph $H$ is a \emph{transversal} (also called  \emph{hitting set} or \emph{vertex cover} or \emph{blocking set} in many papers) if $T$ has a nonempty intersection with every edge of $H$. A vertex \emph{hits}
or \emph{covers} an edge if it belongs to that edge.  The \emph{transversal number} $\tau(H)$ of $H$ is the minimum size of a transversal in $H$, while the \emph{upper transversal number} $\Upsilon(H)$ of $H$ is the maximum cardinality of a minimal transversal in $H$. In hypergraph theory the concept of transversal is  fundamental and well studied. The major monograph \cite{Berge89} of hypergraph theory gives a detailed introduction to this topic. Transversals in hypergraphs are well studied in the literature (see, for example,~\cite{BuHeTu12,BuHeTuYe14,HeLo14,HeYe13,LoWa13} for recent results and further references).



A set $S$ of vertices in a graph $G$ is a \emph{dominating set} of $G$ if each vertex in $V(G) \setminus S$ has a neighbor in $S$. A set is \emph{independent} if no two vertices in it are adjacent.  An \emph{independent dominating set} of $G$ is a set that is both dominating and independent in $G$. The \emph{independent domination number} of $G$, denoted by~$i(G)$, is the minimum cardinality of an independent dominating set. Domination is well studied in graph theory and we refer the reader to the monographs \cite{DomBook1, DomBook2} which detail and survey many results on the topic. A survey of known results on independent domination in graphs can be found in~\cite{GoHe13}.

\section{Main Results}


We have two immediate aims in this paper. First to provide a sharp lower bound on the upper transversal number of graphs. Secondly to present a lower bound on the upper transversal number of  $3$-uniform hypergraphs, and to show that this bound is a sense asymptotically best possible. More precisely, we prove the following results, where we use the notation $\nH =|V(H)|$ to denote the \emph{order} of $H$. Proofs of Theorem~\ref{t:lowbd1} and Theorem~\ref{t:lowbd2} are given in Section~\ref{S:lowbd1} and Section~\ref{S:lowbd2}, respectively.

\begin{theorem}
\label{t:lowbd1}
If $H$ is a connected graph with $\delta(H) \ge \delta$, then
\[
\Upsilon(H) \ge  2\sqrt{\delta \nH} - 2 \delta,
\]
and this bound is sharp.
\end{theorem}




\begin{theorem}
\label{t:lowbd2}
If $H$ is a connected $3$-uniform hypergraph, then
\[
\Upsilon(H) > \sqrt[3]{\frac{\nH}{0.305}} -2  > 1.4855  \sqrt[3]{\nH} - 2.
\]

\noindent
Further, there exist infinitely many connected $3$-uniform hypergraphs $H$ of sufficiently large order~$\nH$ satisfying
\[
\Upsilon(H) < \sqrt[\leftroot{-3}\uproot{3}3]{   16 \cdot  \nH}   < 2.52 \sqrt[3]{\nH}.
\]
\end{theorem}




\section{Proof of Theorem~\ref{t:lowbd1}}
\label{S:lowbd1}


Recall that a transversal in a graph is a set of vertices covering all the edges of the graph, where a vertex covers an edge if it is incident with it. Theorem~\ref{t:lowbd1} can be restated as follows.

\medskip
\noindent \textbf{Theorem~\ref{t:lowbd1}}. \emph{If $G$ is a connected graph of order $n$ with $\delta(G) \ge \delta$, then $\Upsilon(G) \ge  2\sqrt{\delta n} - 2\delta$, and this bound is sharp. } \\

In order to prove Theorem~\ref{t:lowbd1}, we first establish a relationship between the upper transversal number and independent domination number of a graph.

\begin{theorem}
\label{t:relate}
If $G$ is an isolate-free graph on $n$ vertices, then $i(G) + \Upsilon(G) = n$.
\end{theorem}
\begin{proof} Let $G$ be an isolate-free graph. Let $S$ be an independent dominating set in $G$ of minimum cardinality, and so $|S| = i(G)$. Let $T = V(G) \setminus S$ and note that $T$ is a transversal in $G$ as $S$ is an independent set. Since every vertex in $T$ has a neighbor in $S$, we furthermore note that $T$ is a minimal transversal, which implies that $\Upsilon(G) \ge |T| = n - |S| = n - i(G)$.

Conversely, let $T$ be a minimal transversal in $G$ of maximum cardinality, and so $|T| = \Upsilon(G)$.
Let $S = V(G) \setminus T$ and note that $S$ is an independent set as $T$ is a transversal. Since $T$ is a minimal transversal, every vertex in $T$ has a neighbor in $S$, implying that $S$ is an independent dominating set in $G$. Therefore, $i(G) \leq |S| = n - |T| = n - \Upsilon(G)$. Consequently, $i(G) + \Upsilon(G) = n$.
\end{proof}






\medskip
Favaron~\cite{Fa88} was the first to prove the
following upper bound on the independent domination of a graph with no isolated vertex: If $G$ is an isolate-free graph of order~$n$, then $i(G) \le n + 2 - 2\sqrt{n}$. We remark that this result also follows from a result due to Bollob\'{a}s and
Cockayne~\cite{BoCo79} (and was also proved in~\cite{GiVe95}).
Sun and Wang~\cite{SW99idom} proved the following more general result, which was originally posed as a conjecture by Favaron~\cite{Fa88} and was proved for
$\delta=2$ by Glebov and Kostochka~\cite{GlKo98}.

\begin{theorem}{\rm (\cite{SW99idom})} \label{t:FavConj}
If $G$ is a graph of order $n$ with $\delta(G) \ge \delta$, then $i(G) \le n + 2\delta - 2 \sqrt{\delta n}$.
\end{theorem}


Theorem~\ref{t:lowbd1} is an immediate consequence of Theorem~\ref{t:relate} and Theorem~\ref{t:FavConj}. That this bound is sharp, follows from a result of Favaron~\cite{Fa88} who showed that for every
positive integer $\delta$, the bound in
Theorem~\ref{t:FavConj} is attained for infinitely many graphs. The same graphs achieve equality in the bound for Theorem~\ref{t:lowbd1}. For example, for $c \ge 2$, let $G_c$ be the connected graph constructed as follows. Let $F_c$ be the complete graph of order~$c$, and so $F_c \cong K_c$. For every vertex $v$ of $F_c$, add $c-1$ new vertices $v_1, \ldots, v_{c-1}$ and add the $c-1$ edges $vv_i$ for all $i \in [c-1]$. Let $G = G_c$ denote the resulting graph of order $n = c^2$. We note that all the new vertices added to $F_c$ have degree~$1$ in $G_c$. Every transversal in $G_c$ must contain all except possibly one vertex of $F_c$ in order to cover all the edges of $F_c$. If a minimal transversal in $G_c$ contains exactly $c-1$ vertices of $F_c$, say all vertices of $F_c$ except for $v$, then the transversal contains exactly $c-1$ vertices not in $F_c$, namely $v_1, \ldots, v_{c-1}$, in order to cover the edges $vv_i$ for all $i \in [c-1]$. Such a minimal transversal therefore has size exactly $2(c-1)$. If a minimal transversal in $G_c$ contains all $c$ vertices of $F_c$, then it contains no other vertex of $G_c$ and therefore has size exactly $c$. Therefore, the connected graph $G$ of order $n = c^2$ satisfies $\Upsilon(G) = \max\{2(c-1),c\} = 2(c-1) = 2\sqrt{n} - 2$, noting that $c \ge 2$. Thus, the bound of Theorem~\ref{t:lowbd1} when $\delta = 1$ is sharp.
For every $\delta \geq 2$ one can similarly show that Theorem~\ref{t:lowbd1} is tight.

As a special case of Theorem~\ref{t:lowbd1}, if $H$ is a connected $2$-uniform  hypergraph of order~$n \ge 2$, then $\Upsilon(H) \ge  2\sqrt{n} - 2$. When $n \ge 3$, we observe that $2\sqrt{n} - 2 \ge \sqrt{\frac{1}{2}n}$. Further, we observe that when $n = 2$, $\Upsilon(H) = 1 = \sqrt{\frac{1}{2}n}$. Thus, as an immediate consequence of  Theorem~\ref{t:lowbd1} we observe that if $H$ is a connected graph, then $\Upsilon(H) \ge \sqrt{\frac{1}{2} \nH }$.






\section{Proof of Theorem~\ref{t:lowbd2}}
\label{S:lowbd2}

We first prove the lower bound in Theorem~\ref{t:lowbd2}.

\begin{theorem}
\label{t:lowbdproof}
If $H$ is a connected $3$-uniform hypergraph, then $\Upsilon(H) > \sqrt[3]{\frac{\nH}{0.305}} -2$.
\end{theorem}
\begin{proof} Let $H$ be a connected $3$-uniform hypergraph of order $\nH$ and let $T$ be a minimal transversal of maximum size. Let $T=\{t_1,t_2,\ldots,t_c\}$, and so $\Upsilon(H) = |T| = c$. For all $i$ and $j$ where $1 \le i < j \le c$ and for all $k \in [c]$, define $Z_{i,j}$, $E_k$ and $Y_k$ as follows.
\[
\begin{array}{ccl}
Z_{i,j} & = & \{ v \in V(H) \setminus T \, \mid \, \{t_i,t_j,v\} \in E(H) \} \1 \\
E_k & = & \{ e \in E(H) \, \mid \, V(e) \cap T = \{t_k\} \} \1 \\
Y_k & = & V(E_k) \setminus \{t_k\}.
\end{array}
\]

We note that $Y_k \subseteq V(H) \setminus T$ for each $k \in [c]$. Let $Q \subseteq V(T)$ be a minimum set of vertices in $T$ that covers all edges that are completely within $T$ (i.e., all edges $e$ with $V(e) \subseteq V(T)$). Possibly, $Q=\emptyset$.  Let $q = |Q|$. Renaming vertices of $T$ if necessary, we may assume that $Q = \{t_1,\ldots,t_q\}$. Let

\[
\begin{array}{ccl}
\cI & = & \{(i,j) \mid 1 \le i < j \le c\} \1 \\
\cI_{q} & = & \{(i,j) \mid 1 \le i \le q \mbox{ and } i < j \le c\} \1 \\
\cI_{> q} & = & \{(i,j) \mid q+1 \le i < j \le c\}.
\end{array}
\]


We note that $\cI = \cI_{q} \cup \cI_{> q}$. We proceed further with the following claims.


\begin{claim}
\label{c:claim1}
$|Z_{i,j}| \le c-q$ for all $(i,j) \in \cI$.
\end{claim}
\begin{proof}  Suppose, to the contrary, that $|Z_{i,j}| > c-q$ for some $i$ and $j$, where $1 \le i < j \le c$. Let $R = V(H) \setminus \{t_i,t_j\}$. Clearly, $R$ is a transversal in $H$ as it contains all vertices in $H$ except two and $H$ is $3$-uniform. Let $R'$ be obtained from $R$ by removing vertices until we get a minimal transversal in $H$. We note that $Z_{i,j} \subseteq R'$ since each vertex $z \in Z_{i,j}$ is needed in order to cover the edge $\{t_i,t_j,z\}$. Further, $R'$ contains at least $q$ vertices from $T$ in order to cover the edges that are contained entirely within $T$. Hence, $\Upsilon(H) \ge |R'| \ge |Z_{i,j}| + q > c$, contradicting the fact that $\Upsilon(H) = c$.
\end{proof}



\begin{claim}
\label{c:claim2}
$\left| \bigcup\limits_{(i,j) \in \cI_{> q}} Z_{i,j} \right| \le c-q$.
\end{claim}
\begin{proof} Suppose, to the contrary, that
\[
| \bigcup\limits_{(i,j) \in \cI_{> q}} Z_{i,j}| >  c-q.
\]
Let $R = V(H) \setminus \{t_{q+1},\ldots,t_c\}$. By definition of the set $Q$, every edge of $H$ intersects $\{t_{q+1},\ldots,t_c\}$ in at most two vertices, implying that $R$ is a transversal in $H$. Let $R'$ be obtained from $R$ by removing vertices from $R$ until we get a minimal transversal in $H$. We note that \[
\bigcup\limits_{(i,j) \in \cI_{> q}} Z_{i,j} \subseteq R'\] since each vertex $z \in Z_{i,j}$ where $q+1 \le i < j \le c$ is needed in order to cover the edge $\{t_i,t_j,z\}$. Further, $R'$ contains at least $q$ vertices from $Q$ in order to cover the edges that are contained entirely within $T$. Hence,
\[
\Upsilon(H) \ge |R'|  \ge \, | \bigcup\limits_{(i,j) \in \cI_{> q}} Z_{i,j}| + q > c,
\]
contradicting the fact that $\Upsilon(H) = c$.
\end{proof}


\begin{claim}
\label{c:claim3}
$\left| \bigcup\limits_{(i,j) \in \cI} Z_{i,j} \right|  \le \left( {c \choose 2} - {c-q \choose 2} \right) (c-q) + (c-q)$.
\end{claim}
\begin{proof} As observed earlier, $\cI = \cI_{q} \cup \cI_{> q}$.  By Claim~\ref{c:claim1}, $|Z_{i,j}| \le c-q$ for all $(i,j) \in \cI_q$. Since there are ${c \choose 2} - {c-q \choose 2}$ pairs $(i,j) \in \cI_{q}$ where $1 \le i \le q$ and $i < j \le c$, we note by Claim~\ref{c:claim1} and Claim~\ref{c:claim2} that
\[
\left| \bigcup\limits_{(i,j) \in \cI} Z_{i,j} \right| \le \left| \bigcup\limits_{(i,j) \in \cI_{q}} Z_{i,j}\right| + \left| \bigcup\limits_{(i,j) \in \cI_{> q}} Z_{i,j} \right|  \le \left( {c \choose 2} - {c-q \choose 2} \right) (c-q) + (c-q). %\hspace*{0.5cm} \mbox{\tiny ($\Box$)}
\]
\end{proof}


\begin{claim}
\label{c:claim4}
$|Y_{i}| \le (\frac{c-q}{2} + 1)^2$ for all $i \in [c]$.
\end{claim}
\begin{proof} Suppose, to the contrary, that $|Y_{i}| > ((c-q)/2 + 1)^2$ for some $i \in [c]$. Let $H'$ be the graph with vertex set $V(H') = Y_i$ and with edge set $E(H') = \{ e \setminus \{t_i\} \mid e \in E_i\}$. By Theorem~\ref{t:lowbd1}, there is a minimal transversal $T'$ in $H'$, such that $|T'| \ge 2(\sqrt{|Y_i|} -1)$. Let $R' = T' \cup (T \setminus \{t_i\})$ and note that $R'$ is a transversal in $H$. Let $R''$ be obtained from $R'$ by removing vertices from $R'$ until we get a minimal transversal in $H$. In order to cover the edges $E_i$, we must have $T' \subseteq R''$, noting that $T'$ is a minimal transversal in $H'$. Further, $R'$ contains at least $q$ vertices from $T \setminus \{t_i\}$ in order to cover the edges that are contained entirely within $T$. Therefore,
\[
\Upsilon(H) \ge |R''| \ge |T'|+q
       \ge  2(\sqrt{|Y_i|} -1)+q
       >   2\left(\sqrt{\left(\frac{c-q}{2} + 1\right)^2} - 1 \right) +q
       =  c
\]

\noindent
contradicting the fact that $\Upsilon(H) = c$.
\end{proof}

\medskip
Since $T$ is a transversal in $H$, we note that
\begin{equation}
\label{Eq3}
V(H) = T \cup \left(\bigcup_{(i,j) \in \cI}  Z_{i,j} \right) \cup \left(\bigcup_{i=1}^c Y_i\right).
\end{equation}

Let $\beta$ be defined such that $(c-q) = \beta c$. We note that $0 \le \beta \le 1$. By Equation~(\ref{Eq3}) and by Claim~\ref{c:claim3} and~\ref{c:claim4}, we therefore get the following.

\[
\begin{array}{rcl}
\nH & \le & \displaystyle{|T| + \sum_{i,j} |Z_{i,j}| + \sum_i |Y_i|} \2 \\
& \le & c + \left( {c \choose 2} - {c-q \choose 2} \right) (c-q) + (c-q) +  c (\frac{c-q}{2} + 1)^2 \2 \\
& \le & c + \left( \frac{c(c-1)}{2} - \frac{\beta c (\beta c -1)}{2} \right) \beta c + \beta c +  c (\frac{\beta c}{2} + 1)^2 \2 \\
   & = & c + \frac{1}{2} \left( c^2 - c - \beta^2 c^2 + \beta c \right) \beta c + \beta c +  c (\frac{\beta^2 c^2}{4} + \beta c + 1) \2 \\
   & = & c^3 \left( \frac{\beta}{2} - \frac{\beta^3}{2} + \frac{\beta^2}{4} \right)
         + c^2 \left( \frac{-\beta}{2} + \frac{\beta^2}{2} + \beta \right)
         + c (2 + \beta) \2 \\
   & = & \frac{c^3}{4} \left(- 2\beta^3 + \beta^2 + 2 \beta \right)
         + c^2 \left( \frac{\beta}{2} + \frac{\beta^2}{2} \right)
         + c (2 + \beta).
\end{array}
\]
Let
\[
f(\beta) = - 2\beta^3 + \beta^2 + 2 \beta.
\]


The maximum value of $f(\beta)$ when $0 \le \beta \le 1$ is obtained when $\beta = (1+\sqrt{13})/6$, noting that $0 = f'(\beta) = -6\beta^2 + 2\beta + 2$ implies $\beta = (1 \pm \sqrt{13})/6$. Therefore, $f(\beta) \le f\left(\frac{1+\sqrt{13}}{6}\right) < 1.22$
for all $0 \le \beta \le 1$, implying by our earlier observations that

\[
\begin{array}{rcl}
\nH & \le & \frac{c^3}{4} \left(- 2\beta^3 + \beta^2 + 2 \beta \right) + c^2 \left( \frac{\beta}{2} + \frac{\beta^2}{2} \right)
         + c (2 + \beta) \2 \\
& < & \frac{c^3}{4} \left( 1.22 \right) + c^2 \left( \frac{1}{2} + \frac{1}{2} \right)
         + c (2 + 1) \2 \\
& = & 0.305 c^3 + c^2 + 3c \2 \\
& < & 0.305 (c+2)^3, \\
\end{array}
\]
and so $\Upsilon(H) = c > \sqrt[3]{\frac{\nH}{0.305}} - 2$. This completes the proof of Theorem~\ref{t:lowbdproof}.
\end{proof}


\medskip
We remark that $\sqrt[3]{\frac{1}{0.305}} > 1.48559$, and so as a consequence of Theorem~\ref{t:lowbdproof}, if $H$ is a connected $3$-uniform hypergraph of order~$n \ge 3$, then $\Upsilon(H) > 1.4855 \sqrt[3]{n} - 2$. When $n \ge 17$, we observe that $1.4855 \sqrt[3]{n} - 2 > \sqrt[3]{\frac{1}{3}n}$. Further, we observe that when $n = 3$, $\Upsilon(H) = 1 = \sqrt[3]{\frac{1}{3}n}$, while for $4 \le n \le 16$, $\Upsilon(H) \ge 2 > \sqrt[3]{\frac{1}{3}n}$. Thus, as an immediate consequence of  Theorem~\ref{t:lowbdproof}, we observe that if $H$ is a connected $3$-uniform hypergraph, then $\Upsilon(H) \ge \sqrt[3]{\frac{\nH}{3} }$. %
We show next that the lower bound in Theorem~\ref{t:lowbdproof} is asymptotically best possible.



\begin{proposition}
\label{p:k1r3}
For all $n \ge 3$, there exists a connected $3$-uniform hypergraph $H = H_n$ of order $\nH = \frac{1}{2}(n^3-n^2+2n)$ such that
\[
\Upsilon(H) = \sqrt[\leftroot{-3}\uproot{3}3]{   16(1 - \epsilon_n) \cdot  \nH} \hspace*{0.5cm} \mbox{where} \hspace*{0.5cm}
\epsilon_n = \frac{2n^2 - n + 1}{n^3 - n^2 + 2n}.
\]
\end{proposition}
\begin{proof} For each $n \ge 3$, let $H_n$ be the connected $3$-uniform hypergraph constructed as follows. Let $F_n$ be the complete $3$-uniform hypergraph on $n$ vertices, and so $F_n$ has ${n \choose 3}$ hyperedges corresponding to the $3$-element subsets of $V(F_n)$. Thus, every set of three vertices in $F_n$ belongs to a $3$-edge of $F_n$. Let $S = V(F_n)$. For every pair of vertices, $\{x,y\}$, in $S$ add $n$ new vertices, $v_1^{xy}, v_2^{xy}, \dots , v_n^{xy}$ to $F_n$ and add the $n$ hyperedges $\{x,y,v_1^{xy}\}, \{x,y,v_2^{xy}\}, \ldots, \{x,y,v_n^{xy}\}$. Let $H = H_n$ denote the resulting hypergraph of order \[
\nH = {n \choose 2}n + |V(F_n)| = \frac{n^2(n-1)}{2} + n = \frac{1}{2}(n^3-n^2+2n).
\]


We note that all the new vertices added to $F_n$ have degree~$1$ in $H_n$. Every transversal in $H_n$ must contain all $n$ vertices in $F_n$, except for possibly two vertices in order to cover all the edges in $F_n$. Every minimal transversal in $H_n$ contains either exactly $n-1$ vertices of $S$ (and no other vertex in $H_n$) or exactly $n - 2$ vertices of $S$, say all vertices of $S$ except for the vertices $x$ and $y$, and exactly $n$ vertices not in $S$, namely $v_1^{xy}, v_2^{xy}, \dots , v_n^{xy}$, in order to cover the edges $\{x,y,v_1^{xy}\}, \{x,y,v_2^{xy}\}, \ldots, \{x,y,v_n^{xy}\}$, implying that
\[
\Upsilon(H_n) = (|S| - 2) + n = 2(n-1).
\]

Therefore, letting $\epsilon_n = \frac{2n^2 - n + 1}{n^3 - n^2 + 2n}$, we note that the connected $3$-uniform hypergraph $H = H_n$ satisfies

\[
\begin{array}{lcl}
\Upsilon(H) & = & 2(n-1) \2 \\
& = &  \displaystyle{ \sqrt[\leftroot{-3}\uproot{3}3]{  8 \cdot (n-1)^3}  } \3 \\
& = & \displaystyle{ \sqrt[\leftroot{-3}\uproot{3}3]{   16 \cdot \frac{(n-1)^3}{2\nH} \cdot  \nH}  }  \3 \\
& = & \displaystyle{ \sqrt[\leftroot{-3}\uproot{3}3]{   16\left( \frac{n^3-3n^2+3n-1}{n^3-n^2+2n}\right) \cdot  \nH}  } \3 \\
& = & \displaystyle{ \sqrt[\leftroot{-3}\uproot{3}3]{   16\left(1 - \frac{2n^2 - n + 1}{n^3 - n^2 + 2n}\right) \cdot  \nH}  } \3 \\
& = &  \displaystyle{ \sqrt[\leftroot{-3}\uproot{3}3]{   16(1 - \epsilon_n) \cdot  \nH} }.  \hspace*{0.5cm} 
\end{array}
\]
\end{proof}


\medskip
Using the notation introduced in the statement of Proposition~\ref{p:k1r3}, we note that $\frac{2}{3} = \epsilon_3  > \epsilon_4 > \epsilon_5 > \cdots$ and that $\epsilon_n \to 0$ as $n \to \infty$. In particular, we note that given any $\epsilon > 0$, we can choose $n$ sufficiently large so that $\epsilon_n < \epsilon$, implying by Proposition~\ref{p:k1r3} that the connected $3$-uniform hypergraph $H = H_n$ satisfies
\[
\sqrt[\leftroot{-3}\uproot{3}3]{   16(1 - \epsilon) \cdot  \nH} < \Upsilon(H) < \sqrt[\leftroot{-3}\uproot{3}3]{   16 \cdot  \nH}
\]





\section{Closing Conjectures}

We pose the following conjecture. As observed earlier, Conjecture~\ref{c:upperk} is true for $k \in \{2,3\}$. However, we have yet to settle the conjecture for $k \ge 4$.

\begin{conjecture}
\label{c:upperk}
For $k \ge 2$, if $H$ is a connected $k$-uniform hypergraph, then $\displaystyle{ \Upsilon(H) \ge \sqrt[k]{\frac{\nH}{k} }}$.
%\[
%\Upsilon(H) \ge \sqrt[k]{\frac{\nH}{k} }.
%\]
\end{conjecture}



Let $\cH_n$ denote the class of all connected $3$-uniform hypergraphs of order~$n$. As observed earlier, Proposition~\ref{p:k1r3} implies that for $n$ sufficiently large there exist hypergraphs $H \in \cH_n$ such that
\[
\frac{\Upsilon(H)}{\sqrt[3]{n}} > \sqrt[\leftroot{-3}\uproot{3}3]{   16(1 - \epsilon) }
\]

\noindent
for any given $\epsilon > 0$. We close with the following conjecture that we have yet to settle.

\begin{conjecture}
\label{conj3}
$\displaystyle{
\sup_{n \to \infty}  \, \left( \inf_{H \in \cH_n}  \frac{ \Upsilon(H) }{ \sqrt[3]{n} } \right) = \sqrt[3]{16}. }$
\end{conjecture}

\medskip
\begin{thebibliography}{20}

\bibitem{Berge89} C. Berge, Hypergraphs -- Combinatorics of Finite Sets. North-Holland, 1989.
    

\bibitem{BoCo79}  B. Bollob{\'a}s and E. J.  Cockayne. \newblock  Graph-theoretic parameters concerning domination, independence, and  irredundance. \newblock \emph{J. Graph Theory}, 3:241--249, 1979.


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

\bibitem{BuHeTuYe14}  Cs. Bujt\'{a}s, M. A. Henning, Zs. Tuza, and A. Yeo. \newblock  Total transversals and total domination in uniform hypergraphs. \newblock \emph{Electron. J. Combin.}, 21(2) \#P2.24, 22~pp, 2014.

\bibitem{Fa88} O.~Favaron. \newblock Two relations between the parameters of independence and irredundance. \newblock \emph{Discrete Math.}, 70:17--20, 1988.

\bibitem{GiVe95} J. Gimbel and P. D. Vestergaard. \newblock Inequalities for total matchings of graphs. \newblock \emph{Ars Combin.}, 39:109--119, 1995.

\bibitem{GlKo98} N. I. Glebov and A. V. Kostochka. \newblock On the independent domination number of graphs with given minimum degree. \newblock \emph{Discrete Math.}, 118:261--266, 1998.

\bibitem{GoHe13} W. Goddard and M. A. Henning. \newblock Independent domination in graphs: A survey and recent results. \newblock \emph{Discrete Math.}, 313:839--854, 2013.


\bibitem{DomBook1}  T. W. Haynes, S. T. Hedetniemi, P. J. Slater (eds). \emph{Fundamentals of Domination in Graphs}, Marcel Dekker, Inc. New York, 1998.

\bibitem{DomBook2}  T. W. Haynes, S. T. Hedetniemi, P. J. Slater (eds). \emph{Domination in Graphs: Advanced Topics}, Marcel Dekker, Inc. New York, 1998.



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



\bibitem{HeYe13} M. A. Henning and A. Yeo. \newblock Hypergraphs with large transversal number. \newblock \emph{Discrete Math.}, 313:959--966, 2013.


\bibitem{LoWa13} Z. Lonc and K. Warno. \newblock Minimum size transversals in uniform hypergraphs. \newblock \emph{Discrete Math.},  313:2798--2815, 2013.


\bibitem{SW99idom} L. Sun and J, Wang. \newblock An upper bound for the independent domination number. \newblock \emph{J. Combin. Theory, Ser. B},  76:240--246, 1999.

\end{thebibliography}


\end{document}
