Oellermann, Ortrud R. On domination and digital convexity parameters. (English) Zbl 1274.05360 J. Comb. Math. Comb. Comput. 85, 273-285 (2013). Summary: Suppose \(V\) is a finite set and \({\mathcal C}\) a collection of subsets of \(V\) that contains \(\emptyset\) and \(V\) and is closed under taking intersections. Then the ordered pair \((V,{\mathcal C})\) is called a convexity and the elements of \({\mathcal C}\) are referred to as convex sets. For a set \(S\subseteq V\), the convex hull of \(S\) relative to \({\mathcal C}\), denoted by \(CH_{{\mathcal C}}(S)\), is the smallest convex set containing \(S\). The Carathéodory number, relative to a given convexity, is the smallest integer \(c\) such that for any subset \(S\) of \(V\) and any point \(v\in CH_{{\mathcal C}}(S)\) there is a subset \(F\) of \(S\) with \(|F|\leq c\) such that \(v\in CH_{{\mathcal C}}(F)\). A subset \(X\) of \(V\) is said to admit a Radon partition if \(X\) can be partitioned into two sets \(X_1\), \(X_2\) such that \(CH_{{\mathcal C}}(X_1)\cap CH_{{\mathcal C}}(X_2)\neq\emptyset\). The Radon number of a convexity is the smallest integer \(r\) (if it exists) such that every subset \(X\) of \(V\) with at least \(r\) elements admits a Radon partition. A set \(S\) of vertices in a graph \(G\) with vertex set \(V\) is digitally convex if for every vertex \(v\in V\), \(N[v]\subseteq N[S]\) implies \(v\in S\). A set \(X\) is irredundant if \(N[x]- N[X- \{x\}]\neq\emptyset\) for all \(x\in X\). The maximum cardinality of an irredundant set is the upper irredundance number of \(G\), denoted by \(IR(G)\). A set \(X\) of vertices in a graph \(G\) is a local irredundant set for a vertex \(v\) of \(G\), if for each \(x\in X\), \(x\in N[v]- N[X- \{x\}]\) or \(x\) is adjacent with a vertex of \(N[v]- N[X- \{x\}]\). The upper local irredundance number of \(v\), denoted by \(l_{IR}(v)\), is the maximum cardinality of a local irredundant set for \(v\). The upper local irredundance number of a graph \(G\), denoted by \(l_{IR}(G)\), is defined as \(l_{IR}(G)= \max\{l_{IR}(v)\mid v\in V\}\). We show that for the digital convexity of a graph \(G\): (i) the Caratéodory number equals \(l_{IR}(G)\) and (ii) the Radon number is bounded above by \(IR(G)+ 1\) and below by \(\beta(G)+1\) where \(\beta(G)\) is the independence number of \(G\). For the latter result it is shown that there are classes of graphs for which the lower (respectively, upper) bound is attained while the difference between the upper irredundance number and the independence number can be made as large as we wish. Moreover, there are graphs for which the Radon number of the digital convexity lies strictly between the bounds given in (ii) and does not equal one more than the upper domination number. Cited in 2 Documents MSC: 05C69 Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) Keywords:digital convexity; Carathéodory number; Radon number; Helly number; domination; independence; irredundance; local irredundance PDFBibTeX XMLCite \textit{O. R. Oellermann}, J. Comb. Math. Comb. Comput. 85, 273--285 (2013; Zbl 1274.05360)