Exponential independence

DOI10.1016/J.DISC.2016.10.018MaRDI QIDQ2401799zbMATH OpenOpenAlexWikidataFDO

Authors Simon Jäger, Dieter Rautenbach

Publication date 5 September 2017

Published in Discrete Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

exponential dominationexponential independenceindependence

Mathematics Subject Classification ID

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

Abstract: For a set $S$ of vertices of a graph $G$, a vertex $u$ in $V(G)setminusS$, and a vertex $v$ in $S$, let ${mdist}_{(G,S)}(u,v)$ be the distance of $u$ and $v$ in the graph $G-(Ssetminusv)$. Dankelmann et al. (Domination with exponential decay, Discrete Math. 309 (2009) 5877-5883) define $S$ to be an exponential dominating set of $G$ if $w_{(G,S)}(u)geq1$ for every vertex $u$ in $V(G)setminusS$, where $w_{(G,S)}(u)=sumlimit{s}_{vinS}left(frac12ight{)}^{{mdist}_{(G,S)}(u,v)-1}$. Inspired by this notion, we define $S$ to be an exponential independent set of $G$ if $w_{(G,Ssetminusu)}(u)<1$ for every vertex $u$ in $S$, and the exponential independence number $alph{a}_e(G)$ of $G$ as the maximum order of an exponential independent set of $G$. Similarly as for exponential domination, the non-local nature of exponential independence leads to many interesting effects and challenges. Our results comprise exact values for special graphs as well as tight bounds and the corresponding extremal graphs. Furthermore, we characterize all graphs $G$ for which $alph{a}_e(H)$ equals the independence number $alpha(H)$ for every induced subgraph $H$ of $G$, and we give an explicit characterization of all trees $T$ with $alph{a}_e(T)=alpha(T)$.

Recommendations

• Exponential independence number of some graphs
• Exponential independence in subcubic graphs
• On exponential domination of some graphs
• Domination with exponential decay
• Exponential Domination Critical and Stability in Some Graphs

Cites work

• Domination with exponential decay
• Equality of distance packing numbers
• Exponential domination in subcubic graphs
• On exponential domination of \(C_m\times C_n\)
• On exponential domination of some graphs
• On the total influence number of a graph
• Packing in trees
• Relations between packing and covering numbers of a tree
• Unsolved algorithmic problems on trees

Cited in

(5)

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

This page was built for publication: Exponential independence

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