Balloons, cut-edges, matchings, and total domination in regular graphs of odd degree
✍ Scribed by Suil O; Douglas B. West
- Publisher
- John Wiley and Sons
- Year
- 2009
- Tongue
- English
- Weight
- 148 KB
- Volume
- 64
- Category
- Article
- ISSN
- 0364-9024
No coin nor oath required. For personal study only.
✦ Synopsis
Abstract
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
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