The Randi? index and the diameter of graphs

The Randi? indexR(G) of a graph G is defined as the sum of over all edges uv of G, where d_u and d_v are the degrees of vertices u and v, respectively. Let D(G) be the diameter of G when G is connected. Aouchiche et al. (2007) [1] conjectured that among all connected graphs G on n vertices the path P_n achieves the minimum values for both R(G)/D(G) and R(G)−D(G). We prove this conjecture completely. In fact, we prove a stronger theorem: If G is a connected graph, then , with equality if and only if G is a path with at least three vertices.     

On a conjecture of the Randić index and the minimum degree of graphs

The Randi? index $R\left(G\right)$ of a graph $G$ is defined by $R\left(G\right)={\sum }_{uv}\frac{1}{\sqrt{d\left(u\right)d\left(v\right)}}$, where $d\left(u\right)$ is the degree of a vertex $u$ and the summation extends over all edges $uv$ of $G$. Delorme et al. (2002)  [6] put forward a conjecture concerning the minimum Randi? index among all$n$-vertex connected graphs with the minimum degree at least $k$. In this work, we show that the conjecture is true given the graph contains $k$ vertices of degree $n?1$. Further, it is true among $k$-trees.     

Characterization of graphs having extremal Randi? indices

The higher Randi? index R_t(G) of a simple graph G is defined as

     

On a conjecture of the Randi? index

The Randi? index of a graph G is defined as , where d(u) is the degree of vertex u and the summation goes over all pairs of adjacent vertices u, v. A conjecture on R(G) for connected graph G is as follows: R(G)≥r(G)−1, where r(G) denotes the radius of G. We proved that the conjecture is true for biregular graphs, connected graphs with order n≤10 and tricyclic graphs.     

On total chromatic number of planar graphs without 4-cycles

Let G be a simple graph with maximum degree A(G) and total chromatic number Xve(G). Vizing conjectured thatΔ(G) 1≤Xve(G)≤Δ(G) 2 (Total Chromatic Conjecture). Even for planar graphs, this conjecture has not been settled yet. The unsettled difficult case for planar graphs isΔ(G) = 6. This paper shows that if G is a simple planar graph with maximum degree 6 and without 4-cycles, then Xve(G)≤8. Together with the previous results on this topic, this shows that every simple planar graph without 4-cycles satisfies the Total Chromatic Conjecture.     

Conjugated tricyclic graphs with the maximum zeroth-order general Randić index

Let G be a simple connected graph and α be a given real number. The zeroth-order general Randi? index of G is defined as ⁰ R _α (G)=∑ _v∈V(G)[d _G (v)] ^α , where d _G (v) denotes the degree of the vertex v of G. In this paper, for any α>2, we give sharp upper bounds of the zeroth-order general Randi? index ⁰ R _α of all conjugated tricyclic graphs with 2m vertices.     

Relation between the correspondence chromatic number and the Alon–Tarsi number

We study the relation between the correspondence chromatic number, also known as the DP-chromatic number, and the Alon–Tarsi number, both upper bounds on the list chromatic number of a graph. There are many graphs with Alon–Tarsi number greater than the correspondence chromatic number. We present here a family of graphs with arbitrary Alon–Tarsi number, with correspondence chromatic number one larger.     

Sharp bounds of the zeroth-order general Randi? index of bicyclic graphs with given pendent vertices

Let G be a simple connected graph and α be a given real number. The zeroth-order general Randi? index of ⁰R_α(G) is defined as ∑_v∈V(G)[d_G(v)]^α, where d_G(v) denotes the degree of the vertex v of G. In this paper, for any α(≠0,1), we give sharp bounds of the zeroth-order general Randi? index ⁰R_α of all bicyclic graphs with n vertices and k pendent vertices.