Balloons, cut‐edges, matchings, and total domination in regular graphs of odd degree

A balloon in a graph G is a maximal 2‐edge‐connected subgraph incident to exactly one cut‐edge of G . Let b ( G ) be the number of balloons, let c ( G ) be the number of cut‐edges, and let α′( G ) be the maximum size of a matching. Let \documentclass{article}\usepackage{amssymb}\usepackage{amsbsy}\usepackage[mathscr]{euscript}\footskip=0pc\pagestyle{empty}\begin{document}${\mathcal{F}}_{{{n}},{{r}}}$\end{document} be the family of connected (2 r +1)‐regular graphs with n vertices, and let \documentclass{article}\usepackage{amssymb}\usepackage{amsbsy}\usepackage[mathscr]{euscript}\footskip=0pc\pagestyle{empty}\begin{document}${{b}}={{max}}\{{{b}}({{G}}): {{G}}\in {\mathcal{F}}_{{{n}},{{r}}}\}$\end{document} . For \documentclass{article}\usepackage{amssymb}\usepackage{amsbsy}\usepackage[mathscr]{euscript}\footskip=0pc\pagestyle{empty}\begin{document}${{G}}\in{\mathcal{F}}_{{{n}},{{r}}}$\end{document} , we prove the sharp inequalities c ( G )⩽[ r ( n −2)−2]/(2 r 2 +2 r −1)−1 and α′( G )⩾ n /2− rb/ (2 r +1). Using b ⩽[(2 r −1) n +2]/(4 r 2 +4 r −2), we obtain a simple proof of the bound\documentclass{article}\usepackage{amssymb}\usepackage{amsbsy}\usepackage[mathscr]{euscript}\footskip=0pc\pagestyle{empty}\begin{document}\begin{eqnarray*}\alpha\prime(G)\ge\frac{n}{2}-\frac{r}{2}\frac{(2r-1)n+2}{(2r+1)(2r^2+2r-1)}\end{eqnarray*}\end{document} proved by Henning and Yeo. For each of these bounds and each r , the approach using balloons allows us to determine the infinite family where equality holds. For the total domination number γ t ( G ) of a cubic graph, we prove γ t ( G )⩽ n /2− b ( G )/2 (except that γ t ( G ) may be n /2−1 when b ( G )=3 and the balloons cover all but one vertex). With α′( G )⩾ n /2− b ( G )/3 for cubic graphs, this improves the known inequality γ t ( G )⩽α′( G ). © 2009 Wiley Periodicals, Inc. J Graph Theory 64: 116–131, 2010