Counterexamples to the characterisation of graphs with equal independence and annihilation number

DOI10.37236/11458MaRDI QIDQ6117243zbMATH OpenWikidataFDO

Authors Michaela Hiller

Publication date 16 February 2024

Published in The Electronic Journal of Combinatorics (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

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

zbMATH Keywords

annihilation numbercritical independence numberindependence number

Mathematics Subject Classification ID

Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Structural characterization of families of graphs (05C75)

Abstract: We disprove the characterisation of graphs with equal independence and annihilation number by Larson and Pepper (2011). Series of counterexamples with arbitrary number of vertices, arbitrary number of components, arbitrary large independence number and arbitrary large difference between the critical and the regular independence number are provided. Furthermore, we point out the error in the proof of the theorem. However, we show that the theorem still holds for bipartite graphs and connected claw-free graphs.

Review text

Summary: In this paper, we disprove the claimed characterisation of graphs with equal independence and annihilation number as proposed by \textit{C. E. Larson} and \textit{R. Pepper} [ibid. 18, No. 1, Research Paper P180, 9 p. (2011; Zbl 1238.05198)]. The annihilation number of a graph is defined as the largest integer \(p\) such that the sum of its smallest \(p\) degrees is greater than or equal to its size, i.e., its number of edges. Larson and Pepper [loc. cit.] claimed that for a given graph \(G=(V, E)\), its independence number \(\alpha(G)\) equals its annihilation number \(a(G)\) if and only if \begin{align*} a (G) &\geqslant \frac {n}{2}: \quad && \alpha^\prime (G)=a(G) \tag{1} \\ a (G) &= \frac{n-1}{2}: \quad && \alpha'(G-v)=a(G) \,\, \text{for some} \,\, v \in V. \tag{2} \end{align*} This paper provides series of counterexamples with an arbitrarily large number of vertices, an arbitrarily large number of components, an arbitrarily large independence number, and an arbitrarily large difference between the critical and the regular independence number. Furthermore, we identify the error in the proof of Larson and Pepper's [loc. cit.] theorem. Yet, we show that the theorem still holds for bipartite graphs and connected claw-free graphs.

Recommendations

• Graphs with equal independence and annihilation numbers
• On an annihilation number conjecture
• Efficiently recognizing graphs with equal independence and annihilation numbers
• Some more updates on an annihilation number conjecture: pros and cons
• The annihilation number does not bound the 2-domination number from the above

Cites work

• Algorithme de recherche d'un stable de cardinalité maximum dans un graphe sans étoilé
• Efficiently recognizing graphs with equal independence and annihilation numbers
• Graphs with equal independence and annihilation numbers
• On an annihilation number conjecture
• Paths, Trees, and Flowers
• The critical independence number and an independence decomposition

This page was built for publication: Counterexamples to the characterisation of graphs with equal independence and annihilation number

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