Clive Elphick, Pawel Wocjan^a

^aDepartment of Electrical Engineering and Computer Science University of Central Florida, Orlando, USA.

clive.elphick@gmail.com, wocjan@eecs.ucf.edu

In this paper, we define and compare three new measures of graph irregularity. We use these measures to tighten upper bounds for the chromatic number and the Colin de Verdiere parameter. ` We also strengthen the concise Turan theorem for irregular graphs and investigate to what extent ´ Turan's theorem can be similarly strengthened for generalized ´ r-partite graphs. We conclude by relating these new measures to the Randic index and using the measures to devise new normalised ´ indices of network heterogeneity.

Keywords: graph irregularity, clique, chromatic number, Randic index, network heterogeneity Mathematics Subject Classification : 68R10

1. Introduction

Many results in extremal graph theory are exact only for some regular graphs. In this paper we strengthen various bounds, using two degree based measures of irregularity and a spectral measure of irregularity, so that they also become exact for some irregular graphs.

Let G be a simple and undirected graph with vertex set V with |V | = n, edge set E with |E| = m, t triangles, clique number ω, chromatic number χ and vertex degrees ∆ = d¹ ≥ d² ≥ ... ≥ dⁿ = δ. Let µ denote the largest eigenvalue of the adjacency matrix of G and let d denote the average degree.

Existing measures of irregularity include the following. Collatz and Sinogowitz [7] proposed a spectral measure, namely µ − d. Bell [2] proposed a variance measure, namely var(G) = P(dⁱ − d) ²/n = P(d 2 i /n)−d 2 and identified the most irregular graphs for both measures. He also showed

Received: 15 October 2013, Revised: 16 March 2014, Accepted: 4 April 2014.

that the measures are incomparable for some pairs of graphs. Albertson [1] used the measure P ij∈E |dⁱ − d^j |, which has found applications in chemical graph theory. Nikiforov [27] used the measure s(G) = P i |dⁱ − d|. These measures are all greater than or equal to zero, with equality for regular graphs, and can be described as additive measures of irregularity. It is worth noting that var(G) = var(G) and s(G) = s(G), where G denotes the complement of G. The measures defined in this paper are all greater than or equal to one, with equality for regular graphs, and can be described as multiplicative measures of irregularity.

In Section 2 we define and compare the new measures; in Section 3 we use the measures to strengthen upper bounds for the chromatic number; in Section 4 we strengthen Turan's Theorem ´ for irregular graphs; in Section 5 we apply the new measures to generalised r−partite graphs; in Section 6 we bound a graph's radius, Harmonic index and Randic index; and we conclude with ´ bounds for the new measures and new indices of network heterogeneity.

2. Measures of irregularity

Our first measure of irregularity, ν, was introduced by Edwards [13]. He defined a parameter cv, which he termed the "vertex degree coefficient of variation" as follows:

\[\nu = 1 + c_v^2 = \frac{n \sum_{i \in V} d_i^2}{4m^2}.\]

Edwards [13] showed that c^v = 0 if and only if a graph is regular, so ν ≥ 1, with equality only for regular graphs. c^v is the ratio of the standard deviation to the mean of the vertex degrees, which follows the usual definition of a coefficient of variation.

Our second measure of irregularity, , is defined similarly using an "edge degree coefficient of variation" as follows:

\[\epsilon = 1 + c_e^2 = \frac{n \sum_{ij \in E} \sqrt{d_i d_j}}{2m^2}.\]

It follows from Proposition 2.8 in Favaron, Maheo and Sacl ´ e [15] that ´ ≥ 1, with equality only for regular graphs.

Finally we define a spectral measure of irregularity as follows:

\[\beta = \frac{\mu}{d} = \frac{\mu n}{2m}.\]

It is well known that µ ≥ d, with equality only for regular graphs. Therefore β ≥ 1, with equality only for regular graphs.

We can compare these bounds as follows. Hofmeister [19] proved that µ ² ≥ P i∈V d 2 i /n and Favaron et al [15] have proved that µ ≥ P ij∈E p didj/m. It is therefore straightforward that:

\[\beta^2 \ge \nu\] and \(\beta \ge \epsilon\).

We can also show that ν ≥ , as follows:

\[\nu = \frac{n \sum_{i \in V} d_i^2}{4m^2} = \frac{n \sum_{ij \in E} (d_i + d_j)}{4m^2} \ge \frac{n \sum_{ij \in E} \sqrt{d_i d_j}}{2m^2} = \epsilon.\]

Finally, for most but not all irregular graphs, \(\epsilon^2 > \nu\).

3. Upper bounds for the Chromatic Number

Theorem 3.1. Let G be a graph with irregularity \(\nu\). Then

\[\chi(G) \le \frac{n}{\nu}.\]

Proof. Our proof follows that in Deng et al [10], which uses contradictions for \(\chi(G) = 2\), \(\chi(G) = 3\) and \(\chi(G) \ge 4\).

Case 1: \(\chi(G) = 2\).

Note that:

\[\frac{n}{\nu} = \frac{4m^2}{\sum_{i \in V} d_i^2} = \frac{4m^2}{\sum_{ij \in E} (d_i + d_j)} < \chi(G) = 2 = \frac{4m^2}{\sum_{ij \in E} (m + m)}\]

which implies some degrees are greater than m, a contradiction.

Case 2 : \(\chi(G) = 3\).

Let pq be an edge which has the largest weight of \((d_i + d_j)\) for \(ij \in E\). Then:

\[\chi(G) = 3 > \frac{n}{\nu} = \frac{4m^2}{\sum_{ij \in E} (d_i + d_j)} \ge \frac{4m}{(d_p + d_q)} \ge \frac{4(d_p + d_q - 1)}{d_p + d_q} = 4 - \frac{4}{d_p + d_q}.\]

Deng et al [10] demonstrate that this inequality leads to a contradiction.

Case 3 : \(\chi(G) \geq 4\).

Let pq be an edge which has the largest weight of \((d_i + d_j)\) for \(ij \in E\) and consequently the smallest weight of \(\frac{1}{d_i + d_j}\). Deng et al [10] have proved that:

\[\frac{2}{d_n + d_a} > \frac{1}{\chi(G) - 1}.\]

Therefore:

\[\chi(G) > \frac{n}{\nu} = \frac{4m^2}{\sum_{i:i \in F} (d_i + d_i)} \ge \frac{4m}{(d_p + d_q)} > \frac{2m}{\chi(G) - 1}.\]

This implies \(2m < \chi(G)(\chi(G)-1)\). However for all graphs \(2m \ge \chi(G)(\chi(G)-1)\), since there must be at least one edge between each pair of color classes.

This bound strengthens a bound due to Deng et al [10], who recently proved that χ(G) ≤ 2H(G), where H(G) is the Harmonic index. We discuss this index and the Randic index, R(G), in ´ Section 6.

This bound is sometimes better than Wilf's well known bound (χ(G) ≤ 1 + µ). For example for the Star graph on n vertices, the Wilf bound equals 1 + ^√ n − 1 and this new bound equals 4 − 4/n.

Hansen and Vukicevic [18] proved that ´ χ(G) ≤ 2R(G). We can demonstrate that this bound is never better than Wilf's bound because:

\[\chi(G) \le \mu + 1 \le \frac{n}{\beta} \le \frac{n}{\epsilon} \le 2R(G).\]

We show that n/ ≤ 2R(G) in Section 6. The only new inequality is therefore that:

\[\mu + 1 \le \frac{n}{\beta} = \frac{2m}{\mu}.\]

We can prove this inequality using the following lemma.

Lemma 3.1. Let G be a graph with chromatic number χ. Then:

\[\chi(\chi - 1) \le \mu(\mu + 1) \le 2m.\]

Proof. We have noted above that χ(χ − 1) ≤ 2m and χ ≤ 1 + µ. In Section 3.1 below we use that µ ² ≤ 2m(ω − 1)/ω. Therefore:

\[\mu^2 \leq \frac{2m(\omega-1)}{\omega} = \frac{2m\omega(\omega-1)}{\omega^2} \leq \frac{2m\chi(\chi-1)}{\omega^2} \leq \frac{4m^2}{\omega^2}.\]

Therefore:

\[\mu(\mu+1) \le \frac{2m(\omega-1)}{\omega} + \frac{2m}{\omega} = 2m.\]

3.1. Colin de Verdiere parameter `

The Colin de Verdiere parameter, ` λ(G), is the basis for the profound conjecture that χ(G) ≤ 1 + λ(G). There is extensive literature on this conjecture, for example by Holst et al [20] and Goldberg [16]. Several upper bounds for χ(G) are not upper bounds for 1 + λ(G). For example, the Petersen graph demonstrates that λ 6≤ µ and K4,⁵ demonstrates that λ 6≤ n − α, where α denotes the independence number, which is the size of the maximum set of vertices, no two of which are adjacent.

We can, however, use β to create a new upper bound for λ as follows.

Theorem 3.2. Let G be a connected graph with irregularity β. Then:

\[\lambda(G) \le \frac{n}{\beta} - 1 = \frac{2m}{\mu} - 1.\]

Proof. One of the deep properties of λ is that it is minor-monotone, from which it follows immediately that ω ≤ 1 + λ. (A graph parameter φ(G) is called minor-monotone if φ(H) ≤ φ(G) for any minor H of G.)

Pendavingh [30] has proved that if G 6= K3,³ is a connected graph, then

\[\lambda(\lambda+1) \le 2m.\]

We therefore need to consider two options. If G = K3,³ then (eg see Goldberg) λ = 4 < (2m/µ) − 1 = 18/3 − 1 = 5.

If G 6= K3,³ then we use a result due to Nikiforov [26], and conjectured by Edwards and Elphick [14], that:

\[\mu^2 \le \frac{2m(\omega - 1)}{\omega}.\]

Therefore:

\[\mu^2 \le \frac{2m(\omega - 1)}{\omega} \le \frac{2m\lambda}{\lambda + 1} \le \frac{4m^2}{(\lambda + 1)^2},\]

and consequently:

\[\lambda \le \frac{2m}{\mu} - 1 = \frac{n}{\beta} - 1.\]

4. Turan's Theorem for irregular graphs ´

Turan's Theorem, proved in 1941, is a fundamental result in extremal graph theory. In its ´ concise form it states that:

\[2m \le \frac{(\omega - 1)n^2}{\omega}.\]

Observe that the result, due to Nikiforov above, that µ ² ≤ 2m(ω − 1)/ω, is equivalent to the following strengthening of the concise Turan theorem: ´

Theorem 4.1.

\[2m \le \frac{(\omega - 1)n^2}{\omega \beta^2}.\]

Due to the bounds β ² ≥ ν and β ≥ we obtain:

(i) \[2m \leq \frac{(\omega - 1)n^2}{\omega \nu}\] and (ii) \(2m \leq \frac{(\omega - 1)n^2}{\omega \epsilon^2}\).

We provide a non-spectral proof of the bound (i) because it leads to a corollary. Before presenting this proof we explain briefly the intuition underlying the above inequalities. Theorem 4.1 is unusual because it involves m on both sides. A useful way to interpret the theorem is that β, ν and are measures of graph irregularity. Therefore all graphs with a given clique number and, for example, irregularity as measured by ν ≥ 2 have a maximum number of edges that is at most half of the number implied by Turan's Theorem. ´

Proof. This non-spectral proof is based on a 1962 proof of the concise Turan Theorem due to ´ Moon and Moser [24], as written up in an award winning paper by Martin Aigner entitled "Turan's ´ Graph Theorem".

Let C^h denote the set of h-cliques in G with |Ch| = ch. So for example, c¹ = n, c² = m, c³ = t etc. For A ∈ C^h let d(A) equal the number of (h + 1) cliques containing A. Moon and Moser [24] proved that:

\[\frac{c_{h+1}}{c_h} \ge \frac{h^2 c_h / c_{h-1} - n}{h^2 - 1}, \quad \text{for } h \ge 2.\] (1)

They also proved that:

\[nc_h + (h^2 - 1)c_{h+1} \ge \sum_{B \in C_{h-1}} d(B)^2\]

so with h = 2 this becomes:

\[nm + 3c_3 \ge \sum_{i=1}^n d_i^2\], or equivalently \[\frac{c_3}{c_2} = \frac{c_3}{m} \ge \frac{\left(\sum d_i^2/m\right) - n}{3}.\] (2)

Now define θ as follows:

\[\frac{(\theta - 2)n}{\theta} = \frac{\sum d_i^2}{m} - n \tag{3}\]

which is equivalent to:

\[2m = \frac{(\theta - 1)n^2}{\theta \nu}.\]

This definition of θ differs from that in [24] and enables the strengthening of Moon and Moser's proof. Combining (2) and (3) we have:

\[\frac{c_3}{c_2} \ge \frac{\sum d_i^2/m - n}{3} = \frac{(\theta - 2)n}{3\theta}.\] (4)

To prove Theorem 4.1 (i) we need to show that θ ≤ k−1 for graphs without k-cliques. Consider the claim:

\[\frac{c_{h+1}}{c_h} \ge \frac{(\theta - h)n}{\theta(h+1)}, \quad \text{for } h \ge 2.\] (5)

For h = 2, this is inequality (4). We therefore use induction on h and (1) as follows:

\[\frac{c_{h+1}}{c_h} \geq \frac{h^2 c_h / c_{h-1} - n}{h^2 - 1} \geq \frac{h^2 (\theta - h + 1) n / (\theta h) - n}{h^2 - 1}\] \[= \frac{(\theta - h)(h - 1)n}{\theta (h^2 - 1)} = \frac{(\theta - h)n}{\theta (h + 1)}\]

as claimed in (5). Now if G contains no k-clique then c^k = 0 and we infer θ ≤ h = k −1 from (5). We have not attempted a non-spectral proof of the bound.

4.1. Number of k-cliques

Moon and Moser [24] proved that if t is the number of triangles in a graph, then:

\[t \ge \frac{m(4m - n^2)}{3n}.\]

In the following corollary we strengthen this bound for irregular graphs. This corollary is exact for some irregular complete tripartite and Turan graphs. ´

Corollary 4.1. Let G be a graph with irregularity ν. Then:

\[t \ge \frac{m(4m\nu - n^2)}{3n}.\]

Proof. From inequality (4), we know that:

\[t \ge \frac{nm(\theta - 2)}{3\theta} = \frac{\sum d_i^2 - nm}{3} = \frac{4\nu m^2 - n^2 m}{3n}.\]

This approach can be continued for larger cliques. For example, we know from (5) that:

\[c_4 \ge \frac{tn(\theta - 3)n}{4\theta} \ge \frac{m(4m\nu - n^2)}{12}(1 - \frac{3}{\theta}) = \frac{m(4m\nu - n^2)(3m\nu - n^2)}{6n^2}.\]

4.2. Remarks

Theorem 4.1 is exact for all complete bipartite graphs. The full form of Turan's theorem states ´ that m(G) ≤ m(Tr(n)), where Tr(n) is the complete r-partite graph of order n whose classes differ by at most one, with equality holding only if G = Tr(n). It is not the case that for all irregular graphs m(G) ≤ m(Tr(n))/ν or that m(G) ≤ m(Tr(n))/² or that m(G) ≤ m(Tr(n))/β² .

Turan's theorem can be further strengthened by using more complex lower bounds for ´ µ. For example, if tⁱ denotes the sum of the degrees of the vertices adjacent to vⁱ , then Yu, Lu and Tian [32] have proved that:

\[\mu^2 \geq \frac{\sum t_i^2}{\sum d_i^2} \geq \frac{\sum d_i^2}{n} \geq \frac{4m^2}{n^2}.\]

Thus if we define:

\[\alpha = \frac{n^2 \sum t_i^2}{4m^2 \sum d_i^2} \ge \nu\]

it follows, as above, that:

\[2m \le \frac{(\omega - 1)n^2}{\omega \alpha} \le \frac{(\omega - 1)n^2}{\omega \nu}.\]

5. Generalized r-partite graphs

In a series of papers, Bojilov and others have generalized the concept of an r-partite graph. They define the parameter φ to be the smallest integer r for which V (G) has an r-partition:

\[V(G) = V_1 \cup V_2 \cup \ldots \cup V_r\], such that \(d(v) \le n - |V_i|\),

for all v ∈ Vⁱ and for i = 1, 2, . . . , r.

It is notable that φ depends only on the degrees of G, and not on the adjacency matrix of G. Indeed, φ is defined for any set of n integers aⁱ , where 0 ≤ aⁱ ≤ n − 1, which may or may not correspond to the degrees of a graph.

Theorem 2.1 in [3] proves that φ is a lower bound for the clique number and the greedy Algorithm 1 and Theorem 3.1 in [3] demonstrate that φ can be computed in linear time. For d-regular graphs, Theorem 4.4 in [3] proves that:

\[\phi = \left\lceil \frac{n}{n-d} \right\rceil.\]

Khadzhiivanov and Nenov [12] have proved that φ satisfies Turan's Theorem: ´

\[2m \le \frac{(\phi - 1)n^2}{\phi} \le \frac{(\omega - 1)n^2}{\omega}.\] (6)

Theorem 4.1 in [3] provides a simpler proof of (6). The study of φ has therefore led to a novel proof of the concise version of Turan's Theorem, which also demonstrates that this famous result ´ is in fact a function only of the degrees of a graph rather than its adjacency matrix.

It is of interest to see to what extent (6) can be strengthened in a similar way to Theorem 4.1 For example, Bojilov and Nenov [4] have strengthened (6) as follows:

\[2m \le \frac{(\phi - 1)n^2}{\phi\sqrt{\nu}}. (7)\]

Inequality (7) is further strengthened in Theorem 5.4 in [3] where it is shown that:

\[\phi \ge \frac{n}{n - d_{\phi}^*} \ge \frac{n}{n - d_{\phi-1}^*} \ge \dots \ge \frac{n}{n - d_1^*}\]

where

\[d_r^* = \sqrt[r]{\sum d_i^r/n}.\]

Observe that inequality (7) is equivalent to r = 2 in this chain of inequalities.

It is therefore natural to ask whether 2m ≤ (φ − 1)n ²/φν? The answer is no, because, for example, the graph in Figure 1 provides a counter-example.

Figure 1. Graph751 on 7 vertices with degree sequence (5, 5, 2, 2, 2, 1, 1), φ = 2 and ω = 3

There are also various spectral lower bounds for ω of which the simplest, due to Cvetkovic [8], is:

\[\omega \ge \frac{n}{n-\mu}.\tag{8}\]

The graph in Figure 2 is an example of a graph which does not satisfy (8), with ω replaced by φ. It also demonstrates that a variety of other spectral lower bounds for ω are not lower bounds for φ. Furthermore, φ does not satisfy the Motzkin-Straus inequality.

Figure 2. Graph on 7 vertices with degree sequence (4, 4, 4, 3, 3, 3, 3), φ = 2, µ = 3.503

Conjecture 1. We have, however, been unable to find a counter-example to the following conjecture:

\[2m \le \frac{(\phi - 1)n^2}{\phi \epsilon}.\]

6. Bounds on graph radius, Harmonic and Randic indices ´

The Randic index is used in organic chemistry, with bonds between atoms represented by edges ´ in a graph. The Randic index is defined as: ´

\[R(G) = \sum_{ij \in E} \frac{1}{\sqrt{d_i d_j}}.\]

An alternative to the Randic index is the Harmonic index, which is defined as: ´

\[H(G) = \sum_{ij \in E} \frac{2}{d_i + d_j}.\]

Using results due to Xu [31] it is straightforward to show that:

\[\frac{n}{2\nu} \le H(G) \le R(G) \le \frac{n}{2}.\]

Liu [23] has recently proved that triangle-free graphs have H(G) ≥ 2m/n. We can generalise this bound using part (i) of Theorem 4.1 as follows:

\[H(G) \ge \frac{n}{2\nu} \ge \frac{\omega m}{(\omega - 1)n} = \frac{2m}{n}\] when \(\omega = 2\).

We can also show that:

\[\frac{m}{\mu} = \frac{n}{2\beta} \le \frac{n}{2\epsilon} \le R(G)\]

since using Cauchy-Schwartz, we have R(G). P ij∈E p did^j ≥ ( P ij∈E 1)² = m² . Note that for Star graphs, n/2 = √ n − 1, which is the lower bound for R(G) due to Bollobas and Erdos [5]. It is not always the case that n/2 ≤ H(G) or that n/2β ≤ H(G).

The eccentricity ecc(v) of a vertex v in a connected graph G is the maximum distance between v and any other vertex u of G. The minimum graph eccentricity is the radius, r, of the graph. Xu [31] has proved that if H(G) is the Harmonic index, then:

\[H(G) \ge \frac{m}{n-r}.\]

This bound on r can be strengthened as follows.

Theorem 6.1. Let G be a connected graph with irregularity ν. Then:

\[H(G) \ge \frac{n}{2\nu} \ge \frac{m}{n-r}.\]

Proof. Note that for each vertex i ∈ V (G), we have dⁱ ≤ n − ecc(i). Therefore:

\[\frac{n}{2\nu} = \frac{2m^2}{\sum_{ij \in E} (d_i + d_j)} \ge \frac{2m^2}{\sum_{ij \in E} (2n - ecc(i) - ecc(j))} \ge \frac{2m^2}{2m(n-r)} = \frac{m}{n-r}.\]

7. Upper Bounds

Gutman, Furtula and Elphick [17] have proved that:

\[\beta^2 \leq \frac{n^2}{4(n-1)}\] ; \(\nu \leq \frac{n^2}{4(n-1)}\) and \(\epsilon^2 \leq \frac{n^2}{4(n-1)}\)

with equality for Star graphs.

We can obtain alternative bounds on ν(G) by using bounds on Pd 2 i , which is often referred to as the first Zagreb index. For example, Das [9] proved that

\[\sum d_i^2 \le 2m(\Delta + \delta) - n\Delta\delta.\]

Therefore

\[1 \le \nu = \frac{n \sum d_i^2}{4m^2} \le \frac{n(\Delta + \delta)}{2m} - \frac{n^2 \Delta \delta}{4m^2} = \frac{\Delta + \delta}{d} - \frac{\Delta \delta}{d^2}.\]

Alternatively, Izumino, Mori and Seo [21] have proved (their Corollary 3.2) that if 0 ≤ δ ≤ dⁱ ≤ ∆ then:

\[\frac{1}{n}\sum d_i^2 - \left(\frac{\sum d_i}{n}\right)^2 \le \frac{(\Delta - \delta)^2}{4}.\]

Therefore

\[1 \le \nu = \frac{n \sum d_i^2}{4m^2} \le \frac{n^2}{4m^2} \left(\frac{4m^2}{n^2} + \frac{(\Delta - \delta)^2}{4}\right) = 1 + \left(\frac{\Delta - \delta}{2d}\right)^2.\]

We can obtain alternative bounds on (G) by using bounds on the generalised Randic index, Rα(G), with α = 1/2. For example, Li and Yang [22] proved that for α ≥ 0:

\[R_{\alpha} \le \frac{n(n-1)^{1+2\alpha}}{2}.\]

Therefore

\[1 \le \epsilon = \frac{nR_{1/2}}{2m^2} \le \frac{n^2(n-1)^2}{4m^2} = \left(\frac{n-1}{d}\right)^2.\]

Favaron et al [15] demonstrate that ν and 2 are incomparable. However, in practice, ² ≥ ν for almost all graphs. Indeed we have been unable to find a graph amongst the named graphs in Wolfram Mathematica for which ² < ν. Considering the irregular named graphs in Wolfram with 16 vertices, the average value of ν = 1.22, the average value of ² = 1.27 and the average value of β ² = 1.32. As a specific example, DutchWindmill(5,4) has ν = 1.6, ² = 1.675 and β ² = 1.92.

The graphs representing some actual networks, such as the World Wide Web, power grids, academic collaborators and neural networks, are highly irregular. For example, Newman [25] calculated that the World Wide Web graph has c^v = 3.685, implying ν = 14.6. These high values of irregularity for some actual networks may increase the usefulness of the measures described in this paper.

8. Network heterogeneity indices

Estrada [11] and others have noted that many real-world networks have a power law degree distribution. Estrada has proposed that normalised indices of the heterogeneity of such networks should lie in the range (0, 1), with zero corresponding to regular graphs and unity to Star graphs. Estrada devised the following index, using R(G), which meets these criteria:

\[\rho_n = \frac{n - 2R}{n - 2\sqrt{n - 1}}.\]

As discussed above, ν, and β are minimised for regular graphs and maximised for Star graphs. We can therefore devise the following normalised heterogeneity indices:

\[\nu_n=\frac{n^2-(n^2/\nu)}{(n-2)^2} \text{ ; } \epsilon_n=\frac{n-(n/\epsilon)}{n-2\sqrt{n-1}} \text{ and } \beta_n=\frac{n-(n/\beta)}{n-2\sqrt{n-1}}.\]

It follows from the inequalities in Section 6 above that:

\[0 \le \rho_n \le \epsilon_n \le \beta_n \le 1.\]

It may be that βⁿ is the most useful of these indices, perhaps using results due to Chung, Lu and Vu [6] who have investigated the spectrum of random power law graphs.

Acknowledgement

This article is dedicated to the late Dr. C. S. Edwards who supervised the Ph.D. of C. Elphick. P.W. gratefully acknowledges the support of the National Science Foundation CAREER Award CCF-0746600. This work was supported in part by the National Science Foundation Science and Technology Centre for Science of Information, under grant CCF-0939370.

References

• [1] M. O. Albertson, The irregularity of a graph, Ars Comb. 46 (1997), 219–225.
• [2] F. Bell, Note on the irregularity of graphs, Linear Algebra Appl. 161 (1992), 45–54.
• [3] A. Bojilov, Y. Caro, A. Hansberg and N. Nenov, Partitions of graphs into small and large sets, arXiv:1205:1727, (2012).
• [4] A. Bojilov and N. Nenov, An inequality for generalized chromatic graphs, Mathematics and Education in Mathematics (2012), 143–147.
• [5] B. Bollobas and P. Erdos, Graphs of extremal weights, ´ Ars Combin. 50 (1998), 225–233.
• [6] F. Chung, L. Lu and V. Vu, Eigenvalues of Random Power Law Graphs, Annals Combin. 7 (2003), 21–33.

• [7] L. Collatz and U. Sinogowitz, Spektren endlicher Grafen, Abh. Math. Sem. Univ. Hamburg 21 (1957), 63–77.
• [8] D. Cvetkovic, Chromatic number and the spectrum of a graph, Publ. Inst. Math. (Beograd) 14(28), (1972), 25–38.
• [9] K. C. Das, Maximising the sum of the squares of the degrees of a graph, Discrete Math. 285 (2004), 57–66.
• [10] H. Deng, S. Balachandran, S. K. Ayyaswamy and Y. B. Venkatakrishnan, On the harmonic index and the chromatic number of a graph, Discrete Appl. Math. (2013), in press.
• [11] E. Estrada, The Structure of Complex Networks : Theory and Applications, Oxford University Press, (2011).
• [12] N. Khadzhiivanon and N. Nenov, Generalized r-partite graphs and Turan's Theorem, ´ Compt. Rend. Acad. Bulg. Sci. 57 (2004).
• [13] C. S. Edwards, The largest vertex degree sum for a triangle in a graph, Bull. London Math. Soc. 9 (1977), 203–208.
• [14] C. S. Edwards and C. Elphick, Lower bounds for the clique and the chromatic numbers of a graph, Discrete Appl. Math. 5 (1983), 51–64.
• [15] O. Favaron, M. Maheo and J. -F. Sacl ´ e, Some eigenvalue properties in Graphs (conjectures ´ of Graffiti - II, Discrete Math. 111 (1993), 197–220.
• [16] F. Goldberg, The Colin de Verdiere number of a graph ` , Ph.D. thesis, (2010).
• [17] I. Gutman, B. Furtula and C. Elphick, Three New/Old Vertex-Degree-Based Topological Indices, MATCH Commun. Math. Comput. Chem., submitted.
• [18] P. Hansen and D. Vukicevic, On the Randi ´ c index and the chromatic number, ´ Discrete Math. 309 (2009), 4228–4234.
• [19] M. Hofmeister, Spectral radius and degree sequence, Math. Nachr. 139 (1988) 37–44.
• [20] H. van der Holst, L. Lovasz and A. Schrijver, The Colin de Verdiere graph parameter, Bolyai Soc. Math. Stud. 7 (1999), 29–85.
• [21] S. Izumino, H. Mori and Y. Seo, On Ozeki's inequality, J. Inequal. Appl. 2 (1998), 235–253.
• [22] X. Li and Y. Yang, Sharp Bounds on the General Randic Index, ´ MATCH Commun. Math. Comput. Chem. 51 (2004), 155–166.
• [23] J. Liu, On the Harmonic index of Triangle-Free Graphs, Appl. Math. 4 (2013), 1204–1206.
• [24] J. W. Moon and L. Moser, On a problem of Turan, ´ Publ. Math. Inst. Hungar. Acad. Sci. 7 (1962), 283–286.

• [25] M. E. J. Newman, Random graphs as models of networks, Sante Fe Institute, Working Paper 2002-02-005.
• [26] V. Nikiforov, Some inequalities for the largest eigenvalue of a graph, Combin. Probab. Comput. 11 (2002), 179–189.
• [27] V. Nikiforov, Eigenvalues and degree deviation in graphs, Linear Algebra Appl. 414 (2006), 347–360.
• [28] V. Nikiforov, Bounds on graph eigenvalues I, Linear Algebra Appl. 420 (2007), 667–671.
• [29] X. Li and Y. Shi, On a relation between the Randic index and the chromatic number, ´ Discrete Math., 310(17) (2010), 2448–2451.
• [30] R. Pendavingh, On the relation between two minor-monotone graph parameters, Combinatorica 18(2) (1998), 281–292.
• [31] X. Xu, Relationships between Harmonic index and other Topological indices, Appl. Math. Sci. 6(41) (2012), 2013–2018.
• [32] A. Yu, M. Lu and F. Tian, On the spectral radius of graphs, Linear Algebra Appl. 387 (2004), 41–49.