On the order of certain close to regular graphs without a matching of given size
Czechoslovak Mathematical Journal, Tome 57 (2007) no. 3, pp. 907-918
Voir la notice de l'article provenant de la source Czech Digital Mathematics Library
MR Zbl
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 [6] in 1981, and the case $p=0$ was proved by Caccetta and Mardiyono [2] in 1994. Examples show that the given bounds (i)–(viii) are best possible.
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 [6] in 1981, and the case $p=0$ was proved by Caccetta and Mardiyono [2] in 1994. Examples show that the given bounds (i)–(viii) are best possible.
Klinkenberg, Sabine; Volkmann, Lutz. On the order of certain close to regular graphs without a matching of given size. Czechoslovak Mathematical Journal, Tome 57 (2007) no. 3, pp. 907-918. http://geodesic.mathdoc.fr/item/CMJ_2007_57_3_a9/
@article{CMJ_2007_57_3_a9,
author = {Klinkenberg, Sabine and Volkmann, Lutz},
title = {On the order of certain close to regular graphs without a matching of given size},
journal = {Czechoslovak Mathematical Journal},
pages = {907--918},
year = {2007},
volume = {57},
number = {3},
mrnumber = {2356929},
zbl = {1174.05101},
language = {en},
url = {http://geodesic.mathdoc.fr/item/CMJ_2007_57_3_a9/}
}
TY - JOUR AU - Klinkenberg, Sabine AU - Volkmann, Lutz TI - On the order of certain close to regular graphs without a matching of given size JO - Czechoslovak Mathematical Journal PY - 2007 SP - 907 EP - 918 VL - 57 IS - 3 UR - http://geodesic.mathdoc.fr/item/CMJ_2007_57_3_a9/ LA - en ID - CMJ_2007_57_3_a9 ER -
[1] C. Berge: Sur le couplage maximum d’un graphe. C. R. Acad. Sci. Paris 247 (1958), 258–259. (French) | MR | Zbl
[2] L. Caccetta, S. Mardiyono: On the existence of almost-regular-graphs without one-factors. Australas. J. Comb. 9 (1994), 243–260. | MR
[3] G. Chartrand, L. Lesniak: Graphs and Digraphs, 3rd Edition. Chapman and Hall, London, 1996. | MR
[4] W. T. Tutte: The factorization of linear graphs. J. Lond. Math. Soc. 22 (1947), 107–111. | DOI | MR | Zbl
[5] L. Volkmann: Foundations of Graph Theory. Springer-Verlag, Wien-New York, 1996. (German) | MR
[6] W. D. Wallis: The smallest regular graphs without one-factors. Ars Comb. 11 (1981), 295–300. | MR | Zbl