| Title: | Roman domination number of the Cartesian products of paths and cycles |
|---|
| Authors: | ID Repolusk, Polona (Author)
ID Žerovnik, Janez (Author) |
|---|
| Files: |  Electronic_Journal_of_Combinatorics_2012_Repolusk,_Zerovnik_Roman_domination_number_of_the_Cartesian_products_of_paths_and_cycles.pdf (719,06 KB)
MD5: 7B6681AABE2A4F6CEDF9F32D19F96E25
PID: 20.500.12556/dkum/937b65a6-8179-41f3-a998-533d6188b981
 http://www.combinatorics.org/ojs/index.php/eljc/article/view/v19i3p19
|
|---|
| Language: | English |
|---|
| Work type: | Scientific work |
|---|
| Typology: | 1.01 - Original Scientific Article |
|---|
| Organization: | FNM - Faculty of Natural Sciences and Mathematics
|
|---|
| Abstract: | Roman domination is a historically inspired variety of general domination such that every vertex is labeled with labels from $\{0,1,2\}$. Roman domination number is the smallest of the sums of labels fulfilling condition that every vertex, labeled 0, has a neighbor, labeled 2. Using algebraic approach we give ▫$O(C)$▫ time algorithm for computing Roman domination number of special classes of polygraphs (rota- and fasciagraphs). By implementing the algorithm we give formulas for Roman domination number of the Cartesian products of paths and cycles ▫$P_n \Box P_k$▫, ▫$P_n \Box C_k$▫ for ▫$k \leq 8$▫ and ▫$n \in {\mathbb N}$▫ and for ▫$C_n \Box P_k$▫ and ▫$C_n \Box C_k$▫ for ▫$k \leq 5$▫, ▫$n \in {\mathbb N}$▫. We also give a list of Roman graphs among investigated families. |
|---|
| Keywords: | graph theory, Roman domination number, Cartesian product, polygraphs, path algebra |
|---|
| Publication status: | Published |
|---|
| Publication version: | Version of Record |
|---|
| Submitted for review: | 16.01.2011 |
|---|
| Article acceptance date: | 01.08.2012 |
|---|
| Publication date: | 09.08.2012 |
|---|
| Publisher: | Electronic Journal of Combinatorics |
|---|
| Year of publishing: | 2012 |
|---|
| Number of pages: | str. 1-37 |
|---|
| Numbering: | Letn. 19, št. 3 |
|---|
| PID: | 20.500.12556/DKUM-67551  |
|---|
| ISSN: | 1077-8926 |
|---|
| UDC: | 519.17 |
|---|
| ISSN on article: | 1077-8926 |
|---|
| COBISS.SI-ID: | 16394585 |
|---|
| NUK URN: | URN:SI:UM:DK:AX7NMELG |
|---|
| Publication date in DKUM: | 23.08.2017 |
|---|
| Views: | 2005 |
|---|
| Downloads: | 326 |
|---|
| 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. |
