February 04, 2024
The \(\delta\)-complement \(G_\delta\) of a graph \(G\), introduced in 2022 by Pai et al., is a variant of the graph complement, where two vertices are adjacent in \(G_\delta\) if and only if they are of the same degree but not adjacent in \(G\) or they are of different degrees but adjacent in \(G\). In this paper, we provide the Nordhaus-Gaddum-type bounds, in the spirit of Nordhaus and Gaddum (1956), over the maximum degrees, the minimum degrees, the vertex connectivities, and the edge connectivities of a graph and its \(\delta\)-complement. All bounds are attained except for the upper bounds on the product between the minimum degrees of a graph and its \(\delta\)-complement, the vertex connectivities of a graph and its \(\delta\)-complement, and the edge connectivities of a graph and its \(\delta\)-complement.
Keywords. delta-complement; graph complement; Nordhaus-Gaddum relation; vertex degree; vertex connectivity; edge connectivity
MSC. 05C99; 05C07; 05C40; 05C76
In 1956, Nordhaus and Gaddum [1] showed the following relations between the chromatic numbers of a graph \(G\) and \(\overline{G}\). \[2\sqrt{n} \leq \chi(G) + \chi(\overline{G}) \leq n + 1,\] and \[n \leq \chi(G) \cdot \chi(\overline{G}) \leq \left(\frac{n+1}{2}\right)^{2}.\] After that, there have been a lot of results discussing similar relations on other several parameters of a graph and its complement, which are called Nordhaus-Gaddum problems. Some examples are minimum degrees [2], maximum degrees [3], diameters [4], girths [4], circumferences [4], and domination numbers [5]. See [6] and the references therein for more details.
In 2022, Pai, et al. [7] defined the \(\delta\)-complement \(G_{\delta}\) of a graph \(G\), which is defined similarly to the complement of a graph but the complementation only happens among the vertices of the same degree. This operation is closely related to the subgraph complementation introduced in [8] in their study of different kinds of complementations. For this operation, only the subgraph \(G[A]\) induced by a subset of vertices \(A\) is replaced by its complement, while leaving the other part unchanged. Another related operation is the switching operation, introduced in [9], that reverses the adjacenices between \(A\) and \(V(G)\setminus A\), while keeping the adjacencies in \(A\) and \(V(G)\setminus A\) unchanged.
In 2023, Vichitkunakorn, et al. [10] have discussed the Nordhaus-Gaddum-type relation between \(G\) and \(G_{\delta}\) on the chromatic numbers \(\chi(G)\) and \(\chi(G_{\delta})\), with respect to the original theorem from [1]. While this relation has been studied for the chromatic number, to the best of the authors’ knowledge, there is no work on the Nordhaus-Gaddum-type relations between \(G\) and \(G_\delta\) on other graph invariants. To fill this research gap, we give such relations on four graph invariants: the maximum degree, the minimum degree, the vertex connectivity, and the edge connectivity.
In this work, we first show the Nordhaus-Gaddum-type relations over the maximum degrees and the minimum degrees of a graph and its \(\delta\)-complement. The results are then used to show the Nordhaus-Gaddum-type relations over the vertex connectivities and the edge connectivities of a graph and its \(\delta\)-complement. The paper is organized as follows. In Section 2, we review the Nordhaus-Gaddum-type relations on the chromatic numbers, maximum degrees, minimum degrees, vertex connectivities, and edge connectivities of a graph and its complement. Then, we review the definition of the \(\delta\)-complement of a graph and the Nordhaus-Gaddum-type relation on the chromatic numbers of a graph and its \(\delta\)-complement. In Section 3, we give the Nordhaus-Gaddum-type relations between \(G\) and \(G_\delta\) on four graph invariants: the maximum degree, the minimum degree, the vertex connectivity, and the edge connectivity.
Some discussions and further questions are discussed in Section 4.
The complement of a simple graph \(G = (V,E)\), denoted by \(\overline{G} = (V,\overline{E})\), is the graph such that \(uv \in \overline{E}\) if and only if \(uv \notin E\). The chromatic number \(\chi (G)\) of a graph \(G\) is the least number of colors required to label each vertex in \(G\) so that no two adjacent vertices share the same color.
In 1956, Nordhaus and Gaddum studied the relations between the chromatic number \(\chi(G)\) of a graph \(G\) and the chromatic number \(\chi(\overline{G})\) of the complement \(\overline{G}\). They found the upper bounds and lower bounds of the sum and the product of \(\chi(G)\) and \(\chi(\overline{G})\), which are shown in the following theorem.
Theorem 1 ([1]). Let \(G\) be a graph of \(n\) vertices. Then, \[2\sqrt{n} \leq \chi(G) + \chi(\overline{G}) \leq n+1,\] and \[n \leq \chi(G) \cdot \chi(\overline{G}) \leq \left(\frac{n+1}{2}\right)^2.\] Moreover, the bounds are sharp for all \(n\).
Let \(\Delta(G)\) and \(\delta(G)\) be the maximum degree and the minimum degree of \(G\), respectively. In 1991, Xu [3] has proved the bounds on \(\Delta(G)+\Delta(\overline{G})\) as follows.
Theorem 2 ([3]). Let \(G\) be a graph of \(n\) vertices. Then, \[n-1 \leq \Delta(G) + \Delta(\overline{G}) \leq 2n-3.\] Moreover, the bounds are sharp for all \(n\).
The following are obvious upper bound and lower bound on \(\Delta(G)\cdot\Delta(\overline{G})\). However, they are not sharp for all \(n\). \[0 \leq \Delta(G) \cdot \Delta(\overline{G}) \leq (n-1)^2.\]
In 1971, Alavi and Mitchem [2] provided the bounds on the sum and the product between the minimum degrees of a graph and its complement as follows. All bounds are sharp, except for the upper bound on \(\delta(G) \cdot \delta(\overline{G})\) that has not been proved.
Theorem 3 ([2]). For \(n \geq 2\), let \(G\) be a graph of \(n\) vertices. Then, \[1 \leq \delta(G) + \delta(\overline{G}) \leq n-1,\] and \[0 \leq \delta(G) \cdot \delta(\overline{G}) \leq \begin{cases} \left( \frac{n-3}{2} \right) \left( \frac{n+1}{2} \right) & \text{if } n \equiv 3 \pmod 4,\\ \left\lfloor \frac{n-1}{2} \right\rfloor \left\lceil \frac{n-1}{2} \right\rceil & \text{if } n \not\equiv 3 \pmod 4. \end{cases}\]
The vertex connectivity \(\kappa(G)\) of a graph \(G\) is the minimum number of vertices that need to be removed so that the graph becomes disconnected or remains one vertex. If \(G\) is already disconnected or \(G\) contains a single vertex, then \(\kappa(G) = 0\). Similarly, the edge connectivity \(\lambda(G)\) of a graph \(G\) is the minimum number of vertices that need to be removed so that the graph becomes disconnected. If \(G\) is already disconnected or \(G\) contains a single vertex, then \(\lambda(G) = 0\).
Bounds on the sum and the product of the vertex connectivities of a graph and its complement and the bounds on the sum and the product of the edge connectivities of a graph and its complement are also provided in the following theorem.
Theorem 4 ([2]). For \(n \geq 2\), let \(G\) be a graph of \(n\) vertices. Then, \[1 \leq \kappa(G) + \kappa(\overline{G}) \leq n-1, \qquad 0 \leq \kappa(G) \cdot \kappa(\overline{G}) \leq M(n),\] \[1 \leq \lambda(G) + \lambda(\overline{G}) \leq n-1, \qquad 0 \leq \lambda(G) \cdot \lambda(\overline{G}) \leq M(n),\] where \[M(n) = \begin{cases} \left( \frac{n-3}{2} \right) \left( \frac{n+1}{2} \right) & \text{if } n \equiv 3 \pmod 4,\\ \left\lfloor \frac{n-1}{2} \right\rfloor \left\lceil \frac{n-1}{2} \right\rceil & \text{if } n \not\equiv 3 \pmod 4. \end{cases}\] Moreover, all eight bounds are sharp for all \(n \geq 2\).
In 2022, Pai et al. [7] defined the \(\delta\)-complement of a graph as follows.
Definition 5. For a graph \(G = (V,E)\), the \(\delta\)-complement of \(G\), denoted by \(G_\delta\), is the graph \(G_{\delta} = (V,E_{\delta})\) such that \(uv \in E_{\delta}\) if and only if either \(\deg(u) = \deg(v)\) and \(uv \notin E\) or \(\deg(u) \neq \deg(v)\) and \(uv \in E\).
Vichitkunakorn et al. [10] showed a \(\delta\)-complement variant of the Nordhaus-Gaddum-type relation as follows.
Theorem 6 ([10]). For \(n \geq 4\), let \(G\) be a graph of \(n\) vertices. Let \(d_1, d_2, \dots, d_m\) be degrees of vertices in \(G\). Partition \(V(G)\), by vertex degrees, into \(m\) non-empty subsets \(V_{d_i}\). Then, \[2 \cdot \sqrt{\max_{1 \leq i \leq m} \{ \lvert V_{d_i} \rvert \} } \leq \chi(G) + \chi(G_{\delta}) \leq m+n,\] and \[\max_{1 \leq i \leq m} \{ \lvert V_{d_i} \rvert \} \leq \chi(G) \cdot \chi(G_{\delta}) \leq \left(\frac{m+n}{2}\right)^2.\]
To the best of the authors’ knowledge, other works on Nordhaus-Gaddum-type relations over other invariants of a graph and its \(\delta\)-complement are yet to be found.
Before showing the bounds on the sum and product of the minimum degrees of a graph and its \(\delta\)-complement, we will show a significant theorem first.
Theorem 7. Let \(G\) be a graph of \(n\) vertices. Let \(k \in \mathbb{N}\) be such that \(\binom{k}{2} < n \leq \binom{k+1}{2}\). If \(\delta(G_{\delta}) = n - p\) where \(p\leq n\), then \[\delta(G) \leq n - k + p - 1.\]
Proof. Assume \(G\) is a graph of \(n\) vertices such that \(\delta(G_{\delta}) = n - p\) where \(p\leq n\). Partition \(V(G)\) into \(m\) subsets by degrees in \(G\) as \(V_{r_1}, V_{r_2}, \dots, V_{r_m}\) such that \(r_1 < r_2 < \cdots < r_m.\) This means for any vertex \(\upsilon \in V_{r_i} \subseteq V(G)\), we have \(\deg_{G}(\upsilon) = r_i\), for all \(i = 1, 2, \dots, m\).
Let \(v \in V_{r_i}\). We have \(\deg_{G_{\delta}}(v) \geq n - p.\) Write \(\deg_{G}(v) = a + b\) where \(a\) is the number of vertices of different degrees as \(v\) whom \(v\) is adjacent to in \(G\), and \(b\) is the number of vertices of the same degree as \(v\) whom \(v\) is adjacent to in \(G\).
Since \(\deg_{G_\delta}(v) \geq n - p,\) there are at most \(p-1\) vertices of the same degree as \(v\) such that \(v\) is adjacent to in \(G.\) This will get \(b \leq p - 1.\) Also, it is clear that \(a \leq n - \lvert V_{r_i} \rvert.\) Thus, \[r_{i} = \deg_{G}(v) = a + b \leq n - \lvert V_{r_i} \rvert + p - 1.\] This implies that \[\lvert V_{r_i} \rvert \leq n - r_{i} + p - 1.\]
We are now going to prove that \(\delta(G) \leq n - k + p - 1\). If \(p \geq k,\) then we are done. Assume \(p < k.\) Suppose to the contrary that \(\delta(G) > n - k + p - 1.\) This means \(r_{i} > n - k + p - 1\). This will get \[\begin{align} \begin{aligned} n &\leq \lvert V_{n - k + p} \rvert + \lvert V_{n - k + p + 1} \rvert + \dots + \lvert V_{n - 2} \rvert + \lvert V_{n - 1} \rvert\\ &\leq (k-1) + (k-2) + \dots + (p + 1) + p\\ &= \binom{k}{2} - \binom{p}{2}. \end{aligned} \end{align}\] But since \(n > \binom{k}{2},\) this is a contradiction. Therefore, \(\delta(G) \leq n - k + p - 1 .\) ◻
The result is then used to get bounds on \(\delta(G) + \delta(G_{\delta})\) as follows.
Theorem 8. Let \(G\) be a graph of \(n\) vertices. Let \(k \in \mathbb{N}\) be such that \(\binom{k}{2} < n \leq \binom{k+1}{2}\). Then, \[0 \leq \delta(G) + \delta(G_{\delta}) \leq 2n - k - 1.\] Moreover, for \(n\neq 2\), the left-hand side equality is achieved if \(G\) contains exactly one isolated vertex. For all \(n\), the right-hand side equality is achieved if \(G\) is a complete multipartite graph \(K_{1,2, \dots, l-1, l+1, \dots, k-1, k}\) where \(l = \sum_{i=1}^{k} i - n\).
Proof. The left-hand side inequality is trivial. For \(n\neq 2\), the equality is achieved if \(G\) contains exactly one isolated vertex. This vertex will not be adjacent to any other vertices in \(G_{\delta}\), hence \(\delta(G) = \delta(G_{\delta}) = 0\).
From Theorem 7, we can get the upper bound by adding up \(\delta(G)\) and \(\delta(G_{\delta}).\) For each \(n\), if \(G\) is a complete multipartite graph \(K_{1,2, \dots, l-1, l+1, \dots, k-1, k}\) where \(l = \sum_{i=1}^{k} i - n\), then the minimum degree of \(G\) in this case is \(\sum_{i=1}^{l-1} i + \sum_{i = l+1}^{k-1} i = n - k\). Since \(G_{\delta}\) is a complete graph, we get \(\delta(G_{\delta}) = n-1.\) Hence, \(\delta(G) + \delta(G_{\delta}) = 2n-k-1\). This gives the right-hand side equality. ◻
The additive upper bound from Theorem 8 can also imply the multiplicative upper bound as the following.
Theorem 9. Let \(G\) be a graph of \(n\) vertices. Let \(k \in \mathbb{N}\) be such that \(\binom{k}{2} < n \leq \binom{k+1}{2}\). Then, \[0 \leq \delta(G) \cdot \delta(G_{\delta}) \leq \left( \frac{2n-k-1}{2} \right)^2.\] Moreover, the left-hand side equality is achieved if \(G = nK_1\).
Proof. The lower bound is obvious. For all \(n\), the bound is attained when \(G = nK_1\) as \(\delta(G)=0\). By Theorem 8, we have \(\delta(G) + \delta(G_{\delta}) \leq 2n-k-1.\) By AM-GM inequality, we get \[\delta(G) \cdot \delta(G_{\delta}) \leq \left( \frac{2n-k-1}{2} \right)^2,\] as desired. ◻
Theorem 8 can also imply the Nordhaus-Gaddum-type relation over the maximum degrees of \(G\) and \(G_{\delta}\), using the following lemma.
Lemma 10 ([7]). Let \(G\) be a graph. Then, \(\overline{G_{\delta}} \cong (\overline{G})_{\delta}\).
Theorem 11. Let \(G\) be a graph of \(n\) vertices. Let \(k \in \mathbb{N}\) be such that \(\binom{k}{2} < n \leq \binom{k+1}{2}\). Then, \[k - 1 \leq \Delta(G) + \Delta(G_{\delta}) \leq 2n - 2.\] Moreover, the left-hand side equality is achieved if \(G\) is a union of complete graphs \(\sum_{i = 1}^{l-1} K_i + \sum_{i = l+1}^{k} K_i\) where \(l = \binom{k+1}{2} - n.\) For \(n\neq 2\), the right-hand side equality is achieved if \(G = K_{1,n-1}.\)
Proof. Let \(v \in V(G).\) Clearly, \(\deg_{\overline{G}}(v) = (n-1) - \deg_{G}(v).\) This will get \[\begin{align} \label{maxdeg95g} \Delta(G) = (n-1) - \delta(\overline{G}). \end{align}\tag{1}\] In the same way, by Lemma 10, we get \[\begin{align} \label{maxdeg95g95delta} \Delta(G_{\delta}) = (n-1) - \delta(\overline{G_{\delta}}) = (n-1) - \delta((\overline{G})_{\delta}). \end{align}\tag{2}\] Adding up (1 ) and (2 ) together, we have \[\begin{align} \Delta(G) + \Delta(G_{\delta}) = 2(n-1) - ( \delta(\overline{G}) + \delta((\overline{G})_{\delta}) ). \end{align}\] By Theorem 8, we can conclude that \[k - 1 \leq \Delta(G) + \Delta(G_{\delta}) \leq 2(n-1).\]
Furthermore, the left-hand side equality is achieved when \(G\) is a union of complete graphs \(\sum_{i = 1}^{l-1} K_i + \sum_{i = l+1}^{k} K_i\) where \(l = \binom{k+1}{2} - n.\) Clearly, \(\Delta(G) = k-1\). Since \(G\) is a union of complete graphs of distinct orders, \(G_{\delta} = nK_1\) and \(\Delta(G_{\delta}) = 0\). For \(n\neq 2\), the right-hand side equality is achieved when \(G = K_{1,n-1}\). Since \(G_\delta = K_n\), we have \(\Delta(G) = \Delta(G_\delta)=n-1\). ◻
Theorem 12. Let \(G\) be a graph of \(n\) vertices. Then \[0 \leq \Delta(G) \cdot \Delta(G_{\delta}) \leq (n-1)^2.\] Moreover, the left-hand side equality is achieved if \(G=K_n\). For \(n\neq 2\), the right-hand side equality is achieved if \(G=K_{1,n-1}\).
Proof. Since \(0 \leq \deg_{G}(v) \leq n-1\), both bounds are obvious. When \(G=K_n\), we have \(\Delta(G_\delta)=0\). For \(n\neq 2\), if \(G=K_{1,n-1}\), we have \(G_\delta = K_n\). Hence, \(\Delta(G)=\Delta(G_\delta)=n-1\). ◻
Remark 13. We have \(\delta(G)+\delta(G_{\delta}) = \Delta(G) + \Delta(G_{\delta}) = 1\) and \(\delta(G)\cdot\delta(G_{\delta}) = \Delta(G) \cdot\Delta(G_{\delta}) = 0\) for any graph \(G\) of \(2\) vertices.
We can also use Theorem 8 and the fact that \(\kappa(G) \leq \lambda(G) \leq \delta(G)\) to derive the bounds on \(\kappa(G)+\kappa(G_{\delta})\) and \(\lambda(G)+\lambda(G_{\delta})\) as follows.
Theorem 14. Let \(G\) be a graph of \(n\) vertices. Let \(k \in \mathbb{N}\) be such that \(\binom{k}{2} < n \leq \binom{k+1}{2}\). Then, \[0 \leq \kappa(G) + \kappa(G_{\delta}) \leq 2n - k - 1,\] and \[0 \leq \lambda(G) + \lambda(G_{\delta}) \leq 2n - k - 1.\] Moreover, for \(n\neq 2\), the left-hand side equalities are achieved if \(G\) contains exactly one isolated vertex. The right-hand side equalities are achieved if \(G = K_{1,2,\dots,l-1,l+1,\dots,k-1,k}\) where \(l = \sum_{i = 1}^{k} i - n\).
Proof. Using Theorem 8 and the fact that \(\kappa(G) \leq \lambda(G) \leq \delta(G)\), the bounds obviously hold.
For \(n\neq 2\), the left-hand side inequalities for both sums are achieved when \(G\) contains exactly one isolated vertex. This vertex remains isolated in \(G_{\delta}\). This means \(G\) and \(G_{\delta}\) are both disconnected. Therefore, \(\kappa(G) = \kappa(G_{\delta}) = 0\) and \(\lambda(G) = \lambda(G_{\delta}) = 0\).
The equalities on the right-hand side of both sums are achieved for all \(n\) when \(G\) is a complete multipartite graph \(G = K_{1,2,\dots,l-1,l+1,\dots,k-1,k}\) where \(l = \sum_{i = 1}^{k} i - n\). Notice that the induced subgraph \(G[S]\) is disconnected if and only if all vertices in \(S\) are from the same partite set. Hence, the least number of vertices to be removed from \(G\) to make \(G\) disconnected is \(n-k\), as the largest partite set of \(G\) is of size \(k\). Therefore, \(\kappa(G) = n - k\). Since \(G\) is a multipartite graph of different partition sizes, \(G_{\delta} = K_n\). So, \(\kappa(G_{\delta}) = n - 1\). This gives \(\kappa(G) + \kappa(G_{\delta}) = 2n-k-1\).
We know that \(n-k=\kappa(G) \leq \lambda(G)\). Let \(v\) be a vertex in the largest partite set of \(G\). Removing all \(n-k\) edges incident to \(v\) makes \(G\) disconnected. Hence, \(\lambda(G)=n-k\). Since \(\lambda(G_\delta)=\lambda(K_n)=n-1\), we have \(\lambda(G) + \lambda(G_\delta) = 2n-k-1\). ◻
Remark 15. We have \(\kappa(G)+\kappa(G_{\delta}) = \lambda(G) + \lambda(G_{\delta}) = 1\) for any graph \(G\) of \(2\) vertices.
Similarly, we use Theorem 9 to get bounds on \(\kappa(G)\cdot\kappa(G_{\delta})\) and \(\lambda(G)\cdot\lambda(G_{\delta})\).
Theorem 16. Let \(G\) be a graph of \(n\) vertices. Let \(k \in \mathbb{N}\) be such that \(\binom{k}{2} < n \leq \binom{k+1}{2}\). Then, \[0 \leq \kappa(G) \cdot \kappa(G_{\delta}) \leq \left( \frac{2n - k - 1}{2} \right)^2,\] and \[0 \leq \lambda(G) \cdot \lambda(G_{\delta}) \leq \left( \frac{2n - k - 1}{2} \right)^2.\] Moreover, the left-hand side equalities are achieved if and only if at least one of \(G\) and \(G_\delta\) is disconnected or contains a single vertex.
Proof. Using Theorem 9 and the fact that \(\kappa(G) \leq \lambda(G) \leq \delta(G)\), the bounds obviously hold. By definition, \(\kappa(G)=\lambda(G)=0\) if and only if \(G\) is disconnected or contains a single vertex. Hence, the left-hand side equalities are achieved if and only if at least one of \(G\) and \(G_\delta\) is disconnected or contains a single vertex. ◻
We gave the Nordhaus-Gaddum-type relations on the minimum degrees, the maximum degrees, the vertex connectivities, and the edge connectivities of a graph and its \(\delta\)-complement. Thirteen out of sixteen bounds are found sharp. Results from a computation on small values of \(n\) show that the three remaining bounds are not sharp for many values of \(n\). We also conjecture that these bounds are only sharp for a finitely many \(n\).
Results on the Nordhaus-Gaddum-type relations on other graph invariants will be interesting. Furthermore, one can also study the Nordhaus-Gaddum-type relations of a graph and its \(\delta'\)-complement, which is defined in [7] where \(G_{\delta'}=\overline{G_\delta}\). There are also other variants of graph complements studied in [8]. It is interesting to study the Nordhaus-Gaddum-type relations of a graph and its other variants of graph complements. In particular, one can study the subgraph complementation or the switching operation on other subsets of vertices.
In addition to the Nordhaus-Gaddum-type relation, the relations between two (or more) different invariants of a graph and its \(\delta\)-complement are also interesting to study. See [11] and the references therein for more examples.
Supakorn Srisawat was supported by Graduate Fellowship (Research Assistant), Faculty of Science, Prince of Songkla University, Contract no. 1-2565-02-028.