Secure <i>w</i>-Domination in Graphs
This paper introduces a general approach to the idea of protection of graphs, which encompasses the known variants of secure domination and introduces new ones. Specifically, we introduce the study of secure <i>w</i>-domination in graphs, where <inline-formula><math display=&quo...
| Main Authors: | , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
MDPI AG
2020-11-01
|
| Series: | Symmetry |
| Subjects: | |
| Online Access: | https://www.mdpi.com/2073-8994/12/12/1948 |
| _version_ | 1797546786479407104 |
|---|---|
| author | Abel Cabrera Martínez Alejandro Estrada-Moreno Juan A. Rodríguez-Velázquez |
| author_facet | Abel Cabrera Martínez Alejandro Estrada-Moreno Juan A. Rodríguez-Velázquez |
| author_sort | Abel Cabrera Martínez |
| collection | DOAJ |
| description | This paper introduces a general approach to the idea of protection of graphs, which encompasses the known variants of secure domination and introduces new ones. Specifically, we introduce the study of secure <i>w</i>-domination in graphs, where <inline-formula><math display="inline"><semantics><mrow><mi>w</mi><mo>=</mo><mo>(</mo><msub><mi>w</mi><mn>0</mn></msub><mo>,</mo><msub><mi>w</mi><mn>1</mn></msub><mo>,</mo><mo>…</mo><mo>,</mo><msub><mi>w</mi><mi>l</mi></msub><mo>)</mo></mrow></semantics></math></inline-formula> is a vector of nonnegative integers such that <inline-formula><math display="inline"><semantics><mrow><msub><mi>w</mi><mn>0</mn></msub><mo>≥</mo><mn>1</mn></mrow></semantics></math></inline-formula>. The secure <i>w</i>-domination number is defined as follows. Let <i>G</i> be a graph and <inline-formula><math display="inline"><semantics><mrow><mi>N</mi><mo>(</mo><mi>v</mi><mo>)</mo></mrow></semantics></math></inline-formula> the open neighborhood of <inline-formula><math display="inline"><semantics><mrow><mi>v</mi><mo>∈</mo><mi>V</mi><mo>(</mo><mi>G</mi><mo>)</mo></mrow></semantics></math></inline-formula>. We say that a function <inline-formula><math display="inline"><semantics><mrow><mi>f</mi><mo>:</mo><mi>V</mi><mo>(</mo><mi>G</mi><mo>)</mo><mo>⟶</mo><mo>{</mo><mn>0</mn><mo>,</mo><mn>1</mn><mo>,</mo><mo>…</mo><mo>,</mo><mi>l</mi><mo>}</mo></mrow></semantics></math></inline-formula> is a <i>w</i>-dominating function if <inline-formula><math display="inline"><semantics><mrow><mi>f</mi><mrow><mo>(</mo><mi>N</mi><mrow><mo>(</mo><mi>v</mi><mo>)</mo></mrow><mo>)</mo></mrow><mo>=</mo><msub><mo>∑</mo><mrow><mi>u</mi><mo>∈</mo><mi>N</mi><mo>(</mo><mi>v</mi><mo>)</mo></mrow></msub><mi>f</mi><mrow><mo>(</mo><mi>u</mi><mo>)</mo></mrow><mo>≥</mo><msub><mi>w</mi><mi>i</mi></msub></mrow></semantics></math></inline-formula> for every vertex <i>v</i> with <inline-formula><math display="inline"><semantics><mrow><mi>f</mi><mo>(</mo><mi>v</mi><mo>)</mo><mo>=</mo><mi>i</mi></mrow></semantics></math></inline-formula>. The weight of <i>f</i> is defined to be <inline-formula><math display="inline"><semantics><mrow><mi>ω</mi><mrow><mo>(</mo><mi>f</mi><mo>)</mo></mrow><mo>=</mo><msub><mo>∑</mo><mrow><mi>v</mi><mo>∈</mo><mi>V</mi><mo>(</mo><mi>G</mi><mo>)</mo></mrow></msub><mi>f</mi><mrow><mo>(</mo><mi>v</mi><mo>)</mo></mrow></mrow></semantics></math></inline-formula>. Given a <i>w</i>-dominating function <i>f</i> and any pair of adjacent vertices <inline-formula><math display="inline"><semantics><mrow><mi>v</mi><mo>,</mo><mi>u</mi><mo>∈</mo><mi>V</mi><mo>(</mo><mi>G</mi><mo>)</mo></mrow></semantics></math></inline-formula> with <inline-formula><math display="inline"><semantics><mrow><mi>f</mi><mo>(</mo><mi>v</mi><mo>)</mo><mo>=</mo><mn>0</mn></mrow></semantics></math></inline-formula> and <inline-formula><math display="inline"><semantics><mrow><mi>f</mi><mo>(</mo><mi>u</mi><mo>)</mo><mo>></mo><mn>0</mn></mrow></semantics></math></inline-formula>, the function <inline-formula><math display="inline"><semantics><msub><mi>f</mi><mrow><mi>u</mi><mo>→</mo><mi>v</mi></mrow></msub></semantics></math></inline-formula> is defined by <inline-formula><math display="inline"><semantics><mrow><msub><mi>f</mi><mrow><mi>u</mi><mo>→</mo><mi>v</mi></mrow></msub><mrow><mo>(</mo><mi>v</mi><mo>)</mo></mrow><mo>=</mo><mn>1</mn></mrow></semantics></math></inline-formula>, <inline-formula><math display="inline"><semantics><mrow><msub><mi>f</mi><mrow><mi>u</mi><mo>→</mo><mi>v</mi></mrow></msub><mrow><mo>(</mo><mi>u</mi><mo>)</mo></mrow><mo>=</mo><mi>f</mi><mrow><mo>(</mo><mi>u</mi><mo>)</mo></mrow><mo>−</mo><mn>1</mn></mrow></semantics></math></inline-formula> and <inline-formula><math display="inline"><semantics><mrow><msub><mi>f</mi><mrow><mi>u</mi><mo>→</mo><mi>v</mi></mrow></msub><mrow><mo>(</mo><mi>x</mi><mo>)</mo></mrow><mo>=</mo><mi>f</mi><mrow><mo>(</mo><mi>x</mi><mo>)</mo></mrow></mrow></semantics></math></inline-formula> for every <inline-formula><math display="inline"><semantics><mrow><mi>x</mi><mo>∈</mo><mi>V</mi><mo>(</mo><mi>G</mi><mo>)</mo><mo>\</mo><mo>{</mo><mi>u</mi><mo>,</mo><mi>v</mi><mo>}</mo></mrow></semantics></math></inline-formula>. We say that a <i>w</i>-dominating function <i>f</i> is a secure <i>w</i>-dominating function if for every <i>v</i> with <inline-formula><math display="inline"><semantics><mrow><mi>f</mi><mo>(</mo><mi>v</mi><mo>)</mo><mo>=</mo><mn>0</mn></mrow></semantics></math></inline-formula>, there exists <inline-formula><math display="inline"><semantics><mrow><mi>u</mi><mo>∈</mo><mi>N</mi><mo>(</mo><mi>v</mi><mo>)</mo></mrow></semantics></math></inline-formula> such that <inline-formula><math display="inline"><semantics><mrow><mi>f</mi><mo>(</mo><mi>u</mi><mo>)</mo><mo>></mo><mn>0</mn></mrow></semantics></math></inline-formula> and <inline-formula><math display="inline"><semantics><msub><mi>f</mi><mrow><mi>u</mi><mo>→</mo><mi>v</mi></mrow></msub></semantics></math></inline-formula> is a <i>w</i>-dominating function as well. The secure <i>w</i>-domination number of <i>G</i>, denoted by <inline-formula><math display="inline"><semantics><mrow><msubsup><mi>γ</mi><mrow><mi>w</mi></mrow><mi>s</mi></msubsup><mrow><mo>(</mo><mi>G</mi><mo>)</mo></mrow></mrow></semantics></math></inline-formula>, is the minimum weight among all secure <i>w</i>-dominating functions. This paper provides fundamental results on <inline-formula><math display="inline"><semantics><mrow><msubsup><mi>γ</mi><mrow><mi>w</mi></mrow><mi>s</mi></msubsup><mrow><mo>(</mo><mi>G</mi><mo>)</mo></mrow></mrow></semantics></math></inline-formula> and raises the challenge of conducting a detailed study of the topic. |
| first_indexed | 2024-03-10T14:34:09Z |
| format | Article |
| id | doaj.art-8f8ba6aacae44680b42c2c228cd9143a |
| institution | Directory Open Access Journal |
| issn | 2073-8994 |
| language | English |
| last_indexed | 2024-03-10T14:34:09Z |
| publishDate | 2020-11-01 |
| publisher | MDPI AG |
| record_format | Article |
| series | Symmetry |
| spelling | doaj.art-8f8ba6aacae44680b42c2c228cd9143a2023-11-20T22:20:12ZengMDPI AGSymmetry2073-89942020-11-011212194810.3390/sym12121948Secure <i>w</i>-Domination in GraphsAbel Cabrera Martínez0Alejandro Estrada-Moreno1Juan A. Rodríguez-Velázquez2Departament d’Enginyeria Informàtica i Matemàtiques, Universitat Rovira i Virgili, Av. Països Catalans 26, 43007 Tarragona, SpainDepartament d’Enginyeria Informàtica i Matemàtiques, Universitat Rovira i Virgili, Av. Països Catalans 26, 43007 Tarragona, SpainDepartament d’Enginyeria Informàtica i Matemàtiques, Universitat Rovira i Virgili, Av. Països Catalans 26, 43007 Tarragona, SpainThis paper introduces a general approach to the idea of protection of graphs, which encompasses the known variants of secure domination and introduces new ones. Specifically, we introduce the study of secure <i>w</i>-domination in graphs, where <inline-formula><math display="inline"><semantics><mrow><mi>w</mi><mo>=</mo><mo>(</mo><msub><mi>w</mi><mn>0</mn></msub><mo>,</mo><msub><mi>w</mi><mn>1</mn></msub><mo>,</mo><mo>…</mo><mo>,</mo><msub><mi>w</mi><mi>l</mi></msub><mo>)</mo></mrow></semantics></math></inline-formula> is a vector of nonnegative integers such that <inline-formula><math display="inline"><semantics><mrow><msub><mi>w</mi><mn>0</mn></msub><mo>≥</mo><mn>1</mn></mrow></semantics></math></inline-formula>. The secure <i>w</i>-domination number is defined as follows. Let <i>G</i> be a graph and <inline-formula><math display="inline"><semantics><mrow><mi>N</mi><mo>(</mo><mi>v</mi><mo>)</mo></mrow></semantics></math></inline-formula> the open neighborhood of <inline-formula><math display="inline"><semantics><mrow><mi>v</mi><mo>∈</mo><mi>V</mi><mo>(</mo><mi>G</mi><mo>)</mo></mrow></semantics></math></inline-formula>. We say that a function <inline-formula><math display="inline"><semantics><mrow><mi>f</mi><mo>:</mo><mi>V</mi><mo>(</mo><mi>G</mi><mo>)</mo><mo>⟶</mo><mo>{</mo><mn>0</mn><mo>,</mo><mn>1</mn><mo>,</mo><mo>…</mo><mo>,</mo><mi>l</mi><mo>}</mo></mrow></semantics></math></inline-formula> is a <i>w</i>-dominating function if <inline-formula><math display="inline"><semantics><mrow><mi>f</mi><mrow><mo>(</mo><mi>N</mi><mrow><mo>(</mo><mi>v</mi><mo>)</mo></mrow><mo>)</mo></mrow><mo>=</mo><msub><mo>∑</mo><mrow><mi>u</mi><mo>∈</mo><mi>N</mi><mo>(</mo><mi>v</mi><mo>)</mo></mrow></msub><mi>f</mi><mrow><mo>(</mo><mi>u</mi><mo>)</mo></mrow><mo>≥</mo><msub><mi>w</mi><mi>i</mi></msub></mrow></semantics></math></inline-formula> for every vertex <i>v</i> with <inline-formula><math display="inline"><semantics><mrow><mi>f</mi><mo>(</mo><mi>v</mi><mo>)</mo><mo>=</mo><mi>i</mi></mrow></semantics></math></inline-formula>. The weight of <i>f</i> is defined to be <inline-formula><math display="inline"><semantics><mrow><mi>ω</mi><mrow><mo>(</mo><mi>f</mi><mo>)</mo></mrow><mo>=</mo><msub><mo>∑</mo><mrow><mi>v</mi><mo>∈</mo><mi>V</mi><mo>(</mo><mi>G</mi><mo>)</mo></mrow></msub><mi>f</mi><mrow><mo>(</mo><mi>v</mi><mo>)</mo></mrow></mrow></semantics></math></inline-formula>. Given a <i>w</i>-dominating function <i>f</i> and any pair of adjacent vertices <inline-formula><math display="inline"><semantics><mrow><mi>v</mi><mo>,</mo><mi>u</mi><mo>∈</mo><mi>V</mi><mo>(</mo><mi>G</mi><mo>)</mo></mrow></semantics></math></inline-formula> with <inline-formula><math display="inline"><semantics><mrow><mi>f</mi><mo>(</mo><mi>v</mi><mo>)</mo><mo>=</mo><mn>0</mn></mrow></semantics></math></inline-formula> and <inline-formula><math display="inline"><semantics><mrow><mi>f</mi><mo>(</mo><mi>u</mi><mo>)</mo><mo>></mo><mn>0</mn></mrow></semantics></math></inline-formula>, the function <inline-formula><math display="inline"><semantics><msub><mi>f</mi><mrow><mi>u</mi><mo>→</mo><mi>v</mi></mrow></msub></semantics></math></inline-formula> is defined by <inline-formula><math display="inline"><semantics><mrow><msub><mi>f</mi><mrow><mi>u</mi><mo>→</mo><mi>v</mi></mrow></msub><mrow><mo>(</mo><mi>v</mi><mo>)</mo></mrow><mo>=</mo><mn>1</mn></mrow></semantics></math></inline-formula>, <inline-formula><math display="inline"><semantics><mrow><msub><mi>f</mi><mrow><mi>u</mi><mo>→</mo><mi>v</mi></mrow></msub><mrow><mo>(</mo><mi>u</mi><mo>)</mo></mrow><mo>=</mo><mi>f</mi><mrow><mo>(</mo><mi>u</mi><mo>)</mo></mrow><mo>−</mo><mn>1</mn></mrow></semantics></math></inline-formula> and <inline-formula><math display="inline"><semantics><mrow><msub><mi>f</mi><mrow><mi>u</mi><mo>→</mo><mi>v</mi></mrow></msub><mrow><mo>(</mo><mi>x</mi><mo>)</mo></mrow><mo>=</mo><mi>f</mi><mrow><mo>(</mo><mi>x</mi><mo>)</mo></mrow></mrow></semantics></math></inline-formula> for every <inline-formula><math display="inline"><semantics><mrow><mi>x</mi><mo>∈</mo><mi>V</mi><mo>(</mo><mi>G</mi><mo>)</mo><mo>\</mo><mo>{</mo><mi>u</mi><mo>,</mo><mi>v</mi><mo>}</mo></mrow></semantics></math></inline-formula>. We say that a <i>w</i>-dominating function <i>f</i> is a secure <i>w</i>-dominating function if for every <i>v</i> with <inline-formula><math display="inline"><semantics><mrow><mi>f</mi><mo>(</mo><mi>v</mi><mo>)</mo><mo>=</mo><mn>0</mn></mrow></semantics></math></inline-formula>, there exists <inline-formula><math display="inline"><semantics><mrow><mi>u</mi><mo>∈</mo><mi>N</mi><mo>(</mo><mi>v</mi><mo>)</mo></mrow></semantics></math></inline-formula> such that <inline-formula><math display="inline"><semantics><mrow><mi>f</mi><mo>(</mo><mi>u</mi><mo>)</mo><mo>></mo><mn>0</mn></mrow></semantics></math></inline-formula> and <inline-formula><math display="inline"><semantics><msub><mi>f</mi><mrow><mi>u</mi><mo>→</mo><mi>v</mi></mrow></msub></semantics></math></inline-formula> is a <i>w</i>-dominating function as well. The secure <i>w</i>-domination number of <i>G</i>, denoted by <inline-formula><math display="inline"><semantics><mrow><msubsup><mi>γ</mi><mrow><mi>w</mi></mrow><mi>s</mi></msubsup><mrow><mo>(</mo><mi>G</mi><mo>)</mo></mrow></mrow></semantics></math></inline-formula>, is the minimum weight among all secure <i>w</i>-dominating functions. This paper provides fundamental results on <inline-formula><math display="inline"><semantics><mrow><msubsup><mi>γ</mi><mrow><mi>w</mi></mrow><mi>s</mi></msubsup><mrow><mo>(</mo><mi>G</mi><mo>)</mo></mrow></mrow></semantics></math></inline-formula> and raises the challenge of conducting a detailed study of the topic.https://www.mdpi.com/2073-8994/12/12/1948secure dominationsecure Italian dominationweak roman dominationw-domination |
| spellingShingle | Abel Cabrera Martínez Alejandro Estrada-Moreno Juan A. Rodríguez-Velázquez Secure <i>w</i>-Domination in Graphs Symmetry secure domination secure Italian domination weak roman domination w-domination |
| title | Secure <i>w</i>-Domination in Graphs |
| title_full | Secure <i>w</i>-Domination in Graphs |
| title_fullStr | Secure <i>w</i>-Domination in Graphs |
| title_full_unstemmed | Secure <i>w</i>-Domination in Graphs |
| title_short | Secure <i>w</i>-Domination in Graphs |
| title_sort | secure i w i domination in graphs |
| topic | secure domination secure Italian domination weak roman domination w-domination |
| url | https://www.mdpi.com/2073-8994/12/12/1948 |
| work_keys_str_mv | AT abelcabreramartinez secureiwidominationingraphs AT alejandroestradamoreno secureiwidominationingraphs AT juanarodriguezvelazquez secureiwidominationingraphs |