Some comments on the Slater number

DOI10.1016/J.DISC.2017.02.009zbMATH Open1361.05096arXiv1608.04560OpenAlexW2963210814MaRDI QIDQ526227FDOQ526227

Authors: Michael Gentner, Dieter Rautenbach 

Publication date: 10 May 2017

Published in: Discrete Mathematics (Search for Journal in Brave)

Abstract: Let $G$ be a graph with degree sequence $d_{1}geqldotsgeq{d}_n$. Slater proposed $sell(G)=mins:(d_1+1)+cdots+(d_s+1)geqn$ as a lower bound on the domination number $gamma(G)$ of $G$. We show that deciding the equality of $gamma(G)$ and $sell(G)$ for a given graph $G$ is NP-complete but that one can decide efficiently whether $gamma(G)>sell(G)$ or $gamma(G)leqleft(leftlceillnleft(fracn(G)sell(G)ight)ightceil+1ight)sell(G)$. For real numbers $alpha$ and $$ with $$, let $$ be the class of non-null graphs $G$ such that every non-null subgraph $H$ of $G$ has at most $$ many edges. Generalizing a result of Desormeaux, Haynes, and Henning, we show that $$ for every graph $G$ in $$ with $alphaleqfrac32$. Furthermore, we show that $gamma(G)/sell(G)$ is bounded for graphs $G$ in $$ if and only if $alpha<2$. For an outerplanar graph $G$ with $sell(G)geq2$, we show $gamma(G)leq6sell(G)-6$. In analogy to $sell(G)$, we propose $sel{l}_t(G)=mins:d_1+cdots+d_{s}geqn$ as a lower bound on the total domination number. Strengthening results due to Raczek as well as Chellali and Haynes, we show that $sel{l}_t(T)geqfracn+2-n_{1}2$ for every tree $T$ of order $n$ at least $2$ with $n_1$ endvertices.

Full work available at URL: https://arxiv.org/abs/1608.04560

Recommendations

• Improved bounds on the domination number of a tree
• Bounds on the domination number of a digraph
• The Slater and sub-\(k\)-domination number of a graph with applications to domination and \(k\)-domination
• A note on lower bounds for the total domination number of digraphs
• Revisiting \(k\)-tuple dominating sets with emphasis on small values of \(k\)

zbMATH Keywords

sparse graphsdominationtotal dominationouterplanar graphsSlater numberpaired domination

Mathematics Subject Classification ID

Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Density (toughness, etc.) (05C42)

Cites Work

• Best Algorithms for Approximating the Maximum of a Submodular Set Function
• Title not available (Why is that?)
• Title not available (Why is that?)
• Total Domination in Graphs
• Largest domination number and smallest independence number of forests with given degree sequence
• Improved bounds on the domination number of a tree
• Lower bound on the domination number of a tree
• Title not available (Why is that?)
• Title not available (Why is that?)
• Bounds on the connected domination number of a graph
• A note on the total domination number of a tree
• Lower bound on the paired domination number of a tree

Cited In (2)

• Further results on packing related parameters in graphs
• Revisiting \(k\)-tuple dominating sets with emphasis on small values of \(k\)

This page was built for publication: Some comments on the Slater number

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q526227)