| Title: | Graphs with equal Grundy domination and independence number |
|---|
| Authors: | ID Bacsó, Gábor (Author)
ID Brešar, Boštjan (Author)
ID Kuenzel, Kirsti (Author)
ID Rall, Douglas F. (Author) |
|---|
| Files: |  PDF - Presentation file, download (803,91 KB)
MD5: 4AEB000C0E70536E98789402FA20E358
 URL - Source URL, visit https://www.sciencedirect.com/science/article/pii/S1572528623000191
|
|---|
| Language: | English |
|---|
| Typology: | 1.01 - Original Scientific Article |
|---|
| Organization: |  IMFM - Institute of Mathematics, Physics, and Mechanics
|
|---|
| Abstract: | 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. |
|---|
| Keywords: | Grundy domination, independence number, upper domination number, bipartite graphs |
|---|
| Publication status: | Published |
|---|
| Publication version: | Version of Record |
|---|
| Publication date: | 01.05.2023 |
|---|
| Year of publishing: | 2023 |
|---|
| Number of pages: | art. 100777 (15 str.) |
|---|
| Numbering: | Vol. 48, iss. 2 |
|---|
| PID: | 20.500.12556/DiRROS-18642  |
|---|
| UDC: | 519.17 |
|---|
| ISSN on article: | 1572-5286 |
|---|
| DOI: | 10.1016/j.disopt.2023.100777 |
|---|
| COBISS.SI-ID: | 154012931 |
|---|
| Note: |
|
|---|
| Publication date in DiRROS: | 09.04.2024 |
|---|
| Views: | 454 |
|---|
| Downloads: | 332 |
|---|
| Metadata: |    |
|---|
|
:
|
Copy citation |
|---|
| | | | Share: |  |
|---|
Hover the mouse pointer over a document title to show the abstract or click
on the title to get all document metadata. |
