# Article

 Title: On the order of certain close to regular graphs without a matching of given size (English) Author: Klinkenberg, Sabine Author: Volkmann, Lutz Language: English Journal: Czechoslovak Mathematical Journal ISSN: 0011-4642 (print) ISSN: 1572-9141 (online) Volume: 57 Issue: 3 Year: 2007 Pages: 907-918 Summary lang: English . Category: math . Summary: A graph $G$ is a $\lbrace d,d+k\rbrace$-graph, if one vertex has degree $d+k$ and the remaining vertices of $G$ have degree $d$. In the special case of $k=0$, the graph $G$ is $d$-regular. Let $k,p\ge 0$ and $d,n\ge 1$ be integers such that $n$ and $p$ are of the same parity. If $G$ is a connected $\lbrace d,d+k\rbrace$-graph of order $n$ without a matching $M$ of size $2|M|=n-p$, then we show in this paper the following: If $d=2$, then $k\ge 2(p+2)$ and (i) $n\ge k+p+6$. If $d\ge 3$ is odd and $t$ an integer with $1\le t\le p+2$, then (ii) $n\ge d+k+1$ for $k\ge d(p+2)$, (iii) $n\ge d(p+3)+2t+1$ for $d(p+2-t)+t\le k\le d(p+3-t)+t-3$, (iv) $n\ge d(p+3)+2p+7$ for $k\le p$. If $d\ge 4$ is even, then (v) $n\ge d+k+2-\eta$ for $k\ge d(p+3)+p+4+\eta$, (vi) $n\ge d+k+p+2-2t=d(p+4)+p+6$ for $k=d(p+3)+4+2t$ and $p\ge 1$, (vii) $n\ge d+k+p+4$ for $d(p+2)\le k\le d(p+3)+2$, (viii) $n\ge d(p+3)+p+4$ for $k\le d(p+2)-2$, where $0\le t\le \frac{1}{2}{p}-1$ and $\eta =0$ for even $p$ and $0\le t\le \frac{1}{2}(p-1)$ and $\eta =1$ for odd $p$. The special case $k=p=0$ of this result was done by Wallis  in 1981, and the case $p=0$ was proved by Caccetta and Mardiyono  in 1994. Examples show that the given bounds (i)–(viii) are best possible. (English) Keyword: matching Keyword: maximum matching Keyword: close to regular graph MSC: 05C07 MSC: 05C70 idZBL: Zbl 1174.05101 idMR: MR2356929 . Date available: 2009-09-24T11:50:28Z Last updated: 2020-07-03 Stable URL: http://hdl.handle.net/10338.dmlcz/128215 . Reference:  C.  Berge: Sur le couplage maximum d’un graphe.C. R.  Acad. Sci. Paris 247 (1958), 258–259. (French) Zbl 0086.16301, MR 0100850 Reference:  L.  Caccetta, S.  Mardiyono: On the existence of almost-regular-graphs without one-factors.Australas. J.  Comb. 9 (1994), 243–260. MR 1271205 Reference:  G.  Chartrand, L.  Lesniak: Graphs and Digraphs, 3rd Edition.Chapman and Hall, London, 1996. MR 1408678 Reference:  W. T.  Tutte: The factorization of linear graphs.J.  Lond. Math. Soc. 22 (1947), 107–111. Zbl 0029.23301, MR 0023048, 10.1112/jlms/s1-22.2.107 Reference:  L.  Volkmann: Foundations of Graph Theory.Springer-Verlag, Wien-New York, 1996. (German) MR 1392955 Reference:  W. D.  Wallis: The smallest regular graphs without one-factors.Ars Comb. 11 (1981), 295–300. Zbl 0468.05042, MR 0629881 .

## Files

Files Size Format View
CzechMathJ_57-2007-3_10.pdf 261.3Kb application/pdf View/Open