Digital repository of Slovenian research organisations

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

Title:Best possible upper bounds on the restrained domination number of cubic graphs
Authors:ID Brešar, Boštjan (Author)
ID Henning, Michael A. (Author)
Files:.pdf PDF - Presentation file, download (2,13 MB)
MD5: 5A65E5661DF4CBFCFB55FA237EAE42DB
 
URL URL - Source URL, visit https://onlinelibrary.wiley.com/doi/10.1002/jgt.23095
 
Language:English
Typology:1.01 - Original Scientific Article
Organization:Logo IMFM - Institute of Mathematics, Physics, and Mechanics
Abstract:A dominating set in a graph G is a set S of vertices such that every vertex in V(G)∖S is adjacent to a vertex in S. A restrained dominating set of G is a dominating set S with the additional restraint that the graph G−S obtained by removing all vertices in S is isolate-free. The domination number γ(G) and the restrained domination number γr(G) are the minimum cardinalities of a dominating set and restrained dominating set, respectively, of G. Let G be a cubic graph of order n. A classical result of Reed [Combin. Probab. Comput. 5 (1996), 277-295] states that γ(G)≤38n, and this bound is best possible. To determine a best possible upper bound on the restrained domination number of G is more challenging, and we prove that γr(G)≤25n.
Keywords:domination, restrained domination, cubic graphs
Publication status:Published
Publication version:Version of Record
Publication date:01.08.2024
Year of publishing:2024
Number of pages:str. 763–815
Numbering:Vol. 106, iss. 4
PID:20.500.12556/DiRROS-19113 New window
UDC:519.17
ISSN on article:0364-9024
DOI:10.1002/jgt.23095 New window
COBISS.SI-ID:199137795 New window
Note:
Publication date in DiRROS:18.06.2024
Views:511
Downloads:298
Metadata:XML DC-XML DC-RDF
:
BREŠAR, Boštjan and HENNING, Michael A., 2024, Best possible upper bounds on the restrained domination number of cubic graphs. Journal of graph theory [online]. 2024. Vol. 106, no. 4. [Accessed 9 April 2025]. DOI 10.1002/jgt.23095. Retrieved from: https://dirros.openscience.si/IzpisGradiva.php?lang=eng&id=19113
Copy citation
  
Share:Bookmark and Share


Similar works from our repository:

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:Journal of graph theory
Shortened title:J. graph theory
Publisher:Wiley
ISSN:0364-9024
COBISS.SI-ID:25747712 New window

Document is financed by a project

Funder:ARIS - Slovenian Research and Innovation Agency
Project number:P1-0297
Name:Teorija grafov
Funder:ARIS - Slovenian Research and Innovation Agency
Project number:J1-2452
Name:Strukturni, optimizacijski in algoritmični problemi v geometrijskih in topoloških predstavitvah grafov
Funder:ARIS - Slovenian Research and Innovation Agency
Project number:J1-3002
Name:Prirejanja in barvanja povezav v kubičnih grafih
Funder:ARIS - Slovenian Research and Innovation Agency
Project number:N1-0285
Name:Metrični problemi v grafih in hipergrafih
Funder:ARIS - Slovenian Research and Innovation Agency
Project number:J1-4008
Name:Drevesno neodvisnostno število grafov
Funder:Other - Other funder or multiple funders
Funding programme:South African National Research Foundation
Project number:129265
Funder:Other - Other funder or multiple funders
Funding programme:South African National Research Foundation
Project number:132588

Licences

License:CC BY-NC-ND 4.0, Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International
Link:http://creativecommons.org/licenses/by-nc-nd/4.0/
Description:The most restrictive Creative Commons license. This only allows people to download and share the work for no commercial gain and for no other purposes.

Secondary language

Language:Slovenian
Keywords:dominacija, zamejena dominacija, kubični grafi


Back