In this paper, we give a relationship between the covering number of a simple graph \(G\), \(\beta(G)\), and a new parameter associated to \(G\), which is called 2-degree-packing number of \(G\), \(\nu_2(G)\). We prove that \[\lceil \nu_{2}(G)/2\rceil\leq\beta(G)\leq\nu_2(G)-1,\] for any simple graph \(G\), with \(|E(G)|>\nu_2(G)\). Also, we give a characterization of connected graphs that attain the equalities.
In this paper, we consider finite undirected simple graphs. For the terminology, notation and missing basic definitions related to graphs we refer the reader to [1]. Let \(G\) be a graph. We call \(V(G)\) the vertex set of \(G\) and we call \(E(G)\) the edge set of \(G\). For a subset \(A\subseteq V(G)\), \(G[A]\) denotes the subgraph of \(G\) which is induced by the vertex set \(A\). Likewise, for a subset \(R\subseteq E(G)\), \(G[R]\) denotes the subgraph of \(G\) which is induced by the edge set \(R\). The distance between two vertices \(u\) and \(v\) in a graph \(G\) is the number \(d_G(u,v)\) of edges in any shortest \(u-v\) path in \(G\) that joins \(u\) and \(v\); if \(u\) and \(v\) are not joined in \(G\), then \(d_G(u,v)=\infty\). The neighborhood of a vertex \(u\in V(G)\), denoted by \(N_G(u)\), is the subset of \(V(G)\) adjacent to \(u\) in \(G\). The set of edges incident to \(u \in V(G)\) is denoted by \(\mathcal{L}_u\). Hence, the degree of \(u\), denoted by \(\deg(u)\), is \(\deg(x)=|\mathcal{L}_u|\). The minimum and maximum degree of a graph \(G\) is denoted by \(\delta(G)\) and \(\Delta(G)\), respectively. Let \(H\) be a subgraph of \(G\), the restricted degree of a vertex \(u\in V(H)\), denoted by \(\deg_H(u)\), is defined as \(\deg_H(u)=|\mathcal{L}_u\cap E(H)|\).
An independent set of a graph \(G\) is a subset \(I\subseteq V(G)\) such that any two vertices of \(I\) are not adjacent. The independence number of \(G\), denoted by \(\alpha(G)\), is the maximum order of an independent set. A vertex cover of a graph \(G\) is a subset \(T\subseteq V(G)\) such that all edges of \(G\) has at least one end in \(T\). The covering number of \(G\), denoted by \(\beta(G)\), is the minimum order of a vertex cover of \(G\). This parameter is well known and intensively studied in a more general context and with different names, see for example [2-8].
A k-degree-packing set of a graph \(G\) (\(k\leq\Delta(G)\)), is a subset \(R\subseteq E(G)\) such that \(\Delta(G[R])\leq k\). The k-degree-packing number of \(G\), denoted by \(\nu_k(G)\), is the maximum order of a \(k\)-degree-packing set of \(G\). We are interested in this new parameter when \(k=2\), since \(k=1\) is the matching number of \(G\). Hence, the matching number is a particular case of the \(k\)-degree-packing number of a graph when \(k=1\).
The 2-degree-packing number is studied in [5, 9-13] in a more general context, but with a different name, as 2-packing number. The definition of 2-packing in graphs have a different meaning: A set \(X\subseteq V(G)\) is called a 2-packing if \(d_G(u,v)>2\) for any different vertices \(u\) and \(v\) of \(X\), that is, the 2-packing is a subset \(X\subseteq V(G)\) in which all the vertices are in distance at least 3 from each other, see for example [14]. Therefore, we called 2-degree-packing instead of 2-packing only applied for graphs.
As a particular case, Araujo-Pardo el al. proved in [5] any simple graph \(G\) satisfies:
\[\label{des:inf} \lceil \nu_{2}(G)/2\rceil\leq\beta(G).\tag{1}\]
In this paper, we prove that for any simple graph \(G\), with \(|E(G)|>\nu_2(G)\), is such that: \[\label{des:sup} \beta(G)\leq\nu_2(G)-1.\tag{2}\] Hence, by Equations (1) and (2), we have:
Theorem 1. If \(G\) is a simple connected graph with \(|E(G)|>\nu_2(G)\), then \[\lceil \nu_{2}(G)/2\rceil \leq\beta(G)\leq\nu_2(G)-1.\]
In this paper, we give a characterization of simple connected graphs that attain the upper and lower bounds in Theorem 1.
Only connected graphs with \(|E(G)|>\nu_2(G)\) are considered, since \(|E(G)|=\nu_2(G)\) if and only if \(\Delta(G)\leq2\). Moreover, we may assume \(\nu_2(G)\geq4\), since otherwise Araujo-Pardo et al. in [5] proved:
Proposition 2. [5]Let \(G\) be a simple graph with \(|E(G)|>\nu_2(G)\), then \(\nu_2(G)=2\) if and only if \(\beta(G)=1\).
Proposition 3. [5]Let \(G\) be a simple connected graph with \(|E(G)|>\nu_2(G)\). If \(\nu_2(G)=3\), then \(\beta(G)=2\).
If a graph \(G\) satisfies the hypothesis of Proposition 2 with \(\nu(G)=2\), then \(G\) is the complete bipartite graph of the form \(K_{1,m}\), with \(m\geq2\). If the graph \(G\) satisfies the hypothesis of Proposition 3, then \(G\) is one of the graphs shown in Figure 1 (see [5]).
The next proposition shows some simple consequences of the definitions given previously. Also, some results are well known.
Proposition 4.
If \(R\) is a maximum 2-degree-packing of a graph \(G\), then the components of \(G[R]\) are either cycles or paths.
If \(G\) is either a cycle or a path, both of even length, and \(T\) is a minimum vertex cover of \(G\), then \(T\) is an independent set.
If \(G\) is cycle of length odd and \(T\) is a minimum vertex cover of \(G\), then there exists an unique \(u\in T\) such that \(T\setminus\{u\}\) is an independent set. On the other hand, if \(G\) is a path of length odd, then either there exists an unique \(u\in T\) such that \(T\setminus\{u\}\) is an independent set or \(T\) is an independent and \(\deg_T(u)=1\).
If \(G\) is either a path or a cycle of length \(k\), then \(\beta(G)=\lceil \frac{k}{2}\rceil\).
\(\beta(K_n)=\nu_2(K_n)-1\).
Remark 1. Let \(R\) be a maximum 2-degree-packing of a simple graph \(G\). It is clear that the number of components of \(G[R]\) is at most \(\nu_2(G)-1\). Moreover, if \(T\) is a minimum vertex cover of \(G[R]\), then \(\beta(G)\leq k+p\), where \(k\) is the number of components of \(G[R]\) of a single edge, and \(p=|\{v\in V(G[R]): \deg_R(v)=2\}|\). Hence, \(\beta(G)\leq k+p\leq\nu_2(G)\).
Proposition 5. If \(G\) is a simple graph with \(|E(G)|>\nu_2(G)\), then \(\beta(G)\leq\nu_2(G)-1\).
Proof. By Remark 1, we have \(\beta(G)\leq k+p\leq\nu_2(G)\). It is not hard to see, if \(k\geq1\), then \(\beta(G)\leq\nu_2(G)-1\). On the other hand, if \(k=0\), then any component of \(G[R]\) is a cycle, since if \(G[R]\) has a path (of length at least 2) as a component, then \(\beta(G)\leq\nu_2(G)-1\). Hence \(p=\nu_2(G)\). We may assume \(V(G[R])=V(G)\), since otherwise if \(u\in V(G)\setminus V(G[R])\) and \(e_u=uv\in E(G)\setminus R\), where \(v\in V(G[R])\), then the following set \((R\setminus \{e_v\})\cup\{e_u\}\), where \(e_v\in R\), is incident to \(v\), is a maximum 2-degree-packing of \(G\) with a path as a component, which implies that \(\beta(G)\leq\nu_2(G)-1\). Therefore \(\{v\in V(G[R]): \deg_R(v)=2\}\setminus\{u\}\), for any \(u\in V(G[R])\), is a vertex cover of \(G\), implying that \(\beta(G)\leq\nu_2(G)-1\). ◻
Hence, we have:
Theorem 6. If \(G\) is a simple graph with \(|E(G)|>\nu_2(G)\), then \[\lceil \nu_{2}(G)/2\rceil \leq\beta(G)\leq\nu_2(G)-1.\]
We introduce some terminology in order to simplify the description of simple connected graphs \(G\) such that \(\beta(G)=\nu_2(G)-1\).
As a particular case, Araujo-Pardo el al. proved in [5] the following:
Proposition 1. [5]If \(G\) is a simple graph \(G\) with \(\nu_2(G)=4\) and \(|E(G)|>4\), then \(\beta(G)\leq3\).
Also, in this paper [5], the authors give all the connected graphs with \(\nu_2(G)=4\) and \(\beta(G)=3\) and they are certain subgraphs of the graphs given in Figure 2. Hence, by Proposition 7, we may assume \(\nu_2(G)\geq5\).
In [15] Vázquez-Ávila constructed the graph \(T_{s,t}\), with \(s\geq1\) and \(t\geq2\), (see Figure 2 \((a)\)), where: \[\begin{aligned} V(T_{s,t})&=&\{p_1,\ldots,p_{s}\}\cup\{q_1,\ldots,q_{s}\}\cup\{w_1,\ldots,w_t\},\\ E(T_{s,t})&=&\{p_iq_i:i=1,\ldots,s\}\cup\{vp_i:i=1,\ldots,s\}\cup\{vw_i:i=1,\ldots,t\}. \end{aligned}\]
Let \(G_{s,t}\), with \(s\ge1\) and \(t\geq2\), be the graph constructed from \(T_{s,t}\), where (see Figure 3 \((b)\)): \[\begin{aligned} V(G_{s,t})&=&V(T_{s,t}),\\ E(G_{s,t})&=&E(T_{s,t})\cup\{vq_i:i=1,\ldots,s\}. \end{aligned}\]
As a consequence of Corollary 2.1 given in [15], we have:
Corollary 8. [15] \(\beta(T_{s,t})=\nu_2(T_{s,t})-1=s+1\), for every \(s\geq1\) and \(t\geq2\).
Since the graph \(T_{s,t}\) is a spanning graph of \(G_{s,t}\) and any minimum vertex cover of \(T_{s,t}\) is a vertex covering of \(G_{s,t}\), then:
Corollary 9. \(\beta(G_{s,t})=\nu_2(G_{s,t})-1=s+1\), for every \(s\geq1\) and \(t\geq2\).
Corollary 10. If \(T_{s,t}\) is a spanning subgraph of a graph \(G\) and \(G\) is a spanning subgraph of \(G_{s,t}\), then \(\beta(G)=\nu_2(G)-1=s+1\).
Let \(G\) be a simple graph with \(|E(G)|>\nu_2(G)\) and \(R\) be a maximum 2-degree-packing of \(G\). Let \(R_1,\ldots,R_s,R_{s+1},\ldots,R_k\) be the components of \(G[R]\), where \(|R_i|=1\), for \(i=1,\ldots,s\) and \(|R_j|>1\), for \(j=s+1,\ldots,k\). It is not difficult to see that \(s\leq\nu_2(G)-2\). If \(s=\nu_2(G)-2\), then \(k=\nu_2(G)-1\) and \(|E(G[R_k])|=2\). Hence, any edge from \(E(G)\setminus E(G[R])\) is incident with the unique vertex \(v\in V(G[R_k])\) with \(\deg_R(v)=2\). Hence, if \(R_i=p_iq_i\), for \(i=1,\ldots,s\), \(R_k=w_0vw_1\), and \(V(G)\setminus V(G[R])=\{w_3,\ldots,w_t\}\) (an independent set), if \(t\geq3\), then \(T_{s,t}\) is a spanning subgraph of a graph \(G\) and \(G\) is a spanning subgraph of \(G_{s,t}\). Therefore, \(\beta(G)=\nu_2(G)-1=s+1\).
Let \(R_1,\ldots,R_s,R_{s+1},\ldots,R_k\) be the components of a simple connected graph \(G\), with \(k\) as small as possible, where \(|R_i|=1\), for \(i=1,\ldots,s\) and \(|R_j|>1\), for \(j=s+1,\ldots,k\). It is clear that \(\beta(G)=s+\beta(H)\) and \(\nu_2(G)=s+\nu_2(H)\), where \(H\) is given by \[\begin{aligned} V(H)&=&V(G)\setminus\bigcup_{i=1}^su_i,\\\ E(H)&=&E(G)\setminus\bigcup_{i=1}^s\mathcal{L}_{u_i}, \end{aligned}\] where \(u_i\in V(G[R_i])\), for \(i=1,\ldots,s\), and deleting those vertices of degree 0 (if any). Therefore, it may be assumed that any simple connected graph \(G\), with \(|E(G)|>\nu_2(G)\), has a maximum 2-degree-packing \(R\) of \(G\), where each component of \(G[R]\) has at least 2 edges; and as a consequence, the set \(T=\{u\in V(G[R]):\deg_{G[R]}(u)=2\}\) is a vertex cover of \(G\).
Let \(K_n^1\) be the simple connected graph, where \[\begin{aligned} V(K_n^1)&=&\{x_1,\ldots,x_n\}\cup\{u\},\\ E(K_n^1)&=&\{x_ix_j: 1\leq i<j\leq n\}\cup\{ux_1\}. \end{aligned}\]
The graph \(K_n^1\) is the complete graph of \(n\) vertices with one extra edge attached. It is easy to see that \(\beta(K_n^1)=\nu_2(K_n^1)-1=n-1\).
Proposition 11. Let \(G\) be a simple graph with \(|E(G)|>\nu_2(G)\), \(\nu_2(G)\geq5\) and \(\beta(G)=\nu_2(G)-1\). If \(R\) is a maximum 2-degree-packing of \(G\) with \(V(G[R])=V(G)\), then either \(G\) is the complete graph \(K_{\nu_2}\) or \(G\) is \(K_{\nu_2}^1\), where \(\nu_2=\nu_2(G)\).
Proof. Let \(R\) be a maximum 2-degree-packing of \(G\) with \(V(G[R])=V(G)\) and \(R_1,\ldots,R_k\) be the components of \(G[R]\) with \(k\) as small as possible. Then:
Case(i) If \(k=1\), then \(G[R]\) is either a path or a cycle. Suppose that \(R=u_0u_1\cdots u_{\nu_2-1}u_0\) is a cycle: If there are two non-adjacent vertices \(u_i,u_j\in V(G[R])=V(G)\), then \(T=V(G[R])\setminus\{u_i,u_j\}\) is a vertex cover of \(G\) of cardinality \(\nu_2(G)-2\), which is a contradiction. Therefore, any different pair of vertices of \(G\) are adjacent. Hence, the graph \(G\) is the complete graph with \(\nu_2(G)\) vertices.
On the other hand, if \(R=u_0u_1\cdots u_{\nu_2}\) is a path, then \(T=\{u_1,\ldots,u_{\nu_2-1}\}\) is a minimum vertex cover of \(G\). We may assume either \(u_0u_j\in E(G)\) or \(u_{\nu_2}u_j\in E(G)\), for all \(u_j\in T^*=T\setminus\{u_1,u_{\nu_2-1}\}\), since otherwise, \(T\setminus\{u_j\}\) is a vertex cover of \(G\) of cardinality \(\nu_2(G)-2\), which is a contradiction. Without loss of generality, suppose \(u_0u_j\in E(G)\), for all \(u_j\in T^*=T\setminus\{u_1,u_{\nu_2-1}\}\). If \(u_ju_{\nu_2}\in E(G)\), for some \(u_j\in T^*\), then \(R^*=(R\setminus\{u_ju_{j+1}\})\cup\left\{u_ju_{\nu_2},u_0u_{j+1}\right\}\) (since \(\nu_2(G)\geq5\)) is a 2-degree-packing of size \(\nu_2(G)+1\), a contradiction. Hence \(u_ju_{\nu_2}\not\in E(G)\), for all \(u_j\in T^*\), which implies that \(\deg(u_{\nu_2})=1\). On the other hand, if there are two vertices \(u_i, u_j\in T^*\) non-adjacents, then \(\left(T\setminus\{u_i,u_j\}\right)\cup\{u_0\}\) is a vertex cover of \(G\) of size \(\nu_2(G)-2\), which is a contradiction. Also, \(u_1u_j\in E(G)\) and \(u_ju_{\nu_2-1}\in E(G)\), for all \(u_j\in T^*\), otherwise there exists \(u_j\in T^*\) such that either \((T\setminus\{u_1,u_j\})\cup\{u_0\}\) or \((T\setminus\{u_j,u_{\nu_2-1}\})\cup\{u_0\}\) is a vertex cover of \(G\) of size \(\nu_2(G)-2\), which is a contradiction. Therefore, the graphs \(G\) is the graph \(K_{\nu_2}^1\).
Case(ii) Suppose \(k\geq2\) and \(T=\{v\in V(G[R]): \deg_R(v)=2\}\). If there is at least two components as a paths (of length at least 2), say \(R_1\) and \(R_2\), then \[\begin{aligned} \beta(G)\leq|T|&\leq&(|E(R_1)|-1)+(|E(R_2)|-1)+\sum_{i=3}^k|E(R_i)|\\ &=&\sum_{i=1}^{k}|E(R_i)|-2=\nu_2(G)-2, \end{aligned}\] which is a contradiction. Hence, there are at most one component as a path of length at least 2. Let \(u\in V(R_1)\) such that \(\deg_R(u)=1\), then \(\deg_G(u)=1\), otherwise \(T\setminus\{v\}\), where \(u\) and \(v\) are adjacent, is a vertex cover of \(G\) of size \(\nu(G)-1\), which is a contradiction. Moreover, if \(u\in V(R_1)\) such that \(\deg_{R_1}(u)=2\) and there is \(v\in V(G)\setminus V(R_1)\) such that \(u\) and \(v\) are non-adjacents, then \(T\setminus\{v\}\) is a vertex cover of \(G\) of size \(\nu(G)-2\), a contradiction. Therefore \(k=1\), which is a contradiction.
◻
Theorem 12. Let \(G\) be a simple connected graph with \(\nu_2(G)\geq5\) and \(\beta(G)=\nu_2(G)-1\). Then either \(G\) is the complete graph \(K_{\nu_2}\) or \(G\) is \(K_{\nu_2}^1\), where \(\nu_2=\nu_2(G)\).
Proof. Let \(R\) be a maximum 2-degree-packing of \(G\) and \(I=V(G)\setminus V(G[R])\) (independent set of vertices). Then \(I\neq\emptyset\), by the Proposition 6.
Case(i) Suppose \(G[R]\) is the complete graph of \(\nu_2(G)\) vertices. We claim, if \(u\in I\), then \(\deg(u)=1\). To verify the claim, we suppose on the contrary, \(u\) is incident to at least two vertices of \(V(G[R])\), say \(v\) and \(w\). If \(V(G[R])=\{u_1,\ldots,u_{\nu_2}\}\), then without loss of generality \(u_1=v\) and \(u_j=w\), for some \(j\in\{2,\ldots,\nu_2\}\) (\(G[R]\) is a complete graph). Then \[(R\setminus\{u_1u_{\nu_2},u_{j-1}u_j\})\cup\{uu_1,uu_j,u_{j-1}u_{\nu_2}\}\] is a 2-degree-packing of \(G\) of size \(\nu_2(G)+1\), which is a contradiction. Hence, if \(u\in I\), then \(\deg_G(u)=1\).
On the other hand, if \(|I|>1\), let \(u,v\in I\). Without loss of generality, suppose \(u\) is adjacent to \(u_1\) and \(v\) is adjacent to \(u_j\), for some \(j\in\{2,\ldots,\nu_2\}\). Since \(G[R]\) is a complete graph, then \[(R\setminus\{u_1u_{\nu_2},u_{j-1}u_j\})\cup\{uu_1,u_{j-1}u_{\nu_2},vu_j\}\] is a 2-degree-packing of size \(\nu_2(G)+1\), which is a contradiction. Also, if \(u\) and \(v\) are adjacent to \(u_1\), then \[(R\setminus\{u_1u_2,u_1u_{\nu_2}\})\cup\{uu_1,vu_1,u_2u_{\nu_2}\}\]is a 2-degree-packing of size \(\nu_2(G)+1\), which is contradiction. Hence, \(I=\{u\}\) with \(\deg(u)=1\), which implies that the graph \(G\) is \(K_{\nu_2}^1\).
Case(ii) Suppose \(G[R]\) is the graph \(K_{\nu_2}^1\). Let \(v\in V(G)\) such that the \(G[R]-v\) is the complete graph of size \(\nu_2(G)\). If \(u\in I\) is such that \(uw\in E(G)\), whit \(w\in V(G[R])\), then, there exists a 2-degree-packing of \(G\) of size \(\nu_2(G)+1\) (see proof of Proposition 6, which is a contradiction. Then \(uw\not\in E(G)\), for all \(w\in V(G[R])\cup\{v\}\), which implies that \(G\) is a disconnected graph, unless \(I=\emptyset\), and the theorem holds by Proposition 6.
◻
We introduce some terminology and results in order to simplify the description of the simple connected graphs \(G\) which satisfy \(\beta(G)=\lceil{\nu_2(G)/2\rceil}\).
Proposition 13. Let \(G\) be a simple connected graph and \(R\) be a maximum 2-degree-packing of \(G\).
If \(\nu_2(G)\) is an even integer and \(\beta(G)=\displaystyle\frac{\nu_2(G)}{2}\), then the components of \(R\) has even length.
If \(\nu_2(G)\) is an odd integer and \(\beta(G)=\displaystyle\frac{\nu_2(G)+1}{2}\), then there is an unique component of \(R\) of odd length.
Proof. To prove the item 1, let \(R\) be a maximum 2-degree-packing of \(G\) and let \(R_1,\ldots,R_k\) be the components of \(G[R]\). If \(T\) is a minimum vertex cover of \(G\), then \[\frac{\nu_2(G)}{2}=\beta(G)=|T|=\sum_{i=1}^{k}|T\cap V(R_i)|\geq\sum_{i=1}^{k}\beta(R_i)=\sum_{i=1}^{k}\lceil{\nu_2(R_i)/2\rceil}.\]
Hence, if \(R_1\) have a odd number of edges, then\[\sum_{i=1}^{k}\lceil{\nu_2(R_i)/2\rceil}=\frac{\nu_2(R_1)+1}{2}+\sum_{i=2}^{k}\lceil{\nu_2(R_i)/2\rceil}\geq\frac{1}{2}+\sum_{i=1}^{k}\frac{\nu_2(R_i)}{2}=\frac{1}{2}+\frac{\nu_2(G)}{2},\]which is a contradiction. Therefore, each component of \(G[R]\) has an even number of edges. To prove the item 2 we use an analogous argument. ◻
Let \(A\) and \(B\) be two sets of vertices. The complete graph whose set of vertices is \(A\) is denoted by \(K_A\). The graph whose set of vertices is \(A\cup B\) and whose set of edges is \(\{ab:a\in A, b\in B\}\) is denoted by \(K_{A,B}\). On the other hand, let \(k\geq3\) be a positive integer. The cycle of length \(k\) and the path of length \(k\) are denoted by \(C^k\) and \(P^k\), respectively.
If \(A\) and \(B\) are two sets of vertices from \(V(C^k)\) and \(V(P^k)\) (not necessarily disjoint) and \(I\) be an independent set of vertices different from \(V(C^k)\) and \(V(P^k)\) then \(C_{A,B,I}^k=(V(C_{A,B,I}^k),E(C_{A,B,I}^k))\) and \(P_{A,B,I}^k=(V(P_{A,B,I}^k),E(P_{A,B,I}^k))\) are denoted to be the graphs with \(V(C_{A,B,I}^k)=V(C^k)\cup I\) and \(V(P_{A,B,I}^k)=V(P^k)\cup I\), respectively, and \(E(C_{A,B,I}^k)=E(C^k)\cup E(K_A)\cup E(K_{A,B})\cup E(K_{A,I})\) and \(E(P_{A,B,I}^k)=E(P^k)\cup E(K_A)\cup E(K_{A,B})\cup E(K_{A,I})\), respectively. In an analogous way, we denote by \(C_I^k\) to be the graph with \(V(C_I^k)=V(C^k)\cup I\) and \(E(C_I^k)=E(C^k)\) and we denote by \(P_I^k\) to be the graph with \(V(P_I^k)=V(P^k)\cup I\) and \(E(P_I^k)=E(P^k)\). In Figure 4 are depicted the graphs \(C^k_I\) and \(P^k_I\), where \(|I|=i\).
We define \(\mathcal{C}_{A,B,I}^k\) to be the family of connected graphs \(G\) such that \(C_I^k\) is a subgraph of \(G\) and \(G\) is a subgraph of \(C_{A,B,I}^k\). Similarly, we define \(\mathcal{P}_{A,B,I}^k\) to be the family of connected graphs \(G\) such that \(P_I^k\) is a subgraph of \(G\) and \(G\) is a subgraph of \(P_{A,B,I}^k\).
That is \[\mathcal{C}_{A,B,I}^k=\{G: C_I^k\subseteq G\subseteq C_{A,B,I}^k\mbox{ where $G$ is a connected graph}\}\] \[\mathcal{P}_{A,B,I}^k=\{G: P_I^k\subseteq G\subseteq P_{A,B,I}^k\mbox{ where $G$ is a connected graph}\}\]
Proposition 14. Let \(k\geq4\) be an even integer, \(T\) be a minimum vertex cover of \(C^k\) and \(I\) be an independent set of vertices different from \(V(C^k)\). If \(\hat{T}=V(C^k)\setminus T\) and \(G\in \mathcal{C}_{T,\hat{T},I}^k\), then \(\beta(G)=\frac{k}{2}\) and \(\nu_2(G)=k\).
Proof. It is clear that, if \(G\in \mathcal{C}_{T,\hat{T},I}^k\), then \(\beta(G)=\frac{k}{2}\). On the other hand, since \(C^k\) is a 2-degree-packing of \(G\), then \(\nu_2(G)\geq k\). Moreover, since \(\displaystyle\left\lceil\nu_2(G)/2\right\rceil\leq\beta(G)=\frac{k}{2}\), then \(\nu_2(G)=k\). ◻
In Figure 5 are depicted the graphs \(C_{T,\hat{T},I}^6\) and \(P_{T,\hat{T},I}^6\), where \(T=\{x_,x_4,x_6\}\) and \(I=\{c_1,c_2\}\).
Corollary 15. Let \(k\geq4\) be an even integer, \(T\) be a minimum vertex cover of \(P^k\) and \(I\) be an independent set of vertices different from \(V(P^k)\). If \(\hat{T}=V(P^k)\setminus T\) and \(G\in \mathcal{P}_{T,\hat{T},I}^k\), then \(\beta(G)=\frac{k}{2}\) and \(\nu_2(G)=k\).
For instance, any connected graph \(G\) containing the subgraph of Figure 4 (a) and whose supergraph is the graph of Figure 5 (a) is such that \(\tau=3\) and \(\nu_2=6\).
Now, let \(\mathcal{\hat{C}}_{A,B,I}^k\) be the family of simple connected graphs \(G\) with \(\nu_2(G)=k\), such that \(C_I^k\) is a subgraph of \(G\) and \(G\) is a subgraph of \(C_{A,B,I}^k\). Similarly, let \(\mathcal{\hat{P}}_{A,B,I}^k\) be the family of simple connected graphs \(G\) with \(\nu_2(G)=k\) such that \(P_I^k\) is a subgraph of \(G\) and \(G\) is a subgraph of \(P_{A,B,I}^k\). That is \[\mathcal{\hat{C}}_{A,B,I}^k=\{G: C_I^k\subseteq G\subseteq C_{A,B,I}^k\mbox{ where $G$ is connected and $\nu_2(G)=k$}\},\] \[\mathcal{\hat{P}}_{A,B,I}^k=\{G: P_I^k\subseteq G\subseteq P_{A,B,I}^k\mbox{ where $G$ is connected and $\nu_2(G)=k$}\}.\]
Hence if \(k\geq4\) is an even integer, \(T\) is a minimum vertex cover of either \(C^k\) or \(P^k\), and \(I\) is an independent set different from either \(V(C^k)\) or \(V(P^k)\), then by Proposition 8 and Corollary 4, we have \[\mathcal{\hat{C}}_{T,\hat{T},I}^k=\mathcal{C}_{T,\hat{T},I}^k\mbox{ and }\mathcal{\hat{P}}_{T,\hat{T},I}^k=\mathcal{P}_{T,\hat{T},I}^k.\]
However, if \(k\geq5\) is an odd integer, \(T\) is a minimum vertex cover of either \(C^k\) or \(P^k\) and \(I\) is an independent set different from either \(V(C^k)\) or \(V(P^k)\), then \[\mathcal{\hat{C}}_{T,\hat{T},I}^k\neq\mathcal{C}_{T,\hat{T},I}^k\mbox{ and }\mathcal{\hat{P}}_{T,\hat{T},I}^k\neq\mathcal{P}_{T,\hat{T},I}^k.\] To see this, let \(R\) be the cycle of length \(k\) and \(u,v\in T\) adjacent. Hence, if \(G\) is such that \(V(G)=V(C^k)\cup\{w\}\), where \(w\in I\) and \(E(G)=E(C^k)\cup\{uw,vw\}\), then \(G\in \mathcal{C}^k_{T,\hat{T},I}\). However, it is clear that \(\nu_2(G)=k+1\), which implies that \(G\not\in\mathcal{\hat{C}}^k_{T,\hat{T},T}\). A similar argument is used to prove that \(\mathcal{\hat{P}}_{T,\hat{T},I}^k\neq\mathcal{P}_{T,\hat{T},I}^k\).
Proposition 16. Let \(k\geq5\) be an odd integer, \(T\) be a minimum vertex cover of \(C^k\) and \(I\) be an independent set of vertices different from \(V(C^k)\). If \(\hat{T}=V(C^k)\setminus T\) and \(G\in \mathcal{\hat{C}}_{T,\hat{T},I}^k\), then \(\beta(G)=\frac{k+1}{2}\).
Proof. It is clear that
\[\frac{k+1}{2}=\displaystyle\left\lceil\nu_2(C^k_I)/2\right\rceil\leq\displaystyle\left\lceil\nu_2(G)/2\right\rceil\leq\beta(G)\leq|T|=\frac{k+1}{2},\]which implies that \(\beta(G)=\frac{k+1}{2}\). ◻
Corollary 17. Let \(k\geq5\) be an odd integer, \(T\) be a minimum vertex cover of \(P^k\) and \(I\) be an independent set of vertices different from \(V(P^k)\). If \(\hat{T}=V(P^k)\setminus T\) and \(G\in \mathcal{\hat{P}}_{T,\hat{T},I}^k\), then \(\beta(G)=\frac{k+1}{2}\).
Proposition 18. Let \(G\) be a connected graph with \(|E(G)|>\nu_2(G)\) and \(R_1,\ldots, R_k\) be the components of a maximum 2-degree-packing of \(G\). If \(\beta(G)=\left\lceil\nu_2(G)/2\right\rceil\), then \(\beta(G)=\displaystyle\sum_{i=1}^k\beta(R_i)\).
Proof. Let \(R\) be a maximum 2-degree-packing of \(G\) and \(R_1,\ldots,R_k\) be the components of \(G[R]\). Since \(R_i\) is a cycle or a path of length \(\nu_2(R_i)\), then \(\beta(R_i)=\left\lceil\nu_2(R_i)/2\right\rceil\), for \(i=1,\ldots,k\). If \(\beta(G)=\left\lceil\nu_2(G)/2\right\rceil\), then by Proposition 7, we have \[\left\lceil\nu_2(G)/2\right\rceil=\beta(G)\geq\sum_{i=1}^k\beta(R_i)=\sum_{i=1}^k\left\lceil\nu_2(R_i)/2\right\rceil=\left\lceil\nu_2(G)/2\right\rceil.\]Therefore \(\beta(G)=\displaystyle\sum_{i=1}^k\beta(R_i)\). ◻
By Proposition 13 and Proposition 18, we have:
Theorem 19. Let \(G\) be a connected graph with \(|E(G)|>\nu_2(G)\) and \(R_1,\ldots, R_k\) be the components of a maximum 2-degree-packing of \(G\).
Then: \(\beta(G)=\left\lceil\nu_2(G)/2\right\rceil\), if and only if, \(\beta(G)=\displaystyle\sum_{i=1}^k\beta(R_i)\), being:
\(|R_i|\) an even integer, for \(i=1,\ldots,k\), if \(\nu_2(G)\) an even number.
\(|R_1|\) is an odd integer and \(|R_i|\) is an even integer, for \(i=2,\ldots,k\), if \(\nu_2(G)\) is an odd number.
Proposition 20. Let \(G\) be a simple connected graph with \(\nu_2(G)\geq4\), \(|E(G)|>\nu_2(G)\) and \(R_1,\ldots, R_k\) be the components of a maximum 2-degree-packing \(R\) of \(G\), with \(k\) as small as possible. If \(\beta(G)=\left\lceil\nu_2(G)/2\right\rceil\), then \(I=I_1\cup\cdots\cup I_k=V(G)\setminus V(G[R])\), where either \(I_i=\emptyset\) or for every \(u\in I_i\) satisfies \(N(u)\subseteq V(R_i)\), for \(i=1,\ldots,k\).
Proof. Suppose there exists \(u\in I\), \(w_i\in V(R_i)\) and \(w_j\in V(R_j)\), for some \(i\neq j\in\{1,\ldots,k\}\), such that \(uw_i,uw_j\in E(G)\). Hence \((R\setminus\{e_{w_i},e_{w_j}\})\cup\{uw_i,uw_j\}\), where \(w_i\in e_{w_i}\in E(R_i)\) and \(w_j\in e_{w_j}\in E(R_j)\), is a maximum 2-degree-packing with less components than \(R\), which is a contradiction. Therefore \(I=I_1\cup\cdots\cup I_k\), where either \(I_i=\emptyset\) or for every \(u\in I_i\) satisfies \(N(u)\subseteq V(R_i)\), for \(i=1,\ldots,k\). ◻
Proposition 21. Let \(G\) be a simple connected graph with \(\nu_2(G)\geq4\), \(|E(G)|>\nu_2(G)\), \(R_1,\ldots, R_k\) be the components of a maximum 2-degree-packing \(R\) of \(G\), with \(k\) as small as possible, and \(I=I_1\cup\cdots\cup I_k=V(G)\setminus V(G[R])\), where either \(I_i=\emptyset\) or for every \(u\in I_i\) satisfies \(N(u)\subseteq V(R_i)\), for \(i=1,\ldots,k\). If \(\beta(G)=\left\lceil\nu_2(G)/2\right\rceil\), then \(\beta(G[R_i])=\left\lceil\nu_2(G[R_i])/2\right\rceil\), for \(i=1,\ldots,k\).
Proof. The proof of the proposition is completely analogous to the proof Proposition 20. ◻
Proposition 22. Let \(G\) be a simple connected graph with \(\nu_2(G)\geq4\), \(|E(G)|>\nu_2(G)\) and \(R\) be a maximum 2-degree-packingof \(G\), such that \(G[R]\) is a connected graph. If \(\beta(G)=\left\lceil\nu_2(G)/2\right\rceil\), then either \(G\in \mathcal{\hat{C}}_{T,\hat{T},I}^k\) or \(G\in \mathcal{\hat{P}}_{T,\hat{T},I}^k\), where \(T\) is a minimum vertex cover of either \(C^k\) or \(P^k\), \(\hat{T}=V(G[R])\setminus T\) and \(I=V(G)\setminus V(G[R])\).
Proof. By Proposition 13, we have either \(\hat{C}^k_I\) is a subgraph of \(G\) or \(P^k_I\) is a subgraph of \(G\). Let \(T\) be a minimum vertex cover of \(G\) (hence, a minimum vertex cover of \(G[R]\), by Proposition 18). Hence, by definition, if \(e\in E(G)\setminus E(G[R]\), then \(e\) has an end in \(T\), which implies that \(G\) is a subgraph of \(\hat{C}^k_{T,\hat{T},I}\). Therefore, either \(G\in \mathcal{\hat{C}}_{T,\hat{T},I}^k\) or \(G\in \mathcal{\hat{P}}_{T,\hat{T},I}^k\). ◻
By Proposition 18, Proposition 22 and Corollary 21, we have:
Corollary 23. Let \(G\) be a simple connected graph with \(\nu_2(G)\geq4\), \(|E(G)|>\nu_2(G)\), \(R_1,\ldots, R_k\) be the components of a maximum 2-degree-packing \(R\) of \(G\), with \(k\) as small as possible, and \(I=I_1\cup\cdots\cup I_k=V(G)\setminus V(G[R])\), where either \(I_i=\emptyset\) or for every \(u\in I_i\) satisfies \(N(u)\subseteq V(R_i)\), for \(i=1,\ldots,k\). If \(\beta(G)=\left\lceil\nu_2(G)/2\right\rceil\), then either \(G[V_i]\in \mathcal{\hat{C}}_{T_i,\hat{T}_i,I_i}^{k_i}\) or \(G[V_i]\in \mathcal{\hat{P}}_{T_i,\hat{T}_i,I_i}^{k_i}\), where \(V_i=V(G[R_i])\cup I_i\), \(k_i=\nu_2(G[R_i])\), \(T_i\) is a minimum vertex cover of either \(C^{k_i}\) or \(P^{k_i}\) and \(\hat{T}_i=V(G[R_i])\setminus T_i\).
Hence, by Proposition 14, Proposition 22, Corollary 15 and Corollary 23, we have:
Theorem 24. Let \(G\) be a simple connected graph with \(\nu_2(G)\geq4\), \(|E(G)|>\nu_2(G)\), \(R_1,\ldots, R_k\) be the components of a maximum 2-degree-packing \(R\) of \(G\), with \(k\) as small as possible, and \(I=I_1\cup\cdots\cup I_k=V(G)\setminus V(G[R])\), where either \(I_i=\emptyset\) or for every \(u\in I_i\) satisfies \(N(u)\subseteq V(R_i)\), for \(i=1,\ldots,k\). Then \(\beta(G)=\left\lceil\nu_2(G)/2\right\rceil\), if and only if, either \(G[V_i]\in \mathcal{\hat{C}}_{T_i,\hat{T}_i,I_i}^{k_i}\) or \(G[V_i]\in \mathcal{\hat{P}}_{T_i,\hat{T}_i,I_i}^{k_i}\), where \(V_i=V(G[R_i])\cup I_i\), \(k_i=\nu_2(G[R_i])\), \(T_i\) is a minimum vertex cover of either \(C^{k_i}\) or \(P^{k_i}\) and \(\hat{T}_i=V(G[R_i])\setminus T_i\), being
\(|R_i|\) an even integer, for \(i=1,\ldots,k\), if \(\nu_2(G)\) an even number.
\(|R_1|\) is an odd integer and \(|R_i|\) is an even integer, for \(i=2,\ldots,k\), if \(\nu_2(G)\) is an odd number.