The inequality chain \(ir(G)\le \gamma(G)\le i(G)\le \alpha(G) \le \Gamma(G) \le I\!R(G)\) is known as the domination chain, where \(ir(G), \gamma(G), i(G), \alpha(G), \Gamma(G)\) and \(I\!R(G)\) are the lower irredundance number, the domination number, the independence domination number, the independence number, the upper domination number and the upper irredundance number of \(G\), respectively. The Ramsey-type problem seeks to characterize the family \({\mathcal H}\) of graphs such that every \({\mathcal H}\)-free graph \(G\) has a bounded parameter \(\mu\). The classical Ramsey’s theorem states that every \(\{K_n, E_n\}\)-free graph has a bounded number of vertices. Furuya (Discrete Math.Theor 2018) characterized \({\mathcal H}\) such that every connected \({\mathcal H}\)-free graph \(G\) has a bounded domination number. The characterization of the graph family \({\mathcal H}\) for which every connected \({\mathcal H}\)-free graph \(G\) has a bounded independence number was due to Choi, Furuya, Kim, Park (Discrete math. 2020) and Chiba, Furuya (Electron. J. Combin., 2022). In this paper, we further characterize \({\mathcal H}\) such that every connected \({\mathcal H}\)-free graph \(G\) has bounded \(\mu(G)\) for \(\mu\) belonging to the set \(\{ir(G), i(G), \Gamma(G), \text{IR}(G)\}\). This completes the characterization of \({\mathcal H}\) for which every connected \({\mathcal H}\)-free graph \(G\) has bounded \(\mu(G)\) for \(\mu(G)\) along the domination chain. Additionally, we characterize \({\mathcal H}\) such that every connected \({\mathcal H}\)-free graph \(G\) has bounded \(\mu(G)\) for \(\mu\) related to the domination number. Specifically, we consider the following parameters of \(G\): open irredundance number \(O\!I\!R(G)\), independence saturation number \(I\!S(G)\) and irredundance saturation number \(I\!R\!S(G)\).
In this paper, we consider only finite and simple graphs. Let \(G=(V,E)\) be a graph. For a vertex \(v\in V\), let \(N_G(v)=\{u\in V: uv\in E\}\) denote the (open) neighborhood of \(v\), and let \(N_G[v]=N(v)\cup \{v\}\) denote the closed neighborhood of \(v\) (the subscript may be omitted if there is no confusion). For a subset \(S\subseteq V\), let \(N_G[S]=\bigcup_{v\in S}N_G[v]\). We denote by \(G[S]\) the subgraph of \(G\) induced by edges in \(S\). A set \(S\subseteq V\) is called an independent set of \(G\) if there is no edge in \(G[S]\). For a set \(T\subseteq V\) disjoint from \(S\), we denote by \(G[S,T]\) the subgraph of \(G\) induced by edges between \(S\) and \(T\). The more notation, see [7].
For graphs \(H_1\) and \(H_2\), we say \(H_1\prec H_2\) if \(H_1\) is an induced subgraph of \(H_2\). Let \(\mathcal H\) be a family of graphs, we say \(G\) is \(\mathcal H\)-free, if there is no graph \(H\in \mathcal H\) such that \(H\prec G\). For graph families \(\mathcal H_{1}\) and \(\mathcal H_2\), we say \(\mathcal H_1\le \mathcal H_2\) if for any \(H_2\in \mathcal H_2\) there exists \(H_1\in \mathcal H_1\) such that \(H_1\prec H_2\), i.e., each graph in \(\mathcal H_2\) is not \(\mathcal H_1\)-free. The following straightforward result will be commonly used without explicit mention.
Observation 1.1. The relation ‘\(\le\)’ is transitive. Therefore, if \(\mathcal{H}_1\le \mathcal{H}_2\), then every \(\mathcal{H}_1\)-free graph is also \(\mathcal{H}_2\)-free.
As usual, let \(P_n,\, C_n,\, K_n\) and \(E_n\) denote a path, a cycle, a complete graph, and an edgeless graph of order \(n\), respectively. Let \(K_{s,t}\) be the complete bipartite graph with partitions of orders \(s\) and \(t\).
The classical Ramsey’s Theorem can be stated as follows:
(A) (Ramsey’s Theorem [14], 1929) For a family \(\mathcal H\) of graphs, there is a constant \(c=c(\mathcal H)\) such that \(|V(G)|< c\) for every \(\mathcal H\)-free graph \(G\) if and only if \(\mathcal H\le \{K_m,E_n\}\) for some positive integers \(m\) and \(n\);
(B) (The connected version, Proposition 9.4.1 in [7]) For a family \(\mathcal H\) of graphs, there is a constant \(c=c(\mathcal H)\) such that \(|V(G)|< c\) for every connected \(\mathcal H\)-free graph \(G\) if and only if \(\mathcal H\le \{K_n, K_{1,n}, P_n\}\) for some positive integer \(n\).
The Ramsey number \(R(m,n)\) is the least integer \(c=c(\{K_m, E_n\})\) in (A), thus every graph \(G\) of order at least \(R(m,n)\) contains either a complete graph \(K_m\) or an edgeless graph \(E_n\).
In general, given a graph parameter \(\mu\), define \[B\text{-}\mu=\{\mathcal H: \text{there is constant } c \text{ such that } \mu(G)<c \text{ for any connected } \mathcal H\text{-free graph } G\}.\]
A Ramsey-type problem of \(\mu\) is to determine \(B\)–\(\mu\).
Problem 1.2. Given a graph parameter \(\mu\), determine \(\text{B-}\mu\).
In the following, we list more results on different parameters of Problem 1.2.
Let \(nG\) be the graph consisting of \(n\) disjoint copies of \(G\). In order to state the forbidden subgraphs condition conveniently, we introduce additional kinds of graphs (as shown in Figure 1).
In this paper, we mainly concern Problem 1.2 when \(\mu\) are parameters related to domination.
Let \(G=(V,E)\) be a graph. For a property \(P\) about subsets of \(V\), we define a subset \(S\) as a minimal (resp. maximal) \(P\)-set if \(S\) satisfies \(P\), and no proper subset (resp. superset) of \(S\) satisfies \(P\). A set \(S\subseteq V\) is called a dominating set of \(G\) if \(V=N[S]\). Define the domination number of \(G\) as \[\gamma(G)=\min\{|S| : S \text{ is a dominating set of } G\},\] and the upper domination number of \(G\) as \[\Gamma(G)=\max\{|S| : S \text{ is a minimal dominating set of } G\}.\]
Recall that the independence number of \(G\) \[\alpha(G)=\max\{|S| : S \text{ is an independent set of $G$}\}.\]
Define the independence domination number of \(G\) as \[i(G)=\min\{|S| : S \text{ is a maximal independent set of $G$}\}.\]
Let \(S\subseteq V(G)\) and \(v\in S\). The private neighborhood of \(v\) with respect to \(S\) is defined as \[P\!N[v,S]=N_G[v]-N_G[S\setminus\{v\}].\]
A set \(S\subseteq V(G)\) is called an irredundant set if every vertex \(s\) in \(S\) has at least one private neighbor, i.e., \(P\!N[s,S]\neq \emptyset\) for any \(s\in S\).
The upper irredundance number, \(\text{IR}(G)\), is defined as \[\mbox{IR}(G)=\max\{|S| : S \text{ is an irredundant set of $G$} \},\] and the lower irredundance number, \(ir(G)\), of \(G\) is defined as \[ir(G)=\min\{|S| : S \text{ is a maximal irredundant set of $G$} \}.\]
Note that \(\gamma(G)\) is also the minimum size of minimal dominating sets of \(G\) since a dominating set with minimum size must be a minimal dominating set. Similarly, \(\alpha(G)\) (resp. \(\mbox{IR}(G)\)) is the maximum size of maximal independent (resp. irredundant) sets of \(G\). It can be checked directly that a maximal independent set is a minimal dominating set, and a minimal dominating set is a maximal irredundant set. Visually, \[\{\mbox{maximal independent set}\}\subseteq \{\mbox{minimal dominating set}\}\subseteq \{\mbox{maximal irredundant set}\}.\] By the definitions of \(ir(G), \gamma(G), i(G), \alpha(G), \Gamma(G)\), and \(\text{\it IR}(G)\), we have the following inequality chain.
Proposition 1.3 ([10]). For any graph \(G\), it holds that \[ ir(G)\le \gamma(G)\le i(G)\le \alpha(G) \le \Gamma(G) \le \text{IR}(G).\]
The inequality chain above is called the domination chain. As pointed in [10], this inequality chain has become one of the strongest focal points for research in domination theory. Many aspects of this chain has been studied. For the history and more information of these parameters, the reader can survey the book [10] and references therein. For parameters \(\mu\) defined by size of special subsets of \(V(G)\), we will use \(\mu\)-set to mean subset \(S\) realizing parameter \(\mu\); for example, a \(\gamma\)-set \(D\) of \(G\) is a minimum dominating set of \(G\) such that \(\gamma(G)=|D|\).
We first focus on Problem 1.2 for \(\mu\) in the domination chain. Furuya [8] has determined \(B\)–\(\gamma\).
Theorem 1.4 ([8]). \(\mathcal H\in B\)–\(\gamma\) if and only if \(\mathcal H\le \{K_{1,n}^*, K_n^*, P_n\}\) for some positive integer \(n\).
Denote by \(\gamma_n\) the smallest constant depending only on \(n\) in Theorem 1.4, thus \(\gamma(G)<\gamma_n\) for any \(\{K_{1,n}^*, K_n^*, P_n\}\)-free graph \(G\).
Choi, Furuya, Kim, Park [6] and Chiba, Furuya [4] characterized \(B\)–\(\alpha\).
Theorem 1.5 ([6, 4]). \(\mathcal H\in B\)–\(\alpha\) if and only if \(\mathcal H\le \{K_{1,n},K_n^*, P_n\}\) for some positive integer \(n\).
Denote by \(\alpha_n\) the smallest constant depending only on \(n\) in Theorem 1.5, thus \(\alpha(G)<\alpha_n\) for any \(\{K_{1,n}, K_n^*, P_n\}\)-free graph \(G\).
We proceed to determine \(B\text{-}\mu\) for \(\mu\) belonging to the set \(\{ir(G), i(G), \Gamma(G), \text{IR}(G)\}\). This completes the characterization of \(B\)–\(\mu\) for \(\mu\) along the domination chain.
Theorem 1.6.
When we do not want a vertex can serve as the private neighbor of itself, we get an variant of \(\text{IR}\)-number. Given a graph \(G\), a subset \(S\) of \(V(G)\) is an open irredundant set if every vertex \(s\) in \(S\) has at least one private neighbor outside of \(S\), i.e., \(P\!N[s,S]-S\neq \emptyset\). The open irredundance number \(O\!I\!R(G)\) is defined as \[O\!I\!R(G)=\max\{|S| : S \text{ is an open irredundant set of } G\}.\]
Clearly, \(O\!I\!R(G)\le I\!R(G)\) for any graph \(G\) since an open irredundant set must be an irredundant set. We also determine \(B\)–\(O\!I\!R\) in the following.
Theorem 1.7 (OIR). \(\mathcal H\in B\)–\(O\!I\!R\) if and only if \(\mathcal H\le \{K_{1,n}^*, K_n^*, P_n, C\!K_n, F_n\},\) for some positive integer \(n\).
Arumugam, Favaron, Sudha [1] and Arumugam, Subramanian [2] introduced the independence saturation number and the irredundance saturation number respectively.
Let \(G=(V,E)\) be a graph and \(v\in V\). Let \[I\!S(v)=\max\{|S|: S \text{ is an independent set of $G$ with $v\in S$}\},\] and define the independence saturation number of \(G\) as \[I\!S(G)=\min \{I\!S(v):v\in V\}.\]
Let \[I\!R\!S(v)=\max\{|S| : S \text{ is an irredundant set in $G$ with $v\in S$}\},\] and define the irredundance saturation number of \(G\) as \[I\!R\!S(G)=\min \{I\!R\!S(v):v\in V\}.\]
Since all independent sets are irredundant, we have \(I\!S(v)\le I\!R\!S(v)\). Thus \(I\!S(G)\le I\!R\!S(G)\). Since \(I\!S(G)\) is the size of some maximal independent set, \(i(G)\le I\!S(G)\le\alpha(G)\) and similarly \(i\!r(G)\le I\!R\!S(G)\le I\!R(G)\). We determine \(B\)–\(I\!S\) and \(B\)–\(I\!R\!S\) as follows.
Theorem 1.8. IS \(\mathcal H\in B\)–\(I\!S\) if and only if \[\mathcal H\le \{K_{1,n}^*, K_n^*,P_n, K_{n,n}, B\!S_n^p: 2\le p\le n-3\},\] for some \(n\ge 5\).
Theorem 1.9. IRS \(\mathcal H\in B\)–\(I\!R\!S\) if and only if \[\mathcal H\le \{K_{1,n}^*, K_n^*,P_n, K_{n,n}, C\!K_n, B\!S_n^p: 2\le p\le n-3\},\] for some \(n\ge 5\).
Remark 1.10. The methods employed in proving Theorems 1.7, 1.8, and 1.9 are novel, for example, the independence number is bounded hierarchically by induction, whereas the independence saturation number is bounded by contradiction, i.e., the forbidden induced subgraph would be extracted from a large \(I\!S(G)\) set.
The rest of the paper is arranged as follows. In Section 2, We present some necessary lemmas and establish notation conventions for symbols that appear frequently throughout the argument. We give the proofs of Theorems 1.6, 1.7, 1.8, and 1.9 in Section 3.
There exists a quality bound between the lower irredundance number (\(ir(G)\)) and the domination number (\(\gamma(G)\)).
Proposition 2.1 ([10]). For any graph \(G\), it holds that \(ir(G)\le \gamma(G)\le 2ir(G)-1\).
The following lemma [3] serves as the bipartite graph version of Ramsey’s theorem.
Lemma 2.2 ([3]). For any positive integer \(n\), there exists a smallest integer \(B\!R(n)\) such that every bipartite graph \(G=(V_{1},V_{2}, E)\) with \(|V_i|\ge B\!R(n)\) for \(i= 1,2\), there are subsets \(U_i\subseteq V_i\) of order \(n\) satisfying that \(G[U_1,U_2]\cong K_{n,n}\) or \(E_{2n}\).
Let \(\mathcal B\!\mathcal S_n^p\) be the family of graphs obtained by adding additional edges connecting the leaves adjacent to one center and the leaves adjacent to anther center of \(B\!S_n^p\).
Lemma 2.3. \(\{K_{n,n}, B\!S_n^p\}\le \mathcal B\!\mathcal S_{B\!R(n)}^p\).
Proof. Denote by \(V_i \, (i=1,2)\) the set of leaves adjacent to the corresponding two centers of \(B\!S_{B\!R(n)}^p\), respectively. Then \(|V_1|=|V_2|=B\!R(n)\). Recall that any graph \(G\in \mathcal B\!\mathcal S_{B\!R(n)}^p\) is obtained by adding some edges between \(V_1\) and \(V_2\) from \(B\!S_{B\!R(n)}^p\). Applying Lemma 2.2 to the bipartite graph \(G[V_1,V_2]=G(V_1\cup V_2)\), since \(V_1\) and \(V_2\) are independents , we can find \(U_i\subseteq V_i\) with \(|U_i|=n\) for \(i=1,2\) such that \(G[U_1, U_2]\cong K_{n,n}\), thus \(K_{n,n}\prec G\); or \(G[U_1, U_2]\) is an edgeless graph, thus \(B\!S_n^p\prec G\) in this case. Therefore, \(\{K_{n,n}, B\!S_n^p\}\le \mathcal B\!\mathcal S_{B\!R(n)}^p\). \(\square\)
The following result was given by Zverovich and Zverovich in [17].
Theorem 2.4 ([17]). If a graph \(G\) is \(\mathcal B\!\mathcal S_{k-1}^2\)-free, where \(k\ge 3\), then \[i(G)\le \gamma(G)(k-2)-(k-3).\]
The following lemma of Lozin [13] can be used to bound the matching number \(\nu(G)\) of bipartite graphs.
Lemma 2.5 ([13]). Let \(G\) be an \(\{nK_2,K_{n,n}\}\)-free bipartite graph. Then there exists a minimum \(q(n)\), such that \(\nu(G)<q(n)\).
In order to extract induced subgraphs we need from an irredundant set in proofs of next section, we will use the following fact and notation frequently. Let \(S\) be an irredundant set of graph \(G\). Suppose that \(v\in S\) is not an isolated vertex of \(G[S]\), i.e., there exists a vertex \(w\in S\) satisfying \(vw\in E(G)\). Take a vertex \(v’\in PN[v,S]=N[v]-N[S\setminus \{v\}]\). Thus \(v’\neq v\) as \(v\in N(w)\subseteq N[S\setminus \{v\}]\). Moreover, \(v’\notin S\) otherwise \(v’\in N[v’]\subseteq N[S\setminus \{v\}]\), a contradiction. For \(T\subseteq S\), let \(T’=\{v’:v\in S\}\), where each \(v’\in PN[v,S]-S\) is a private neighbor of \(v\) outside \(S\). Note that \(u’\neq v’\) as \(N(u’)\cap S=\{u\}\neq \{v\}=N(v’)\cap S\). Thus \(|T’|=|T|\). At this time, \(G[T,T’]\) is isomorphic to \(|T|K_2\). For \(X’\subseteq T’\), we will let \(X=\{v\in T:v’\in X’\}\) implicitly.
Proof of Theorem 1.6. (1) It is a corollary of Theorem 1.4 and Proposition 2.1.
(2) We first prove the “only if” part. Suppose that there is a constant \(c\) such that every connected \(\mathcal H\)-free graph \(G\) satisfies \(i(G)< c\). Let \(n=3c-2\). Then \(i(K_{1,n}^*)=i(K_n^*)=i(K_{n,n})=n\), \(i(P_n)=c\), and \(i(B\!S_n^2)=n+1\). This implies that \(K_{1,n}^*, K_n^*, P_n, K_{n,n}\), and \(B\!S_n^2\) are not \(\mathcal H\)-free. Therefore, \(\mathcal H\le \{K_{1,n}^*, K_n^*, P_n, K_{n,n}, B\!S_n^2\}\).
Next we prove the “if” part. Now suppose \(\mathcal H\le \{K_{1,n}^*, K_n^*, P_n, K_{n,n}, BS_n^2\}\). Given any connected \(\mathcal H\)-free graph \(G\), we know that \(G\) is \(\{K_{1,n}^*, K_n^*, P_n, K_{n,n}, B\!S_n^2\}\)-free. Clearly \(G\) is \(\{K_{1,n}^*, K_n^*, P_n\}\)-free. By Theorem 1.4, \(\gamma(G)<\gamma_n\). By Lemma 2.3, \(G\) is \(\mathcal B\!\mathcal S_{B\!R(n)}^2\)-free. According to Theorem 2.4, \[i(G)\le \gamma(G)(B\!R(n)-1)-(B\!R(n)-2)<\gamma_n B\!R(n).\]
(3) Recall that we need to prove the following statements are equivalent (a) \(\mathcal H\in B\)–\(\text{IR}\), (b) \(\mathcal H\in B\)–\(\Gamma\), and (c) \(\mathcal H\le \{K_{1,n}, K_n^*, P_n, CK_n\}\) for some positive integer \(n\).
\((a)\Rightarrow (b)\) is clear since \(\Gamma(G)\le \text{IR}(G)\). In order to prove \((b)\Rightarrow (c)\), we only need to show that \(K_{1,n}, K_n^*, P_n\) and \(CK_n\) have unbounded upper domination number \(\Gamma\) as \(n\) increases. By Theorem 1.5, \(K_{1,n}, K_n^*\) and \(P_n\) have unbounded independence number \(\alpha\), so does the upper domination number \(\Gamma\). The maximum clique of \(C\!K_n\) forms a largest minimal dominating set of \(C\!K_n\). Therefore, we have \(\Gamma(C\!K_n)=n\).
Now we prove that \((c)\Rightarrow (a)\). We claim that, for any connected \(\{K_{1,n}, K_n^*, P_n, CK_n\}\)-free graph \(G\), it holds that \(\text{IR}(G)< R(R(n,\alpha_n),\alpha_n)\). Suppose not, thus there exists an \(\text{IR}\)-set \(S\) of \(G\) such that \(|S|\ge R(R(n,\alpha_n),\alpha_n)\). According to Theorem 1.5, \(\alpha(G)<\alpha_n\) as \(G\) is \(\{K_{1,n}, K_n^*, P_n\}\)-free. Since \(\alpha(G[S])\le \alpha(G) <\alpha_n\), there exists a clique \(K\subseteq S\) of order \(R(n,\alpha_n)\). Each vertex \(v\) in \(K\) is not an isolated vertex. Thus we can take \(K’=\{v’:v\in K\}\), where each \(v’\) is a private neighbor of \(v\) outside \(S\). Thus \(|K’|=|K|=R(n,\alpha_n)\). Since \(\alpha(G[K’])\le \alpha(G) <\alpha_n\), there exists a clique \(X’\subseteq K’\) of order \(n\). Let \(X=\{v\in K:v’\in X’\}\). Hence \(G[X\cup X’]\) forms an induced \(C\!K_n\). This leads to a contradiction. The proof is completed. \(\square\)
The proof of Theorem 1.7 as follows.
Proof of Theorem 1.7. The “only if” part can be checked directly from the fact that \(O\!I\!R(K_{1,n}^*)=O\!I\!R(K_n^*)=O\!I\!R(C\!K_n)=O\!I\!R(F_n)=n\), and \(O\!I\!R(P_n)=\lceil n/3\rceil\).
Now we prove the “if” part. All we need to show is that if a connected graph \(G\) satisfies \[O\!I\!R(G)\ge R(R(n,n),R(n,2n\gamma_n)),\] then \(G\) contains an induced \(K_{1,n}^*, K_n^*, P_n, C\!K_n\) or \(F_n\). Take an \(O\!I\!R\)-set \(S\) of \(G\), and thus \(|S|\ge R(R(n,n),R(n,2n\gamma_n))\). Note that each element in \(S\) has at least one private neighbor outside of \(S\). For any \(v\in S\), fix one and denote it by \(v’\). For any subset \(X\) of \(S\), let \(X’=\{x’:x\in X\}\).
If \(G[S]\) contains a clique \(K\) of order \(R(n,n)\), then \(|K’|=|K|=R(n,n)\). Applying Ramsey’s theorem to graph \(G[K’]\), there exists a subset \(L’\subseteq K’\) of order \(n\) such that \(L’\) is a clique or an independent set. Let \(L=\{v\in S:v’\in L’\}\). If \(L’\) is a clique, then \(G[L\cup L’]\) forms an induced \(C\!K_n\); otherwise, \(L’\) is an independent set, in this case, \(G[L\cup L’]\) forms an induced \(K_n^*\).
Now assume \(G[S]\) contains an independent set \(E\) of order \(R(n,2n\gamma_n)\). Thus \(|E’|= |E|=R(n,2n\gamma_n)\). If there exists a clique \(X’\subseteq E’\) of order \(n\), then \(G[X\cup X’]\) forms \(K_n^*\), where \(X=\{v\in S:v’\in X’\}\); otherwise, \(G[E’]\) contains an independent set \(Y’\) of order \(2n\gamma_n\). Let \(D\) be a \(\gamma(G)\)-set. If \(|D|\ge \gamma_n\), then \(G\) contains an induced \(K_n^*, P_n\) or \(K_{1,n}^*\) by Theorem 1.4. We are done. Thus we may assume \(|D|<\gamma_n\). Since \[Y’\subseteq V(G)=N[D]=\bigcup_{d\in D}N[d],\] there exist a vertex \(u\in D\) such that \(|N[u]\cap Y’|\ge |Y’|/|D|>2n\). Therefore, we can choose \(Z’\subseteq N(u)\cap Y’\) with \(|Z’|=2n-1\). Let \(Z=\{v\in S:v’\in Z’\}\) denote the subset of \(S\) corresponding to \(Z’\). Then \(|Z|=|Z’|=2n-1\). It holds that \(u\not \in Z\cup Z’\) as \(Z’\subseteq N(u)\) and \(G[Z,Z’]\) is isomorphic to \(nK_2\).
If \(u\) dominates at least \(n\) vertices in \(Z\), i.e., there exists vertices \(z_1,\cdots ,z_n\in Z\cap N(u)\), then \(G[\{u,z_1,z_1′,\cdots ,z_n,z_n’\}]\) forms an induced \(F_n\). Otherwise, there are at least \(n\) vertices of \(Z\) nonadjacent to \(u\), i.e., there exists vertices \(z_1,\cdots ,z_n\in Z-N(u)\), in this case \(G[\{u,z_1,z_1′,\cdots ,z_n,z_n’\}]\) forms an induced \(K_{1,n}^*\). Therefore, for any connected \(\mathcal H\)-free graph \(G\), it holds that \[O\!I\!R(G)< R(R(n,n),R(n,2n\gamma_n)).\] \(\square\)
Proof of Theorem 1.8. We first prove the “only if” part. \(I\!S(G)\ge i(G)\) can be arbitrarily large for \(G\in\{K_{1,n}^*, K_n^*,P_n, K_{n,n}\}\) by Theorem 1.6 (2). For graph \(B\!S_n^p\), each vertex \(v\) together with the leaves adjacent to some center of \(B\!S_n^p\) can form an independent set of order \(n+1\). Thus \(I\!S (B\!S_n^p)=n+1\). Therefore, \(\mathcal H\le \{K_{1,n}^*, K_n^*,P_n, K_{n,n}, B\!S_n^p: 2\le p\le n-3\}\) for some \(n\ge 5\).
Next we prove the “if” part. Let \[N=(\gamma_n-1)(q(n)+2B\!R(n)-1)+2,\] where \(q(n)\) is defined in Lemma 2.5 and \(B\!R(n)\) is defined in Lemma 2.2. We will show that if a connected graph \(G\) satisfies \(I\!S(G)\ge N\), then \(G\) contains an induced \(K_{1,n}^*, K_n^*, P_n,K_{n,n}\) or \(B\!S_n^p\) for some integer \(p\). (We do not require \(p\le n-3\) as \(P_n\prec B\!S_n^p\) if \(p>n-3\).) By Theorem 1.4, we may assume that \(G\) has a \(\gamma\)-set \(D\) with \(|D|< \gamma_n\), otherwise, \(G\) contains an induce \(K_{1,n}^*, K_n^*\), or \(P_n\), we are done.
Let \(u\) be a vertex of \(G\) with maximum local independence number \(\alpha_l(u):=\alpha(G[N(u)])\). Choose \(U\subseteq N(u)\) be an independent set of order \(\alpha_l(u)\). Since \(I\!S(u)\ge I\!S(G)\ge N\), there exists an \(I\!S(u)\)-set \(V_1\) such that \(u\in V_1\), \(|V_1|\ge N\), and \(V_1\) is an independent set. Let \(V_2=V_1-\{u\}\). Thus \(|V_2|\ge N-1\) and \(N(u)\cap V_2=\emptyset\) as \(V_1\) is an independent set. Since \[V_2\subseteq V(G)=N[D]=\bigcup_{d\in D}N[d],\] by the pigeonhole principle, there is a vertex \(v\in D\) such that \[\Big|N[v]\cap V_2\Big|\ge \Big\lceil\frac{|V_2|}{|D|}\Big\rceil \ge \Big\lceil\frac{N-1}{\gamma_n-1}\Big\rceil\ge q(n)+2B\!R(n)>1.\]
\(v\notin V_2\) as \(V_2\) is an independent set. Thus \(N[v]\cap V_2=N(v)\cap V_2\). Note that \(v\neq u\) as \(N(u)\cap V_2=\emptyset\). Let \(V=N(v)\cap V_2\). Thus \(\alpha_l(v):=\alpha(G[N(v)])\ge |V|\ge q(n)+2B\!R(n).\) Recall that vertex \(u\) has maximum local independence number, thus \[|U|=\alpha_l(u) \ge \alpha_l(v)\ge q(n)+2B\!R(n).\]
As established above, we have found vertices \(u\) and \(v\), independent sets \(U\subseteq N(u)\) and \(V\subseteq N(v)\). \(u\notin V\) but maybe \(v\in U\). \(U\cap V=\emptyset\) as \(V\cap N(u)=\emptyset\).
Case 1. \(N_G(v)\cap (U\cup \{u\})\neq \emptyset\).
Let \(U_1=N(v)\cap U\) and \(U_2=U-U_1\).
Claim 1. \(|U_2-\{v\}|\ge B\!R(n)\).
Proof. Note that bipartite graph \(G[U_1,V]\), defined as the graph induced by edges between \(U_1\) and \(V\), is actually the induced subgraph \(G[U_1\cup V]\), since both \(U_1\) and \(V\) are independent sets. Thus \(\alpha_l(v)=\alpha(G[N(v)])\ge \alpha(G[U_1,V])\) as \(U_1\cup V\subseteq N(v)\). Apply König’s Theorem to the bipartite graph \(G[U_1,V]\), we have \[\alpha(G[U_1,V])+\nu(G[U_1,V])=|U_1|+|V|.\]
If \(\nu(G[U_1,V])\ge q(n)\), then, by Lemma 2.5, \(nK_2\prec G[U_1,V]\). Thus the \(nK_2\) in \(G[U_1,V]\) together with \(u\) forms an induced \(K_{1,n}^*\) in \(G\) as \(U_1\subseteq N(u)\) and \(V\cap N(u)=\emptyset\), we are done. Therefore, we may assume \(\nu(G[U_1,V])<q(n)\). Since \(\alpha_l(u)\) is maximum, we have \[\begin{aligned} 0\ge& \alpha_l(v)-\alpha_l(u)\\ \ge& \alpha(G[U_1, V])-|U|\\ =& (|U_1|+|V|-\nu(G[U_1,V])-(|U_1|+|U_2|)>|V|-q(n)+|U_2|. \end{aligned}\]
Therefore, \(|U_2|> |V|-q(n)\ge 2B\!R(n)\). Thus \(|U_2-\{v\}|\ge B\!R(n)\). \(\square\)
If \(uv\in E(G)\), then some graph in \(\mathcal B\!\mathcal S_{B\!R(n)}^2\) appears in \(G[\{u,v\}\cup U_2\cup V]\). By Lemma 2.3, \(G\) contains an induced \(K_{n,n}\) or \(B\!S_n\). Now assume \(uv\notin E(G)\). Thus there exists a vertex \(p\in U\) satisfying \(pv\in E(G)\) as \(N(v)\cap (U\cup \{u\})\neq \emptyset\). If \(|N(p)\cap V|\ge B\!R(n)\), then some graph in \(\mathcal B\!\mathcal S_{B\!R(n)}^2\) appears in \[G[\{u,p\}\cup (U\setminus\{p\}) \cup (N(p)\cap V)].\]
If \(|N(p)\cap V|<B\!R(n)\), Then \[|V\setminus N(p)|= |V|-|N(p)\cap V|> q(n)+2B\!R(n)-B\!R(n)\ge B\!R(n).\]
Thus some graph in \(\mathcal B\!\mathcal S_{B\!R(n)}^3\) appears in \(G[\{u,p,v\}\cup U_2 \cup (V\setminus N(p))]\). In a word, we are done from Lemma 2.3.
Case 2. \(N_G(v)\cap ( U\cup \{u\})=\emptyset\).
Case 2.1 There exist \(p\in U\) and \(q\in V\) satisfying \(pq\in E(G)\).
If \(|N(p)\cap V|<B\!R(n)\), then some graph in \(\mathcal B\!\mathcal S_{B\!R_n}^2\) appears in \[G[\{u,p\}\cup (U\setminus\{p\}) \cup (N(p)\cap V)].\]
If \(|N(q)\cap U|<B\!R(n)\), then some graph in \(\mathcal B\!\mathcal S_{B\!R_n}^2\) appears in \[G[\{v,q\}\cup (N(q)\cap U)\cup (V\setminus\{q\})].\]
Now we may assume \(|N(p)\cap V|\ge B\!R(n)\) and \(|N(q)\cap U|<B\!R(n)\). Thus \[|V-N(p)|=|V|-|N(p)\cap V|>q(n)+2B\!R(n)-B\!R(n)\ge B\!R(n),\] and similarly \(|U-N(q)|\ge B\!R(n).\) At this time some graph in \(\mathcal B\mathcal S_{B\!R(n)}^4\) appears in \[G[\{u,p,q,v\}\cup (U-N(q))\cup (V-N(p))].\]
Therefore, we are done from Lemma 2.3 in each possibility.
Case 2.2 \(E_G[\{u\}\cup U, \{v\}\cup V]=\emptyset.\)
Let \(P=x_1\dots x_p\) be a shortest path connecting \(\{u\}\cup U\) and \(\{v\}\cup V\) such that \[N(x_1)\cap (\{u\}\cup U)\not =\emptyset \text{ and } N(x_p)\cap (\{v\}\cup V)\not =\emptyset.\]
Since \(E_G[\{u\}\cup U, \{v\}\cup V]=\emptyset\), \(P\) is well-defined, i.e., \(p\ge 1\).
Assume \(|U\setminus N(x_1)|<n\) and \(|V\setminus N(x_p)|<n\) first. If \(x_1=x_p\), then \[\begin{aligned} \alpha_l(x_1)&\ge |N(x_1)\cap (U\cup V)|&\text{as } U\cup V \text{ is an independent set}\\ &=|N(x_1)\cap U|+|N(x_p)\cap V| &\text{as }x_1=x_p\\ &=(|U|-|U\setminus N(x_1)|)+(|V|-|V\setminus N(x_p)|)\\ &> (|U|-n)+(|V|-n)>|U|=\alpha_l(u), \end{aligned}\] a contradiction to that \(u\) has maximum local independence number. Thus \(x_1\neq x_p\). At this time we can get an induced \(B\!S_n^p\) from \(\{x_1,\dots ,x_p\}\cup (N(x_1)\cap U)\cup (N(x_p)\cap V)\).
Second, we assume \(|U\setminus N_G(x_1)|\ge n\) by symmetry. If \(x_1u\in E(G)\), define \[T_{p+1}=\{u,x_1,\cdots, x_p\}\cup (U\setminus N(x_1)).\]
Otherwise, if \(x_1u\notin E(G)\), choose \(x_0\in U\cap N(x_1)\) as \(N(x_1)\cap (\{u\}\cup U)\neq \emptyset\). Define \[T_{p+2}=\{u,x_0,x_1,\cdots, x_p\}\cup (U\setminus N(x_1)).\]
Uniformly, write \(T_{p+1}\) or \(T_{p+2}\) as \(T_i\) for \(i\in \{p+1,p+2\}\). If \(|V\setminus N_G(x_p)|<n\), then \(T_i\cup (N(x_p)\cap V)\) contains an induced \(B\!S_n^{i}\). Now we assume \(|V\setminus N_G(x_p)|\ge n\). If \(x_pv\in E(G)\), then \(T_i\cup \{v\}\cup (V\setminus N(x_p))\) contains an induced \(B\!S_n^{i+1}\). Otherwise, \(v\notin N(x_p)\). Choose \(x_{p+1}\in N(x_p)\cap V\). At this time, \(T_i\cup \{x_{p+1},v\}\cup (V\setminus N(x_p))\) contains an induced \(B\!S_n^{i+2}\). Anyway, \(G\) contains an induced \(BS_n^j\) for some \(j\in \{p+1,p+2,p+3,p+4\}\). The proof is complete. \(\square\)
Denote by \(I\!S_n\) the smallest constant depending only on \(n\) in Theorem 1.8, thus \(I\!S(G)<I\!S_n\) for any \(\{K_{1,n}^*, K_n^*,P_n, K_{n,n}, B\!S_n^p: 2\le p\le n-3\}\)-free graph \(G\).
Proof of Theorem 1.9. We first prove the “only if” part. Recall that \(I\!R\!S(G)\ge I\!S(G)\) for any graph \(G\). Thus, by Theorem 1.8, \(I\!R\!S(G)\) is unbounded for any \(G\in \{K_{1,n}^*, K_n^*,P_n, K_{n,n}, B\!S_n^p: 2\le p\le n-3\}\) as \(n\) increases. Note that each vertex in \(C\!K_n\) belongs to an irredundant set of order \(n\). Thus \(I\!R\!S(C\!K_n)=n\). Therefore, \(\mathcal H\le \{K_{1,n}^*, K_n^*,P_n, K_{n,n}, C\!K_n, B\!S_n^p: 2\le p\le n-3\}\) for some \(n\ge 5\).
Next we prove the “if” part. All we need to show is that if a connected graph \(G\) satisfies \(I\!R\!S(G)\ge I\!S_n+R(R(n,n),R(n,I\!S_n+n))\), then \(G\) contains an induced \(K_{1,n}^*, K_n^*, P_n, K_{n,n}\), \(C\!K_n\), or \(B\!S_n^p\) for some positive integer \(p\). By Theorem 1.8, we may assume that there is a vertex \(v\in V(G)\) such that \(I\!S(v)=I\!S(G)< I\!S_n\).
Let \(S\) be an \(I\!R\!S(v)\)-set. Thus \(v\in S\). Let \(I\) be the set of isolated vertices in \(G[S]\). Then \(I\cup \{v\}\) is an independent set. Thus \(|I\cup \{v\}|\le I\!S(v)<I\!S_n\). Let \(X=S\setminus (I\cup\{v\})\). Then every vertex in \(X\) has at least one private neighbor outside of \(S\). For any \(x\in X\), fix one of its private neighbor as \(x’\). Let \(X’=\{x’:x\in X\}\). Then \[|X’|= |X|=|S|-|I\cup \{v\}| \ge I\!R\!S(G)-I\!S_n\ge R(R(n,n),R(n,I\!S_n+n)).\]
Assume first there exists a clique \(K’\subseteq X’\) of order \(R(n,n)\). Let \(K=\{x\in X:x’\in K’\}\). Thus \(|K|=|K’|=R(n,n)\). Applying Ramsey’s Theorem to \(G[K]\), there exists a subset \(L\subseteq K\) of order \(n\) such that \(L\) is a clique or an independent set. If \(L\) is a clique, then \(G[L\cup L’]\) forms \(C\!K_n\); otherwise \(L\) is an independent set, at this case, \(G[L\cup L’]\) forms \(K_n^*\). Now assume that \(G[X’]\) contains an independent set \(Y’\) of order \(R(n,I\!S_n+n)\). Let \(Y=\{x\in X: x’\in Y’\}\). Thus \(|Y|=|Y’|=R(n,I\!S_n+n)\). Applying Ramsey’s Theorem to \(G[Y]\), there exists either a clique \(C\) of order \(n\) or an independent set \(Z\) of order \(I\!S_n+n\). The former case implies that \(G[C\cup C’]\) forms an induced \(K_n^*\). For the latter, \(|N(v)\cap Z|\ge n\) since \(I\!S(v)<I\!S_n\). Let \(z_1,\cdots, z_n\in N(v)\cap Z\), in this case \(G[\{v,z——1,z_1’\cdots, z_n,z_n’\}]\) forms an induced \(K_{1,n}^*\). The proof is completed. \(\square\)
This work was supported by the National Key Research and Development Program of China (2023YFA1010200), the National Natural Science Foundation of China (No. 12471336, and No. 12071453), and the Innovation Program for Quantum Science and Technology (2021ZD0302902).