论文标题
图中的部分统治和无数数字
Partial Domination and Irredundance Numbers in Graphs
论文作者
论文摘要
图$ g =（v，e）$的主导集是一个顶点$ d $，因此$ v（g）\ setminus d $中的每个顶点都与$ d $中的顶点相邻。 $ d $的最小统治集的基数称为$ g $的统治数，并用$γ（g）$表示。如果$ g-n_ {g} [g} [d] $包含no $ k $ -cliques。 $ g $的$ k $隔离套件的最低基数称为$ k $ solation $ g $，并用$ b {k}（g）$表示。显然，$γ（g）= 〜I_ {1}（g）$。如果对于每个非分离的顶点$ v $ $ g [i] $，一个顶点套装$ i $是不余后的，存在$ v \ setminus i $ in of pertex $ u $，以至于$ n_ {g}（g}（u）\ cap i = \ cap i = \ {v \ {v \} $。如果设置$ i \ cup \ {u \} $不再是v（g）\ setminus i $中的任何$ u \，则不再是不再是不retedentapen的。最大性不繁殖集的最低基数称为$ g $的不重新登记，并用$ ir（g）$表示。 Allan和Laskar \ Cite {Al1978}以及Bollobás和Cockayne \ cite {Boco1979}独立证明$γ（g）<2ir（g）$，可以写入$ _1（g）<2ir（g）<2ir（g）$，对于任何图$ G $。在本文中，对于具有最高度$δ$的图$ g $，我们以$ r（g）$为$ uir（g）$ for $δ-2 \ leq k \ leq k \ lequqΔ+ 1 $在$ ar_ {k}（g）上建立了尖锐的上限。
A dominating set of a graph $G=(V,E)$ is a vertex set $D$ such that every vertex in $V(G) \setminus D$ is adjacent to a vertex in $D$. The cardinality of a smallest dominating set of $D$ is called the domination number of $G$ and is denoted by $γ(G)$. A vertex set $D$ is a $k$-isolating set of $G$ if $G - N_{G}[D]$ contains no $k$-cliques. The minimum cardinality of a $k$-isolating set of $G$ is called the $k$-isolation number of $G$ and is denoted by $ι_{k}(G)$. Clearly, $γ(G) = ι_{1}(G)$. A vertex set $I$ is irredundant if, for every non-isolated vertex $v$ of $G[I]$, there exists a vertex $u$ in $V \setminus I$ such that $N_{G}(u) \cap I = \{v\}$. An irredundant set $I$ is maximal if the set $I \cup \{u\}$ is no longer irredundant for any $u \in V(G) \setminus I$. The minimum cardinality of a maximal irredundant set is called the irredundance number of $G$ and is denoted by $ir(G)$. Allan and Laskar \cite{AL1978} and Bollobás and Cockayne \cite{BoCo1979} independently proved that $γ(G) < 2ir(G)$, which can be written $ι_1(G) < 2ir(G)$, for any graph $G$. In this paper, for a graph $G$ with maximum degree $Δ$, we establish sharp upper bounds on $ι_{k}(G)$ in terms of $ir(G)$ for $Δ- 2 \leq k \leq Δ+ 1$.
