Carathéodory Number of \(P_3\)-Convexity of Claw-Free Graphs

1. Introduction

The theory of abstract convexity spaces was originally developed to generalize classical convexity invariants such as Helly, Carathéodory, and Radon numbers in \(\mathbb{R}^d\). This idea was later extended to abstract convexity spaces by notable researchers such as Sierksma [1-3] and Duchet [4]. A comprehensive treatment of these concepts of abstract convexity can be found in the work of Van de Vel [5].
Graph convexity spaces have been a topic of much interest among the several structures of abstract convexity spaces. Many researchers have studied graph convexities from different perspectives. The most prominent types of graph convexities are defined in terms of paths in the graph, such as geodesic, induced path, and all-paths convexity [6-10]. An interesting type of path convexity in graphs is defined using the paths \(P_3\) on three vertices, known as \(P_3\)-convexity. The \(P_3\)-convexity was initially studied for directed graphs by Parker et al. in [11]. For undirected graphs, the \(P_3\)-convexity has been discussed in [12-14], and [15].

The Carathéodory number is a classical convexity invariant whose relationship with two other classical convexity invariants, namely, the Helly and Radon numbers of abstract convexities, has been extensively studied in [5, 16]. Parker et al. studied the Carathéodory number of the \(P_3\)-convexity of multipartite tournaments in [11] and proved that the maximum possible Carathéodory number is 3. The Carathéodory number of the \(P_3\)-convexity in undirected graphs was investigated by Barbosa et al. in [13] and Coelho et al. in [15]. Some general results concerning the Carathéodory number of the \(P_3\)-convexity are presented in [13], where it is shown that determining the Carathéodory number is NP-hard even in bipartite graphs. However, efficient algorithms are presented to determine such parameter in trees and block graphs. Coelho et al. further demonstrated in [15] that the Carathéodory number of \(P_3\)-convexity in a chordal graph can be determined in polynomial time. In this paper, we aim to contribute to the study of the Carathéodory number of \(P_3\)-convexity in claw-free graphs. This paper builds upon a conjecture posed in [13], which states that the Carathéodory number of \(P_3\)-convexity on claw-free graphs is less than or equal to \(\dfrac{2n(G)+6}{5}\). Our main objective is to prove this conjecture in the affirmative and to identify all extremal graphs that attain the bound. The paper is structured into two sections. In Section 2, we settle the conjecture for the Carathéodory number of the \(P_3\)-convexity in claw-free graphs. To aid in our discussion, we introduce the notations and terminology for the various concepts that we employ.

We restrict our attention to finite, simple, and undirected graphs. We denote a graph by \(G=(V,E)\), where \(V\) and \(E\) are the sets of vertices and edges, respectively. Let \(\mathcal{C}\) be a collection of subsets of \(V\). We say that \(\mathcal{C}\) is a convexity on \(V\) if the following conditions hold:

1. \(\emptyset,V \in \mathcal{C}\), and

2. \(\mathcal{C}\) is closed under arbitrary intersections.

A convexity space is a pair \((V,\mathcal{C})\) where \(V\) is a nonempty finite set and \(\mathcal{C}\) is a convexity on \(V\), with the members of \(\mathcal{C}\) referred to as convex sets [11,12]. For a connected graph \(G = (V,E)\) and a convexity \(\mathcal{C}\) on \(V\) such that \((V,\mathcal{C})\) is a convexity space, we form the graph convexity space \((G,\mathcal{C})\) [11,12]. Given a subset \(S\subseteq V\), the smallest convex set containing \(S\) is denoted by \(\langle S \rangle\) and call it the convex hull of \(S\). We say that a subset \(A \subseteq V\) of a graph \(G\) is a Carathéodory set if \(\langle A \rangle \neq \bigcup_{a \in A} \langle A \setminus \{a\} \rangle\). Equivalently, the set \(A\) is a Carathéodory set if \(\langle A \rangle \setminus \bigcup_{a \in A} \langle A \setminus \{a\} \rangle \neq \emptyset\). We denote this set as \(\partial H_G(S)\). The Carathéodory number \(C(G)\) of a convexity space \(\mathcal{C}\) is the maximum cardinality of a Carathéodory set [10,11,13,15,17]. Given a graph \(G = (V,E)\), a set \(S\subseteq V\) is said to be \(P_3\)-convex if for every path \(xyz\) in \(G\) where \(x,z\in S\), it holds that the vertex \(y\) also belongs to \(S\). In other words, a set \(S \subseteq V\) is \(P_3\)-convex if every vertex of \(G\) outside of \(S\) has at most one neighbor in \(S\). The collection of all \(P_3\)-convex sets in \(G\) form a convexity in \(G\), called the \(P_3\)-convexity. We say that a graph \(G\) is claw-free if it does not contain the claw, which is the complete bipartite graph \(K_{1,3}\), as an induced subgraph. Next Proposition states some elementary properties of Carathéodory sets.

2. Upper bound of Carathéodory Number of Claw-free Graphs

In this section, we settle the Conjecture 4 on the upper bound of Carathéodory number of claw-free graphs from [13]. We state it as a theorem (Theorem 1). To establish the theorem, we commence by introducing relevant notations and subsequently derive a lemma that specifically addresses a single case of the theorem. Let \(G\) be a graph with vertex set \(V\) and let \(S\) be a subset of \(V\). We prove the lemma and the theorem using the discharging method, similar to the approach used to prove a weaker improvement of Conjecture 4, stated as Theorem 5 in [13]. This theorem asserts that if \(G\) is a claw-free graph of order \(n(G)\), then \(C(G) \leq \frac{8n(G) + 12}{17}\). In [13], the proof technique for Theorem 5 involves constructing sets \(A, B\) and \(C\) in a specific manner and assigning initial charges \(\dfrac{1}{3|A|}\),\(\dfrac{1}{3|B|}\), and \(\dfrac{1}{3|C|}\) to vertices in \(A\), \(B\), and \(C\), respectively. In [13], only initial charges are assigned to the vertices. However, here we not only give initial charges to vertices but also distribute the charges of some vertices to some of the neighbors of the vertices by decreasing the charges of these vertices and increasing the charges of their neighbors. For convenience, we use a function to manage the charges, ensuring that the total charge remains constant. We define the function \(f\) from \(V\) to the set of non-negative rational numbers \(\mathbb{Q}^+\). We first choose a vertex sequence with certain properties.
By definition of \(P_3\)-convex hull, for any \(v \in \langle S \rangle\), there exists a \(k\) such that \(v \in P_3^k[S]\). Consequently, \(v\) has two neighbors in \(P_3^{k-1}[S]\), denoted as \(v_i\) and \(v_j\). As \(v_i, v_j \in P_3^{k-1}[S]\), there exist two neighbors of \(v_i\) and two neighbors of \(v_j\) in \(P_3^{k-2}[S]\). By iteration, this process yields a sequence \(v_1, v_2, \ldots, v_r = v\) such that each \(v_i\) has at least two neighbors in \(S \cup \{v_1, v_2, \ldots, v_{i-1}\}\). Now, assume that \(S = \{v_1, v_2, \ldots, v_l\}\) is a Carathéodory set of \(G\). Choose the sequence \(v_{l+1}, v_{l+2}, \ldots, v_k\) consisting of minimum number of distinct vertices (having minimum index ) in \(V(G) \setminus S\) such that \(v_k \in \partial H_G(S)\), and for every \(v_i\) with \(l+1 \leq i \leq k\), there are \(2\) neighbors of \(v_i\) in \({v_1,v_2,\ldots,v_{i-1}}\). Since \(S\) is a Carathéodory set of \(G\), every \(v_i\) with \(1 \leq i \leq l\) has at least one neighbor \(v_j\) with \(j > i\) such that \(v_j\) has only one neighbor in \(\{v_1, v_2, \ldots, v_{j-1}\} \setminus \{v_i\}\). For any \(v_i\) such that \(l+1 \leq i \leq k\), let \(S_{v_i}\) be the set of 2 neighbors of \(v_i\) in \(\{v_1, v_2, \ldots, v_{i-1}\}\) with minimum indices, and let \(s_{v_iv_j} \in S_{v_i}\) be the vertex with minimum index other than \(v_j\). Since by the choice of the sequence \(v_{l+1},v_{l+2},\ldots,v_k\), for every \(i\) with \(l+1 \leq i \leq k\), there are 2 distinct vertices in \(\{v_1, v_2, \ldots, v_k\}\) which are adjacent to \(v_i\), \(S_{v_i}\) and \(s_{v_iv_j}\) are well-defined. Now define \[f(v)= \begin{cases} \dfrac{2}{5}, \hspace{1.9cm} \text{ if } v\in \{v_1,v_2,\ldots,v_{k-1}\},\\ \dfrac{2}{5}+\dfrac{6}{5}=\dfrac{8}{5,} \hspace{.5cm}\text{ if } v=v_k,\\ 0, \hspace{2cm}\text{ otherwise.} \end{cases}\] For every vertex \(v\) in \(V(G)\), there is a \(\frac{2}{5}\) contribution to the sum \(\frac{2n(G)+6}{5}\), since \(n(G)=|V|\). So \[\sum_{i=1}^k f(v_i) = \frac{2|\{v_1,v_2,\dots,v_k\}|+6}{5} \leq \frac{2n(G)+6}{5}.\] We will adjust the \(f\)-values of certain vertices such that eventually, we achieve \(f(v) \geq 1\) for all \(v \in S\), while ensuring that \(f(v_i) \geq 0\) for all \(v_i\) and maintaining the sum \(\sum_{i=1}^k f(v_i)\) as a constant throughout. Note that after the transformations, \(f(v_i) \geq 0\) for all \(v_i\), and hence \(\sum_{i=l+1}^k f(v_i) \geq 0\). Therefore, we have: \[C(G) = |S| = l \leq \sum_{v \in S} f(v) \leq \sum_{i=1}^k f(v_i) \leq \frac{2n(G) + 6}{5},\] which is the required inequality.

Proof. Let \(G\) be a claw-free graph, and let \(S=\{v_1, v_2, \ldots, v_l\}\) be a Carathéodory set of cardinality \(C(G)\) . We now describe a procedure to adjust the values of \(f(v)\) such that \(f(v) \geq 1\) for all \(v \in S\), \(f(v) \geq 0\) for all \(v\), and \(\sum_{i=1}^k f(v_i)\) remains unchanged.

Now consider \(v_k\). Let \(u_1, u_2 \in S_{v_k}\). Since \(S_{v_k}\cap S \neq \emptyset\), we have 2 cases.

1. Case 1:

   Both \(u_1,u_2\) belongs to \(S\).

2. Case 2:

   One of the \(u_1,u_2\) belongs to \(S\) and other does not belong to \(S\).

Case (1): If \(\{u_1, u_2\} \subseteq S\), then \(S = \{u_1, u_2\}\) because \(v_k \in \langle \{u_1, u_2\}\rangle\) and \(v_k \in \partial H_G(S)\). We can then adjust the values of \(f(u_1)\) and \(f(u_2)\) as follows: \(f(u_1) \longrightarrow f(u_1) + \dfrac{3}{5}\), \(f(u_2) \longrightarrow f(u_2) + \dfrac{3}{5}\), and \(f(v_k) \longrightarrow f(v_k) – \dfrac{6}{5}\). Note that this transformation does not change the value of \(\Sigma_{i=1}^kf(v_i)\) and guarantees that \(f(v) \geq 1\) for all \(v\) in \(S\) and \(f(v)\geq 0\) for all \(v\) in \(V(G)\).
Case (2): If one of the vertices \(u_1,u_2\), say \(u_1 \in S\) and the other \(u_2 \notin S\). Then there are two cases: \(u_1u_2 \in E(G)\) or \(u_1u_2 \notin E(G)\).
Subcase (2.1): \(u_1u_2 \in E(G)\).

Since \(u_2 \notin S\) implies that \(u_2 \in \{v_{l+1},\ldots,v_k\}\). So \(S_{u_2} \neq \emptyset\). Let \(u_3 = s_{u_2u_1}\). Then change \(f(u_1) \longrightarrow f(u_1) + \frac{3}{5}\), \(f(u_3) \longrightarrow f(u_3) + \frac{4}{5}=\dfrac{6}{5}\), \(f(u_2) \longrightarrow f(u_2) – \frac{2}{5}\), and \(f(v_k) \longrightarrow f(v_k) – \frac{5}{5}\). Note that \(f(v_i)\geq 0\) and \(\sum_{i=1}^k f(v_i)\) is not changed under the transformation.

If \(u_3 \in S\) (as in Figure 1), then \(S = \{u_1,u_3\}\) since \(v_k\in \langle \{u_1,u_3\}\rangle\), \(\{u_1,u_3\}\subset S\) and \(S\) is a Carathéodory set. Note that \(f(v) \geq 1\) for all \(v\) in \(S\) and \(f(v)\geq 0\) for all \(v\in V(G)\). Also, \(\sum_{i=1}^k f(v_i)\) is not changed.

Suppose \(u_3 \notin S\). Then we know that either \(u_1\) is in \(S_{u_3}\) or it is not. In the former case, as shown in Figure 2\((i)\), we can select the vertex \(u_4\) (distinct from \(u_1\)) and update \(f\) as follows:\(f(u_4)\longrightarrow f(u_4)+\dfrac{4}{5},f(u_3)\longrightarrow f(u_3)-\dfrac{4}{5}\). Here \(f(u_3)=\dfrac{6}{5}-\dfrac{4}{5}\geq 0\). We can then continue the process with \(u_4\) in place of \(u_3\). If \(u_1 \notin S_{u_3}\), we let \(S_{u_3}=\{u_4,u_5\}\). Since the induced subgraph \(G[\{u_2,u_3,u_4,u_5\}]\) cannot be a claw, we know that either \(u_2u_4 \in E(G)\) or \(u_2u_5 \in E(G)\), or \(u_4u_5 \in E(G)\). However, by the choice of \(u_2,u_3,u_4,u_5\), we have \(u_2u_4\) and \(u_2u_5\) not in \(E(G)\). Therefore, we conclude that \(u_4u_5\) must be an edge in \(G\), as depicted in Figure 2\((ii)\).

\((i)\) \((ii)\)

If \(u_4, u_5 \in S\), then \(S=\{u_1,u_4,u_5\}\) similarly as above. We can now change \(f(u_4)\longrightarrow f(u_4)+\dfrac{3}{5}, f(u_5)\longrightarrow f(u_5)+\dfrac{3}{5}, f(u_3) \longrightarrow f(u_3)-\dfrac{6}{5}=0\) to ensure that \(f(v)\geq 1\) for all \(v\) in \(S\), without changing \(\Sigma_{i=1}^k f(v_i)\) and \(f(v)\geq 0\) for all \(v\in V(G)\).

If \(|S_{u_3}\cap S|=1\), we let \(u_4 \in S\) and \(u_5\notin S\). Then we let \(u_6=s_{u_5u_4}\). We can now change \(f(u_4)\longrightarrow f(u_4)+\dfrac{3}{5}, f(u_6)\longrightarrow f(u_6)+\dfrac{4}{5}, f(u_5)\longrightarrow f(u_5)-\dfrac{2}{5}, f(u_3)\longrightarrow f(u_3)-\dfrac{5}{5}\), and continue with \(u_6\). If both \(u_4\) and \(u_5\) are not in \(S\), then there are three possibilities for \(|S_{u_4} \cap S_{u_5}|\): it can be 0, 1, or 2.
Subsubcase 2.1.1: \(|S_{u_4} \cap S_{u_5}| = 0\).

If either \(u_5 \in S_{u_4}\) or \(u_4 \in S_{u_5}\). Then rename the vertex which has 2 neighbors in \((S_{u_4}\cup S_{u_5})\setminus \{u_4,u_5\}\) as \(u_4\), and the other vertex as \(u_5\) if necessary. Let \(u_6=s_{u_5u_4}\). If \(u_5 \notin S_{u_4}\) and \(u_4 \notin S_{u_5}\), we rename \(u_4\) and \(u_5\) if necessary such that \(S_{u_5}\) contains the vertex \(w\) in \(S_{u_4} \cup S_{u_5}\) with the maximum index. Let \(u_6=s_{u_5w}\). In both cases, as shown in Figure [f3], we change \(f(u_4) \longrightarrow f(u_4) + \frac{4}{5}\), \(f(u_6) \longrightarrow f(u_6) + \frac{4}{5}\), \(f(u_5) \longrightarrow f(u_5) – \frac{2}{5}\), and \(f(u_3) \longrightarrow f(u_3) – \frac{6}{5}\), and continue with \(u_4\) and \(u_6\).

Subsubcase 2.1.2: \(|S_{u_4} \cap S_{u_5}|=1\).

Let \(u_6 \in S_{u_4} \cap S_{u_5}\). If \(u_4 \in S_{u_5}\) or \(u_5 \in S_{u_4}\), rename the vertex in \(\{u_4,u_5\}\) that has two neighbors in \(S_{u_4} \cup S_{u_5} \setminus\{u_5,u_4\}\) as \(u_4\), and the other vertex as \(u_5\) if necessary. Then change \(f(u_4) \longrightarrow f(u_4)+\dfrac{4}{5}\) and \(f(u_3) \longrightarrow f(u_3)-\dfrac{4}{5}\), and continue with \(u_4\). If \(u_5 \notin S_{u_4}\) and \(u_4 \notin S_{u_5}\), rename the vertices in \({u_4,u_5}\) if necessary such that \(S_{u_5}\) contains the vertex \(v\) with the largest index in \(S_{u_4} \cup S_{u_5}\) other than \(u_6\). Let \(S_{u_4}=\{u_6,u_7\}\). If \(u_6 \in S\) or \(v \notin S_{u_6}\), then change \(f(u_4) \longrightarrow f(u_4)+\dfrac{4}{5}\) and \(f(u_3) \longrightarrow f(u_3)-\dfrac{4}{5}\), and continue with the vertices \(u_6\) and \(u_7\) as similar to \(u_4\) and \(u_5\). (Note that if \(u_6 \notin S\) and \(v \notin S_{u_6}\), then the vertices in \(S_{u_6}\) have lower indices than \(v\), since \(vu_6 \in E(G)\)). Otherwise, \(u_6 \notin S\) and \(v \in S_{u_6}\). Then \(S_{u_6}=\{u_7,v\}\) (since the vertex \(u_7\) is adjacent to \(u_6\) and has a lower index than \(v\)). Change \(f(u_3) \longrightarrow f(u_3)-\dfrac{4}{5}\), \(f(v) \longrightarrow f(v)+\dfrac{4}{5}\), \(f(u_7) \longrightarrow f(u_7)+\dfrac{4}{5}\), \(f(u_4) \longrightarrow f(u_4)-\dfrac{2}{5}\), and \(f(u_6) \longrightarrow f(u_6)-\dfrac{2}{5}\), and continue with \(u_7\) and \(v\).

Sub-subcase 2.1.3: If both neighbours are same (Figure 5).

Then change \(f(u_4) \longrightarrow f(u_4)+\dfrac{4}{5},f(u_3 )\longrightarrow f(u_3)-\dfrac{4}{5}\) and continue.

In general, if \(u_i\) is a vertex not in \(S\) such that \(f(u_i)\geq \frac{6}{5}\), then \(S_{u_i}\neq \phi\), say \(u_{i+1},u_{i+2} \in S_{u_i}\). If one of them has been considered, we can simply rename the other vertex as \(u_{i+1}\), if necessary. We then update the values of \(f(u_{i+1})\) and \(f(u_i)\) as follows: \(f(u_{i+1}) \longrightarrow f(u_{i+1})+\frac{4}{5}\) and \(f(u_i) \longrightarrow f(u_i)-\frac{4}{5}\), and continue with \(u_{i+1}\). If both neighbors are already considered, we stop and continue with another vertex \(u_j\) with \(f(u_j) \geq \frac{6}{5}\), if there is any such vertex.

Now continue the process with \(u_i\), \(u_{i+1}\), and \(u_{i+2}\) in place of \(u_3\), \(u_4\), and \(u_5\). It is important to note that in every step, the sum \(\Sigma_{i=1}^k f(v_i)\) remains unchanged and \(f(v_i)\geq 0\) for all \(v_i\). Continuing like this, we obtain a sequence of vertices \(u_1,u_2,\ldots\). Since \(G\) is finite, this sequence must terminate. Let the terminating vertex be \(u_j\). By our construction of the \(u_i\)’s, we have \(v_k \in [S\cap {u_1,u_2,\ldots,u_j}]\). Furthermore, since \(v_k \in \partial H_G(S)\), it follows that \(S \subseteq \{u_1,u_2,\ldots,u_j\}\). Moreover, we have modified the values of \(f(u_i)\) such that \(f(u_i) \geq 1\) whenever \(u_i \in S\).
Subcase 2.2: \(u_1u_2 \notin E(G)\) and \(u_1 \in S\), \(u_2 \notin S\).

We change \(f(u_1) \longrightarrow f(u_1) + \dfrac{3}{5}\), \(f(u_2) \longrightarrow f(u_2) + \dfrac{4}{5}\), and \(f(v_k) \longrightarrow f(v_k) – \dfrac{7}{5}\). Since \(u_2 \notin S\), we have \(S_{u_2}\neq \phi\). Let \(u_3,u_4\in S_{u_2}\). Then \(u_3u_4 \in E(G)\) since \(G\) is claw-free (as shown in Figure \(6\)). Next, we continue with \(u_2\) as we did with \(u_3\) in subcase 2.1.

We obtain a sequence of vertices \(u_1, u_2, \ldots, u_j\) that includes all vertices in \(S\) and satisfies \(f(v) \geq 1\) for all \(v \in S\), as per our construction. Thus we get \(C(G)\leq \dfrac{2n(G)+6}{5}\). ◻

Proof. Let \(G\) be a claw-free graph of order \(n(G)\) and \(S,v_{l+1},v_{l+2},\ldots v_k,f\) be the same as described earlier. If \(S_{v_k}\cap S\neq \emptyset\) then \(C(G) \leq \dfrac{2n(G)+6}{5}\) by Lemma 1.

If \(S_{v_k}\cap S=\emptyset\), let \(S_{v_k}=\{u_1,u_2\}\). If \(u_1u_2 \in E(G)\), we can continue as in above lemma with \(v_k\) inplace of \(u_i\) since \(f(v_k) \geq \dfrac{6}{5}\). If \(u_1u_2 \notin E(G)\), let \(S_{u_1}=\{u_3, u_4\}\) and \(S_{u_2}=\{u_5, u_6\}\). Then there are three cases:
Case 1: \(S_{u_1}=S_{u_2}\).

If \(S_{u_1}=S_{u_2}\), then \(S=\{u_3, u_4\}\) (as in Figure 7\((i)\)). Otherwise, we must have \(u_1u_2 \in E(G)\) since \(G\) is claw-free, which leads to a contradiction.

Case 2: If \(|S_{u_1}\cap S_{u_2}|=1\), let’s say \(u_4 = u_6\) (as depicted in Figure 7\((ii)\)). Then, either \(u_4 \in S\) or \(S_{u_4}=\{u_3, u_5\}\); otherwise, there exists a neighbor \(u_7\) with an index less than \(u_4\), and \(u_7 \neq u_3,u_5\). Since \(u_2,u_1,u_4,u_7\) do not form a claw, there are three possibilities: either \(u_2u_7 \in E(G)\), or \(u_1u_7 \in E(G)\), or \(u_1u_2 \in E(G)\). However, since \(u_4\) and \(u_5\) are two neighbors of \(u_2\) with minimum indices, and the index of \(u_7\) is less than \(u_4\), we have \(u_2u_7 \notin E(G)\). Similarly, \(u_1u_7 \notin E(G)\).It follows that \(u_1u_2 \in E(G)\), which contradicts our assumption that \(u_1u_2 \notin E(G)\). Therefore, either \(u_4 \in S\) or \(S_{u_4}=\{u_3,u_5\}\) and since \(G\) is claw-free, we have \(u_4u_3,u_4u_5 \in E(G)\).
Subcase 2.1: If \(u_4 \in S\).

If \(u_3u_5 \in E(G)\) and \(u_3\) or \(u_5\) is in \(S\), say \(u_3\), then \(S=\{u_3,u_4\}\) since \(v_k \in \partial H_G(S)\). We then change \(f(u_3) \longrightarrow f(u_3) +\dfrac{3}{5}\) and \(f(u_4) \longrightarrow f(u_4) +\dfrac{3}{5}\), and \(f(v_k) \longrightarrow f(v_k)-\dfrac{6}{5}\).

If \(u_3u_5 \notin E(G)\) and \(u_3\) or \(u_5\) is in \(S\), say \(u_3\) (since \(u_4 \in S\), not both \(u_3\) and \(u_5\) belong to \(S\)), we let \(u_6 = S_{u_5u_4}\) and change \(f(u_3) \longrightarrow f(u_3) +\dfrac{3}{5}\), \(f(u_4) \longrightarrow f(u_4) +\dfrac{3}{5}\), \(f(v_k) \longrightarrow f(v_k)-\dfrac{6}{5}\), \(f(u_6) \longrightarrow f(u_6) + \dfrac{4}{5}\), \(f(u_5) \longrightarrow f(u_5) – \dfrac{2}{5}\), and \(f(u_2) \longrightarrow f(u_2) – \dfrac{2}{5}\), and continue with \(u_6\) as above.

If \(u_3,u_5 \notin S\) and \(u_3u_5 \notin E(G)\), we consider \(u_6=S_{u_3u_4}\) and \(u_7=S_{u_5u_4}\). If \(u_6=u_7\), then \(S=\{u_4,u_6\}\) since \(v_k\in \langle \{u_4,u_6\}\rangle,u_4,u_6\in S\) and \(S\) is a Carathéodory set. Change \(f(u_4 ) \longrightarrow f(u_4) +\dfrac{3}{5}\), \(f(u_6) \longrightarrow f(u_6) +\dfrac{3}{5}\), and \(f(v_k) \longrightarrow f(v_k) – \dfrac{6}{5}\). If \(u_6 \neq u_7\), we change \(f(u_4) \longrightarrow f(u_4) +\dfrac{3}{5}\), \(f(u_6) \longrightarrow f(u_6) +\dfrac{4}{5}\), \(f(v_k) \longrightarrow f(v_k)-\dfrac{7}{5}\), \(f(u_7) \longrightarrow f(u_7) + \dfrac{4}{5}\), \(f(u_5) \longrightarrow f(u_5) – \dfrac{2}{5}\), and \(f(u_2) \longrightarrow f(u_2) – \dfrac{2}{5}\), and continue with \(u_6\) and \(u_7\) similar to the above case.

If \(u_3,u_5 \notin S\) and \(u_3u_5 \in E(G)\), we let \(u_3\) have a lower index than \(u_5\) and consider \(u_6=S_{u_3u_4}\). Then change \(f(u_6)\longrightarrow f(u_6)+\dfrac{4}{5}, f(u_4) \longrightarrow f(u_4)+\dfrac{3}{5},f(v_k)\longrightarrow f(v_k)-\dfrac{7}{5}\) and continue with \(u_6\)
Subcase 2.2: If \(u_4 \notin S\), then \(u_3,u_5 \in S_{u_4}\) and change \(\longrightarrow f(u_4)+ \dfrac{6}{5} ,f(v_k) \longrightarrow f(v_k) – \dfrac{6}{ 5}\) and continue with \(u_4\).
Case 3: If all neighbours are distinct(as given in Figure 7\((iii)\)), then change \(f(u_1) \longrightarrow f(u_1)+\dfrac{4}{5},f(u_2) \longrightarrow f(u_2) +\dfrac{4}{5} ,f(v_k) \longrightarrow f(v_k) -\dfrac{8}{ 5}\) and continue with \(u_1\) and \(u_2\).

\((i)\)\((ii)\) \((iii)\)

By following the procedure mentioned above, we eventually obtain a finite sequence of vertices \(u_1, u_2, \ldots, u_j\) that includes all vertices in the set \(S\), while ensuring that \(f(v) \geq 1\) for all \(v \in S\) and without changing the sum \(\sum_{i=1}^k f(v_i)\), and \(f(v_i) \geq 0\) for all \(v_i\). Thus, we can conclude that \(C(G) = |S| = l \leq \Sigma_{v\in S} f(v) \leq \Sigma_{i=1}^k f(v_i) \leq \frac{2n(G)+6}{5}\). ◻

Next, our goal is to identify all claw-free graphs that attain the upper bound of the Carathéodory number for \(P_3\)-convexity as given in the above inequality. Let \(G\) be a graph that satisfies equality in the above inequality. Then, \(\dfrac{2n(G)+6}{5}\) is an integer, implying that \(n(G) = 5k+2\) for some integer \(k\). Since the Carathéodory number of a graph of order \(2\) is \(1\), and the Carathéodory number of \(G_0\) in Figure 8 (which has order \(7\)) is \(4\), the smallest order of a graph that attains the bound in the above inequality is \(7\).

Now, we will construct a collection of possible graphs from \(G_0\) in Figure \(8\) that attain the bound in the above inequality. We define the extension of \(G_0\) through \(u_6\) and \(u_7\) as the graph \(H_0\), which is obtained by attaching a triangle at vertex \(u_6\) and a paw (a graph obtained by joining a cycle graph \(C_3\) to a singleton graph \(K_1\) with a bridge) at vertex \(u_7\), as shown in Figure \(8\). If \(u_i\) and \(u_{i+1}\) are the endpoints of a branch in \(H_0\) (i.e., they lie in a triangle, and no vertex lies below them), we can extend the graph \(H_0\) through \(u_i\) and \(u_{i+1}\) by attaching a triangle at \(u_i\) and a paw at \(u_{i+1}\).

More generally, if \(G\) is a graph obtained by a finite extension of \(G_0\), and \(u\) and \(v\) are endpoints of a particular branch, we can define the extension of \(G\) through \(u\) and \(v\) as the graph obtained by attaching a triangle at \(u\) and a paw at \(v\). Let \(\mathcal{G}\) be the family of graphs that consists of \(G_0\) and every graph obtained from \(G_0\) by a finite extension.

Theorem 2. Let \(G\) be a graph. if \(G \in \mathcal{G}\) , then \(C(G) =\dfrac{2n(G)+6}{5}\).

Proof. We can verify that \(S=\{u_6,u_7,u_8,u_9\}\), which is the set of all end vertices of branches in \(G_0\), is a Carathéodory set of \(G_0\) with cardinality \(\dfrac{2n(G_0)+6}{5}\).

Now, we will prove that if \(G\) is a graph in \(\mathcal{G}\) and let \(S\) be the set of all end vertices of branches in \(G\), which is a Carathéodory set of \(G\), with \(|S|=\dfrac{2n(G)+6}{5}\), then \(S_1=S\setminus \{u,v\} \cup \{v_1,v_2,v_4,v_5\}\) is a Carathéodory set of \(G_1\). Here, \(G_1\) arises from \(G\) by replacing vertex \(u\) with a triangle \(u,v_1,v_2\), and vertex \(v\) with a paw \(v,v_3,v_4,v_5\).

It should be noted that \(u\) and \(v\) are both elements of set \(S\). We have \(\partial H_G(S) \subseteq \partial H_{G_1}(S_1)\) because \[\begin{aligned} \partial H_{G_1}(S_1) &= \langle S_1 \rangle \setminus \Big(\bigcup_{w \in S \setminus \{u,v\}} \langle S_1\setminus\{w\}\rangle \ \bigcup \bigcup_{w\in \{v_1,v_2,v_4,v_5\}} \langle S_1\setminus\{w\}\rangle \Big) \ \\&= \langle S \rangle \bigcup \{v_1,v_2,v_3,v_4,v_5\} \ \setminus \Big(\bigcup_{w \in S \setminus \{u,v\}} \langle S\setminus\{w\}\rangle \ \\&\qquad \bigcup \{v_1,v_2,v_3,v_4,v_5\} \cup \langle S\setminus\{u,v\}\rangle \ \bigcup \langle S\setminus\{v\}\rangle \bigcup \{v_1,v_2,v_3,v_4,v_5\}\Big) \ \\&= \langle S \rangle \setminus \Big(\bigcup_{w \in S \setminus \{u,v\}} \langle S\setminus\{w\}\rangle \ \bigcup \langle S\setminus\{v\}\rangle \bigcup \langle S\setminus\{u,v\}\rangle\Bigg) \ \\& \supseteq \langle S \rangle \setminus \bigcup_{w \in S} \langle S\setminus\{w\}\rangle \ \\&= \partial H_G(S). \end{aligned}\] Thus, \(S_1\) is a Carathéodory set of \(G_1\). Therefore, \[\begin{aligned} C(G_1)\geq|S_1|&=|S|-2+4=|S|+2\\&= \dfrac{2n(G)+6}{5}+2 = \dfrac{2n(G)+10+6}{5}\\&=\dfrac{2(n(G)+5)+6}{5}=\dfrac{2n(G_1)+6}{5}. \end{aligned}\] Now, \(C(G_1) \leq \dfrac{2n(G_1)+6}{5}\) since the graph \(G_1\) is claw-free. Thus, \(C(G_1)=\dfrac{2n(G_1)+6}{5}\). Therefore, if \(G \in \mathcal{G}\) then \(C(G)=\dfrac{2n(G)+6}{5}\). ◻

Theorem 3. Let \(G\) be a claw-free graph of order \(n(G)\). Then, \(C(G)=\dfrac{2n(G)+6}{5}\) if and only if \(G \in \mathcal{G}\).

Proof. The sufficiency of the statement is proven by the theorem mentioned above. To prove the converse part of the theorem, suppose \(G\) is a graph of order \(n(G)\) such that \(C(G) = \frac{2n(G)+6}{5}\), and let \(S\) be a Carathéodory set of cardinality \(C(G)\). Then \(G\) is minimal in the sense that \(G\) has no proper subgraph with the same Carathéodory number. Let \(v_1,v_2,\dots,v_k\) be the subset of \(V\) as described in the main theorem’s proof. Since \(V(G) \neq \{v_1,v_2,\dots,v_k\}\) would imply that \(G[{v_1,v_2,\dots,v_k}]\) is a proper subgraph of \(G\) with fewer than \(n(G)\) vertices and a Carathéodory set of cardinality \(C(G)\), this contradicts the minimality of \(G\). Therefore, \(V(G) = \{v_1,v_2,\dots,v_k\}\).

For \(G\) to attain equality in the upper bound of Theorem 1,we need \(|S| = \sum_{i=1}^k f(v_i) = \sum_{i=1}^kf(v_k) = \frac{2n(G)+6}{5}\). After the transformation described in the proof, this implies that \(f(v) = 1\) for all \(v \in S\) and \(f(v) = 0\) for all \(v \notin S\). Therefore, cases (1) and (2), where \(f(v_k) > 0\), cannot happen since \(v_k \notin S\).

For subcases (a) and (b) of case 3, we have \(f(v_k) > 0\), and since \(v_k \notin S\), neither case (a) nor (b) is possible. Therefore, subcase (c) of case 3 applies to \(G\).

Now, as in the proof, let \(u_3\) and \(u_4\) be vertices in \(S_{u_1}\). Either \(u_3\) and \(u_4\) are both in \(S\) or both are not in \(S\); otherwise, as described in the proof, \(f(u_1) >0\), which is not possible .

If they are not in \(S\), let \(u_5,u_6\in S_{u_3}\), and let \(u_7,u_8\in S_{u_4}\) . Then \(u_5,u_6,u_7,\) and \(u_8\) must all be distinct; otherwise, we would have \(f(u_1)> 0\), which is not possible since \(u_1 \notin S\). Suppose \(u_5\) and \(u_6\) are neighbors of \(u_3\), and \(u_7\) is a neighbor of \(u_4\). Then, \(u_7 \notin S\), or otherwise \(f(u_7) > 1\), which is not possible. Consider two neighbors \(u_8\) and \(u_9\) of \(u_7\). In general, let \(u_i\) be a vertex not in \(S\), and let \(u_{i+1}\) and \(u_{i+2}\) be two neighbors of \(u_i\) in \(S\). If either \(u_{i+1}\) or \(u_{i+2}\) has already been considered, then we would have \(f(u_i) > 0\), which is not possible. Thus, both \(u_{i+1} \neq u_j\) and \(u_{i+2} \neq u_j\) for all \(j < i\).

We continue by considering the vertices \(u_i\), \(u_{i+1}\), and \(u_{i+2}\), and observe that either both \(u_{i+1}\) and \(u_{i+2}\) are in \(S\), or neither of them is. Otherwise, we would have \(f(u_i) > 0\), which is not possible since \(u_i \notin S\). We must also have \(S_{u_{i+1}} \cap S_{u_{i+2}} = \emptyset\); otherwise, \(f(u_i) > 0\).

Now, as in the proof, let \(u_{i+3},u_{i+4} \in S_{u_{i+1}}\) and \(u_{i+5} \in S_{u_{i+2} }\). Then \(u_{i+5} \notin S\), otherwise \(f(u_{i+5}) >1\), which is not possible. Thus, \(u_{i+5} \notin S\). Now consider \(u_{i+6},u_{i+7}\in S_{u_{i+5}}\).

Note that if any of these five vertices has already been considered, then we would have \(f(u_{i+1}) > 0\), \(f(u_{i+2}) > 0\), or \(f(u_{i+5}) > 0\), which is not possible. Therefore, either both \(u_{i+1}\) and \(u_{i+2}\) are in \(S\), or we obtain five other vertices \(u_{i+3}\), \(u_{i+4}\), \(u_{i+5}\), \(u_{i+6}\), and \(u_{i+7}\) with edges \(u_{i+3}u_{i+4}\), \(u_{i+3}u_{i+1}\), \(u_{i+4}u_{i+1}\), \(u_{i+2}u_{i+5}\), \(u_{i+6}u_{i+5}\), \(u_{i+5}u_{i+7}\), \(u_{i+6}u_{i+7}\).

Assume that there exists an edge between a vertex \(u\) in one branch to another vertex \(v\) in another branch. Let \(U_i\) be the set of vertices in the same branch below the vertex \(u_i\) including \(u_i\). Then \(S \cap U_i \neq \emptyset\).

Then \(u \neq v_k\)(if \(u=v_k\), then \(v_k \in \langle S \cap U_1\rangle)\) or \(v_k \in \langle S \cap U_2\rangle\), which is not possible since \(v_k \in \partial H_G(S)\). Thus, \(u=u_i\) for some \(i\).

Now there are two cases: (1) \(u_i \in S\) and (2) \(u_i \notin S\).
Case (1): If \(u_i \in S\), then as in the previous argument, \(u_i\) is adjacent to some vertex in \(S\) in the same branch (if \(u_j\) is the vertex such that \(u_i, u_{i+1} \in S_{u_j}\), then either both belong to \(S\) or both do not belong to \(S\), since \(u_i \in S\) implies \(u_{i+1} \in S\)). Then, \(u_i \in \langle (S \cap U_{i'} )\cup \{u_{i+1}\}\rangle \subseteq \langle S \setminus \{u_i\}\rangle\) where \(v=u_{i'}\), which is not possible since \(S\) is a Carathéodory set.
Case (2): \(u_i \notin S\). Then, we have three cases, which are shown in Figure 9:

1. \(u_i \notin S\) and \(u_{i+1}, u_{i+2} \in S\) where \(u_{i+1}, u_{i+2} \in S_{u_i}\) as in Figure 9\((i)\). Then, \(v_k \in \langle S \setminus \{u_{i+1}\}\rangle\), which is not possible since \(v_k \in \partial H_G(S)\).

2. \(u_i \notin S\), both \(u_{i+1}\) and \(u_{i+2}\) are not in \(S\) as in Figure 9\((ii)\). Then, \(v_k \in \langle S \setminus (S \cap U_{i+5})\rangle\), which is not possible since \(v_k \in \partial H_G(S)\).

3. \(u_i \notin S\), both \(u_{i+1}\) and \(u_{i+2}\) are not in \(S\) as in Figure 9\((iii)\). Then, \(v_k \in \langle S \setminus (S \cap U_{i+1})\rangle\), which is not possible since \(v_k \in \partial H_G(S)\). We have discussed all the cases since \(u \neq v_k\) and all other vertices in \(G\) must belong to any of these four cases (by the above argument, since \(G\) satisfies \(C(G) = \frac{2n(G)+6}{5}\)). Thus, there is no edge between branches of \(G\).

Thus, If \(G\) be a graph such that \(C(G) =\dfrac{2n(G)+6}{5}\), then \(G \in \mathcal{G}\). ◻

Example 1. Consider a graph \(G\) with \(C(G)<\dfrac{2n(G)+6}{5}\).

Here \(C(G)=3\) but \(n(G)=7\) thus \(\dfrac{2n(G)+6}{5} =4\).

Definition 1. Let \(A\) be the set of vertices in a graph \(G\) that are the centers of an induced claw. A graph \(G\) is almost claw-free if \(A\) is independent, and for every \(x\) in \(A\), the subgraph induced by \(N(x)\) has a dominating set of atmost 2.

Theorem 4. If \(G\) is an almost claw-free graph of order \(n(G)\) then, \[C(G) \leq \dfrac{2n(G)+6}{5}.\]

Proof. Let \(G\) be an almost claw-free graph of order \(n(G)\), and let \(S=\{v_1,v_2,\ldots,v_l\}\) be a Carathéodory set of cardinality \(C(G)\). Let the sequence \(v_{l+1},v_{l+2},\ldots,v_k\), the set \(S_{v_i}\), the vertex \(s_{v_iv_j}\), and the \(f\)-values of \(v_i\) be as described in Theorem 1.

We now describe a procedure that adjusts the values \(f(v)\) of some vertices in \(\{v_1,v_2,\ldots,v_k\}\) such that \(f(v) \geq 1\) for all \(v \in S\) and \(f(v)\geq 0\) without changing the value of \(\sum_{i=1}^k f(v_i)\) as in Theorem 1. Let \(u_1,u_2 \in S_{v_k}\).
Case 1: If \(u_1,u_2 \in S\), then \(S=\{u_1,u_2\}\), and we change \(f(u_1) = f(u_1) + \frac{3}{5}\), \(f(u_2) = f(u_2) + \frac{3}{5}\), and \(f(v_k) = f(v_k) – \frac{6}{5}\) as in Theorem 1
Case 2: If only one of them belongs to \(S\), say \(u_1\), and \(u_2 \notin S\).
Subcase 2.1: If \(u_1u_2\in E(G)\), let \(u_3=s_{u_2u_1}\). Then change \(f(u_3)=f(u_3)+\frac{4}{5}\), \(f(u_1)=f(u_1)+\frac{3}{5}\), \(f(u_2)=f(u_2)-\frac{2}{5}\), and \(f(v_k)=f(v_k)-\frac{5}{5}\) as in Theorem 1.

If \(u_3 \notin S\), then let \(u_4,u_5\in S_{u_3}\). If \(u_1 \in S_{u_3}\), then continue with \(s_{u_3u_1}\), say \(u_4\), by changing \(f(u_3)=f(u_3)-\frac{4}{5}\) and \(f(u_4)=f(u_4)+\frac{4}{5}\).

If \(u_1 \notin S_{u_3}\) and \(u_4u_5 \in E(G)\), then change the \(f\) values of \(u_4,u_5,u_3\) similarly to the proof of Theorem 1.

If \(u_4u_5 \notin E(G)\), then \(u_2,u_3,u_4,u_5\) form a claw, implying that the subgraph induced by \(N(u_3)\) has a dominating set of order at most 2. Then there exists a vertex \(w_3\) which is adjacent to at least 2 of \(u_4,u_5,u_2\) and belongs to \(N(u_3)\). Continue with \(u_4,u_5\) by changing \(f(u_4)=f(u_4)+\frac{4}{5}\), \(f(u_5)=f(u_5)+\frac{4}{5}\), \(f(u_3)=f(u_3)-\frac{6}{5}\), and \(f(w_3)=f(w_3)-\dfrac{2}{5}\).

Now, in general, if \(u_i\) is a vertex not in \(S\) such that \(f(u_i) \geq \frac{6}{5}\) and \(u_{i+1}, u_{i+2} \in S_{u_i}\), if \(u_{i+1}\) or \(u_{i+2}\) is equal to \(w_j\) for some \(w_j\) which has already been considered, say \(u_{i+2} = w_j\), then there exists a vertex \(u_j\) adjacent to \(w_j\), and the subgraph induced by \(N(u_j)\) has a claw which has vertices in \(\{u_1, u_2,\ldots, u_{j+2}\}\) and has a dominating set containing \(w_j\) with cardinality at most 2. Then, \(w_j\) is adjacent to 2 vertices in \(N(u_j)\) which are non-adjacent to each other, say \(u\) and \(v\). If \(u_i, w_j, u, v\) form a claw with center \(w_j\), then \(w_j \in A\).

Since \(u_j \in A\), we get that \(A\) is dependent, a contradiction. Thus, \(u_{i+1} = w_j, u, v, u_i\) is not a claw. Therefore, one of \(u_iv, u_iu\), or \(uv\) belongs to \(E(G)\). Since \(uv \notin E(G)\), we have \(u_iu\) or \(u_iv\) is in \(E(G)\).

Since \(u, v \in \{u_1, u_2,\ldots, u_{i-1}\}\), we then continue with \(u_{i+1}\) by changing \(f(u_i) \longrightarrow f(u_i) – \frac{4}{5}\) and \(f(u_{i+1}) \longrightarrow f(u_{i+1}) + \frac{4}{5}\).

If both of them belong to \(\{u_1,u_2,\ldots,u_{i-1}\}\), then stop and continue with another vertex \(u_j\) with \(f(u_j) \geq \frac{6}{5}\). If only one of them belongs to \(\{u_1,u_2,\ldots,u_{i-1}\}\), then it is enough to consider the vertex which is not equal to any \(u_j\) where \(j<i\), say \(u_{i+1}\), and continue by changing \(f(u_{i+1}) = f(u_{i+1}) + \frac{4}{5}\) and \(f(u_i) = f(u_i) – \frac{4}{5}\).

If \(u_{i+1}u_{i+2}\in E(G)\), then we continue by changing the \(f\)-values similarly as in the proof of Theorem 1.

If \(u_{i+1}u_{i+2} \notin E(G)\), then \(u_{i-1},u_i, u_{i+1},u_{i+2}\) form a claw, and since \(G\) is almost claw-free, there exists \(w_i\in N(u_i)\) such that \(w_i\) is adjacent to 2 vertices in \(u_{i+1},u_{i+2},u_{i-1}\), say \(u\) and \(v\).

If \(w_i=w_j\) for some \(j<i\), then there exists a vertex \(u_j\) such that the subgraph induced by \(N(u_j)\) contains a claw of vertices in \({u_1,u_2,\ldots,u_{i-1}}\), and \(w_j\) dominates at least 2 vertices in the claw, say \(u',v'\). Then, \(u',v',w_i,u_i\) is not a claw; otherwise, \(A\) is dependent, which is not possible. Since \(u'v' \notin E(G)\), this implies that either \(u_iu'\) or \(u_iv'\) belongs to \(E(G)\); let it be \(u'\). Then we continue with \(s_{u_iu'}\) by changing \(f(u_i) \longrightarrow f(u_i)-\dfrac{4}{5}\), and \(f(s_{u_iu'}) \longrightarrow f(s_{u_iu'})+\dfrac{4}{5}\).

If \(w_i=u_r\) where \(u_r,u_i\in S_{u_{i-1}}\) and \(f(u_r)=\dfrac{2}{5}\), then change \(f(u_i) \longrightarrow f(u_i)-\dfrac{6}{5}\), \(f(u_r)\longrightarrow f(u_r)-\dfrac{2}{5}\), \(f(u_{i+1})\longrightarrow f(u_{i+1})+\dfrac{4}{5}\), \(f(u_{i+2})\longrightarrow f(u_{i+2})+\dfrac{4}{5}\) and continue.

If \(w_i=u_r\) where \(u_r,u_i\in S_{u_{i-1}}\) and \(f(u_r)=0\), then \(S_{u_r}\cap S_{u_i}=\emptyset\). Since \(f(u_i)\geq \dfrac{6}{5}\), this implies \(S_{u_r}\) contains vertices with larger indices in \({v_1,v_2,\ldots,v_k}\) than \(u_{i+1},u_{i+2}\). Since \(u_ru_{i+1}\) or \(u_ru_{i+2}\) is in \(E(G)\), say \(u_{i+1}u_r \in E(G)\), this implies that vertices in \(S_{u_r}\) have smaller indices than \(u_{i+1}\) in \(\{v_1,v_2,\ldots,v_k\}\), a contradiction.

If \(w_i=u_j\) for some \(j<i\) and \(u_j \notin S_{u_{i-1}}\), then \(u',v',w_i,u_{j-1}\) is not a claw since \(u_iw_i \in E(G)\) and \(A\) is independent. Thus, \(u'u_{j-1}\) or \(v'u_{j-1}\) belongs to \(E(G)\). Let \(u'u_{j-1}\in E(G)\), then \(u' \in \langle u_j, u_{j-1}\rangle\). Then continue by changing \(f(u_i)\longrightarrow f(u_i)-\dfrac{4}{5}\) and \(f(v')\longrightarrow f(v') +\dfrac{4}{5}\).

Similarly, if \(v'u_{j-1}\in E(G)\), continue by changing \(f(u_i)\longrightarrow f(u_i)-\dfrac{4}{5}\) and \(f(u')\longrightarrow f(u') +\dfrac{4}{5}\).

If \(w_i\neq w_j\) and \(w_i\neq u_j\) for \(j<i\), then continue by changing \(f(u_{i+1})=f(u_{i+1})+\dfrac{4}{5}\), \(f(u_{i+2})=f(u_{i+2})+\dfrac{4}{5}\), \(f(u_i)=f(u_i)-\dfrac{6}{5}\), and \(f(w_i)=f(w_i)-\dfrac{2}{5}\).
Subcase 2.2: \(u_1u_2 \notin E(G)\). Continue the process as in case a by changing \(f(u_1) \longrightarrow f(u_1) +\dfrac{3}{5}\), \(f(u_2)\longrightarrow f(u_2) +\dfrac{4}{5}\), and \(f(v_k) \longrightarrow f(v_k)- \dfrac{7}{5}\).
Case 3: Both \(u_1\) and \(u_2\) are not in \(S\). Continue the process similar to the above cases by changing \(f(u_1) \longrightarrow f(u_1)+ \dfrac{4}{5}\), \(f(u_2) \longrightarrow f(u_2)+\dfrac{4}{5}\), and \(f(v_k) \longrightarrow f(v_k)-\dfrac{8}{5}\).

Continuing like this, we get a sequence that contains \(S\) and \(v_k \in \langle \{u_1,u_2,\ldots,u_s\}\rangle\) such that \(f(v) \geq 1\) for all \(v\) in \(S\) and \(f(v)\geq0\) for all \(v\) in \(V(G)\) without changing the sum \(\sum_{i=1}^n f(v_i)\). Thus, we get \(C(G) \leq \dfrac{2n(G)+6}{5}\). ◻