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

DOI10.1016/J.DISC.2019.111707zbMATH Open1437.05187arXiv1904.12141OpenAlexW2982454030MaRDI QIDQ2174567FDOQ2174567

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)

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].

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

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

zbMATH Keywords

cactus graph2-domination numberannihilation number2-dominating set

Mathematics Subject Classification ID

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

Cites Work

• Graph theory
• Independence and \(k\)-domination in graphs
• Title not available (Why is that?)
• Total domination in graphs
• \(k\)-domination and \(k\)-independence in graphs: A survey
• Independence and the Havel-Hakimi residue
• Relating the annihilation number and the 2-domination number of a tree
• A note on the k-domination number of a graph
• Relating the annihilation number and the 2-domination number of block graphs
• Bounds on the 2-domination number
• A note on the annihilation number and 2-domination number of a tree
• Title not available (Why is that?)
• Relating the annihilation number and the total domination number of a tree
• Average eccentricity, \(k\)-packing and \(k\)-domination in graphs
• Relating the total domination number and the annihilation number of cactus graphs and block graphs
• Title not available (Why is that?)

Cited In (11)

• Relating the annihilation number and the 2-domination number of a tree
• A note on the annihilation number and 2-domination number of a tree
• The domination number of wrapped butterfly digraphs
• 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
• The restrained double Roman domination in graphs
• Rainbow domination numbers of generalized Petersen graphs
• Relating the annihilation number and the total domination number for some graphs
• Counterexamples to the characterisation of graphs with equal independence and annihilation number
• 3-component domination numbers in graphs
• Relating the annihilation number and the 2-domination number of block 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)