The domatic number of regular and almost regular graphs

Details The domatic number of regular and almost regular graphs The domatic number of regular and almost regular graphs

2001-11-24

arxiv.org/abs/math/0111257v1

Mathematics

Combinatorics

10 pages

Scientific paper

The domatic number of a graph $G$, denoted $dom(G)$, is the maximum possible cardinality of a family of disjoint sets of vertices of $G$, each set being a dominating set of $G$. It is well known that every graph without isolated vertices has $dom(G) \geq 2$. For every $k$, it is known that there are graphs with minimum degree at least $k$ and with $dom(G)=2$. In this paper we prove that this is not the case if $G$ is $k$-regular or {\em almost} $k$-regular (by ``almost'' we mean that the minimum degree is $k$ and the maximum degree is at most $Ck$ for some fixed real number $C \geq 1$). In this case we prove that $dom(G) \geq (1+o_k(1))k/(2\ln k)$. We also prove that the order of magnitude $k/\ln k$ cannot be improved. One cannot replace the constant 2 with a constant smaller than 1. The proof uses the so called {\em semi-random method} which means that combinatorial objects are generated via repeated applications of the probabilistic method; in our case iterative applications of the Lov\'asz Local Lemma.

Affiliated with

Also associated with

No associations

Rating

The domatic number of regular and almost regular graphs does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with The domatic number of regular and almost regular graphs, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and The domatic number of regular and almost regular graphs will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-30854