Disjoint Paired-Dominating sets in Cubic Graphs

A paired-dominating set of a graph G is a dominating set D with the additional requirement that the induced subgraph G[D] contains a perfect matching. We prove that the vertex set of every claw-free cubic graph can be partitioned into two paired-dominating sets.

Detalles Bibliográficos
Autores principales: Bacsó, Gábor, Bujtás, Csilla, Tompkins, Casey, Tuza, Zsolt
Formato: Online Artículo Texto
Lenguaje:English
Publicado: Springer Japan 2019
Materias:
Original Paper
Acceso en línea:https://www.ncbi.nlm.nih.gov/pmc/articles/PMC6777509/
https://www.ncbi.nlm.nih.gov/pubmed/31631942
http://dx.doi.org/10.1007/s00373-019-02063-w
_version_ 1783456642482831360
author Bacsó, Gábor
Bujtás, Csilla
Tompkins, Casey
Tuza, Zsolt
author_facet Bacsó, Gábor
Bujtás, Csilla
Tompkins, Casey
Tuza, Zsolt
author_sort Bacsó, Gábor
collection PubMed
description A paired-dominating set of a graph G is a dominating set D with the additional requirement that the induced subgraph G[D] contains a perfect matching. We prove that the vertex set of every claw-free cubic graph can be partitioned into two paired-dominating sets.
format Online
Article
Text
id pubmed-6777509
institution National Center for Biotechnology Information
language English
publishDate 2019
publisher Springer Japan
record_format MEDLINE/PubMed
spelling pubmed-67775092019-10-17 Disjoint Paired-Dominating sets in Cubic Graphs Bacsó, Gábor Bujtás, Csilla Tompkins, Casey Tuza, Zsolt Graphs Comb Original Paper A paired-dominating set of a graph G is a dominating set D with the additional requirement that the induced subgraph G[D] contains a perfect matching. We prove that the vertex set of every claw-free cubic graph can be partitioned into two paired-dominating sets. Springer Japan 2019-07-15 2019 /pmc/articles/PMC6777509/ /pubmed/31631942 http://dx.doi.org/10.1007/s00373-019-02063-w Text en © The Author(s) 2019 Open AccessThis article is distributed under the terms of the Creative Commons Attribution 4.0 International License (http://creativecommons.org/licenses/by/4.0/), which permits unrestricted use, distribution, and reproduction in any medium, provided you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons license, and indicate if changes were made.
spellingShingle Original Paper
Bacsó, Gábor
Bujtás, Csilla
Tompkins, Casey
Tuza, Zsolt
Disjoint Paired-Dominating sets in Cubic Graphs
title Disjoint Paired-Dominating sets in Cubic Graphs
title_full Disjoint Paired-Dominating sets in Cubic Graphs
title_fullStr Disjoint Paired-Dominating sets in Cubic Graphs
title_full_unstemmed Disjoint Paired-Dominating sets in Cubic Graphs
title_short Disjoint Paired-Dominating sets in Cubic Graphs
title_sort disjoint paired-dominating sets in cubic graphs
topic Original Paper
url https://www.ncbi.nlm.nih.gov/pmc/articles/PMC6777509/
https://www.ncbi.nlm.nih.gov/pubmed/31631942
http://dx.doi.org/10.1007/s00373-019-02063-w
work_keys_str_mv AT bacsogabor disjointpaireddominatingsetsincubicgraphs
AT bujtascsilla disjointpaireddominatingsetsincubicgraphs
AT tompkinscasey disjointpaireddominatingsetsincubicgraphs
AT tuzazsolt disjointpaireddominatingsetsincubicgraphs

Ejemplares similares