scientific article; zbMATH DE number 1161346
Let \(G=(V,E)\) be a graph and let \(S\subseteq V\). For \(v\in V\) denote \(N(v)=\{u\in V\mid uv\in E\}\) and \(N[v]=N(v)\cup\{v\}\). Extend these definitions on \(S\) by setting \(N(S)=\bigcup_{v\in S} N(v)\) and \(N[S]=N(S)\cup S\). The authors generalize such notions as domination number, independence number and others by introducing the function \[ f(S;i,a,d,z)=i\cdot | I(S)| + a\cdot | A(S)| + d\cdot | \partial(S)| + z\cdot | Z(S)|. \] Here \(I(S)=S-N(S)\), \(A(S)=S\cap N(S)\), \(\partial(S)=N[S]-S\) and \(Z(S)=V-N[S]\). Denote \(f(G;i,a,d,z)=\max_{S\subseteq V} f(S;i,a,d,z)\). The paper is devoted to properties of this function. It is shown that \(-f(G;-1,-1,0,-\infty)\) is the independence number of \(G\), \(-f(G;-1,-\infty,0,-\infty)\) is the independent domination number, \(f(G;1,-\infty,0,z)\) is the independence number for any \(z\leq 0\). Similar equalities which involve some other graph parameters are established as well. Moreover, the function in question is in a sense monotone, i.e. if \(a\geq i\), \(d\geq z\) and \(e\) is an edge of the complement of \(G\) then \(f(G+e;i,a,d,z)\geq f(G;i,a,d,z)\) and conversely if \(a\leq i\) and \(d\leq z\). As further results some Gallai-type equalities are derived. Furthermore, it turns out that for any tree \(T\) and fixed \(i,a,d,z\) the number \(f(T;i,a,d,z)\) can be computed in polynomial time.
- Inequalities involving independence domination, f-domination, connected and total f-domination numbers
- On f-domination number of a graph
- scientific article; zbMATH DE number 1156620
- Generalized independence and domination in graphs
- A structure preserving generalization of independence, domination and irredundance
- Generalized independence and domination in graphs
- On the differential polynomial of a graph
- On the 2-packing differential of a graph
- The differential of the line graph \(\mathcal{L} (G)\)
- From the strong differential to Italian domination in graphs
- \(\beta\)-differential of a graph
- On the differential and Roman domination number of a graph with minimum degree two
- Relations between the differential and parameters in graphs
- A structure preserving generalization of independence, domination and irredundance
- A general method in the theory of domination in graphs
- Inequalities involving independence domination, f-domination, connected and total f-domination numbers
- Mod-2 independence and domination in graphs
- On the perfect differential of a graph
- The differential on graph operator \(\mathrm{R}(G)\)
- Restrained differential of a graph
This page was built for publication:
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4393345)
