A characterization of star-perfect graphs

Abstract

Motivated by Berge perfect graphs, we define star-perfect graphs and characterize them. For a finite simple graph G(V, E), let ${\theta }_s(G)$ denote the minimum number of induced stars contained in G such that the union of their vertex sets is V(G), and let ${\alpha }_s(G)$ denote the maximum number of vertices in G such that no two of them are contained in the same induced star of G. We call a graph G star-perfect if ${\alpha }_s(H)={\theta }_s(H)$, for every induced subgraph H of G. A graph G is star-perfect if and only if G is $(C_3,C_{3k+1},C_{3k+2})$-free, for every $k\ge 1$. A bipartite graph G is star-perfect if and only if every induced cycle in G is of length $6k,k\ge 1$. The minimum parameter ${\theta }_s(G)$ and the maximum parameter ${\alpha }_s(G)$ have been extensively studied in various contexts.

Keywords:

• Perfect graph
• star-perfect graph
• star-imperfect graph

Mathematics Subject Classification:

• 05C17
• 05C75

1 Introduction

All our graphs are finite and simple. We follow West [11] and Bondy and Murty [3] for basic terminologies and notations. If G is a graph, then V(G) and E(G) are its vertex set and edge set, respectively. As usual, $K_n(n\ge 1),C_n(n\ge 3),P_n(n\ge 1)$ denote the complete graph, cycle and path on n vertices, respectively. If $D\subseteq V(G)$, the subgraph of G induced by D is obtained by deleting the vertices of $V(G)-D$ and is denoted by $G[D]$. Given a graph H, we say that a graph G is H-free, if G does not contain an induced subgraph isomorphic to H. Given a family $\{H_1,H_2,\dots \}$ of graphs, we say that G is $(H_1,H_2,\dots )$-free if G is H_i - free, for every $i\ge 1$.

The neighborhood of a vertex v is the set of vertices adjacent to v and is denoted by $N_G(v)$ (or N(v)). The closed neighborhood of v is the set $N_G(v)\cup \left\{v\right\}$ and is denoted by $N_G[v]$ (or $N[v]$). Suppose H₁ and H₂ are two induced subgraphs in G. We say that H₁ and H₂ are adjacent in G, and is denoted by $H_1\leftrightarrow H_2$, if either (i) there exists at least a common vertex between H₁ and H₂ ($V(H_1)\cap V(H_2)\ne \varnothing$), or (ii) there is an edge in G such that one of the end vertices of the edge is in H₁ and the other is in H₂. In a graph G, the distance between two vertices u and v, denoted by d(u, v), is the length of a shortest path connecting them. Let $A,B\subseteq V(G)$. The distance between A and B, denoted by d(A, B), is the length of a shortest (a, b)-path where $a\in A$ and $b\in B$. The symbol $[A,B]$ denotes the set {$e\in E(G):e$ has one end vertex in A and the other end vertex in B}.

A star is a graph on t + 1 vertices, $t\ge 0$, say $v_0,v_1,v_2,\dots ,v_t$ such that v₀ is adjacent to every vertex in $W=\{v_1,v_2,\dots ,v_t\}$ and no two vertices in W are adjacent. The vertex v₀ is called the central vertex of the star and we say that the star is centered at v₀ and all other vertices of the star are non-central vertices. Note that K₁ and K₂ are stars. Berge’s perfect graphs [2] have inspired various researchers to study many variations of perfect graphs [5]. Ravindra introduced the concept of F-perfect graphs [10]. Litjens et al. defined and characterized sum-perfect graphs [8].

Let G be a graph. A star-cover of G, denoted by $\mathcal{S}$, is a family of induced stars contained in G such that every vertex of G is in one of the induced stars. The star-covering number of G is the minimum cardinality of a star-cover and is denoted by ${\theta }_s(G)$. A θ_s-cover of G is a star-cover of G containing ${\theta }_s(G)$ stars.

A set $T\subseteq V(G)$ is a star-independent set of G if no two vertices of T are contained in the same induced star in G (equivalently, any two vertices in T are at a distance at least 3). The maximum cardinality of a star-independent set is called the star-independence number of G and is denoted by ${\alpha }_s(G)$. An α_s- independent set of G is a star-independent set with ${\alpha }_s(G)$ vertices.

The minimum parameter ${\theta }_s(G)$ and the maximum parameter ${\alpha }_s(G)$ have been extensively studied in various contexts with different terminology. For example, star-independent sets are studied in [4], where a star-independent set in G corresponds to a color class in a $(k,3)$-coloring of G. It is also interesting to note that for a triangle free graph G, the central vertices of stars in star cover of G is a dominating set of G (Recall that a set $D\subseteq V(G)$ is called a dominating set of G if every vertex in $V(G)-D$ is adjacent to at least one vertex in D). So for a triangle free graph G, ${\theta }_s(G)$ is the minimum dominating set $\gamma (G)$ of G. Domination is a much studied topic, for example see [1] and references therein. It is well known that DOMINATION PROBLEM is NP-complete for triangle free graphs and several subfamilies of triangle free graphs; see [6]. By our earlier remark that ${\theta }_s(G)$ is $\gamma (G)$ for triangle free graphs, the decision problem of finding ${\theta }_s(G)$ is also NP-complete for triangle free graphs.

The union of vertex disjoint graphs $G_1,G_2,\dots ,G_k$, written ${\cup }_{i=1}^k{G}_i$ is the graph with vertex set ${\cup }_{i=1}^{k}V(G_i)$ and edge set ${\cup }_{i=1}^{k}E(G_i)$.

It is easy to see that the graph parameters ${\alpha }_s(G)$ and ${\theta }_s(G)$ both satisfy the additive property, that is

• ${\alpha }_s({\cup }_{i=1}^k{G}_i)={\sum }_{i=1}^k{\alpha }_s(G_i)$, and

• ${\theta }_s({\cup }_{i=1}^k{G}_i)={\sum }_{i=1}^k{\theta }_s(G_i)$.

Clearly, for any graph G, ${\theta }_s(G)\ge {\alpha }_s(G)$. We call a graph G a star-perfect graph if ${\theta }_s(H)={\alpha }_s(H)$, for every induced subgraph H of G. We call a graph star-imperfect if it is not star-perfect. For example, the cycle C₆ is a star-perfect graph, since ${\theta }_s(C_6)=2={\alpha }_s(C_6)$ and ${\theta }_s(H)={\alpha }_s(H)$ for every proper induced subgraph H of G, while C₄ is a star-imperfect graph, since ${\theta }_s(C_4)=2$ and ${\alpha }_s(C_4)=1$. Similarly, C₃ is star-imperfect graph, since ${\theta }_s(C_3)=2$ and ${\alpha }_s(C_3)=1$.

A graph G is said to be minimal star-imperfect if (i) ${\theta }_s(G)\ne {\alpha }_s(G)$ and (ii) G – v is star-perfect for every vertex v of G. Every minimal star-imperfect graph is a connected graph, since a graph G is star-perfect if and only if every component of G is star-perfect. Moreover, every star-imperfect graph contains a minimal star-imperfect graph.

Since star-perfectness is a hereditary property, one expects a forbidden graph characterization for star perfect graphs. We realize this in this paper as given below.

Main Theorem: A graph G is star-perfect if and only if G is $(C_3,C_{3k+1},C_{3k+2})$-free, $k\ge 1$.

The theorem is a min-max theorem for star-perfect graphs. Our characterization goes parallel to a characterization of β-perfect graphs due to Markossyan, Gasparyan and Reed [9]. They have proved that the graphs G and $\overline{G}$ are β-perfect if and only if G and $\overline{G}$ are even-hole-free ($C_{2k}$-free, $k\ge 2$). Yet another concept that comes close to our concept of star-perfectness is the concept of neighborhood perfect graphs due to Lehel and Tuza [7].

For ready reference, we collect in one place the observations and remarks made above. Throughout the paper we often use these properties without explicitly referring to them.

• (1.1)The graph parameters ${\alpha }_s(G)$ and ${\theta }_s(G)$ both satisfy the additive property.

• (1.2)For any graph G, ${\theta }_s(G)\ge {\alpha }_s(G)$. So, if for some graph H, ${\theta }_s(G)\le {\alpha }_s(H)$, then ${\alpha }_s(H)={\theta }_s(H)$.

• (1.3)Every minimal star-imperfect graph is a connected graph, since a graph G is star-perfect if and only if every component of G is star-perfect.

• (1.4) Every star-imperfect graph contains a minimal star-imperfect graph.

• (1.5)If G is a star-perfect graph and S is a θ_s -cover and I is an α_s -independent set of G, then every star in S contains exactly one vertex of I.

Before proving the main theorem we establish a few properties of minimal star-imperfect graphs.

2 Minimal star-imperfect graphs

Throughout the paper, we fix a clockwise orientation to a cycle C in G.

Lemma 2.1.

Let k be any positive integer. Then,

1. ${\theta }_s(P_k)=\lceil \frac{k}{3}\rceil$ and ${\alpha }_s(P_k)=\lceil \frac{k}{3}\rceil$.

2. P_k is star-perfect.

3. The disjoint union of paths is a star-perfect graph.

Proof.

Let P_k be the path $v_1{v}_2\dots v_k,k\ge 1$.

(i) If $k\equiv 0(\mathit{\text{mod}}3)$, let $k=3p,p\ge 1$. Then the family of stars $\{v_1{v}_2{v}_3,v_4{v}_5{v}_6,v_7{v}_8{v}_9,\dots v_{3p-2}{v}_{3p-1}{v}_{3p}\}$ is a star cover of P_k , so ${\theta }_s(P_k)\le k$. On the other hand, every star contained in P_k has at most three vertices, therefore, ${\theta }_s(P_k)\ge p$. Combining the two inequalities, we have ${\theta }_s(P_k)=p=\frac{k}{3}$. Let I be any star-independent set in P. Since any two vertices in I are at a distance at least 3, $\left|I\right|\le p=\lceil \frac{k}{3}\rceil$. So ${\alpha }_s(P_k)\le p$. The set $T=\{v_2,v_5,\dots ,v_{3p-1}\}$ is a star-independent set of P_k , since any two vertices in T are at a distance at least 3 in P_k . Thus ${\alpha }_s(P_k)\ge \left|T\right|=p=\lceil \frac{k}{3}\rceil$. Combining the two inequalities, we have ${\alpha }_s(P_k)=\lceil \frac{k}{3}\rceil$.

If $k\equiv 1(\mathit{\text{mod}}3)$, let $k=3p+1,p\ge 0$. Then the family of stars $\{v_1{v}_2{v}_3,v_4{v}_5{v}_6,v_7{v}_8{v}_9,\dots v_{3p-2}{v}_{3p-1}{v}_{3p},[\left\{v_{3p+1}\right\}]\}$ is a star cover of P_k , so ${\theta }_s(P_k)\le p+1=\lceil \frac{k}{3}\rceil$. On the other hand, every star contained in P_k has at most three vertices, therefore, ${\theta }_s(P_k)\ge \lceil \frac{k}{3}\rceil =\lceil \frac{3p+1}{3}\rceil =p+1$. Combining the two inequalities, we have ${\theta }_s(P_k)=p+1=\lceil \frac{k}{3}\rceil$. Let I be any star-independent set in P. Since any two vertices in I are at a distance at least 3, $\left|I\right|\le p+1=\lceil \frac{k}{3}\rceil$. So ${\alpha }_s(P_k)\le p+1$. The set $T=\{v_2,v_5,\dots ,v_{3p+1}\}$ is a star-independent set of P_k , since any two vertices in T are at a distance at least 3 in P_k . Thus ${\alpha }_s(P_k)\ge \left|T\right|=p+1=\lceil \frac{k}{3}\rceil$. Combining the two inequalities, we have ${\alpha }_s(P_k)=k+1=\lceil \frac{k}{3}\rceil$ and ${\theta }_s(P_k)=k+1=\lceil \frac{k}{3}\rceil$.

If $k\equiv 2(\mathit{\text{mod}}3)$ one can show that ${\theta }_s(P_k)=\lceil \frac{k}{3}\rceil$ by using similar arguments as above.

Combining the three cases we have ${\theta }_s(P_k)=\lceil \frac{k}{3}\rceil$ and ${\alpha }_s(P_k)=\lceil \frac{k}{3}\rceil$.

(ii) Every proper induced subgraph of P is a disjoint union of paths. Therefore, by (i), and additive property it follows that P_k is star-perfect.

(iii) The assertion follows since a graph G is star-perfect if and only if every component of G is star-perfect. □

Lemma 2.2.

For any integer $k\ge 2$ the following statements are true.

1. ${\theta }_s(C_{3k})=k$ and ${\alpha }_s(C_{3k})=k$.

2. $C_{3k}$ is star-perfect.

Proof.

(i) Let C be a 3k-cycle $v_1{v}_2\dots v_{3k}{v}_1$. We first prove that ${\theta }_s(C)=k$. Every star contained in C has at most 3 vertices, so ${\theta }_s(C)\ge \frac{3k}{3}=k$. Next the set of stars $S=\{v_{3k}{v}_1{v}_2,v_3{v}_4{v}_5,\dots ,v_{3k-3}{v}_{3k-2}{v}_{3k-1}\}$ is a star-cover of C with k stars. Hence ${\theta }_s(C)\le k$. Combining the two inequalities, we have ${\theta }_s(G)=k$.

Next we prove that ${\alpha }_s(C_{3k})=k$. Let I be any star-independent set in C. Since any two vertices in I are at a distance at least 3, $\left|I\right|\le \frac{3k}{3}=k$. So ${\alpha }_s(C)\le k$. The set $T=\{v_1,v_4,\dots ,v_{3k-2}\}$ is a star-independent set of C, since any two vertices in T are at a distance at least 3 in C. Thus $k=\left|T\right|\le {\alpha }_s(C)$. Combining the two inequalities, we have ${\alpha }_s(C)=k$.

Therefore, ${\alpha }_s(C)=k$, and ${\theta }_s(C)=k$.

(ii) Every proper induced subgraph of C is a disjoint union of paths. Therefore, by Lemma 2.1 $C_{3k}$ is star-perfect. □

In our next lemma, we identify minimal star-imperfect cycles.

Lemma 2.3.

Let k be any positive integer. Then,

1. ${\theta }_s(C_3)=2,{\alpha }_s(C_3)=1$; ${\theta }_s(C_{3k+1})=k+1,{\alpha }_s(C_{3k+1})=k$; ${\theta }_s(C_{3k+2})=k+1$ and ${\alpha }_s(C_{3k+2})=k$.

2. The cycles C₃, $C_{3k+1}$ and $C_{3k+2}$ are star-imperfect graphs.

3. The cycles C₃, $C_{3k+1}$ and $C_{3k+2}$ are minimal star-imperfect graphs.

Proof.

We prove (i) in three steps depending on the length of the cycles.

Step 1: For C₃, ${\alpha }_s(C_3)=1$ and ${\theta }_s(C_3)=2$. And every proper induced subgraph of C₃ is K₁ or K₂, each of which is star-perfect. Therefore, C₃ is minimal star-imperfect.

Step 2: Let C be a $(3k+1)$-cycle $v_1{v}_2\dots v_{3k+1}{v}_1$. We claim that ${\theta }_s(C)=k+1$ and ${\alpha }_s(C)=k$. Every star contained in C has at most 3 vertices. Hence, ${\theta }_s(C)\ge \lceil \frac{3k+1}{3}\rceil =k+1$. Next the family of stars $\{v_{3k+1}{v}_1{v}_2,v_3{v}_4{v}_5,\dots ,v_{3k-3}{v}_{3k-2}{v}_{3k-1},[\left\{v_{3k}\right\}]\}$ is a star-cover of C with k + 1 stars. Hence, ${\theta }_s(C)\le k+1$. Combining the two inequalities, we have ${\theta }_s(G)=k+1$.

Next, let I be any star-independent set in C. Since any two vertices in I are at distance at least 3, we deduce $\left|I\right|\le \lfloor \frac{3k+1}{3}\rfloor =k$. So ${\alpha }_s(C)\le k$. The set $T=\{v_1,v_4,\dots ,v_{3k-2}\}$ is a star-independent set of C, since any two vertices in T are at distance at least 3 in C. Thus, $k=\left|T\right|\le {\alpha }_s(C)$. Combining the two inequalities, we have ${\alpha }_s(C)=k$ and hence our claim is proved.

Step 3: We can show that $C_{3k+2}$ is a minimal star-imperfect graph, by using similar arguments as given in Step 2.

(ii) is a consequence of (i).

(iii) Every proper induced subgraph of C is a disjoint union of paths and so by Lemma 2.1 (iii) it follows that every induced subgraph is star-perfect. We conclude that C is a minimal star-imperfect graph. □

Our next goal is to show that a minimal star-imperfect graph is a block.

Lemma 2.4.

Let G be a connected star-perfect graph and v be a vertex of G. Then one of the following is true.

1. The vertex v is in an α_s -independent set of G.

2. A neighbor of v is in an α_s -independent set of G.

Proof.

If (i) is not true, then there exists an α_s -independent set $S=\{u_1,u_2,\dots ,u_k\}$ that does not contain v, where $k={\alpha }_s(G)$. We claim that $[N(v),S]\ne \varphi$. Assume the contrary that $[N(v),S]=\varphi$. Therefore, $d(N(v),S)\ge 2$. Let P be a shortest path between N(v) and S. By our assumption, length $(P)\ge 2$. Since P is a shortest path, $d(v,S)\ge 3$, for all $u\in S$. Therefore, $\left\{v\right\}\cup S$ is a star-independent set in G of size ${\alpha }_s(G)+1$, a contradiction. Hence our claim $[N(v),S]\ne \varphi$ holds.

Since $[N(v),S]\ne \varphi$, let without loss of generality $w_1{u}_1\in [N(v),S]$. We assert that $d(w_1,S-\{u_1\})\ge 3$. If not, then $d(w_1,u_i)\le 2$, for some $u_i\in S-\left\{u_1\right\}$. If $d(w_1,u_i)=1$, then u₁ and u_i belong to a star and therefore, they are not star-independent, a contradiction. Next, if $d(w_1,u_i)=2$, then w₁ and u_r , for some r such that $2\le r\le k$ are adjacent to a vertex in G. Let $Q(w_1,u_r)$ be a shortest path of length 2.

The vertex v is at a distance at most 2 from some vertex $u_r,2\le r\le k$. If not, $d(v,u_i)\ge 3$, for all $u_i,2\le i\le k$. Therefore, $d(v,u_i)\ge 3$ and so $\left\{v\right\}\cup \{u_2,u_3,\dots ,u_k\}$ is an α_s -independent set in G, a contradiction to our first assumption. So let $R(u_r,v)$ be a shortest path of length 2. Then $w_{1}Q{u}_r{\mathit{\text{Rvw}}}_1$ is an induced C₅, a contradiction to the assumption that G is star-perfect. Hence, $d(w_1,S-\{u_1\})\ge 3$ and our assertion is true. Thus, $\{w_1,u_2,\dots ,u_k\}$ is an α_s -independent set of G, and so (ii) holds. This completes the proof. □

Note. The condition that G is star-perfect is necessary. For example, see Figure 1.

Fig. 1 Bull graph.

Bull graph is star-imperfect and $\{u_1,u_2\}$ is the only α_s -independent set and neither v nor any of its neighbors $\{w_1,w_2\}$ is in an α_s -independent set of bull graph.

Lemma 2.5.

If G is a minimal star-imperfect graph and v is a cut vertex of G, then every component of G – v has at least two vertices.

Proof.

Let $G_1,G_2,\dots ,G_k$ be the components of G – v where $k\ge 2$. Contrary to the lemma, assume that at least one of the components, say G₁, has exactly one vertex u. The star uv together with θ_s -cover of ${\cup }_{i=2}^k{G}_i$ forms a θ_s -cover of G. So ${\theta }_s(G)\le {\sum }_{i=2}^k{\theta }_s(G_i)+1$. The star $K_1=[\{u\}]$ together with θ_s -cover of ${\cup }_{i=2}^k{G}_i$ forms a star-cover of G – v, since u is isolated in G – v. Thus, ${\sum }_{i=2}^k{\theta }_s(G_i)+1={\theta }_s(G-v)$ and we have ${\theta }_s(G)\le {\theta }_s(G-v)$. The vertex u together with α_s -independent set of ${\cup }_{i=2}^k{G}_i$ is a star-independent set of G. Then ${\alpha }_s(G)\ge {\sum }_{i=2}^k{\alpha }_s(G_i)+1={\alpha }_s(G-v)$. These two inequalities imply that $$\begin{array}{c}{\theta }_s(G)\le {\theta }_s(G-v)\\ ={\alpha }_s(G-v),\text{since }G-v\text{ is star‐perfect}\\ \le {\alpha }_s(G)\end{array}$$

Next since ${\alpha }_s(G)\le {\theta }_s(G)$ is always true, we have ${\alpha }_s(G)={\theta }_s(G)$. On the other hand since G is a minimal star-imperfect graph, we have ${\theta }_s(G)\ne {\alpha }_s(G)$. We have arrived at a contradiction. □

Lemma 2.6.

If G is a minimal star-imperfect graph, then G is a block.

Proof.

G is connected by (1.3). Contrary to the lemma, let v be a cut vertex in G and let $C_1,C_2,\dots ,C_k$ be the components of G – v, where $k\ge 2$. By Lemma 2.5 none of C_i is K₁. Let G₁ = C₁ and $G_2={\cup }_{i=2}^k{C}_i$. Let L₁ be the subgraph induced by $[V(G_1)\cup \{v\}]$ and let L₂ be the subgraph induced by $[V(G_2)\cup \{v\}]$. Let $H_1=L_1-N_G[v]$ and $H_2=L_2-N_G[v]$. Since G is minimal star-imperfect, we have (i) ${\alpha }_s(G_i)={\theta }_s(G_i)$, (ii) ${\alpha }_s(L_i)={\theta }_s(L_i)$, and (iii) ${\alpha }_s(H_i)={\theta }_s(H_i)$, for all i, i = 1, 2. Therefore, there exists two non empty subgraphs G₁ and G₂ of G – v such that G₁ and G₂ have just the vertex v in common. We make two cases and in each case we arrive at a contradiction.

Case 1: There exists some α_s -independent set of G, say I containing v.

Let $I_{s1}=V(G_1)\cap (I-\{v\})$ and $I_{s2}=V(G_2)\cap (I-\{v\})$. Note that $I_{s1}$ and $I_{s2}$ are α_s -independent sets of G₁ and G₂, respectively. Moreover they are star-independent sets of G. Thus, we deduce ${\alpha }_s(G)$ as follows. $$\begin{array}{c}{\alpha }_s(G)=\left|I\right|\\ =\left|I_{s1}\right|+\left|I_{s2}\right|+1\\ ={\alpha }_s(G_1)+{\alpha }_s(G_2)+1\\ ={\theta }_s(G_1)+{\theta }_s(G_2)+1,\text{since }{G}_1\text{ and }{G}_2\text{ are}\\ \mathrm{\hspace{1em}}\mathrm{\hspace{1em}}\hspace{1em}\text{star‐perfect graphs as remarked above}\\ ={\theta }_s(G-v)+1\\ \ge {\theta }_s(G),\text{since }{\theta }_s(G-v)\text{‐set together with the }\\ \hspace{1em}\text{star centered at }v\text{ covers all the vertices of }G\end{array}$$

Therefore, ${\alpha }_s(G)\ge {\theta }_s(G)$. Hence, ${\alpha }_s(G)={\theta }_s(G)$, a contradiction to the property that G is minimal star-imperfect graph.

Case 2: No α_s -independent set of G contains v.

At the outset we observe that $d_G(x,y)=d_{L_i}(x,y)$, for every $x,y\in V(L_i),i=1,2$. Then, every star-independent set in $L_i(i=1,2)$ is a star-independent set in G.

Since L₁ is star-perfect and v does not belong to any α_s -independent set of G, by Lemma 2.4, there exists $u\in N_{L_1}(v)$ such that u is in an α_s -independent set of L₁, say I. Then $I-\left\{u\right\}$ is an α_s -independent set of H₁. Let $T_1=I-\left\{u\right\}$. Let T₂ be an α_s -independent set of H₂. Let $T_3=\left\{u\right\}$. Then one can easily verify that $T_1\cup T_2\cup T_3$ is a star-independent set in G. Hence ${\alpha }_s(G)\ge \left|T_1\right|+\left|T_2\right|+1$. (1)

Next let S_i be θ_s -cover of $H_i,i=1,2$ and let S₃ be the star $[N[v]]$ in G. It follows that $S_1\cup S_2\cup S_3$ is a star-cover of G. Hence ${\theta }_s(G)\le \left|S_1\right|+\left|S_2\right|+1$. (2)

Hence we derive, $$\begin{array}{c}{\theta }_s(G)\le \left|S_1\right|+\left|S_2\right|+1,\text{by }\mathrm{(}2\mathrm{)}\\ =\left|T_1\right|+\left|T_2\right|+1,\text{since }\left|S_1\right|=\left|T_1\right|\text{ and }\\ \mathrm{\hspace{1em}}\mathrm{\hspace{1em}}\left|S_2\right|=\left|T_2\right|\text{ because }{H}_1\text{ and }{H}_2\text{ are}\\ \mathrm{\hspace{1em}}\mathrm{\hspace{1em}}\text{ star‐perfect graphs }\\ \le {\alpha }_s(G),\text{ by }\mathrm{(}1\mathrm{)}\end{array}$$

Therefore, ${\alpha }_s(G)\ge {\theta }_s(G)$. Hence, ${\alpha }_s(G)={\theta }_s(G)$, a contradiction to the property that G is minimal star-imperfect graph.

□

Note. The parameters $\alpha (G)$ and $\theta (G)$ of Berge perfect graphs satisfy monotone property, that is if H is an induced subgraph of G, then $\alpha (H)\le \alpha (G)$ and $\theta (H)\le \theta (G)$. However, the parameters ${\alpha }_s(G)$ and ${\theta }_s(G)$ do not satisfy monotone property. That is, if H is an induced subgraph of G, ${\alpha }_s(H)$ (or ${\theta }_s(H)$) may exceed ${\alpha }_s(G)$ (or ${\theta }_s(G)$). For example if $G=K_{1,n},n\ge 2$ with central vertex v₀, then ${\alpha }_s(K_{1,n})=1$ and ${\theta }_s(K_{1,n})=1$. However ${\alpha }_s(K_{1,n}-v_0)=n$ and ${\theta }_s(K_{1,n}-v_0)=n,n\ge 2$.

So the property that the parameters α_s and θ_s do not satisfy monotone property causes difficulty in some of the results related to their equality.

Corollary 2.1.

Every tree is a star-perfect graph.

Proof.

On the contrary, suppose there exists a star-imperfect tree T. By (1.4), T contains a minimal star-imperfect tree $T\prime$. By Lemma 2.6, $T\prime$ is a block and so it is either K₁ or K₂. However, K₁ and K₂ are star-perfect graphs, a contradiction to our supposition. □

The following two lemmas are easily verifiable.

Lemma 2.7.

If G is triangle free and if G has an odd cycle of length at least 5, then G has an induced cycle of length at least 5. □

Lemma 2.8.

If G is triangle free and if G has a cycle of length 8 with at least one chord, then G has an induced cycle of length 4 or 5. □

Before moving on to the next lemma it is convenient to introduce and fix a notation.

In what follows, let G be a minimal star-imperfect graph. So for every vertex v, G – v is a star-perfect graph. Let v₀ be a fixed vertex in G and let ${\theta }_s(G-v_0)={\alpha }_s(G-v_0)=l$, for some positive integer l. Let $S_1,S_2,\dots ,S_l$ be a θ_s -cover of $G-v_0$, where S_i is a star centered at v_i , $1\le i\le l$. Thus, $L=\{S_0,S_1,\dots ,S_l\}$ is a star-cover of G where S_i is a star centered at v_i , $0\le i\le l$. Therefore, ${\theta }_s(G)\le l+1$. Let $v_{i1},v_{i2},\dots$ denote the vertices adjacent to v_i , that is $\left\{v_i\right\}\cup \{v_{i1},v_{i2},\dots \}=V(S_i)$. Let M be the set of stars in L that are adjacent to v₀ and N be the set of stars in L not adjacent to v₀. Let v₀ be adjacent to $v_{i1}$, for all stars $S_i\in M$ with central vertex v_i .

Lemma 2.9.

The cardinality of M is at least 2.

Proof.

Contrary to the lemma, let $\left|M\right|<2$. Since G is minimal star imperfect, it is a block and so $\left|M\right|\ne 0$. Next possibility is $\left|M\right|=1$. Let v₀ be any vertex in G and v₀ is adjacent to v₁₁. If v₁₂ exists then $v_0\nleftrightarrow v_{12}$, otherwise we have an induced C₄, a contradiction. Hence, v₁₁ is a cut vertex in G and $G-v_{11}$ has a component which is $[\{v_0\}]=K_1$, a contradiction to Lemma 2.5. Hence $\left|M\right|\ge 2$. □

Lemma 2.10.

If the stars in M are mutually vertex disjoint, then each star in M has at least two vertices.

Proof.

If the lemma is not true, then for some star, say $S_1=K_1\in M$. Let $S_1=[\{v_1\}]$ and by Lemma 2.9, there is one more star, say S₂ in M.

$S_1\nleftrightarrow S_2$. If otherwise, we have induced C₃ or C₄ or C₅, contradiction to G being minimal star-imperfect. If $S_1\leftrightarrow S_k\in N$, then we observe that $S_k\nleftrightarrow S_j,j\ne 1$ and j < k.

If $v_1\leftrightarrow v_k$, then $v_k\nleftrightarrow v_2$ or v₂₁, otherwise we have induced C₄ or C₅, a contradiction. Then the only adjacency possible is $v_k\leftrightarrow v_{22}$. Also no other vertex of S_k is adjacent to S₂, otherwise we have induced C₅ or C₇, a contradiction. This implies $G-v_k$ has two components one containing S₂ and the other containing S_k , contradicting that G is a block.

If $v_1\leftrightarrow v_{k1}$ or $v_1\leftrightarrow v_{k2}$, we similarly arrive at a contradiction to G being a block. Thus in all the cases we arrive at a contradiction, and hence the lemma is true. □

Note. In view of this lemma, v₀ is not adjacent to any of the central vertices of the stars in M.

Lemma 2.11.

There is at most one edge between a pair of stars in M.

Proof.

Let $S_1=\{v_1,v_{11},v_{12}\}$ and $S_2=\{v_2,v_{21},v_{22}\}$. Since G is a minimal star-imperfect graph, G is $(C_3,C_{3k+1},C_{3k+2})$-free.

Using Lemma 2.10 we show that $v_0\nleftrightarrow v_i,1\le i\le l$. If not, let $v_0\leftrightarrow v_k$, for some i = k. Then by Lemma 2.10 $v_{k1}$ exists and $v_{k1}$ is adjacent to v₀. Then $v_0{v}_k{v}_{k1}{v}_0$ is a cycle of length 3, a contradiction. Thus v₀ is not adjacent to any central vertices.

Let H be the subgraph of G induced by the vertices $\{v_0,v_1,v_{11},v_{12},v_2,v_{21},v_{22}\}$. The only possible edge between S₁ and S₂ is $v_1{v}_{22}$ or $v_2{v}_{11}$ for otherwise, there exists induced $C_3,C_4,C_5,C_7$, a contradiction to G being minimal star-imperfect graph. If both $v_1{v}_{22}$ and $v_2{v}_{11}$ exist, then we have an induced C₄, a contradiction.

Hence, there exists at most one edge between two stars in M and hence the lemma is proved. □

Note. From now, we assume every star in M has at least 2 vertices and the stars in M are pairwise disjoint. If S₁ has two vertices, and S₂ has three vertices and if $V(S_1)\cap V(S_2)\ne \varphi$, the vertices in $V(S_1)\cap V(S_2)$ could be retained in S₂. By similar arguments $V(S_1)\cap V(S_3),V(S_2)\cap V(S_3)$ is empty. Continuing the arguments we see that any two stars in M are disjoint and the stars could be arranged in increasing order with respect to their number of vertices.

Lemma 2.12.

The set N is non-empty.

Proof.

Contrary to the lemma, suppose N is empty. Since G is minimal star-imperfect, G is a block. If there is no edge between any two of the stars in M, then v₀ is a cut vertex of G, contradicting the fact G is a block. There exist two stars $S_i,S_j\in M$ such that there is at most one edge between them by Lemma 2.11. If both S_i and S_j have exactly two vertices, there is no edge between S_i and S_j , otherwise we have induced C₃, C₄ or C₅, a contradiction. So one of them has at least two vertices and the other has at least three vertices. Assuming S_i has only two vertices, as observed in the proof of Lemma 2.11, $v_i{v}_{j2}$ is the only edge between S_i and S_j (See Figure 2). We observe that if S_k is a star in M, $i,j\ne k$, then there is no edge between S_k and S_i or S_k and S_j . If there is an edge between S_j and S_k , say $v_k{v}_{j2}$, then we observe that there is no edge between S_i and S_j except $v_i{v}_{j2}$, otherwise we have induced C₃, C₄ or C₅, a contradiction. Let $H=[V(S_i)\cup V(S_j)\cup V(S_k)\cup \{v_0\}]$. If the vertices $v_{\mathit{\text{ir}}},v_{\mathit{\text{js}}},v_{\mathit{\text{kt}}},r\ge 2,s\ge 3,t\ge 2$ exist, they are pendent in G, a contradiction. Then H is as in Figure 2.

Fig. 2 $H=[V(S_i)\cup V(S_j)\cup V(S_k)\cup \{v_0\}]$.

In H, the set $\{v_0,v_{j2}\}$ is α_s -independent set of H of order 2 and the stars centered at $v_0,v_{j2}$ is θ_s -cover of H of order 2. Therefore, ${\alpha }_s(H)={\theta }_s(H)$. If $S_{k+1}$ is a star in M other than these three, we construct H₁ with vertex set V(H) and $V(S_{k+1})$ and by similar arguments, we see that ${\alpha }_s(H_1)={\theta }_s(H_1)$. Recursively we reach a stage where ${\alpha }_s(G)={\theta }_s(G)$, contradiction to G being minimal star-imperfect graph. Hence our assumption is false and N is non-empty. □

Note. Although C₅ is a minimal star-imperfect graph, Lemma 2.12 does not hold good for C₅.

Lemma 2.13.

Let G be a minimal star-imperfect graph. Let H₁ be the induced subgraph of G on $\{v_0,v_1,v_{11},v_{12},v_2,v_{21},v_{22},v_3,v_{31},v_{32}\}$ where $\{v_1,v_{11},v_{12}\}\subseteq S_1\in M,\{v_2,v_{21},v_{22}\}\subseteq S_2\in M$ and $\{v_3,v_{31},v_{32}\}\subseteq S_3\in N$. Then H₁ does not contain induced C₆ or C₉.

Proof.

If the lemma is not true, H₁ possibly contains an induced C₆ or C₉.

Case 1: v₀ is adjacent to a vertex of the stars S₁ and S₂ and H₁ contains a C₆. (See Figure 3 for possible C₆)

Fig. 3 $v_0{v}_{11}{v}_{31}{v}_3{v}_2{v}_{21}{v}_0$ is a cycle of length 6.

The set L₁ of stars of H₁ centered at $v_1,v_2,v_3,v_0$ is a star-cover of H₁; so ${\theta }_s(H_1)\le \left|L_1\right|=4$. The set $T_1=\{v_{12},v_{22},v_{32},v_0\}$ is a star-independent set in H₁, since $d(x,y)\ge 3$ for all $x,y\in T_1$ else H₁ contains a forbidden cycle (some edges of the forbidden cycle are edges of the cycle shown in Figure 3). It follows that ${\theta }_s(H_1)\le 4\le {\alpha }_s(H_1)$, that is ${\theta }_s(H_1)\le {\alpha }_s(H_1)$ and ${\theta }_s(H_1)={\alpha }_s(H_1)$.

Let H₂ be the induced subgraph of G on $V(G)-V(H_1)$. If $V(H_2)=\varphi$, then G = H₁. So ${\alpha }_s(G)={\alpha }_s(H_1)={\theta }_s(H_1)={\theta }_s(G)$. Thus, ${\alpha }_s(G)={\theta }_s(G)$, a contradiction to G being minimal star-imperfect. So let $V(H_2)\ne \varphi$ and T₂ be a star-independent set in G containing T₁ and has maximum cardinality. Since $V(H_2)\ne \varphi$, it follows that H₂ is star-perfect.

Claim 1: If $K⊒H_1$, then $T_1=\{v_{12},v_{22},v_{32},v_0\}$ is also a star independent set in K.

For any two vertices $x,y\in T_1$, we know $d_{H_1}(x,y)\ge 3$. We set to prove that $d_K(x,y)\ge 3$. Contrary to this let $d_K(x,y)\le 2$. We know that $d_K(x,y)\ne 1$, since H₁ is an induced subgraph of K. If $d_K(x,y)=2$, then say a pair of vertices in T₁ is adjacent to a common vertex $u\in V(K)-V(H_1)$. Then it is easy to verify that we obtain an induced forbidden cycle such as C₅, C₇ or C₈, a contradiction. Hence, $d_K(x,y)\ne 1$ or 2. This proves that T₁ is star-independent set in K as well.

Claim 2: $(T_2-T_1)\ne \varphi$

If not, then $T_2-T_1=\varphi$ and T₂ = T₁. This implies that there exists no vertex $v\in V(G)-V(H_1)$ such that $d_G(v,t)\ge 3$, for any $t\in T_1$. Therefore, $K⊒H_1$, we have ${\alpha }_s(K)=4$, or else we have contradiction to the maximality of T₁. (1)

Since $V(H_2)\ne \varphi$, let $H\prime$ be a maximum induced subgraph of G containing H₁ such that ${\theta }_s(H\prime )={\theta }_s(H_1)$. (2)

If $H\prime =G$, then $$\begin{array}{c}{\theta }_s(G)={\theta }_s(H\prime )={\theta }_s(H_1),\text{by }\mathrm{(}2\mathrm{)}\\ ={\alpha }_s(H_1),\text{since }{H}_1\text{ is}\\ \text{star‐perfect}\\ ={\alpha }_s(H\prime ),\text{by }\mathrm{(}1\mathrm{)}\\ ={\alpha }_s(G),\text{ by Claim 1}\end{array}$$

Therefore, ${\theta }_s(G)={\alpha }_s(G)$, a contradiction to G being minimal star-imperfect graph.

So let $H\prime \ne G$, then there exists a vertex u in $G-H\prime$ such that ${\theta }_s(H\prime \cup \{u\})\ne {\theta }_s(H_1)$. Using ${\theta }_s(H\prime \cup \{u\})\ne {\theta }_s(H_1)$ and (1) we have, ${\alpha }_s(H\prime \cup \{u\})=4={\alpha }_s(H_1)={\theta }_s(H_1)\ne {\theta }_s(H\prime \cup \{u\})$. Hence for the proper induced subgraph $H\prime \cup \left\{u\right\}$ of G, ${\theta }_s(H\prime \cup \{u\})\ne {\alpha }_s(H\prime \cup \{u\})$, a contradiction to G being minimal star-imperfect graph. Therefore, $T_2-T_1=\varphi$ is not possible and hence our claim.

The sets T₁, T₂ are star-independent sets in G. Let L₂ be a set of stars in H₂ such that each of the star contains a vertex of $T_2-T_1$ (such an L₂ exists because stars centered at each vertex of $T_2-T_1$ is such an L₂). Note that L₂ need not be a star-cover of H₂. Let H₃ be an induced subgraph on $V(H_1)\cup \underset{S\in L_2}{\cup }V(S)$. Let t be a vertex in $H″=[V(G)-V(H_3)]$. If t is star-independent with T₂ then we have a contradiction to maximality of T₂. By similar arguments as in claim 2, it implies that ${\theta }_s(H_3^{\prime })\ne {\alpha }_s(H_3^{\prime })$ where $H_3^{\prime }$ is the induced subgraph on $V(H_3)\cup \left\{t\right\}$, a contradiction to G being minimal star-imperfect graph.

Hence our assumption that H₁ contains an induced C₆ is not true and hence the lemma is proved.

Case 2: v₀ is adjacent to a vertex of the stars S₁ and S₂ and H₁ contains a C₉. (See Figure 4 for possible C₉)

Fig. 4 $v_0{v}_{11}{v}_1{v}_{12}{v}_{32}{v}_3{v}_{22}{v}_2{v}_{21}{v}_0$ is a cycle of length 9.

The set L₁ of stars of H₁ centered at $v_{11},v_{32},v_3$ is a star-cover of H₁; so ${\theta }_s(H_1)\le \left|L_1\right|=3$. The set $T_1=\{v_{12},v_{22},v_0\}$ is a star-independent set in H₁, since $d(x,y)\ge 3$ for all $x,y\in T_1$ else H₁ contains a forbidden cycle (some edges of the forbidden cycle are edges of the cycle shown in Figure 4). It follows that ${\theta }_s(H_1)\le 3\le {\alpha }_s(H_1)$, that is ${\theta }_s(H_1)\le {\alpha }_s(H_1)$ and ${\theta }_s(H_1)={\alpha }_s(H_1)$.

By repeating the same arguments as in Case 1, we see that H₁ contains an induced C₉ is not true and hence the lemma.

□

Lemma 2.14.

If G is minimal star-imperfect, then ${\theta }_s(G)={\alpha }_s(G)+1$.

Proof.

Using Lemma 2.3, we have that G is $(C_3,C_{3k+1},C_{3k+2})$-free, $k\ge 1$.

Let H₁ be the induced subgraph on $\underset{S_i\in M}{\cup }V(S_i)\cup \left\{v_0\right\}$ and H₂ be the induced subgraph on $\underset{S_j\in N}{\cup }V(S_j)$. By Lemma 2.9 we already know that $\left|M\right|\ge 2$ and H₂ is not a null graph. Let T₁ and T₂ be α_s -independent sets of H₁ and H₂, respectively. Let $T_2{}^{\prime }$ be a maximum subset (with respect to cardinality) of T₂ such that $T_1\cup T_2{}^{\prime }$ is a star-independent set of G. We consider the following two cases.

Case 1: $T_2{}^{\prime }=T_2$

Since G is minimal star-imperfect graph, ${\theta }_s(G-v_0)={\alpha }_s(G-v_0)$. Therefore, there exists a θ_s -cover, say F of $G-v_0$ such that every star in F contains exactly one vertex of α_s -independent set, say I of $G-v_0$.

Moreover, I is a star-independent set of G, since $H_1=\underset{S_i\in M}{\cup }V(S_i)\cup \left\{v_0\right\}$. $$\begin{array}{c}{\alpha }_s(G)\ge \left|I\right|,\text{ by above remark}\\ ={\alpha }_s(G-v_0),\text{since }I\text{ is an }{\alpha }_s\text{‐independent}\\ \mathrm{\hspace{1em}}\mathrm{\hspace{1em}}\text{set of }G-v_0\\ =l,\text{ by notation}\\ ={\theta }_s(G)-1,\text{by notation}\end{array}$$

So we have, ${\alpha }_s(G)\ge {\theta }_s(G)-1$, implying either ${\alpha }_s(G)={\theta }_s(G)-1$ or ${\alpha }_s(G)\ge {\theta }_s(G)$. In the former case, ${\alpha }_s(G)={\theta }_s(G)-1$, that is, ${\theta }_s(G)={\alpha }_s(G)+1$, which we set out to prove and in the later case, ${\alpha }_s(G)\ge {\theta }_s(G)$, a contradiction since G is a minimal star-imperfect graph (Figure 5).

Fig. 5 $H_1=[\underset{S_i\in M}{\cup }V(S_i)\cup \{v_0\}]$ and $H_2=[\underset{S_j\in N}{\cup }V(S_j)]$.

Case 2: $T_2{}^{\prime }\ne T_2$

This implies $T_2^{\prime }\subset T_2$. Then there exists $u\in T_2-T_2^{\prime }$.

If u is star-independent with $T_1\cup \{v_{32}$, we have a contradiction to choice of $T_2^{\prime }$. So, let u be not star-independent with $T_1\cup \left\{v_{32}\right\}$. Then, $d(u,v_{12})\le 2$ where $u=v_{42}$.

When $d(u,v_{12})=1$, u is not adjacent to any vertex in the set $\{v_1,v_{11},v_{12},v_2,v_{22}\}$, or else induced forbidden cycle.

When $d(u,v_{12})=2$, u is not adjacent to any vertex in the set $\{v_1,v_{11},v_{12},v_2,v_{21}\}$, or else induced forbidden cycle.

For cases $d(u,v_{12})=1$ and $u\leftrightarrow v_{21}$, we obtain C₆ and $d(u,v_{12}=2$ and $u\leftrightarrow v_{22}$, we obtain C₉. Using Lemma 2.13 we have a contradiction.

If v₄₁ and v₄ are not star-independent to $T_1\cup \left\{v_{32}\right\}$ then no vertex of S₄ is star-independent with $T_1\cup \left\{v_{32}\right\}$. This implies that ${\theta }_s(H_3)\ne {\alpha }_s(H_3)$ where H₃ is the induced subgraph on $V(H_1)\cup V(S_3)\cup V(S_4)$. This implies that v₄ or V₄₁ is star-independent with $T_1\cup \left\{v_{32}\right\}$. This contradicts choice of $T_2^{\prime }$. Hence case 2 does not arise at all.

This completes the proof of the lemma. □

Lemma 2.15.

Let G be a minimal star-imperfect graph. Let H₁ be the induced subgraph of G on $\{v_0,v_i,v_{i1},v_{i2},v_j,v_{j1},v_{j2},v_k,v_{k1},v_{k2}\}$ where $\{v_i,v_{i1},v_{i2}\}\subseteq S_i\in M,\{v_j,v_{j1},v_{j2}\}\subseteq S_j\in M$ and $\{v_k,v_{k1},v_{k2}\}\subseteq S_k\in N$. If S_k is adjacent to S_j , then S_k is not adjacent to any other star in M.

Proof.

If no star in M is adjacent to any star in N, then v₀ is a cut vertex in G, a contradiction by Lemma 2.6. So let $S_j\in M$ be adjacent to $S_k\in N$. The following adjacencies are possible between S_j and S_k .

If S_k is not adjacent to any other stars in M, then we are done. If not, let S_k be also adjacent to $S_i\in M$.

We look into each case mentioned in Table 1 in view of S_k adjacent to S_i as well.

Table 1 Adjacencies between $S_j\in M$ and $S_k\in N$.

$v_j\leftrightarrow v_k$	$v_j\leftrightarrow v_{k1}$	$v_{j1}\leftrightarrow v_k$
$v_{j1}\leftrightarrow v_{k1}$	$v_{\mathit{\text{jp}}}\leftrightarrow v_k$, for some $p\ge 2$	$v_{\mathit{\text{jp}}}\leftrightarrow v_{k1}$, for some $p\ge 2$

Since G is minimal star-imperfect, G is $(C_3,C_{3k+1},C_{3k+2})$-free, $k\ge 1$. In each of the following cases other than those mentioned in each of them, we obtain induced $C_4,C_5,C_7,C_8$ or C₁₀, a contradiction.

Case I:$v_j\leftrightarrow v_k$ (Figure 6)

Fig. 6 $v_j\leftrightarrow v_k$.

If S_k is adjacent to $S_i\in M$, the following adjacencies are possible.

If $v_{\mathit{\text{kp}}}(p\ge 1)\leftrightarrow v_{i1}$ (Figure 7), then $v_{\mathit{\text{kp}}}{v}_k{v}_j{v}_{j1}{v}_0{v}_{i1}{v}_{\mathit{\text{kp}}}$ is an induced cycle of length 6, a contradiction to Lemma 2.13.

Fig. 7 $v_{\mathit{\text{kp}}}{v}_k{v}_j{v}_{j1}{v}_0{v}_{i1}{v}_{\mathit{\text{kp}}}$ is an induced C₆.

Case II:$v_j\leftrightarrow v_{k1}$ (Figure 8)

Fig. 8 $v_j\leftrightarrow v_{k1}$.

If S_k is adjacent to $S_i\in M$, the following adjacencies are possible:

If $v_{k1}\leftrightarrow v_i$, then $v_{k1}{v}_j{v}_{j1}{v}_0{v}_{i1}{v}_i{v}_{k1}$ forms C₆, a contradiction to Lemma 2.13.

If $v_{k1}\leftrightarrow v_{\mathit{\text{iq}}}(q\ge 2)$, then $v_{k1}{v}_j{v}_{j1}{v}_0{v}_{i1}{v}_{\mathit{\text{iq}}}{v}_{k1}$ is an induced cycle of length 6, a contradiction to Lemma 2.13.

If $v_{\mathit{\text{kp}}}(p\ge 2)\leftrightarrow v_{\mathit{\text{iq}}}(q\ge 2)$, then $v_{\mathit{\text{kp}}}{v}_k{v}_{k1}{v}_j{v}_{j1}{v}_0{v}_{i1}{v}_i{v}_{\mathit{\text{iq}}}{v}_{\mathit{\text{kp}}}$ is an induced C₉, a contradiction to Lemma 2.13.

If $v_k\leftrightarrow v_{i1}$, then $v_k{v}_{k1}{v}_j{v}_{j1}{v}_0{v}_{i1}{v}_k$ is an induced cycle of length 6, a contradiction to Lemma 2.13.

Case III:$v_{j1}\leftrightarrow v_k$ (Figure 9)

Fig. 9 $v_{j1}\leftrightarrow v_k$.

If S_k is adjacent to $S_i\in M$, the following adjacencies are possible: If $v_{k1}\leftrightarrow v_i$, then $v_{k1}{v}_k{v}_{j1}{v}_0{v}_{i1}{v}_i{v}_{k1}$ is an induced cycle of length 6, a contradiction to Lemma 2.13.

If $v_k\leftrightarrow v_{\mathit{\text{iq}}}(q\ge 2)$, then $v_k{v}_{j1}{v}_0{v}_{i1}{v}_i{v}_{\mathit{\text{iq}}}{v}_k$ is an induced cycle of length 6, a contradiction to Lemma 2.13.

Case IV:$v_{j1}\leftrightarrow v_{k1}$ (Figure 10)

Fig. 10 $v_{j1}\leftrightarrow v_{k1}$.

If S_k is adjacent to $S_i\in M$, the following adjacencies are possible:

If $v_k\leftrightarrow v_i$, then $v_k{v}_{k1}{v}_{j1}{v}_0{v}_{i1}{v}_i{v}_k$ is an induced cycle of length 6, a contradiction to Lemma 2.13.

If $v_{k1}\leftrightarrow v_{\mathit{\text{iq}}}(q\ge 2)$, then $v_{k1}{v}_{j1}{v}_0{v}_{i1}{v}_i{v}_{\mathit{\text{iq}}}{v}_{k1}$ is an induced cycle of length 6, a contradiction to Lemma 2.13.

If $v_{\mathit{\text{kp}}}(p\ge 2)\leftrightarrow v_{i1}$, then $v_{\mathit{\text{kp}}}{v}_k{v}_{k1}{v}_{j1}{v}_0{v}_{i1}{v}_{\mathit{\text{kp}}}$ is an induced cycle of length 6, a contradiction to Lemma 2.13.

Case V:$v_{\mathit{\text{jp}}}\leftrightarrow v_k$, for some $p\ge 2$ (Figure 11)

Fig. 11 $v_{\mathit{\text{jp}}}\leftrightarrow v_k$, for some $p\ge 2$.

If S_k is adjacent to $S_i\in M$, the following adjacencies are possible:

If $v_k\leftrightarrow v_{i1}$, then $v_k{v}_{i1}{v}_0{v}_{j1}{v}_j{v}_{\mathit{\text{jp}}}{v}_k$ is an induced cycle of length 6, a contradiction to Lemma 2.13.

If $v_{k{p}_1}(p_1\ge 1)\leftrightarrow v_{\mathit{\text{iq}}}(q\ge 2)$, then $v_{k{p}_1}{v}_{\mathit{\text{iq}}}{v}_i{v}_{i1}{v}_0{v}_{j1}{v}_j{v}_{\mathit{\text{jp}}}{v}_k{v}_{k{p}_1}$ is an induced cycle of length 9, a contradiction to Lemma 2.13.

Case VI:$v_{\mathit{\text{jp}}}\leftrightarrow v_{k1}$, for some $p\ge 2$ (Figure 12)

Fig. 12 $v_{\mathit{\text{jp}}}\leftrightarrow v_{k1}$, for some $p\ge 2$.

If S_k is adjacent to $S_i\in M$, the following adjacencies are possible:

If $v_k\leftrightarrow v_{\mathit{\text{iq}}}(q\ge 2)$, then $v_k{v}_{\mathit{\text{iq}}}{v}_i{v}_{i1}{v}_0{v}_{j1}{v}_j{v}_{\mathit{\text{jp}}}{v}_{k1}{v}_k$ is an induced cycle of length 9, a contradiction to Lemma 2.13.

If $v_{k1}\leftrightarrow v_{i1}$, then $v_{k1}{v}_i{v}_{i1}{v}_0{v}_{j1}{v}_j{v}_{j3}{v}_k{v}_{k1}$ is an induced cycle of length 6, a contradiction to Lemma 2.13.

Thus we find that none of these six cases arise at all and hence our lemma. □

Theorem 2.1

(Main Theorem). A graph G is star-perfect if and only if G is $(C_3,C_{3k+1},C_{3k+2})$-free, $k\ge 1$.

Proof.

If G is star-perfect, then by Lemma 2.3, G is $(C_3,C_{3k+1},C_{3k+2})$-free, $k\ge 1$.

Conversely, suppose G is $(C_3,C_{3k+1},C_{3k+2})$-free, $k\ge 1$. If G is not star-perfect, assume G is a minimal star-imperfect graph.

Let v₀ be a vertex in G such that $\mathrm{\text{deg}}(v_0)=\Delta (G)$. We assume $\Delta (G)\ge 3$. Since G is minimal star-imperfect, $G-v_0$ is star-perfect and ${\alpha }_s(G-v_0)={\theta }_s(G-v_0)$. Let $S_1,S_2,\dots ,S_l$ be a θ_s -cover of $G-v_0$. Then $S_0=\left\{v_0\right\},S_1,S_2,\dots ,S_l$ will be a θ_s -cover of G and ${\theta }_s(G)=l+1$ and ${\alpha }_s(G)=l$, by Lemma 2.14. Then obviously v₀ is not adjacent to a central vertex of $S_1,S_2,\dots ,S_l$.

Let $S_i,S_j\in M$ and $S_k\in N$ be three stars such that $i\ge 1,j\ge 2,i<j<k$. Without loss of generality, let $S_k\leftrightarrow S_j$. By Lemma 2.15, if $S_k\in N$ is adjacent to $S_j\in M$, then S_k is not adjacent to any other star S_r in M where $r\ne j$. (1)

Since $\mathrm{\text{deg}}(v_0)=\Delta (G)\ge 3$, there exists $S_1,S_2,S_j\in M$. Further $S_k\leftrightarrow S_j$ and by Lemma 2.11, there is at most one edge between them. If S₁ and S₂ are adjacent, then only possible edge is $v_1{v}_{22}$ or $v_2{v}_{12}$. Then S_j is not adjacent to S₁ and S₂, otherwise we obtain an induced induced C₅, C₇ or C₈. This implies that $G-v_0$ has two different components one containing S₁ and S₂ and the other containing S_k , by (1). This contradicts that G is a block.

Next if S₁ and S₂ are not adjacent, and if S₁ is adjacent to S_j then S₂ is not adjacent to S_j , otherwise we obtain an induced C₅, C₇ or C₈. This implies that $G-v_0$ has two different components one containing S₂ and the other containing S_k , by (1), a contradiction to G being a block. Therefore, our assumption that $\mathrm{\text{deg}}(v_0)=\Delta (G)\ge 3$ is not true.

This implies that $\mathrm{\text{deg}}(v_0)=\Delta (G)\le 2$. If $\mathrm{\text{deg}}(v_0)=\Delta (G)=1$, then G is K₂, a contradiction to G being minimal star-imperfect graph. Therefore, only possibility is $\Delta (G)=2$ and G is $C_{3k},k\ge 2$ which is star-perfect, by Lemma 2.2, a contradiction to G being minimal star-imperfect. This completes the proof of the main theorem. □

Corollary 2.2.

A bipartite graph G is star-perfect if and only if every induced cycle of G is $C_{6k},k\ge 1$.

Proof.

From the above main theorem, a bipartite graph G is star-perfect if and only if every induced cycle of G is of the form $C_{3k},k\ge 2$. It is well know that a graph is bipartite if and only if every induced cycle is of the form $C_{2k},k\ge 0$. Combining these two statements we get that a bipartite graph G is star-perfect if and only if every induced cycle of G is $C_{6k},k\ge 1$. □

Immediately we get the following corollary.

Corollary 2.3.

A perfect graph G is star-perfect if and only if G is bipartite graph in which all induced cycles of G are of the form $C_{6k},k\ge 1$.

3 Future directions

All the stars in a star-cover of G studied in this paper are induced. We can extend this study to ${\theta }_S(G)$ which is the minimum number of stars (not necessarily induced) contained in G such that the union of their vertex sets is V(G) and let ${\alpha }_S(G)$ denote the maximum number of vertices in G such that no two of them are contained in the same star (not necessarily induced) of G. We call a graph G S-perfect if ${\alpha }_S(H)={\theta }_S(H)$, for every induced subgraph H of G. It will be an interesting problem to characterize S-perfect graphs.

Acknowledgments

We thank profusely Professor S. A. Choudum, Christ (Deemed to be University), for all fruitful discussions and critical comments on the entire paper.