The annihilation number does not bound the 2-domination number from the above

DOI10.1016/J.DISC.2019.111707MaRDI QIDQ2174567zbMATH OpenOpenAlexFDO

Authors Jun Yue, Shizhen Zhang, Yiping Zhu, Sandi Klavžar, Yongtang Shi

Publication date 21 April 2020

Published in Discrete Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

2-dominating set2-domination numberannihilation numbercactus graph

Mathematics Subject Classification ID

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

Abstract: The $2$-domination number $gamm{a}_2(G)$ of a graph $G$ is the minimum cardinality of a set $SsubseteqV(G)$ such that every vertex from $V(G)setminusS$ is adjacent to at least two vertices in $S$. The annihilation number $a(G)$ is the largest integer $k$ such that the sum of the first $k$ terms of the non-decreasing degree sequence of $G$ is at most the number of its edges. It was conjectured that $gamm{a}_2(G)leqa(G)+1$ holds for every connected graph $G$. The conjecture was earlier confirmed, in particular, for graphs of minimum degree $3$, for trees, and for block graphs. In this paper, we disprove the conjecture by proving that the $2$-domination number can be arbitrarily larger than the annihilation number. On the positive side we prove the conjectured bound for a large subclass of bipartite, connected cacti, thus generalizing a result of Jakovac from [Discrete Appl. Math. 260 (2019) 178--187].

Recommendations

• Relating the annihilation number and the 2-domination number of block graphs
• Relating the annihilation number and the 2-domination number of a tree
• Relating the total domination number and the annihilation number of cactus graphs and block graphs
• Bounding the domination number of a tree in terms of its annihilation number
• Relating the annihilation number and the total domination number for some graphs

Cites work

• \(k\)-domination and \(k\)-independence in graphs: A survey
• A note on the annihilation number and 2-domination number of a tree
• A note on the k-domination number of a graph
• Average eccentricity, \(k\)-packing and \(k\)-domination in graphs
• Bounds on the 2-domination number
• Graph theory
• scientific article; zbMATH DE number 3914370 (Why is no real title available?)
• scientific article; zbMATH DE number 7033848 (Why is no real title available?)
• scientific article; zbMATH DE number 5037208 (Why is no real title available?)
• Independence and k-domination in graphs
• Independence and the Havel-Hakimi residue
• Relating the annihilation number and the 2-domination number of a tree
• Relating the annihilation number and the 2-domination number of block graphs
• Relating the annihilation number and the total domination number of a tree
• Relating the total domination number and the annihilation number of cactus graphs and block graphs
• Total domination in graphs

Cited in

(13)

• Relating the annihilation number and the 2-domination number of block graphs
• Relating the total domination number and the annihilation number for quasi-trees and some composite graphs
• Some more updates on an annihilation number conjecture: pros and cons
• Rainbow domination numbers of generalized Petersen graphs
• The domination number of wrapped butterfly digraphs
• A note on the annihilation number and 2-domination number of a tree
• The restrained double Roman domination in graphs
• Relating the annihilation number and the total domination number for some graphs
• Relating the annihilation number and the 2-domination number of a tree
• Counterexamples to the characterisation of graphs with equal independence and annihilation number
• 3-component domination numbers in graphs
• On the equality of domination number and 2-domination number
• On 3-component domination numbers in graphs

This page was built for publication: The annihilation number does not bound the 2-domination number from the above

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