Mathematics – Combinatorics
Scientific paper
2010-01-06
Disc. App. Math. 159(1) 2011, 46-52
Mathematics
Combinatorics
Scientific paper
The existence problem of the total domination vertex critical graphs has been studied in a series of articles. The aim of the present article is twofold. First, we settle the existence problem with respect to the parities of the total domination number m and the maximum degree Delta : for even m except m=4, there is no m-gamma_t-critical graph regardless of the parity of Delta; for m=4 or odd m \ge 3 and for even Delta, an m-gamma_t-critical graph exists if and only if Delta \ge 2 \lfloor \frac{m-1}{2}\rfloor; for m=4 or odd m \ge 3 and for odd Delta, if Delta \ge 2\lfloor \frac{m-1}{2}\rfloor +7, then m-gamma_t-critical graphs exist, if Delta < 2\lfloor \frac{m-1}{2}\rfloor, then m-gamma_t-critical graphs do not exist. The only remaining open cases are Delta = 2\lfloor \frac{m-1}{2}\rfloor +k, k=1, 3, 5. Second, we study these remaining open cases when m=4 or odd m \ge 9. As the previously known result for m = 3, we also show that for Delta(G)= 3, 5, 7, there is no 4-gamma_t-critical graph of order Delta(G)+4. On the contrary, it is shown that for odd m \ge 9 there exists an m-gamma_t-critical graph for all Delta \ge m-1.
Kim Dongseok
Kwon Young Soo
Lee Jaeun
Sohn Moo Young
No associations
LandOfFree
On the existence problem of the total domination vertex critical 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 On the existence problem of the total domination vertex critical graphs, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and On the existence problem of the total domination vertex critical graphs will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-163590