On the order of certain close to regular graphs without a matching of given size

Sabine Klinkenberg; Lutz Volkmann

Czechoslovak Mathematical Journal (2007)

  • Volume: 57, Issue: 3, page 907-918
  • ISSN: 0011-4642

Abstract

top
A graph G is a { d , d + k } -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 0 and d , n 1 be integers such that n and p are of the same parity. If G is a connected { d , d + k } -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 2 ( p + 2 ) and (i) n k + p + 6 . If d 3 is odd and t an integer with 1 t p + 2 , then (ii) n d + k + 1 for k d ( p + 2 ) , (iii) n d ( p + 3 ) + 2 t + 1 for d ( p + 2 - t ) + t k d ( p + 3 - t ) + t - 3 , (iv) n d ( p + 3 ) + 2 p + 7 for k p . If d 4 is even, then (v) n d + k + 2 - η for k d ( p + 3 ) + p + 4 + η , (vi) n d + k + p + 2 - 2 t = d ( p + 4 ) + p + 6 for k = d ( p + 3 ) + 4 + 2 t and p 1 , (vii) n d + k + p + 4 for d ( p + 2 ) k d ( p + 3 ) + 2 , (viii) n d ( p + 3 ) + p + 4 for k d ( p + 2 ) - 2 , where 0 t 1 2 p - 1 and η = 0 for even p and 0 t 1 2 ( p - 1 ) and η = 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.

How to cite

top

Klinkenberg, Sabine, and Volkmann, Lutz. "On the order of certain close to regular graphs without a matching of given size." Czechoslovak Mathematical Journal 57.3 (2007): 907-918. <http://eudml.org/doc/31171>.

@article{Klinkenberg2007,
abstract = {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.},
author = {Klinkenberg, Sabine, Volkmann, Lutz},
journal = {Czechoslovak Mathematical Journal},
keywords = {matching; maximum matching; close to regular graph; matching; maximum matching; close to regular graph},
language = {eng},
number = {3},
pages = {907-918},
publisher = {Institute of Mathematics, Academy of Sciences of the Czech Republic},
title = {On the order of certain close to regular graphs without a matching of given size},
url = {http://eudml.org/doc/31171},
volume = {57},
year = {2007},
}

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
PB - Institute of Mathematics, Academy of Sciences of the Czech Republic
VL - 57
IS - 3
SP - 907
EP - 918
AB - 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.
LA - eng
KW - matching; maximum matching; close to regular graph; matching; maximum matching; close to regular graph
UR - http://eudml.org/doc/31171
ER -

References

top
  1. Sur le couplage maximum d’un graphe, C. R.  Acad. Sci. Paris 247 (1958), 258–259. (French) (1958) Zbl0086.16301MR0100850
  2. On the existence of almost-regular-graphs without one-factors, Australas. J.  Comb. 9 (1994), 243–260. (1994) MR1271205
  3. Graphs and Digraphs, 3rd Edition, Chapman and Hall, London, 1996. (1996) MR1408678
  4. 10.1112/jlms/s1-22.2.107, J.  Lond. Math. Soc. 22 (1947), 107–111. (1947) Zbl0029.23301MR0023048DOI10.1112/jlms/s1-22.2.107
  5. Foundations of Graph Theory, Springer-Verlag, Wien-New York, 1996. (German) (1996) MR1392955
  6. The smallest regular graphs without one-factors, Ars Comb. 11 (1981), 295–300. (1981) Zbl0468.05042MR0629881

NotesEmbed ?

top

You must be logged in to post comments.