Upper $k$-star-forming sets and $k$-independence in bipartite graphs

Introduction

Let $G$ be a finite simple graph and $k$ a positive integer. A set $I$ of vertices is $k$-independent if the induced subgraph $G[I]$ has maximum degree less than $k$, and $\beta_k(G)$ is the largest size of such a set; this notion goes back to Fink and Jacobson [7], see the survey [5] and [3]. Chellali and Favaron [4] called a set $S$ $k$-star-forming if for every vertex $v \notin S$ the graph $G[S \cup\{v\}]$ contains a copy of the star $K_{1,k}$ that contains $v$, and they showed that $\beta_k(G) \le\mathrm{SF}_k(G)$, where $\mathrm{SF}_k(G)$ is the largest size of a minimal $k$-star-forming set.¹ For $k = 1$

Email address: [email protected] (Deep Bhattacharjee) these are the independence number $\alpha$ and the upper domination number $\Gamma$, and the theorem of Cockayne, Favaron, Payan and Thomason [6] that $\Gamma= \alpha$ for bipartite graphs is the first case of the following conjecture of Sahbi.²

Sahbi proved the equality for complete bipartite graphs and every $k$, and for chain graphs when $k = 2$; he gave a triangle-free graph on ten vertices with $\beta_4 < \mathrm{SF}_4$, and asked [13 Problem 7.3] whether $\beta_3 = \mathrm{SF}_3$ for every triangle-free graph. The case $k = 2$ of the conjecture was refuted by a ten-vertex bipartite graph with $\beta_2 = 5$ and $\mathrm{SF}_2 = 6$, posted on 9 October 2026 to a public repository of refutations [1].³ We show that the conjecture fails for every larger $k$ as well.

The equality does survive on the more rigid class of chain graphs, the bipartite graphs in which the neighbourhoods of the vertices on one side are nested. Sahbi proved $\beta_2 = \mathrm{SF}_2$ for chain graphs and conjectured [13 Conjecture 6.4] that $\beta_k = \mathrm{SF}_k$ for chain graphs and all $k \ge3$; this is his Problem 9.1. We prove it.

The proof in § 4 shows that in a chain graph a minimal $k$-star-forming set has at most one vertex with $k$ or more neighbours inside it, and that this vertex can be exchanged for a vertex outside the set. The graphs $G_k$ show that some such rigidity is needed: in $G_k$ all $k-1$ hubs have $2k-1$ neighbours in the set $S$ of Lemma 3.1.

Sahbi also asked [13 Problem 9.3] for the complexity of computing $\mathrm{SF}_2$ on bipartite graphs, and in particular whether it is NP-complete to decide, for a bipartite graph $G$ and an integer $t$, whether $G$ has a minimal 2-star-forming set with at least $t$ vertices. It is. For a graph $H$ let $H^\sharp$ be the graph obtained from $H$ by replacing every edge with a path of length four and attaching a pendant vertex to every vertex of $H$ (§ 5).

The graphs $H^\sharp$ satisfy Sahbi’s equality, so the hardness does not come from a gap between the two numbers. The same identity gives another proof that computing $\beta_2$, the dissociation number, is NP-hard on bipartite graphs, a result of Yannakakis [14].

The graphs $G_k$

We write $N_S(v)$ for the set of neighbours of $v$ in $S$ and $d_S(v)=\lvert N_S(v)\rvert$. A copy of $K_{1,k}$ in $G[S\cup\{v\}]$ containing $v\notin S$ has $v$ as its centre or as a leaf, which gives the following local form of the definition [13 Lemma 2.2].

Fix $k\ge2$. The graph $G_k$ has the $3k+3$ vertices

Write $H=\{h_1,\ldots,h_{k-1}\}$ for the hubs, $X_1=\{u_1,\ldots,u_{k-1}\}$, $X_2=\{w_1,\ldots,w_{k-1}\}$ and $X=X_1\cup X_2\cup\{x_0\}$. The edges are

• $h_i x$ for every hub $h_i$ and every $x \in X$;

• $x_0p$, $c_1q_1$ and $c_2q_2$;

• $c_1u_j$ and $c_2w_j$ for $1 \leq j \leq k - 1$.

So $G_k$ has $(k-1)(2k-1)+2(k-1)+3=2k^2-k+2$ edges. It is connected, and it is bipartite with parts $H \cup\{p,c_1,c_2\}$ and $X \cup\{q_1,q_2\}$. Figure 1 shows $G_3$, which has 12 vertices and 17 edges.

The vertices $x_0$, $c_1$ and $c_2$ each see exactly $k-1$ vertices of $H \cup X$: the hubs, the block $X_1$ and the block $X_2$, respectively. Each of them also carries a pendant vertex, and the three pendant vertices $p$, $q_1$, $q_2$ are left outside the set $S$ below. Each pendant vertex is a leaf of a star whose centre and other leaves are forced into $S$, and this is what makes $S$ minimal although $S$ is far from $k$-independent: a hub has $2k-1$ neighbours in $S$.

Proof of Theorem 1.2

Proof. Clearly $|S|=3(k-1)+3=3k$. In $S$ we have $N_S(x_0)=H$, $N_S(c_1)=X_1$ and $N_S(c_2)=X_2$, so $d_S(x_0)=d_S(c_1)=d_S(c_2)=k-1$. The only vertices outside $S$ are $p$, $q_1$, $q_2$, and their neighbours $x_0$, $c_1$, $c_2$ lie in $S$; by Lemma 2.1, $S$ is $k$-star-forming.

For minimality we use Lemma 2.1 again. The pendant vertices have degree $1 < k$, so after the deletion of a vertex $s$ from $S$ a pendant vertex is still in a star only if its unique neighbour remains in $S \setminus\{s\}$ with at least $k-1$ neighbours there. If $s$ is a hub, then $x_0$ keeps only $k-2$ neighbours, so $p$ lies in no star. If $s=x_0$, then $p$ has no neighbour left. Likewise deleting a vertex of $X_1$, or $c_1$, leaves $q_1$ outside every star, and deleting a vertex of $X_2$, or $c_2$, does the same to $q_2$. These cases cover all of $S$.

Proof of Theorem 1.2. By Lemma 3.1, $\mathrm{SF}_k(G_k) \ge|S|=3k$, and by Lemma 3.2, $\beta_k(G_k)=2k+2$, which is smaller than $3k$ once $k \ge3$.

Chain graphs

Let $G$ be a chain graph with parts $A$ and $B$, so that the neighbourhoods $N(a)$, $a \in A$, form a chain under inclusion. Then the neighbourhoods $N(b)$, $b \in B$, form a chain as well.⁴ Two vertices on the same side therefore satisfy $N(u) \subseteq N(v)$ or $N(v) \subseteq N(u)$, and $N(u) \subseteq N(v)$ implies $d_S(u) \le d_S(v)$ for every set $S$. We say that $S$ covers a vertex $v \notin S$ if $v$ satisfies the condition of Lemma 2.1. Deleting a vertex $s$ from $S$ changes $d_S$ only on the neighbours of $s$, which lie on the other side.

The exchange step works in every graph.

Proof. If no vertex of $S$ has $d_S(v) \ge k$, then $S$ itself is $k$-independent. Otherwise let $h$ be the vertex with $d_S(h) \ge k$. By Lemma 2.1 some vertex $z \notin S \setminus\{h\}$ is not covered by $S \setminus\{h\}$: it has at most $k-1$ neighbours in $S \setminus\{h\}$, and each of these has at most $k-2$ neighbours in $S \setminus\{h\}$. As $h$ has $d_S(h) \ge k$ neighbours in $S \setminus\{h\}$, we have $z \ne h$, so $z \notin S$. In $I = (S \setminus\{h\}) \cup\{z\}$ the vertex $z$ has at most $k-1$ neighbours, each neighbour of $z$ has at most $(k-2)+1$, and every other vertex $v$ has at most $d_S(v) \le k-1$, since $v \ne h$. Hence $I$ is $k$-independent, and $|I| = |S|$.

Proof. We first show that every neighbour $y$ of $h$ in $S$ has a neighbour $w \notin S$ such that $d_S(u) \le k-2$ for every neighbour $u \ne y$ of $w$ in $S. Some vertex $w \notin S \setminus\{y\}$ is not covered by $S \setminus\{y\}$. It is not $y$, since $h$ is a neighbour of $y$ with $d_S(h)-1 \ge k-1$ neighbours in $S \setminus\{y\}$; so $w \notin S$, and $S$ covers $w$. Suppose $w$ lies on the side of $y$. Then $w$ is not adjacent to $y$, so $d_S(w) = d_{S \setminus\{y\}}(w) < k$, and $w$ has a neighbour $u \in S$ with $d_S(u) \ge k-1$, and $u$ lies on the side of $h$. If $N(u) \subseteq N(h)$, then $h$ is a neighbour of $w$ with at least $k-1$ neighbours in $S \setminus\{y\}$; if $N(h) \subseteq N(u)$, then $d_S(u) \ge d_S(h) \ge k$ and $u$ keeps at least $k-1$ neighbours in $S \setminus\{y\}$. Either way $S \setminus\{y\}$ covers $w$, which is impossible. So $w$ lies on the side of $h$, and its neighbours, lying on the side of $y$, have the same degree in $S \setminus\{y\}$ as in $S$. If $w$ were not adjacent to $y$, it would also keep its own degree, and $S \setminus\{y\}$ would cover $w$ as $S$ does. Hence $w$ is adjacent to $y$, and since $S \setminus\{y\}$ does not cover $w$, every neighbour $u \ne y$ of $w$ in $S$ has $d_S(u) \le k-2$.

Now $h$ has two neighbours $a \ne b$ in $S$, and we may assume $N(a) \subseteq N(b)$. Let $w$ be the vertex just found for $a$. Then $w$ is adjacent to $b$, so $d_S(b) \le k-2$. Let $y \in S$ lie on the side of $a$ and $b$. If $N(y) \subseteq N(b)$, then $d_S(y) \le d_S(b) \le $k-2$. If $N(b) \subseteq N(y)$, then $w$ is adjacent to $y$, so $d_S(y) \le k-2$ when $y \ne a$, while $d_S(a) \le d_S(b)$. $\square$

Proof. Suppose that $h \ne t$ are two such vertices. By Lemma 4.2 they lie on the same side, and we may assume $N(t) \subseteq N(h)$. Some vertex $z \notin S \setminus\{t\}$ is not covered by $S \setminus\{t\}$, and $z \ne t$ since $d_{S\setminus\{t\}}(t) = d_S(t) \ge k$. So $z \notin S$, and $S$ covers $z$. If $z$ lies on the side of $t$, then $z$ is not adjacent to $t$, so $d_S(z) = d_{S\setminus\{t\}}(z) < k$, and $z$ has a neighbour $u \in S$ with $d_S(u) \ge k-1$; but $u$ lies on the other side from $h$, and $d_S(u) \le k-2$ by Lemma 4.2. If $z$ lies on the other side, then $z$ is not adjacent to $h$, which has $d_S(h) \ge k$ neighbours in $S \setminus\{t\}$; hence $z$ is not adjacent to $t$ either, as $N(t) \subseteq N(h)$. Then neither $z$ nor any of its neighbours, which lie on the side of $t$, changes its degree when $t$ is deleted, and $S \setminus\{t\}$ covers $z$ as $S$ does. Both cases are impossible. $\square$

Proof of Theorem 1.3. We have $\beta_k(G) \le\operatorname{SF}_k(G)$ by [4]. Conversely, every minimal $k$-star-forming set $S$ satisfies $|S| \le\beta_k(G)$ by Lemmas 4.3 and 4.1. $\square$

For $k = 1$ the equality holds on all bipartite graphs [6]; the argument above needs $k \ge2$, since in Lemma 4.2 the vertex $h$ must have two neighbours in $S$.

Complexity

Let $H$ be a graph with vertex set $V$, $n$ vertices and $m$ edges, and write each edge as an ordered pair $e = (u_e, v_e)$ of its ends, in either order. The graph $H^\sharp$ has the vertices of $H$, a new vertex $v'$ for every $v \in V$ and three new vertices $a_e, b_e, c_e$ for every edge $e$. Its edges are $vv'$ for $v \in V$ and the four edges of the path $u_ea_eb_ec_ev_e$ for every edge $e$ of $H$. So $H^\sharp$ has $2n + 3m$ vertices; it is bipartite with parts $V \cup\{b_e\}$ and $\{v'\} \cup\{a_e, c_e\}$, and it is planar when $H$ is. Figure 2 shows $K^\sharp_3$.

Proof. The size is clear, since $J(I)$ contains exactly one of $a_e$ and $c_e$ for each edge $e$. We check that every vertex of $J(I)$ has at most one neighbour in $J(I)$. A vertex $v'$ has only one neighbour, and $b_e$ has exactly one of its neighbours $a_e,c_e$ in $J(I)$. Let $v\in I$. For an edge $e$ with $u_e=v$ the set $J(I)$ contains $c_e$ and not $a_e$, and for an edge $e$ with $v_e=v$ we have $u_e\notin I$, because $I$ is independent, so $J(I)$ contains $a_e$ and not $c_e$; hence $v'$ is the only neighbour of $v$ in $J(I)$. If $a_e\in J(I)$, then $u_e\notin I$, so $b_e$ is its only neighbour in $J(I)$. If $c_e\in J(I)$, then $u_e\in I$, so $v_e\notin I$, and again $b_e$ is its only neighbour in $J(I)$.

For the upper bound we use Lemma 2.1 with $k=2$: a set $S$ covers $w\notin S$ if $d_S(w)\ge2$ or $w$ has a neighbour $x\in S$ with $d_S(x)\ge1$. Let $s\in S$. If a vertex $w\notin S$ is neither adjacent to $s$ nor at distance two from it, then $d_{S\setminus\{s\}}(w)=d_S(w)$, and every neighbour $x$ of $w$ satisfies $x\ne s$ and $d_{S\setminus\{s\}}(x)=d_S(x)$, so $S\setminus\{s\}$ covers $w$ whenever $S$ does. Hence, to see that $S\setminus\{s\}$ is still 2-star-forming, we only have to check $s$ and the vertices outside $S$ within distance two of $s$.

(c) If both ends of an edge $e$ lie in $Y$, then at most one of $a_e,b_e,c_e$ lies in $S$.

Proof. (a) The vertex $v'$ has the single neighbour $v$, so if $v' \notin S$ then $S$ covers $v'$ only through $v \in S$.

(b) Suppose that $a_e,b_e,c_e \in S$, and put $S' = S \setminus\{b_e\}$. The vertex $b_e$ has its two neighbours $a_e,c_e$ in $S'$. The vertices outside $S$ at distance two from $b_e$ are among $u_e$ and $v_e$. If $u_e \notin S$, then $u'_e \in S$ by (a), so $u_e$ has the two neighbours $u'_e$ and $a_e$ in $S'$, and likewise for $v_e$. So $S'$ is 2-star-forming, against the minimality of $S$.

(c) Let $u_e,v_e \in Y$ and suppose that two of $a_e,b_e,c_e$ lie in $S$; by (b) the third does not. Since $u'_e \in S$ and $v'_e \in S$, the vertices $u_e$ and $v_e$ keep at least one neighbour in $S$ after the deletion of any of $a_e,b_e,c_e$, so every vertex outside $S$ that is adjacent to $u_e$ or $v_e$ stays covered. If $b_e \notin S$, put $S' = S \setminus\{a_e\}$: then $a_e$ is covered through $u_e$, and $b_e$ through $c_e$, whose neighbour $v_e$ is in $S'$. If $c_e \notin S$, put $S' = S \setminus\{a_e\}$: then $a_e$ is covered through $u_e$, and $c_e$ has the two neighbours $b_e$ and $v_e$ in $S'$. The case $a_e \notin S$ is symmetric to the previous one, with $S' = S \setminus\{c_e\}$. In each case the vertices outside $S$ within distance two of the deleted vertex are covered by $S'$, so $S'$ is 2-star-forming, against the minimality of $S$.

Proof of Theorem 1.4. The order and the bipartition of $H^\sharp$ were noted above. By Lemma 5.1 applied to a largest independent set, $\beta_2(H^\sharp) \ge n+2m+\alpha(H)$, and $\beta_2 \le\mathrm{SF}_2$ by [4]. Now let $S$ be a minimal 2-star-forming set of $H^\sharp$ and $Y$ as in Lemma 5.2. By part (a) the set $S$ contains both of the vertices $v,v'$ if $v \in Y$ and one of them otherwise, and by parts (b) and (c) it contains at most two of $a_e,b_e,c_e$, and at most one if both ends of $e$ lie in $Y$. Writing $e(Y)$ for the number of edges of $H$ with both ends in $Y$, we get

The graph $H[Y]$ has at least $|Y| - e(Y)$ components, and one vertex from each component forms an independent set, so $|Y| - e(Y) \le\alpha(H)$. Hence $|S| \le n + 2m + \alpha(H)$, and the three numbers are equal.

The decision problem lies in NP, since by Lemma 2.1 one checks in polynomial time that a given set $S$ is 2-star-forming and that $S \setminus\{s\}$ is not, for each $s \in S$. For hardness, $H$ has an independent set with at least $t$ vertices if and only if $H^\sharp$ has a minimal 2-star-forming set with at least $n + 2m + t$ vertices, and $H^\sharp$ is built from $H$ in polynomial time. Node Cover, and with it Independent Set, is NP-complete [9], also on planar graphs [8], and $H^{\#}$ is planar when $H$ is.

For $k \ge3$ we have not determined the complexity of computing $\mathrm{SF}_k$ on bipartite graphs.

Remarks

Remark 6.1. For $k = 2$ the two numbers in Lemmas 3.1 and 3.2 coincide, and indeed $\beta_2(G_2) = \mathrm{SF}_2(G_2) = 6$. An exhaustive computation over all subsets shows that $\mathrm{SF}_k(G_k) = 3k$ exactly for $3 \le k \le7$, so in this range $\mathrm{SF}_k(G_k)/\beta_k(G_k) = 3k/(2k + 2)$, which tends to $3/2$.

Remark 6.2. We computed $\beta_k$ and $\mathrm{SF}_k$ for every bipartite graph with at most 12 vertices, generated with nauty [11], and $2 \le k \le7$. The smallest bipartite graphs with $\beta_k < \mathrm{SF}_k$ have 10 vertices for $k = 2$ (the graph of [1], which is unique), 12 vertices for $k = 3$ (there are 51 such graphs, $G_3$ among them), 10 vertices for $k = 4$ (a single graph) and 12 vertices for $k = 5$; for $k = 6, 7$ there is none with at most 12 vertices. Among triangle-free graphs the smallest ones with $\beta_3 < \mathrm{SF}_3$ have 10 vertices, and there are two of them. We also found no tree with at most 16 vertices and $\beta_k < \mathrm{SF}_k$ for $2 \le k \le6$, and, in accordance with Theorem 1.3, no such chain graph with at most 16 vertices for $3 \le k \le8$. These computations are not part of the proofs.

Remark 6.3. We also checked Theorem 1.4 by computer in two independent ways: by exhaustive search over all vertex subsets of $H^{\#}$ for every connected graph $H$ with $2n + 3m \le26$, which also confirms parts (a)–(c) of Lemma 5.2 for every minimal 2-star-forming set, and with a SAT solver for every connected graph $H$ with at most 7 vertices.

Formal verification

Theorems 1.2, 1.3 and 1.4 are formalised in Lean 4 [12] with Mathlib [10]. The definitions follow [13]: a set is $k$-star-forming if every outside vertex $v$ lies in a copy of $K_{1,k}$ inside $G[S \cup\{v\}]$, minimality is required against every proper subset, and $\beta_k$ and $\mathrm{SF}_k$ are the largest sizes of $k$-independent and of minimal $k$-star-forming sets. For every $k \ge3$ the formal statement gives a 2-colouring of $G_k$ together with $\beta_k(G_k) = 2k + 2$ and $\mathrm{SF}_k(G_k) \ge3k$. Theorem 1.3 is proved for every finite graph with a bipartition in which the neighbourhoods on one side are nested, and the inequality $\beta_k \le\mathrm{SF}_k$ of [4] is proved along the way. The identity of Theorem 1.4 is proved for every finite graph $H$ whose vertices are linearly ordered, the order fixing the ends $u_e < v_e$, together with a 2-colouring of $H^\sharp$; here $\alpha(H)$ is the independence number of Mathlib. The NP-completeness, which follows from the identity by the argument above, is not formalised. The proofs are checked by the kernel and use only the standard axioms of Lean. The development and the search programs are archived in [2].

Declaration of competing interest

The author has no competing interests to declare.

Funding

This research did not receive any specific grant from funding agencies in the public, commercial, or not-for-profit sectors.

Data availability

The Lean 4 development, the C and Python checks and the search programs are available at https://github.com/creelie/Conjecture-002 and on Zenodo, doi:10.5281/zenodo.23360032.

Declaration of generative AI and AI-assisted technologies in the manuscript preparation process

During the preparation of this work the author used Claude (Anthropic) to find the construction and the reduction, to check them in C, Python and Lean, and to draft the text. After using this tool, the author reviewed and edited the content as needed and takes full responsibility for the content of the published article.

Author

Deep Bhattacharjee (sole author); [email protected], [email protected]; ORCID 0000-0003-0466-750X.