Keywords

1 Introduction

Throughout the paper, we deal with simple undirected graphs G, with vertex set \(V(G)=\left\{ 1, \ldots , n\right\} \) and edge set \(E(G) \ne \emptyset .\) Since this graph has n vertices, we say that the graph has order n. We write \(u \sim v\) whenever the vertices u and v are adjacent. The neighborhood of a vertex \(i \in V(G)\), that is, the set of vertices adjacent to i, is denoted by \(N_G(i)\), the degree of i is \(d_G(i)=|N_G(i)|\), \(\varDelta (G) = \max _{i \in V(G)}d_G(i)\) and \(\delta (G) = \min _{i \in V(G)}d_G(i)\). The subgraph of G induced by the vertex subset \(S \subset V(G)\) is denoted by G[S]. The graph G is p-regular when all vertices have the same degree equal to p. A vertex subset \(S \subseteq V(G)\) is \((k,\tau )\)-regular if it induces a k-regular subgraph and \(\forall v\notin S, \; |N_G(v)\cap S|=\tau \). The adjacency matrix \(A_G=\left( a_{i,j}\right) \) is the \(n\times n\) matrix defined by

$$\begin{aligned} a_{i,j}= & {} \left\{ \begin{array}{cl} 1 &{} \text {if } i \sim j, \\ 0 &{} \text {otherwise.} \end{array} \right. \end{aligned}$$

The Laplacian matrix \(L_G = \left( l_{i,j}\right) \) and the signless Laplacian matrix \(Q_G=\left( q_{i,j}\right) \) of the graph G, are the matrices \(L_G=D_G-A_G\) and \(Q_G=D_G+A_G\), respectively, where \(D_G\) stands for the diagonal matrix of order n with the i-th entry equal to the vertex degree \(d_G(i)\). Therefore, \(A_G ,\ L_G\) and \(Q_G\) are real symmetric matrices and then all their eigenvalues are real. These eigenvalues are herein denoted, in nonincreasing order, respectively by \(\lambda _1 \ge \cdots \ge \lambda _n\), \(\mu _1 \ge \cdots \ge \mu _n\) and \(q_1 \ge \cdots \ge q_n\). If G has at least one edge, then \(\lambda _1> 0 > \lambda _n\). From now on we consider only simple undirected graphs with at least one edge which will be called graphs.

Each adjacency eigenvalue of a graph G is main if the corresponding eigenspace contains an eigenvector which is not orthogonal to the all ones vector, otherwise is non-main. From Geršgorin’s theorem, the eigenvalues of \(L_G\) and \(Q_G\) are nonnegative real numbers and since the entries of each row of \(L_G\) sum 0,  then the eigenvalue \(\mu _n=0\) is associated to the all ones eigenvector \(\hat{e}\). The multiplicity of 0, as an eigenvalue of \(L_G\), is equal to the number of connected components of G. Furthermore, G is bipartite if and only if \(q_n=0\). Further basic details about graph spectra can be found in [6, 8]. A vertex subset inducing a 0-regular subgraph is called an independent (or stable) set. A maximum independent set is an independent set of maximum cardinality and its cardinality is called independence number and it is denoted by \(\alpha (G)\).

In [3] it was proved that the problem of finding a maximum cardinality subset of vertices inducing a k-regular subgraph is NP-hard . Throughout this paper, this maximum is denoted by \(\alpha _k(G)\). Note that in the particular case of \(k=0\), \(\alpha _0(G)=\alpha (G)\).

The study of spectral upper bounds on the order of k-regular induced subgraphs (it should be noted that the independent sets are 0-regular induced subgraphs) appear in [3,4,5]. In [1] (see also [11]) an upper bound on the order of induced subgraphs with average degree d (based on adjacency eigenvalues ) was obtained for regular graphs , extending the ratio bound (7) to the general case of maximum k-regular induced subgraphs (when \(k=0\), this bound coincide with the ratio bound). A similar result was obtained in [3], using convex quadratic programming techniques. In [4, 5] the arbitrary graph case is analyzed and upper bounds on the order of k-regular induced subgraphs are presented. In [4], the upper bounds are obtained using adjacency eigenvalues and eigenvectors , namely the least eigenvalue (whether it is non-main) and the corresponding eigenspace. In [5], the upper bound is obtained using a quadratic programming technique jointly with the main angles (see [8] for details) and the induced subgraph just must have average degree d.

The main goal of this paper is to introduce some new spectral upper bounds on the order of k-regular induced subgraphs , making an analytic comparison between them when possible. These new upper bounds are based on adjacency , Laplacian and signless Laplacian eigenvalues . Finally, a few computational experiments are presented.

2 Concepts and Fundamental Results

In this section, we introduce some definitions and we recall the previously obtained results needed for the deductions in the next section. In particular, we survey results concerning to spectral upper bounds on the order of k-regular induced subgraphs .

For arbitrary graphs , consider a graph G of order n with \(V(G)=S\cup S^c\), where \(S\subseteq V(G)\) denotes a vertex subset inducing a k-regular subgraph and \(S^c\) is its complement. The set of edges with just one end vertex in S, that is, the cut set defined by S is denoted \(\partial (S)\). Hence, \(|\partial (S)|=|S|(\bar{d}_S-k)\), where \(\bar{d}_S=\frac{1}{|S|}\displaystyle {\sum _{i\in S}d_G(i)}\).

The next result relates the cardinality of the cut set \(\partial (S)\) to the largest eigenvalue of the Laplacian matrix of a graph G.

Lemma 1

([16]) Let G be a graph of order n and \(S\subseteq V(G)\). Then

$$\begin{aligned} |\partial (S)|\le \mu _1\frac{|S|(n-|S|)}{n}. \end{aligned}$$
(1)

Another relationship involving the largest Laplacian eigenvalue and the least adjacency eingenvalue of a graph G is (see [8]).

$$\begin{aligned} \delta (G)-\lambda _n\le \mu _1\le \varDelta (G)-\lambda _n. \end{aligned}$$
(2)

Now we consider some relationships involving signless Laplacian eigenvalues . Assuming that G is a connected graph of order n, according to [7], the least eigenvalue of \(Q_G\) is zero if and only if G is bipartite and, in that case, zero is a simple eigenvalue . They also proved that

$$\begin{aligned} 2\delta (G) \le q_1 \le 2\varDelta (G). \end{aligned}$$
(3)

Moreover, according to [9],

$$\begin{aligned} q_n < \delta (G). \end{aligned}$$
(4)

From Weyl’s inequalities we have an improvement of inequalities (3) and we state relationships between signless Laplacian and adjacency eigenvalues .

$$\begin{aligned} \delta (G)+\lambda _1\le q_1\le \varDelta (G)+\lambda _1 \end{aligned}$$
(5)

and

$$\begin{aligned} \delta (G)+\lambda _n\le q_n\le \varDelta (G)+\lambda _n. \end{aligned}$$
(6)

We now present some spectral upper bounds on the size of k-regular induced subgraphs starting with the particular case of \(k=0\), for which we consider only the ones most related with this work.

2.1 Bounds on \(\alpha (G)\)

In the case of regular graphs , the well known ratio bound, obtained by Hoffman (unpublished) and presented by Lovász in [14] can be stated by the following theorem where, for the last statement, the necessary condition was proved in [12] and the sufficient condition was proved in [2].

Theorem 1

([2, 12, 14]) If G is a regular graph of order n, then

$$\begin{aligned} \alpha (G)\le n\frac{-\lambda _n}{\lambda _1-\lambda _n}. \end{aligned}$$
(7)

Furthermore, the cardinality of an independent set S attains the upper bound if and only if S is \((0,\tau )\)-regular, with \(\tau =-\lambda _n\).

The ratio bound (7) was extended by Haemers for arbitrary graphs , according to the following theorem.

Theorem 2

([11]) If G is a graph of order n, then

$$\begin{aligned} \alpha (G)\le \frac{-n\; \lambda _n\; \lambda _1}{\delta ^2(G)-\lambda _n\; \lambda _1}. \end{aligned}$$
(8)

The next spectral upper bound based on the largest Laplacian eigenvalue was independently deduced in [10, 15].

Theorem 3

([10, 15]) If G is a graph of order n, then

$$\begin{aligned} \alpha (G) \le n \frac{\mu _1 - \delta (G)}{\mu _1}. \end{aligned}$$
(9)

2.2 Bounds on \(\alpha _k(G)\)

Cardoso, Kamińsky and Lozin in [3] introduced the following family of convex quadratic programming problems:

$$\begin{aligned} \upsilon _k(G)=\max _{x \ge 0}2 \hat{e}^Tx - \frac{\tau }{k+\tau }x^T\left( \frac{A_G}{\tau }+I_n\right) x, \end{aligned}$$
(10)

where \(\hat{e}\) is the all ones vector, \(I_n\) the identity matrix of order n, \(k \in \mathbbm {N}\cup \{0\}\) and \(\tau =-\lambda _n\) and they proved that \(\alpha _k(G)\le \upsilon _k(G)\), where \(\alpha _k(G)\) is the cardinality of a vertex subset inducing a k-regular subgraph of maximum order. In fact, in [3], the obtained result was stated as follows.

Theorem 4

([3]) Let G be a graph and k a non-negative integer. If \(S \subseteq V (G)\) induces a subgraph of G with average degree k, then \(|S| \le \upsilon _k(G)\). The equality holds if and only if \(\tau + k \le |N_{G}(v)\cap S| \;\;\forall v \notin S\).

Considering the particular case of regular graphs we have the following theorem, where the upper bound was obtained in [11] and the last statement was proved in [3].

Theorem 5

([3, 11]) If G is a p-regular graph of order n, then

$$\begin{aligned} \alpha _k(G) \le n \frac{k-\lambda _n}{p-\lambda _n}. \end{aligned}$$
(11)

Furthermore, the equality holds if and only if there exists \(S \subseteq V(G)\) which \((k,k+\tau )\)-regular, with \(\tau =-\lambda _n\). In this case, \(\alpha _k(G)=|S|=n \frac{k-\lambda _n}{p-\lambda _n}\).

In [4], considering the quadratic program not necessary convex (10), with \(\tau >0\), it was proved that

$$\begin{aligned} \alpha _k(G)\le \lambda _{max}(A_{{G}^c})+k+1, \end{aligned}$$
(12)

where \({G}^c\) denotes the complement of the graph G, that is, the graph such that \(V(G^c)=V(G)\) and \(E(G^c)=\{ij: ij \notin E(G)\}\). Furthermore, the following upper bound was obtained.

Theorem 6

([4]) Consider a graph G such that \(\lambda _{min}(A_G) = \lambda _n = \cdots = \lambda _{n-(p-1)}\) is a non-main eigenvalue with multiplicity p. Assuming that the eigenvectors \(\hat{u}_1, \ldots , \hat{u}_n\), associated to the eigenvalues \(\lambda _1, \ldots , \lambda _n\), respectively, are unitary and pairwise orthogonal, then

$$\begin{aligned} \alpha _k(G)\le & {} \sum _{j=1}^{n-p}{\frac{-\lambda _n+k}{-\lambda _n+\lambda _j}(\hat{e}^T\hat{u}_j)^2}. \end{aligned}$$
(13)

Later, in [5], using a quadratic programming technique jointly with the main angles of G, the upper bound (13) was improved as follows.

Theorem 7

([5]) Let G be a graph of order n, and let S be a set of vertices which induces a k-regular subgraph of G \((0 \le k \le n - 1)\). If \(t > -\lambda _n\) then

$$\begin{aligned} \alpha _k(G)\le h^G_k(t), \end{aligned}$$
(14)

where \(h^G_k(t)=(k+t)\left( 1-\frac{P_{G^c}(t-1)}{(-1)^n P_G(-t)}\right) \) and \(P_G(x)=\det (xI-A)\).

3 Upper Bounds Based on the Spectrum of \(A_G\), \(L_G\) and \(Q_G\)

Now it is worth to recall the following theorem obtained by Haemers.

Theorem 8

([11]) Let G be a graph on n vertices of average degree d and let the vertex set of G be partitioned into two sets such that \(G_1\) and \(G_2\) are the subgraphs induced by these two sets. For \(i=1,2\) let \(n_i\) be the number of vertices of \(G_i\), \(d_i\) be the average of vertex degrees of \(G_i\) and let \(\bar{d}_i\) be the average of vertex degrees in G over the vertices of \(G_i\). Then

  1. (i)

    \(\lambda _1\lambda _2 \ge \frac{nd_i d-n_i{\bar{d_i}}^2}{n-n_i} \ge \lambda _1\lambda _n\).

  2. (ii)

    If the equality holds on one of the sides, then \(G_1\) and \(G_2\) are regular and also the degrees in G are constant over the vertices of \(G_1\) and \(G_2\).

As a consequence of this theorem, we have the following corollary.

Corollary 1

If G is a graph of order n, then,

$$\begin{aligned} \alpha _k(G) \le \frac{2k|E(G)|-n\lambda _1 \lambda _n}{\delta (G)^2-\lambda _1 \lambda _n}. \end{aligned}$$
(15)

Proof

Let us consider the vertex partition \(V(G)=S \cup S^c\), where S induces a k regular subgraph of G. Applying Theorem 8-(i), setting \(n_1=|S|\) and \(d_1=k\), we have,

$$\begin{aligned} \frac{nkd-\bar{d_1}^2|S|}{n-|S|} \ge \lambda _1\lambda _n\Leftrightarrow & {} \lambda _1\lambda _n(n-|S|) \le nkd-\bar{d_1}^2|S| \\\Leftrightarrow & {} |S|(\bar{d_1}^2-\lambda _1\lambda _n) \le nkd-n\lambda _1\lambda _n\\\Leftrightarrow & {} |S| \le \frac{nkd-n\lambda _1\lambda _n}{\bar{d_1}^2-\lambda _1\lambda _n}. \end{aligned}$$

Since \(\bar{d_1} \ge \delta \) and \(d=\frac{2|E(G)|}{n}\), the inequality (15) follows. \(\square \)

Notice that, when G is p-regular , \(\lambda _1=\delta (G)\) and \(|E(G)|=\frac{np}{2}\) whereby the upper bound (15) is equal to (11).

The next corollary is a consequence of Lemma 1.

Corollary 2

If G is a graph of order n, then

$$\begin{aligned} \alpha _k(G) \le n\frac{k+\mu _1-\delta (G)}{\mu _1}. \end{aligned}$$
(16)

Proof

Considering a vertex subset \(S\subseteq V(G)\) inducing a k-regular subgraph and taking into account that (as defined before) \(\overline{d_S}=\frac{1}{|S|}\sum _{i \in S}{d_G(i)}\), it follows that \(|\partial (S)|=|S|(\bar{d_S}-k)\). Then applying Lemma 1 we have

$$\begin{aligned} |S|(\bar{d_S}-k) \le \mu _1 \frac{|S|(n-|S|)}{n}\Leftrightarrow & {} \frac{n(\bar{d_S}-k)}{n-|S|} \le \mu _1\\\Leftrightarrow & {} \mu _1|S| \le n \mu _1 -n(\bar{d_S}-k)\\\Leftrightarrow & {} |S|\le n\;\frac{k+\mu _1-\bar{d_S}}{\mu _1}. \end{aligned}$$

Since \(\bar{d}_S\ge \delta (G)\), the inequality (16) follows.\(\square \)

If a graph G is p-regular, from (2) \(\mu _1 + \lambda _n = p\) and we may conclude that the upper bound (16) is equal to (11).

Before the introduction of a new upper bound on the order of k-regular induced subgraphs in function of the largest and the least eigenvalues of the signless Laplacian matrix , it is worth to introduce the following lemma.

Lemma 2

Let G be a graph of order n without isolated vertices. If G is bipartite or \(\delta (G) \ge \frac{\varDelta (G)}{2}\) or \(q_1<4\delta (G)\), then \(4 \delta (G)^2-q_n q_1>0\).

Proof

Let \(\delta =\delta (G)\) and \(\varDelta =\varDelta (G)\).

  1. 1.

    If G is bipartite without isolated vertices, then \(q_n=0\), \(\delta >0\) and therefore, \(4 \delta ^2-q_n q_1>0\).

  2. 2.

    If \(\delta \ge \frac{\varDelta }{2}\), we have \(\delta ^2\ge \frac{\delta \varDelta }{2}\Leftrightarrow 4\delta ^2\ge 2\delta \varDelta \) and, taking into account (3) and (4), since \(q_1\le 2\varDelta \) and \(\delta >q_n\) it follows \(4 \delta ^2-q_n q_1>0\).

  3. 3.

    Finally, if \(q_1<4\delta \), then \(q_1q_n\le 4\delta q_n<4\delta ^2\), that is, \(q_1q_n<4\delta ^2\) and so \(4 \delta ^2-q_n q_1>0\).

\(\square \)

Notice that there are graphs G,  with \(\delta =\delta (G)\), such that \(4\delta ^2-q_nq_1 \le 0\), as it is the case of the graph depicted in Fig. 1 which has \(\delta =2\), \(q_n=1.4991\) and \(q_1=10.8517\).

Fig. 1
figure 1

Graph G, with \(4\delta (G)^2-q_nq_1 \le 0\)

Full size image

Theorem 9

Let G be a graph of order n such that \(4 \delta ^2(G)-q_n q_1>0\). Then

$$\begin{aligned} \frac{2k|E(G)| -n\lambda _1\lambda _n}{\delta ^2(G)-\lambda _1\lambda _n} \le \frac{4|E(G)|( \varDelta (G)+ k)-n q_n q_1}{4 \delta ^2(G)-q_n q_1}. \end{aligned}$$
(17)

Proof

Considering \(\varepsilon =|E(G)|\), \(\delta =\delta (G)\), \(\varDelta =\varDelta (G)\) and assuming that the inequality of (17) holds, we have

$$\begin{aligned} \frac{2k\varepsilon -n\lambda _1\lambda _n}{\delta ^2-\lambda _1\lambda _n} -\frac{\varepsilon (\varDelta +k)-n\frac{q_1}{4}q_n}{\delta ^2-\frac{q_1}{4}q_n}&\le 0\\&\Updownarrow \\ 2k\varepsilon \delta ^2-\frac{q_1}{2}q_nk\varepsilon -n\delta ^2\lambda _1\lambda _n-\delta ^2\varDelta \varepsilon -\delta ^2 k\varepsilon +n\delta ^2\frac{q_1}{4}q_n+\lambda _1\lambda _n \varepsilon \varDelta +\lambda _1\lambda _n\varepsilon k&\le 0\\&\Updownarrow \\ k(\delta ^2\varepsilon -\frac{q_1}{2}q_n\varepsilon +\lambda _1\lambda _n\varepsilon )-n\delta ^2\lambda _1\lambda _n-\delta ^2\varDelta \varepsilon +n\delta ^2\frac{q_1}{4}q_n+\lambda _1\lambda _n\varepsilon \varDelta&\le 0 \end{aligned}$$

Let \(f(k)\,=\,k(\delta ^2\varepsilon \,-\,\frac{q_1}{2}q_n\varepsilon \,+\,\lambda _1\lambda _n\varepsilon )\,-\,n\delta ^2\lambda _1\lambda _n-\delta ^2\varDelta \varepsilon +n\delta ^2\frac{q_1}{4}q_n+\lambda _1\lambda _n\varepsilon \varDelta \). Then,

$$\begin{aligned} f'(k)= & {} \delta ^2\varepsilon -\frac{q_1}{2}q_n\varepsilon +\lambda _1\lambda _n\varepsilon \\= & {} \varepsilon (\delta ^2- \frac{q_1}{2}q_n+\lambda _1\lambda _n). \end{aligned}$$

From (6),

$$ \delta +\lambda _n< q_n \Leftrightarrow \delta ^2+\delta \lambda _n< \delta q_n \Leftrightarrow \delta ^2-\delta q_n+\delta \lambda _n < 0. $$

Since, from (3), \(\frac{q_1}{2}\ge \delta \) and, as it is well known, \(\lambda _1\ge \delta \), it follows that \(\delta ^2-\frac{q_1}{2} q_n+\lambda _1\lambda _n \le \delta ^2-\delta q_n+\delta \lambda _n < 0\), that is, \(f'(k) < 0\). Therefore, f(k) is a decreasing function .

Considering the function f(k) and setting \(k=0\) and \(\varDelta =\delta +\xi \) with \(\xi \) a nonnegative integer we may define the function

$$g(\delta ,\xi )=-n\delta ^2\lambda _1\lambda _n-\delta ^2(\delta +\xi )\varepsilon +n\delta ^2\frac{q_1}{4}q_n+\lambda _1\lambda _n\varepsilon (\delta +\xi ).$$

Then

$$\begin{aligned} \frac{\partial g(\delta ,\xi )}{\partial \xi }= & {} -\delta ^2\varepsilon +\lambda _1\lambda _n\varepsilon \\= & {} \varepsilon (-\delta ^2+\lambda _1\lambda _n)\\< & {} 0. \end{aligned}$$

Therefore, \(g(\delta ,\xi )\) is a decreasing function with respect to \(\xi \). Since \(g(\delta ,0)=-n\delta ^2\lambda _1\lambda _n-\delta ^3\varepsilon +n\delta ^2\frac{q_1}{4}q_n+\lambda _1\lambda _n\varepsilon \delta \) and \(\delta =\varDelta \) it follows that \(\lambda _1=\delta \). Furthermore, from (3), \(\frac{q_1}{2}=\delta \) and from (6), \(q_n=\delta +\lambda _n\). Therefore,

$$\begin{aligned} g(\delta ,0)= & {} -n\delta ^3\lambda _n-\delta ^3\varepsilon +n\frac{\delta ^3}{2}(\delta +\lambda _n)+\lambda _n\varepsilon \delta ^2 \\= & {} -n\delta ^3\lambda _n-\delta ^3\varepsilon +n\frac{\delta ^4}{2}+n\frac{\delta ^3}{2}\lambda _n+\lambda _n\varepsilon \delta ^2. \end{aligned}$$

Finally, since \(\varepsilon =\frac{n\delta }{2}\) we obtain \(g(\delta ,0)= -n\delta ^3\lambda _n-n\frac{\delta ^4}{2}+n\frac{\delta ^4}{2}+n\frac{\delta ^3}{2}\lambda _n+n\frac{\delta ^3}{2}\lambda _n=0 \) and thus, for all nonnegative integers \(\delta \) and \(\xi \), \(g(\delta ,\xi )\le 0\). Therefore, \(f(0) \le 0\) and, since f(k) is a decreasing function , we may conclude that \(f(k) \le 0\) for all k. \(\square \)

As immediate consequence of Corollary 1 and Theorem 9 we have the following corollary.

Corollary 3

If G is a graph of order n, \(\varepsilon \) edges, \(\varDelta =\varDelta (G)\) and \(\delta =\delta (G)\), such that \(4 \delta ^2-q_n q_1>0\), then

$$\begin{aligned} \alpha _k(G) \le \frac{4\varepsilon ( \varDelta + k)-n q_n q_1}{4 \delta ^2-q_n q_1}. \end{aligned}$$
(18)

According to [7], a graph G with n vertices and \(\varepsilon \) edges is regular if and only if \(4\varepsilon =nq_1\). Furthermore, when G is regular its degree is equal to \(\frac{q_1}{2}\). Thus, assuming that G is p-regular , has n vertices and \(\varepsilon \) edges, by Lemma 2 the hypothesis of Corollary 3 is fulfilled and then we may write

$$\begin{aligned} \alpha _k(G)\le & {} \frac{nq_1(p+k-q_n)}{2pq_1-q_nq_1}\;\; (\text {since } \varDelta (G) = \delta (G) = p=\frac{q_1}{2} \text { and } 4\varepsilon =nq_1) \nonumber \\= & {} \frac{n(p+k-q_n)}{2p-q_n}=n \frac{k-\lambda _n}{p-\lambda _n}\;\; (\text {since } q_n-\lambda _n=p). \end{aligned}$$

Therefore, for regular graphs , all the upper bounds (11) (15), (16) and (18) are equal. Notice that there are graphs for which these upper bounds are tight. For instance, if \(G=K_n\) (a complete graph of order n), then \(\lambda _1 = n-1\) and \(\lambda _n=-1\). Thus, if \(S \subseteq V(K_n)\) induces a k-regular subgraph , then \(n\frac{k-\lambda _n}{\lambda _1-\lambda _n}=k+1=|S|.\) Therefore, when G is a complete graph , for each k, the upper bounds (15), (16) and (18) on the cardinality of vertex subsets inducing k-regular subgraphs are all reached. More generally, according to Theorem 5, if G is a regular graph and \(S \subset V(G)\) is a \((k,k+\tau )\)-regular set, with \(\tau =-\lambda _n\), then all the above referred upper bounds are reached.

Throughout the paper, in all the proofs of the presented results, only the average degree in S is used and then, in all the obtained results we may replace k-regular induced subgraph by induced subgraph with average degree k. Moreover, all the obtained results remain valid when we consider positive weights on the edges, assuming in that case that the degree of a vertex v is then the sum of the weights of the edges incident to v.

Table 1 Computational experiments with the upper bounds (15), (16) and (18)
Full size table

4 Computational Experiments and Conclusions

In this section, several computational experiments with the upper bounds (15), (16) and (18) are presented in Table 1. In each row of this table appears the order n, the maximum degree \(\varDelta \), the minimum degree \(\delta \), the degree of a regular induced subgraph k and the computed upper bounds on the order of this induced subgraphs for some of the graphs of the family considered in the Second DIMACS Implementation Challenge (see [13]).

Notice that for the particular case of regular graphs the upper bounds (15), (16) and (18) are all equal. Moreover since, according to the Theorem 9, the upper bound (15) is less or equal than the upper bound (18), it follows that

$$\begin{aligned} \frac{4|E(G)|( \varDelta (G)+ k)-n q_n q_1}{4 \delta (G)^2-q_n q_1} \ge \min \left\{ \frac{2k|E(G)| -n\lambda _1\lambda _n}{\delta ^2-\lambda _1\lambda _n}, n\frac{k+\mu _1-\delta }{\mu _1}\right\} . \end{aligned}$$

Concerning the comparison between the upper bounds (15) and (16) and also between (16) and (18), the computational results presented in the Table 1 show that none of them is always better than the others.

In fact, regarding the upper bounds (15) and (16), for \(k=0, 1, 2\), the former is better than the later. However, for much greater values of k, there are several graphs for which the upper bound (16) is better than (15). Finally, it should be noted that for the graphs MANN-a9 and MANN-a27 for \(k=0,1,2\) the upper bound (18) is better than the upper bound (16).