Girth, minimum degree, independence, and broadcast independence

DOI10.22049/CCO.2019.26346.1098MaRDI QIDQ5242945zbMATH OpenOpenAlexFDO

Authors Stéphane Bessy, Dieter Rautenbach

Publication date 8 November 2019

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

independence packing broadcast independence

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

Abstract: An independent broadcast on a connected graph

G

is a function

f : V (G) o m a t h b b N_{0}

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

a l p h a_{b} (G)

of

G

is the largest weight

s u m l i m i t s_{x i n V (G)} f (x)

of an independent broadcast

f

on

G

. It is known that

a l p h a (G) l e q a l p h a_{b} (G) l e q 4 a l p h a (G)

for every connected graph

G

, where

a l p h a (G)

is the independence number of

G

. If

G

has girth

g

and minimum degree

d e l t a

, we show that

a l p h a_{b} (G) l e q 2 a l p h a (G)

provided that

g g e q 6

and

d e l t a g e q 3

or that

g g e q 4

and

d e l t a g e q 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

a l p h a_{b} (G) g e q 2 l e f t (1 - f r a c 1 k i g h t) a l p h a (G)

. Our results imply that lower bounds on the girth and the minimum degree of a connected graph

G

can lower the fraction

f r a c a l p h a_{b} (G) a l p h a (G)

from

4

below

2

, but not any further.

Recommendations

Cites work

Cited in

(11)

This page was built for publication: Girth, minimum degree, independence, and broadcast independence

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