Balloons, cut‐edges, matchings, and total domination in regular graphs of odd degree
- 18 November 2009
- journal article
- research article
- Published by Wiley in Journal of Graph Theory
- Vol. 64 (2) , 116-131
Abstract
Aballoonin a graphGis a maximal 2‐edge‐connected subgraph incident to exactly one cut‐edge ofG. Letb(G) be the number of balloons, letc(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}${\mathcal{F}}_{{{n}},{{r}}}$ be the family of connected (2r+1)‐regular graphs withnvertices, and let\documentclass{article}\usepackage{amssymb}\usepackage{amsbsy}\usepackage[mathscr]{euscript}\footskip=0pc\pagestyle{empty}${{b}}={{max}}\{{{b}}({{G}}): {{G}}\in {\mathcal{F}}_{{{n}},{{r}}}\}$ . For\documentclass{article}\usepackage{amssymb}\usepackage{amsbsy}\usepackage[mathscr]{euscript}\footskip=0pc\pagestyle{empty}${{G}}\in{\mathcal{F}}_{{{n}},{{r}}}$ , we prove the sharp inequalitiesc(G)⩽[r(n−2)−2]/(2r2+2r−1)−1 and α′(G)⩾n/2−rb/(2r+1). Usingb⩽[(2r−1)n+2]/(4r2+4r−2), we obtain a simple proof of the boundproved by Henning and Yeo. For each of these bounds and eachr, 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 ben/2−1 whenb(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
Keywords
This publication has 13 references indexed in Scilit:
- On matching and total domination in graphsDiscrete Mathematics, 2008
- Tight Lower Bounds on the Size of a Maximum Matching in a Regular GraphGraphs and Combinatorics, 2007
- Total domination of graphs and small transversals of hypergraphsCombinatorica, 2007
- A linear Vizing‐like relation relating the size and total domination number of a graphJournal of Graph Theory, 2005
- Tight bounds on maximal and maximum matchingsDiscrete Mathematics, 2004
- Some remarks on dominationJournal of Graph Theory, 2004
- Small transversals in hypergraphsCombinatorica, 1992
- Transversal numbers of uniform hypergraphsGraphs and Combinatorics, 1990
- ber die Zerlegung regul rer Streckenkomplexe ungerader OrdnungCommentarii Mathematici Helvetici, 1937
- Die Theorie der regulären graphsActa Mathematica, 1891