| Naslov: | Graphs with equal Grundy domination and independence number |
|---|
| Avtorji: | ID Bacsó, Gábor (Avtor)
ID Brešar, Boštjan (Avtor)
ID Kuenzel, Kirsti (Avtor)
ID Rall, Douglas F. (Avtor) |
|---|
| Datoteke: |  PDF - Predstavitvena datoteka, prenos (803,91 KB)
MD5: 4AEB000C0E70536E98789402FA20E358
 URL - Izvorni URL, za dostop obiščite https://www.sciencedirect.com/science/article/pii/S1572528623000191
|
|---|
| Jezik: | Angleški jezik |
|---|
| Tipologija: | 1.01 - Izvirni znanstveni članek |
|---|
| Organizacija: |  IMFM - Inštitut za matematiko, fiziko in mehaniko
|
|---|
| Povzetek: | The Grundy domination number, ${\gamma_{\rm gr}}(G)$, of a graph $G$ is the maximum length of a sequence $(v_1,v_2,\ldots, v_k)$ of vertices in $G$ such that for every $i\in \{2,\ldots, k\}$, the closed neighborhood $N[v_i]$ contains a vertex that does not belong to any closed neighborhood $N[v_j]$, where $j<i$. It is well known that the Grundy domination number of any graph $G$ is greater than or equal to the upper domination number $\Gamma(G)$, which is in turn greater than or equal to the independence number $\alpha(G)$. In this paper, we initiate the study of the class of graphs $G$ with $\Gamma(G)={\gamma_{\rm gr}}(G)$ and its subclass consisting of graphs $G$ with $\alpha(G)={\gamma_{\rm gr}}(G)$. We characterize the latter class of graphs among all twin-free connected graphs, provide a number of properties of these graphs, and prove that the hypercubes are members of this class. In addition, we give several necessary conditions for graphs $G$ with $\Gamma(G)={\gamma_{\rm gr}}(G)$ and present large families of such graphs. |
|---|
| Ključne besede: | Grundy domination, independence number, upper domination number, bipartite graphs |
|---|
| Status publikacije: | Objavljeno |
|---|
| Verzija publikacije: | Objavljena publikacija |
|---|
| Datum objave: | 01.05.2023 |
|---|
| Leto izida: | 2023 |
|---|
| Št. strani: | art. 100777 (15 str.) |
|---|
| Številčenje: | Vol. 48, iss. 2 |
|---|
| PID: | 20.500.12556/DiRROS-18642  |
|---|
| UDK: | 519.17 |
|---|
| ISSN pri članku: | 1572-5286 |
|---|
| DOI: | 10.1016/j.disopt.2023.100777 |
|---|
| COBISS.SI-ID: | 154012931 |
|---|
| Opomba: |
|
|---|
| Datum objave v DiRROS: | 09.04.2024 |
|---|
| Število ogledov: | 942 |
|---|
| Število prenosov: | 625 |
|---|
| Metapodatki: |    |
|---|
|
:
|
Kopiraj citat |
|---|
| | | | Objavi na: |  |
|---|
Postavite miškin kazalec na naslov za izpis povzetka. Klik na naslov izpiše
podrobnosti ali sproži prenos. |
