Girth, minimum degree, independence, and broadcast independence

Document Type : Original paper

Authors

1 LIRMM

2 89069 Ulm, Germay

Abstract

An independent broadcast on a connected graph G is a function f:V(G)→N0 such that, for every vertex x of G, the value f(x) is at most the eccentricity of x in G, and f(x)>0 implies that f(y)=0 for every vertex y of G within distance at most f(x) from x. The broadcast independence number αb(G) of G is the largest weight ∑x∈V(G)f(x) of an independent broadcast f on G. It is known that α(G)≤αb(G)≤4α(G) for every connected graph G, where α(G) is the independence number of G. If G has girth g and minimum degree δ, we show that αb(G)≤2α(G) provided that g≥6 and δ≥3 or that g≥4 and δ≥5. Furthermore, we show that, for every positive integer k, there is a connected graph G of girth at least k and minimum degree at least k such that αb(G)≥2(1−1k)α(G). Our results imply that lower bounds on the girth and the minimum degree of a connected graph G can lower the fraction αb(G)α(G) from 4 below 2, but not any further.

Keywords

Main Subjects

References

[1] M. Ahmane, I. Bouchemakh, and E. Sopena, On the broadcast independence number of caterpillars, Discrete Appl. Math. 244 (2018), 20–35.
[2] S. Bessy and D. Rautenbach, Algorithmic aspects of broadcast independence, arXiv 1809.07248.
[3] S. Bessy and D. Rautenbach, Relating broadcast independence and independence, Manuscript 2018.
[4] I. Bouchemakh and M. Zemir, On the broadcast independence number of grid graph, Graphs Combin. 30 (2014), no. 1, 83–100.
[5] R. Diestel, Graduate Texts in Mathematics, Springer-Verlag New York, Incorporated, 2000.
[6] J.E. Dunbar, D.J. Erwin, T.W. Haynes, S.M. Hedetniemi, and S.T. Hedetniemi, Broadcasts in graphs, Discrete Appl. Math. 154 (2006), no. 1, 59–75.
[7] P. Erdős, Graph theory and probability II, Canad. J. Math. 13 (1961), 346–352.
[8] D.J. Erwin, Cost domination in graphs, (Ph.D. thesis), Western Michigan University, 2001.
[9] F. Joos and D. Rautenbach, Equality of distance packing numbers, Discrete Math. 338 (2015), no. 12, 2374–2377.
[10] J. Topp and L. Volkmann, On packing and covering numbers of graphs, Discrete Math. 96 (1991), no. 3, 229–238.
 
Communications in Combinatorics and Optimization
Volume 4, Issue 2
Special issue in honour of Prof. Lutz Volkmann
December 2019
Pages 131-139

Files

Share

How to cite

Statistics