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