Exponential independence in subcubic graphs

DOI10.1016/J.DISC.2021.112439MaRDI QIDQ2032859zbMATH OpenOpenAlexWikidataFDO

Authors Johannes Pardey, Dieter Rautenbach, Stéphane Bessy

Publication date 14 June 2021

Published in Discrete Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

exponential dominationexponential independence

Mathematics Subject Classification ID

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

Abstract: A set $S$ of vertices of a graph $G$ is exponentially independent if, for every vertex $u$ in $S$, ${\displaystyle }$sumlimits_{vin Ssetminus { u}}left(frac{1}{2} ight)^{{ m dist}_{(G,S)}(u,v)-1}<1,${\displaystyle }$ where ${mdist}_{(G,S)}(u,v)$ is the distance between $u$ and $v$ in the graph $G-(Ssetminusu,v)$. The exponential independence number $alph{a}_e(G)$ of $G$ is the maximum order of an exponentially independent set in $G$. In the present paper we present several bounds on this parameter and highlight some of the many related open problems. In particular, we prove that subcubic graphs of order $n$ have exponentially independent sets of order $Omega(n/lo{g}^2(n))$, that the infinite cubic tree has no exponentially independent set of positive density, and that subcubic trees of order $n$ have exponentially independent sets of order $(n+3)/4$.

Recommendations

• Exponential independence number of some graphs
• Exponential independence
• Exponential domination in subcubic graphs
• Independent domination in subcubic graphs

Cites work

• Bounds on the exponential domination number
• Domination with exponential decay
• Exponential Domination Critical and Stability in Some Graphs
• Exponential domination in subcubic graphs
• Exponential independence
• Exponential independence number of some graphs
• Hereditary equality of domination and exponential domination
• On exponential domination of \(C_m\times C_n\)
• On exponential domination of some graphs
• Relating domination, exponential domination, and porous exponential domination

Cited in

(4)

• On exponential trees
• Exponential independence
• Exponential domination in subcubic graphs
• Exponential independence number of some graphs

This page was built for publication: Exponential independence in subcubic graphs

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