A characterization of trees with equal 2-domination and 2-independence numbers
A set $S$ of vertices in a graph $G$ is a $2$-dominating set if every vertex of $G$ not in $S$ is adjacent to at least two vertices in $S$, and $S$ is a $2$-independent set if every vertex in $S$ is adjacent to at most one vertex of $S$. The $2$-domination number $\gamma_2(G)$ is the minimum cardina...
| Main Authors: | , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Discrete Mathematics & Theoretical Computer Science
2017-03-01
|
| Series: | Discrete Mathematics & Theoretical Computer Science |
| Subjects: | |
| Online Access: | https://dmtcs.episciences.org/1443/pdf |
| _version_ | 1827323762295439360 |
|---|---|
| author | Christoph Brause Michael A. Henning Marcin Krzywkowski |
| author_facet | Christoph Brause Michael A. Henning Marcin Krzywkowski |
| author_sort | Christoph Brause |
| collection | DOAJ |
| description | A set $S$ of vertices in a graph $G$ is a $2$-dominating set if every vertex
of $G$ not in $S$ is adjacent to at least two vertices in $S$, and $S$ is a
$2$-independent set if every vertex in $S$ is adjacent to at most one vertex of
$S$. The $2$-domination number $\gamma_2(G)$ is the minimum cardinality of a
$2$-dominating set in $G$, and the $2$-independence number $\alpha_2(G)$ is the
maximum cardinality of a $2$-independent set in $G$. Chellali and Meddah [{\it
Trees with equal $2$-domination and $2$-independence numbers,} Discussiones
Mathematicae Graph Theory 32 (2012), 263--270] provided a constructive
characterization of trees with equal $2$-domination and $2$-independence
numbers. Their characterization is in terms of global properties of a tree, and
involves properties of minimum $2$-dominating and maximum $2$-independent sets
in the tree at each stage of the construction. We provide a constructive
characterization that relies only on local properties of the tree at each stage
of the construction. |
| first_indexed | 2024-04-25T01:58:47Z |
| format | Article |
| id | doaj.art-acf9109aa9274ce1924a249232c974eb |
| institution | Directory Open Access Journal |
| issn | 1365-8050 |
| language | English |
| last_indexed | 2024-04-25T01:58:47Z |
| publishDate | 2017-03-01 |
| publisher | Discrete Mathematics & Theoretical Computer Science |
| record_format | Article |
| series | Discrete Mathematics & Theoretical Computer Science |
| spelling | doaj.art-acf9109aa9274ce1924a249232c974eb2024-03-07T15:32:47ZengDiscrete Mathematics & Theoretical Computer ScienceDiscrete Mathematics & Theoretical Computer Science1365-80502017-03-01Vol. 19 no. 1Graph Theory10.23638/DMTCS-19-1-11443A characterization of trees with equal 2-domination and 2-independence numbersChristoph BrauseMichael A. HenningMarcin KrzywkowskiA set $S$ of vertices in a graph $G$ is a $2$-dominating set if every vertex of $G$ not in $S$ is adjacent to at least two vertices in $S$, and $S$ is a $2$-independent set if every vertex in $S$ is adjacent to at most one vertex of $S$. The $2$-domination number $\gamma_2(G)$ is the minimum cardinality of a $2$-dominating set in $G$, and the $2$-independence number $\alpha_2(G)$ is the maximum cardinality of a $2$-independent set in $G$. Chellali and Meddah [{\it Trees with equal $2$-domination and $2$-independence numbers,} Discussiones Mathematicae Graph Theory 32 (2012), 263--270] provided a constructive characterization of trees with equal $2$-domination and $2$-independence numbers. Their characterization is in terms of global properties of a tree, and involves properties of minimum $2$-dominating and maximum $2$-independent sets in the tree at each stage of the construction. We provide a constructive characterization that relies only on local properties of the tree at each stage of the construction.https://dmtcs.episciences.org/1443/pdfmathematics - combinatorics05c05, 05c69 |
| spellingShingle | Christoph Brause Michael A. Henning Marcin Krzywkowski A characterization of trees with equal 2-domination and 2-independence numbers Discrete Mathematics & Theoretical Computer Science mathematics - combinatorics 05c05, 05c69 |
| title | A characterization of trees with equal 2-domination and 2-independence numbers |
| title_full | A characterization of trees with equal 2-domination and 2-independence numbers |
| title_fullStr | A characterization of trees with equal 2-domination and 2-independence numbers |
| title_full_unstemmed | A characterization of trees with equal 2-domination and 2-independence numbers |
| title_short | A characterization of trees with equal 2-domination and 2-independence numbers |
| title_sort | characterization of trees with equal 2 domination and 2 independence numbers |
| topic | mathematics - combinatorics 05c05, 05c69 |
| url | https://dmtcs.episciences.org/1443/pdf |
| work_keys_str_mv | AT christophbrause acharacterizationoftreeswithequal2dominationand2independencenumbers AT michaelahenning acharacterizationoftreeswithequal2dominationand2independencenumbers AT marcinkrzywkowski acharacterizationoftreeswithequal2dominationand2independencenumbers AT christophbrause characterizationoftreeswithequal2dominationand2independencenumbers AT michaelahenning characterizationoftreeswithequal2dominationand2independencenumbers AT marcinkrzywkowski characterizationoftreeswithequal2dominationand2independencenumbers |