| Title: | Lower bounds for domination and total domination number of direct products graphs |
|---|
| Authors: | ID Mekiš, Gašper (Author) |
|---|
| Files: |  http://www.imfm.si/preprinti/PDF/01100.pdf
|
|---|
| Language: | English |
|---|
| Work type: | Not categorized |
|---|
| Organization: | FNM - Faculty of Natural Sciences and Mathematics
|
|---|
| Abstract: | An exact lower bound for the domination number and the total domination number of the direct product of finitely many complete graphs is given: ▫$gamma(times_{i=1}^t K_{n_i} ge t+1$▫, ▫$t ge 3$▫. Sharpness is established in the case when the factors are large enough in comparison to the number of factors. The main result gives a lower bound for the domination (and the total domination) number of the direct product of two arbitrary graphs: ▫$gamma(G times H) ge gamma(G) + gamma(H) - 1$▫. Infinite families of graphs that attain the bound are presented. For these graphs it also holds ▫$gamma_t(G times H) = gamma(G) + gamma(H) - 1$▫. Some additional parallels with the total domination number are made. |
|---|
| Keywords: | matematika, teorija grafov, dominacijska množica, dominacijsko število, celotna dominacijska množica, celotno dominacijsko število, direktni produkt grafov, poln graf, mathematics, graph theory, dominating set, domination number, total dominating set, total domination number, direct product graphs, complete graphs |
|---|
| Year of publishing: | 2009 |
|---|
| Number of pages: | str. 1-15 |
|---|
| Numbering: | Vol. 47, št. 1100 |
|---|
| PID: | 20.500.12556/DKUM-51800  |
|---|
| ISSN: | 1318-4865 |
|---|
| UDC: | 519.17 |
|---|
| COBISS.SI-ID: | 15246425 |
|---|
| NUK URN: | URN:SI:UM:DK:V19CW8I1 |
|---|
| Publication date in DKUM: | 10.07.2015 |
|---|
| Views: | 1638 |
|---|
| Downloads: | 46 |
|---|
| Metadata: |    |
|---|
| Categories: | Misc.
|
|---|
|
:
|
Copy citation |
|---|
| | | | Average score: | (0 votes) |
|---|
| Your score: | Voting is allowed only for logged in users. |
|---|
| Share: |  |
|---|
Hover the mouse pointer over a document title to show the abstract or click
on the title to get all document metadata. |
