Digital repository of Slovenian research organisations

Show document
A+ | A- | Help | SLO | ENG

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 PDF - Presentation file, download (803,91 KB)
MD5: 4AEB000C0E70536E98789402FA20E358
 
URL URL - Source URL, visit https://www.sciencedirect.com/science/article/pii/S1572528623000191
 
Language:English
Typology:1.01 - Original Scientific Article
Organization:Logo IMFM - Institute of Mathematics, Physics, and Mechanics
Abstract:The Grundy domination number, γgr(G), of a graph G is the maximum length of a sequence (v1,v2,…,vk) of vertices in G such that for every i∈{2,…,k}, the closed neighborhood N[vi] contains a vertex that does not belong to any closed neighborhood N[vj], 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 Γ(G), which is in turn greater than or equal to the independence number α(G). In this paper, we initiate the study of the class of graphs G with Γ(G)=γgr(G) and its subclass consisting of graphs G with α(G)=γ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 Γ(G)=γ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 New window
UDC:519.17
ISSN on article:1572-5286
DOI:10.1016/j.disopt.2023.100777 New window
COBISS.SI-ID:154012931 New window
Note:
Publication date in DiRROS:09.04.2024
Views:578
Downloads:391
Metadata:XML DC-XML DC-RDF
:
BACSÓ, Gábor, BREŠAR, Boštjan, KUENZEL, Kirsti and RALL, Douglas F., 2023, Graphs with equal Grundy domination and independence number. Discrete optimization [online]. 2023. Vol. 48, no. 2. [Accessed 7 April 2025]. DOI 10.1016/j.disopt.2023.100777. Retrieved from: https://dirros.openscience.si/IzpisGradiva.php?lang=eng&id=18642
Copy citation
  
Share:Bookmark and Share



Similar works from other repositories:

No similar works found

Hover the mouse pointer over a document title to show the abstract or click on the title to get all document metadata.

Record is a part of a journal

Title:Discrete optimization
Publisher:Elsevier
ISSN:1572-5286
COBISS.SI-ID:513620761 New window

Document is financed by a project

Funder:ARRS - Slovenian Research Agency
Project number:P1-0297
Name:Teorija grafov
Funder:ARRS - Slovenian Research Agency
Project number:J1-2452
Name:Strukturni, optimizacijski in algoritmični problemi v geometrijskih in topoloških predstavitvah grafov
Funder:ARRS - Slovenian Research Agency
Project number:J1-3002
Name:Prirejanja in barvanja povezav v kubičnih grafih
Funder:ARRS - Slovenian Research Agency
Project number:J1-4008
Name:Drevesno neodvisnostno število grafov
Funder:Other - Other funder or multiple funders
Funding programme:National Research, Development and Innovation Office - NKFIH, Hungary
Project number:SNN 129364

Licences

License:CC BY 4.0, Creative Commons Attribution 4.0 International
Link:http://creativecommons.org/licenses/by/4.0/
Description:This is the standard Creative Commons license that gives others maximum freedom to do what they want with the work as long as they credit the author.

Secondary language

Language:Slovenian
Keywords:Grundyjeva dominacija, neodvisnostno število, zgornje dominantno število, dvodelni grafi


Back