The hub set measures the connectivity of any nodes in graphs and the determination of it is found to be NP-complete. This paper deduces several properties and characterize of one such hub parameter, the doubly connected hub number for its value equal to 1 and 2. Moreover, a few bounds and Nordhaus-Gaddum type inequalities are discussed.
Consider a graph \(G =(V ,E )\) which is a finite, undirected graph with no loops and multiple edges. The number of vertices in \(G\) is called the order of \(G\) and the number of edges in \(G\) is called the size of \(G\). A graph with \(p\) vertices and \(q\) edges is called a \((p,q)\) graph. The open neighborhood and the closed neighborhood of \(v\in V (G )\) are defined by \(N(v)=\{u\in V :uv\in E \}\) and \(N[v]=N(v)\cup\{v\}\), respectively. The connectivity \(\kappa(G )\) of \(G\) is the minimum number of vertices whose removal results in a disconnected or a trivial graph. A vertex with degree \(|V (G )|-1\) is called a universal vertex and a vertex with degree \(1\) is called a pendant vertex. A vertex that is a neighbor of a pendant vertex is called a support. The cutvertex of a graph \(G\) is vertex whose removal increases the number of components in \(G .\) The independence set a set \(S\) of vertices such that for every two vertices in \(S\), there is no edge connecting the two. A maximum independent set is an independent set of largest possible size for a given graph \(G\). This size is called the independence number of \(G\) and is denoted by \(\beta_0(G).\)” For further graph theoretic terminology, we refer to [1].
Walsh proposed the concept of hub set in graph theory by modelling a transportational problem [2], as ‘the vertex subset \(\mathcal{H}\) of \(\,G\) such that any two vertices outside \(\mathcal{H}\) are connected by a path whose all internal vertices are elements of \(\mathcal{H}\) (If \(uv\) is an edge in \(\langle V (G ) \setminus \mathcal{H}\rangle\) then it itself is a trivial path)’. “The minimum cardinality of a hub set in \(G\) is called a hub number of \(G\) and is denoted by \(h(G )\). A hub set \(\mathcal{H}\) of a connected graph \(G\) is called a connected hub set if \(\langle \mathcal{H}\rangle\) is connected. The minimum cardinality of a connected hub set is called connected hub number of \(G\) and is denoted by \(h_{c}(G )\).” Further, he showed that the determination of the hub and connected hub set in any graph of size \(q\) is NP-complete. In recent years, the hub theory has attracted more and more attention from researchers due to its different applications in the field of networks. To illustrate, consider a transport network operating in a metropolis with multiple destinations and a signal transport network among multiple servers. By representing each location (or server) by a vertex of a graph, there exists an edge between two locations (or servers) if the transition from one to another location is easy. Here, by finding the \(h(G )\) of this corresponding graph, we obtain the lowest number of locations or servers required for corresponding transitions from one location to another in these different types of networks. For this reason, various hub parameters are being defined for graphs and its properties are being studied extensively in the literature [3– 9].
The hub parameters measure the connectivity of vertices in a graph, while the domination parameters deal with the proximity of the same. By understanding the relationship between these two parameters, one can gain insight into the structure of a graph and its potential applications. As a result, several articles have been widely studied on this topic [2, 3, 10– 13] which has sparked interest in many researchers.
In 2021, A. M. Sahal coined and studied the notion of doubly connected hub set (DCHS) as a ‘set \(\mathcal{S}\subseteq V (G )\) which is a hub set of \(G\) such that both \(\langle \mathcal{S}\rangle\) and \(\langle V \setminus \mathcal{S}\rangle\) are connected. The cardinality of the minimum doubly connected hub set (MDCHS) in \(G\) is called the doubly connected hub number (DCHN) of \(G\) and is denoted by \(h_{cc}(G )\)’. This is well defined if \(G\) is connected and \(h(G )\leq h_{c}(G )\leq h_{cc}(G )\) [3]. Further, it has been revealed that the doubly connected hub number can increase significantly, depending on certain conditions.
One can observe that \(h_{cc}(G )\) acts as a convenient measure to differentiate graphs based on the connectedness of vertices outside the hub set. Consider the following example of graphs \(M _1, M _2\) and \(M _3\) as shown in the Figure 1. Clearly from Figure 1, the central vertex \(\{ v_6\}\) forms a minimum hub set and minimum connected hub set, thus we obtain \(h(M _1) =h_c(M _1) = h(M _2)=h_c(M _2)=h(M _3) =h_c(M _3) = 1\). So, the hub number and connected hub number will not differentiate the graphs \(M _1,M _2\) and \(M _3\) based on its connectedness, whereas the MDCHS of \(M_1, M_2,\) and \(M_3\) are \(\{ v_5, v_6\}\), \(\{ v_1,v_2, v_6\}\) and \(\{ v_1,v_2, v_5, v_6\}\), respectively. Hence \(h_{cc}(M _1) =2, h_{cc}(M _2)=3, h_{cc}(M _3) = 4\) inferring that \(h_{cc}(G )\) varies for dissimilar graphs, and plays an vital role in study of connectivity of the induced subgraphs of both the hub set and its complement.
This paper extends the current understanding of DCHN by providing novel bounds and results. The results of this study indicate that DCHS could be further leveraged to improve routing efficiency in communication networks. Our findings provide a useful reference point for future research on the topic of doubly connected hub numbers.
The following are the results that are considered in this paper.
Proposition 1. [14] The inequality \(\gamma_{cc} (G ) \leq p – \kappa(G ) + 1\) hold, where \(G\) is any connected graph of order \(p \geq 2\).
Theorem 1. [14] The inequalities \(\dfrac{p}{\Delta(G ) + 1} \leq \gamma_{cc}(G ) \leq 2q – p + 1\) hold, where \(G\) is any connected graph of order \(p \geq 2.\)
Theorem 2. [3] Let \(G\) be a connected graph, then \(h_{cc}(G ) \leq \gamma_{cc}(G )\).
Theorem 3. [3] Let \(G\) be a connected graph with \(p\) vertices, then \(h_{cc}(G ) \geq p – \Delta(G ) – 1 .\)
Here we provide a clear set of bounds and results. The ensuing results are obtained straight away from the definition of DCHN of graphs.
Observation 1. \(h_{cc}(W_{n})=1\), for every wheel graph \(W_p.\)
Observation 2. For any graph \(G\) of the form \(G = K_n \cup {H} , n \geq 1\) where \({H}\) is non-complete graph, \(h_{cc}(G )= |V ({H})|\).
Observation 3. If \(G = K_n \cup K_m , n,m \geq 1\) then \(h(G )=h_{c}(G )= h_{cc}(G )= min \{ n ,\, m \}\).
Proposition 1. For any connected graph \(G\) of order \(p \geq 2\), \(h_{cc} (G ) \leq p – \kappa(G ) + 1.\)
Proof. Proof follows from Proposition 1 and Theorem 2. ◻
Let \(p_1, p_2\) and \(p_3\) represent the number of pendant vertices, cutvertices and supports respectively, of \(G\). We have the following result.
Proposition 3. For any connected graph \(G\) of order \(p \geq 3\), if \(\mathcal{S}\) is a doubly connected hub set of \(G\) with minimum cardinality, then
The above proposition is a direct deduction from the first Proposition in [3]. Here we can see that the equality of \((iii)\) holds only when \(G =K_{1,2}\).
Proposition 4. Every connected graph \(G\) of order \(p \geq 3\), \(h_{cc}(G )\geq p_1+p_3-2\) and this inequality is sharp only when each vertex \(r\in V (G )\) is either a pendant or a support vertex and \(G\) has at least one support of degree \(2\).
Proof. Let \(\Omega(G )\) and \(\Gamma(G )\) represent the sets of all pendant and support vertices, respectively in \(G\). By \((ii)\) and \((iii)\) of Proposition 3, \(h_{cc}(G )\geq p_{3}-1\) and \(h_{cc}(G )\geq p_{1}-1\). So, \(h_{cc}(G )\geq p_{1}+p_{3}-2\). Now, if each \(r \in V (G )\) is either a pendant or a support vertex, then \(\Omega(G )\cup\Gamma(G )=V (G )\) and \(p_{1}+p_{3}=p\). So, \(p-2=p_{1}+p_{3}-2\). Also \(G\) has at least one support \(s\) such that deg \(s =2\) and \(t\) be the pendant vertex adjacent to \(s\). Then \(V (G )\setminus \{s,t\}\) is a MDCHS of \(G\). Hence \(h_{cc}(G )=p_{1}+p_{3}-2\).
Conversely, suppose that \(h_{cc}(G )=p_{1}+p_{3}-2\). Then the MDCHS contains every vertex of \(\Omega(G )\) except a pendant vertex. Now, if no support of \(G\) has degree \(2\), then \(h_{cc}(G )=p-1=p_{1}+p_{3}-1\), a contradiction. Hence \(G\) has a support of degree \(2\) and \(G\) contains all vertices of the set \(\Gamma(G)\) except one support. ◻
The following corollary provides a graph class where every vertex is either a pendant or a support vertex in \(G\), having atleast on support of degree \(2\).
Corollary 1. Let \(G ={H}\circ K_1\), where \({H}\) is a connected graph of order \(p\geq 3\). Then, \(h_{cc}(G )=|V (G )|-2.\)
The following result is obtained analogous to Proposition 4.
Proposition 5. For every connected graph \(G\) of order \(p \geq 3\), \(h_{cc}(G )\geq p_1+p_3-2\) and this inequality is sharp if and only if each vertex \(r\in V (G )\) is either a pendant or a support vertex and \(G\) has at least one cutvertex of degree \(2\).
Corollary 2. For any path \(P_p\), \(h_{cc}(P_p) = p-2.\)
Corollary 3. Let \(T\) be a tree of order \(p\geq 3\) vertices having at least one support of degree \(2\), then \(h_{cc}(T)=p-2\).
Proof. Every vertex in a tree \(T\) is either a cutvertex or a pendant vertex. Since every support is a cutvertex, by Proposition 5 we get, \(h_{cc}(T)\geq n-2\). Further, if \(r\) is a pendant vertex of \(T\) and \(s\) is a support such that deg \(s=2\) and \(s\) is adjacent to \(r\), then \(S=V (T)\setminus\{r,s\}\) is a DCHS. Thus \(h_{cc}(T)\leq p-2\). Hence \(h_{cc}(T)=p-2\). ◻
Consider the representation \(\mathfrak{T}(T_1, T_2)\), where \(T_1\) and \(T_2\) are any two vertex-disjoint trees. Here, \(\mathfrak{T}(T_1, T_2)\) denotes the collection of all graphs that are obtained from the trees \(T_1\) and \(T_2\) by introducing \(|V(T_2)|\) edges, such that each vertex of \(T_2\) is connected to an arbitrary vertex of \(T_1\) with an edge. For any graph \(H\), if there exist two trees \(T_1\) and \(T_2\) such that \(H \in \mathfrak{T}(T_1, T_2)\), then \(H\) is considered to belong to the family \(\mathfrak{F}\). The graph \(H\) shown in Figure 2 belongs to the family \(\mathfrak{F}\).
Theorem 4. Let \(H\) be a connected graph of order \(p\geq 2\) and size \(q\). Then \[2p-q-2-k\leq h_{cc}(H ),\] where \(k\) represents the total number of universal vertices in \(\langle V (H )\setminus \mathcal{S}\rangle\) for any minimum doubly connected hub set \(\mathcal{S}\) of \(H\). This bound is sharp for any graph \(H\) belonging to the family \(\mathfrak{F}\).
Proof. Let \(\mathcal{S}\) be a MDCHS of \(G\). Then \(\langle \mathcal{S}\rangle\) and \(\langle V (H )\setminus \mathcal{S}\rangle\) are connected. So, we have \(|E (\langle \mathcal{S}\rangle)|\geq |\mathcal{S}|-1=h_{cc}(H )-1\) and \(|E (\langle V (H )\setminus \mathcal{S}\rangle)\geq |V (H )\setminus \mathcal{S}|-1\) \(=p-h_{cc}(H )-1\). The number of edges \(q_h\) joining vertices of \(\langle V (H )\setminus \mathcal{S}\rangle\) to vertices of \(\langle \mathcal{S}\rangle\) is given by, \(q_h\geq p-h_{cc}(H)-k\). Adding all these three inequalities, we get \[\begin{aligned} q=&|E (\langle \mathcal{S}\rangle)|+|E (\langle V (H )\setminus \mathcal{S}\rangle)|+q_h \geq h_{cc}(H )-1+p-h_{cc}(H )-1+p-h_{cc}(H )-k = 2p-h_{cc}(H )-2-k . \end{aligned}\]
Hence, \(h_{cc}(H )\geq 2p-q-2-k\).
Now to prove that \(h_{cc}(H )=2p-q-2-k\) only when \(H \in \mathfrak{F}\). Suppose that \(H \in \mathfrak{F}\). Then there exist trees \(T_1\) and \(T_2\) with \(H \in \mathfrak{T}(T_1, T_2)\). Here, the set \(V (T_1)\backslash \{r\}\), where \(r\) is the universal vertex of \(T_2\) forms a DCHS of \(H.\) \[\begin{aligned} \label{eq1} h_{cc}(H )&\leq& |V (T_1)|-k, \end{aligned} \tag{1}\] here \(k\) is either 0 or \(1\) as \(T_2\) has at most one universal vertex. Also by above discussion \(h_{cc}(G )\geq 2p-q-2-k\). Since \(|V (H )| = |V (H _1)+V (H _2)|\) and \(|E (H )| = |E (H _1)+E (H _2)+ V (H _2)|\), we have \[\begin{aligned} 2p-q-2-k=&2(|V (T_1)|+|V (T_2)|)-(|E (T_1)|+|E (T_2)|+|V (T_2)|)-2-k \nonumber \\ = & 2(|V (T_1)|+|V (T_2)|)-(|V (T_1)|-1+|V (T_2)|-1+|V (T_2)|)-2-k \nonumber \\ =&|V (T_1)|-k. \nonumber \end{aligned}\]
Consequently, \[\begin{aligned} \label{eq2} h_{cc}(G )&\geq& |V (T_1)|-k. \end{aligned} \tag{2}\]
From (1) and (2) it follows that \[\begin{aligned} h_{cc}(G )=&|V (T_1)|-k=2p-q-2-k. \nonumber \end{aligned}\]
Conversely, suppose that \(h_{cc}(G )=2p-q-2-k\) where \(k\) represents the number of universal vertices in \(\langle V (H )\setminus \mathcal{S}\rangle\) for any MDCHS \(\mathcal{S}\) of \(H\). Then, \(|E (\langle \mathcal{S}\rangle)|=h_{cc}(H )-1=|V (\langle \mathcal{S}\rangle)|-1\), \(|E (\langle V (H )\setminus \mathcal{S}\rangle)|=p-h_{cc}(H )-1=|V (\langle V (G )\setminus \mathcal{S}\rangle)|-1\) and \(q_h=p-h_{cc}(H )-k\). This implies that \(\langle \mathcal{S} \rangle\) and \(\langle V (H )\setminus \mathcal{S}\rangle\) are both trees such that each vertex in \(\langle V (H )\setminus \mathcal{S}\rangle\) has exactly one neighbor in \(\langle\mathcal{S}\rangle\). Therefore, \(H\) can be formed by trees \(T_1\) and \(T_2\) by adding \(|V (T_2)|\) edges with each vertex of \(T_1\) is connected to an arbitrary vertex of \(T_2\) by an edge. Hence \(H \in\mathfrak{F}\). ◻
Theorem 5. For any two nontrivial connected graphs \(H _1\) and \(H _2\), \[h_{cc}(H _1 \circ H _2) =|V (H _1 \circ H _2)| – |V (H _2 )| – 1.\]
Proof. If \(H _1\) and \(H _2\) are two nontrivial connected graphs, then cardinality of vertex set of the graph \(H _1 \circ H _2\) is given by \(|V (H _1 \circ H _2)| = ( |V (H _2 )| + 1 )|V (H _1 )| .\) Since the graph \(H _1 \circ H _2\) has \(|V (H _1 )|\) copies of \(H _2\) which are all independent with respect to each other, the DCHS must contain all the vertices of at least \(|V (H _1 )| -1\) copies of \(H _2\) in it along with \(|V (H _1 )| -1\) number of connecting vertices of \(H _1\). But to retain the connectedness of this hub set, the chosen \(|V (H _1 )| -1\) vertices of \(H _1\) must contain every cutvertex of \(H _1\).
Thus, the DCHN is given by \[\begin{aligned} h_{cc}(H _1 \circ H _2) & = \left( |V (H _1 )| -1\right) |V (H _2 )| + |V (H_1 )| -1 \\ & = |V (H _1 )| |V (H _2 )| -|V (H _2 )| + |V (H _1 )| -1 \\ & = |V (H _1 \circ H _2)| – |V (H _2 )| – 1. \end{aligned}\] ◻
Theorem 6. The difference \(h_{cc}(H)-\beta_{0}\) can be arbitrarily large.
Proof. Let \(n\) be a positive integer and \(H =K_{n+1}\circ K_{1}\). Then the set of pendant vertices of \(H\) is the maximum independent set of \(H\) so that \(\beta_{0}(H )=n+1\). As \(H\) is obtained by corona product, it follows from Corollary 1 that, \(h_{cc}(H )=|V (H )|-2=2(n+1)-2=2n+2-2=2n\). So, \(h_{cc}(H )-\beta_{0}(H )=2n-(n+1)=n-1\). ◻
Present section deals with the characterization of the DCHN of graphs according to its nature, and demonstrate its efficacy by presenting following results.
Lemma 1. For any non-complete graph \(G\) with \(h_{cc}(G ) = 1\), if \(\{ r\}\) is the MDCHS of \(G\), then \(r\) is a non-cutvertex of \(G .\)
Proof. Let \(\{ r\}\) be the MDCHS of \(G\). Suppose \(r\) is a cutvertex of \(G ,\) then that \(\langle G -r \rangle\) has atleast two disjoint components of \(G ,\) which contradicts our hypothesis, that \(\{ r\}\) is the DCHS of \(G\). Hence \(G\) is a non-cutvertex of \(G .\) ◻
Theorem 7. Given any \(m \in \mathbb{Z}^+,\) there exists a graph \(G\) with \(h_{cc}(G ) = m.\)
For example, consider \(m \in \mathbb{Z}^+, \; m \geq 3\). Then for \(G = P_{m+2},\) we have \(h_{cc}(G ) = m.\) Similarly for \(G = C_{m+3},\) we have \(h_{cc}(G ) = m.\)
Theorem 8. Given any two positive integers \(k\) and \(p\) with \(2k \leq p,\) there exists a connected graph \(G\) of order \(p\) such that \(h_{cc}(G ) = k.\)
Proof. Consider the complete graph \(K_{p-k}\) whose vertex set \(V (K_{p-k} ) = \{ v_1, v_2, \cdots , v_{p-k}\}\) and a cycle \(C_k\) with \(V (C_k ) = \{ u_1, u_2, \cdots , u_k\}\). Since \(p-k \geq k\), we construct a graph \(G\) from \(K_{p-k}\) and \(C_k\) by taking and adding the new edges \(u_iv_i\) for all \(i, \; 1\leq i \leq k.\) Then \(G\) is connected graph of order \(p\) and \(\{ u_1, u_2, \cdots , u_k\}\) is a MDCHS of \(G\) and hence \(h_{cc}(G ) = k.\) ◻
Figure 3 depicts an example of the structure discussed in the proof of the Theorem 8 by taking \(p=10\) and \(k=4 .\)
Theorem 9. Let \(G\) be a non-complete graph with \(p\) vertices, then \(h_{cc}(G ) = 1\) if and only if \(G\) has a vertex \(r\) of degree \(p-1\) satisfying one of the following:
Proof. Consider a non-complete graph \(G\) of order \(p\) and has a vertex \(r\) of degree \(p-1 .\) If \(r\) is a non-cutvertex, then \(\{r\}\) is a MDCHS of \(G\) and thus \(h_{cc}(G ) = 1\). If \(r\) is a cutvertex such that \(\langle N(r) \rangle = K_1 \cup K_{p-2}\) then \(G = K_1 + (K_1 \cup K_{p-2}) =K_2 \bullet K_{p-1 }\). Here, the pendant vertex of \(G\) forms a MDCHS of \(G\) and thus \(h_{cc}(G ) = 1\).
Conversely, suppose \(G\) is a non-complete graph of order \(p\) with \(h_{cc}(G ) = 1\), then there exits at least one vertex \(r\) say, through which any pair of remaining \(p-1\) vertices have \(\{r\}-\) path in \(G\). Therefore, \(G\) has at least one vertex \(r\) of degree \(p-1\).
Case 1. If \(r\) is a non-cutvertex of \(G\), then there is nothing to prove.
Case 2. If \(r\) is a cutvertex of \(G\) then by hypothesis there exists at least one vertex say \(s,\) such that \(\{ s\}\) is a MDCHS of \(G\). From Lemma 1, \(s\) is a non-cutvertex of \(G\) and hence \(s \ne r.\) Now we claim that \(\langle N(r) \rangle = \langle G -r\rangle\) has exactly two components.
Suppose \(\langle G -r\rangle\) has more than two components. Let \(\mathcal{R}\) be the component of \(\langle G -r\rangle\) which contains \(s\). Then \(s\) is adjacent only to the vertices of \(\mathcal{R}\) and not adjacent to any vertex of other components in \(\langle G -r\rangle\). So, any path between two vertices of different component other than \(\mathcal{R}\) is through \(r\) only and not through \(s\). This implies, \(\{ s\}\) is not a hub set of \(G ,\) a contradiction. Thus, \(G -r = \mathcal{R} \cup \mathcal{P}\) which implies that \(s \in V (\mathcal{R})\) or \(s \in V (\mathcal{P})\). Without loss of generality, let \(s \in V (\mathcal{R})\). Since \(\{ s\}\) is a MDCHS, \(\mathcal{R}\) cannot have any vertex other than \(s\). For, if \(t \in V (\mathcal{R}), t \ne s\), then there is no \(\{ s\}\)-path between \(t\) and the vertices of \(V (\mathcal{P})\) and hence \(\mathcal{R} = K_1.\) Also \(\mathcal{P}= K_{p-2}\), since \(\{r, s\} \notin \mathcal{P}\) and between any two vertices of \(\mathcal{P}\) there exists a \(\{ s\}\)-path. Therefore, \(G -r = \langle N(r) \rangle = K_1 \cup K_{p-2} .\) ◻
Theorem 10. Let \(G\) be a graph with \(p\) vertices, then \(h_{cc}(G ) = 2\) if and only if \(G\) has the following structure:
Proof. Suppose that \(h_{cc}(G ) = 2\). Then the first three conditions are obvious by taking \(\{ r,s \}\) as the MDCHS and letting \(U\) and \(W\) to be the sets of neighbors and nonneighbors of \(\{ r,s \}\) , respectively. Since \(W = V (G ) \setminus N[\{r,s\}]\), for any vertex \(t \in W\) there is no \(\{rs\}\)-path between \(t\) and any other vertex in \(V (G ) \setminus \{ r,s \}\). Hence every vertex of \(W\) must be adjacent to all vertices of \(V (G ) \setminus \{ r,s\}\). Also since \(\langle \{r,s \} \rangle\) and \(\langle V (G ) \setminus \{ r,s \} \rangle\) are connected, the next five conditions are evident. The last condition is true, otherwise \(h_{cc}(G ) = 1\), which contradicts our hypothesis. The converse is trivial. ◻
This section deals with two edge based graph operations known as edge subdivision and edge removal and study consequences based on \(h_{cc}(G ).\) “An edge subdivision in a graph \(G\) is an operation of removal of an edge \(x=rs\) and the addition of a new vertex \(t\) and edges \(rt\) and \(ts\). A graph obtained from \(G\) by subdividing the edge \(x=rs\) is denoted by \(G \oplus t_{rs}\) [14].”
Theorem 11. Let \(G\) be a connected graph, then \(h_{cc}(G )\leq h_{cc}(G \oplus w_{uv})\).
Proof. Let \(x=rs\) be the subdivided edge of \(G\) and \(\mathcal{S}\) be a MDCHS of \(G \oplus t_{rs}\). Consider the following cases :
Case 1. \(t\in \mathcal{S}\). Since \(\langle \mathcal{S} \rangle\) is connected, \(r\) or \(s\) belong to \(\mathcal{S}\). If \(r,s\in \mathcal{S}\) then \(\mathcal{S}\setminus \{t\}\) is a DCHS of \(G\). If \(r\in \mathcal{S}\) and \(s\notin \mathcal{S}\), then also \(\mathcal{S}\setminus \{t\}\) is a DCHS of \(G\) and hence in either cases, \(h_{cc}(G )\leq |\mathcal{S}|=h_{cc}(G \oplus t_{rs})\).
Case 2. \(t\notin \mathcal{S}\). Since \(\mathcal{S}\) is a hub set and \(t\) is adjacent to only \(r\) and \(s\), either of them belong to \(\mathcal{S}\). Then proceeding as in Case 1, we obtain \(h_{cc}(G )\leq |\mathcal{S}|=h_{cc}(G \oplus t_{rs})\). ◻
The difference between the two values on either side of inequality in Theorem 11 can be arbitrarily large, meaning there is no limit to how much they can vary from each other. This indicates a wide range of possibilities.
Theorem 12. The extent of the difference \(h_{cc}(G \oplus w_{uv})-h_{cc}(G )\) can be expanded to an arbitrarily large value.
Proof. Let \(G =S_{n,m}+K_1, n\leq m\) as shown in the Figure 4. The set \(S_1=\{x\}\) is a MDCHS of \(G\) and thus \(h_{cc}(G )=1\). The set \(S_2=N[u]\setminus \{w\}\) is a MDCHS of \(G \oplus w_{uv}\), and thus \(h_{cc}(G \oplus w_{uv})=n+1\). Hence, \(h_{cc}(G \oplus w_{uv})-h_{cc}(G )=n+1-1=n\).
Theorem 13. The extent of the difference \(h_{cc}(G -x)-h_{cc}(G )\) can be expanded to an arbitrarily large value, where \(x\) is an edge of \(G\).
Proof. Consider two wheel graphs \(W_n\) and \(W_m\) with vertex sets \(\{u_0,u_{1},u_{2},\cdots,u_{n-1}\}\) and \(\{v_0,v_{1}, v_{2}, \cdots ,v_{m-1}\},\) \(4\leq n \leq m\) respectively, where \(u_0\) and \(v_0\) are central vertices. Now we construct a graph \(G\) by identifying the vertex \(u_1\) with \(v_1\) and naming it as \(u'\) and further joining \(u_3\) and \(v_3\) by an edge. Then, the set \(V (W_n) \cup \{v_0 \}\) is a MDCHS of \(G -x\), where \(x=u_3v_3\) and so, \(h_{cc}(G -x)=n+1\). The set \(\{u_0, v_0, u' \}\) is a MDCHS of \(G\) and thus \(h_{cc}(G )=3\). Thus, \(h_{cc}(G -x)-h_{cc}(G )=n+1-3=n-2\). ◻
This section, discusses certain Nordhaus-Gaddum inequalities on \(h_{cc}(G ).\)
Theorem 14. For a connected graph \(G\) with \(p\) vertices and \(q\) edges, whose complement \(\overline{G }\) is connected, \[h_{cc}(G ) + h_{cc}(\overline{G }) \leq p^2 -3p +2.\]
Proof. From Theorem 1 and Theorem 2, we get \[h_{cc}(G )\leq 2q -p +1 \mbox{ and } h_{cc}(\overline{G })\leq 2\left( \dfrac{p(p-1)}{2} – q\right) -p +1 .\]
Now, \[\begin{aligned} h_{cc}(G ) + h_{cc}(\overline{G }) & \leq 2q -p +1 + 2\left( \dfrac{p(p-1)}{2} – q\right) -p +1\\ & \leq 2q -p +1 + p^2 -p -2q -p +1\\ & \leq p^2 -3p +2. \end{aligned}\] ◻
Theorem 15. For any connected graph \(G\) with \(p\) vertices, whose complement \(\overline{G }\) is connected, then \[h_{cc}(G ) + h_{cc}(\overline{G }) \geq p – \Delta(G ) +\delta(G ) -1 .\]
Proof. From Theorem 3, we have \(h_{cc}(G )\geq p – \Delta(G ) – 1 \mbox{ and } h_{cc}(\overline{G }) \geq p – \Delta(\overline{G }) – 1 .\) Now,
\[\begin{aligned} h_{cc}(G ) + h_{cc}(\overline{G }) & \geq 2p – \left[ \Delta(G ) + \Delta(\overline{G }) \right] -2\\ & \geq 2p – \left[\Delta(G ) + p -1 – \delta(G ) \right] -2 \\ & \geq p – \Delta(G ) + \delta(G ) -1. \end{aligned}\] The bound is sharp for \(G \cong C_7.\) ◻
Overall investigation of this research deals with the properties and results of the DCHN of graphs. Further it provides bounds on this parameter and given several characterizations of it. As part of our study, we encounter some problems that need further study.
Harary, F. (1969). Graph Theory. Addison-Wesley.
Walsh, M. (2006). The Hub Number of a Graph. International Journal of Mathematics and Computer Science, 1, 117-124.
Sahal, A. M. (2021). The doubly connected hub number of graph. International Journal of Mathematical Combinatorics, 1, 79-84.
Basavanagoud, B., Sayyed, M., & Barangi, A. P. (2022). Hub number of generalized middle graphs. TWMS Journal of Applied and Engineering Mathematics, 12(1), 284-295.
Lin, C. H., Liu, J. J., Wang, Y. L., & Yen, W. C. K. (2011). The hub number of Sierpiński-like graphs. Theory of Computing Systems, 49(3), 588-600.
Liu, J. J., Wang, C. T. H., Wang, Y. L., & Yen, W. C. K. (2015). The hub number of co-comparability graphs. Theoretical Computer Science, 570, 15-21.
Khala, S. I., & Mathad, V. (2020). Hub and global hub numbers of a graph. Proceedings of the Jangjeon Mathematical Society, 23(2), 231-239.
Mathad, V., Sahal, A. M., & Kiran, S. (2014). The total hub number of graphs. Bulletin of the International Mathematical Virtual Institute, 4, 61-67.
Mathad, V., & Puneeth, S. (2023). Co-even hub number of a graph. Advances and Applications in Discrete Mathematics, 39(2), 245-257.
Johnson, P., Slater, P., & Walsh, M. (2011). The connected hub number and the connected domination number. Networks, 58(3), 232-237.
Grauman, T., Hartke, S. G., Jobson, A., Kinnersley, B., West, D. B., Wiglesworth, L., Wu, H. (2008). The hub number of a graph. Information Processing Letters, 108(4), 226-228.
Mathad, V., Anand & Puneeth, S. (2023). Bharath hub number of graphs. TWMS Journal of Applied and Engineering Mathematics 13(2), 661-669.
Liu, X., Dang, Z., & Wu, B. (2014). The hub number, girth and Mycielski graphs. Information Processing Letters, 114(10), 561-563.
Cyman, J., Lemańska, M., & Raczek, J. (2006). On the doubly connected domination number of a graph. Central European Journal of Mathematics, 4(1), 34-45.
