Graph Irregularity and a Problem Raised by Hong
Tamás Réti · Acta Polytechnica Hungarica · 2018
Starting with the study of the Collatz-Sinogowitz and the Albertson graph irregularity indices the relationships between the irregularity of graphs and their spectral radius are investigated.We also use the graph irregularity index defined as Ir(G) = Δ -δ, where Δ and δ denote the maximum and minimum degrees of G. Our observations lead to the answer for a question posed by Hong in 1993.The problem concerning graphs with the smallest spectral radius can be formulated as follows: If G is a connected irregular graph with n vertices and m edges, and G has the smallest spectral radius, is it true that Ir(G) =1?It will be shown that the answer is negative; counterexamples are represented by several cyclic graphs.Based on the previous considerations the problem proposed by Hong can be reinterpreted (refined) in the form of the following conjecture: If G is a connected irregular graph with n vertices and m edges, and G has the smallest spectral radius, then Ir(G)=1 if such a graph exists, and if not, then Ir(G)=2.Considering the family of unicyclic graphs for which Ir(G) ≥ 2, we prove that among n-vertex irregular unicyclic graphs the minimal spectral radius belongs to the uniquely defined short lollipop graphs where a pendent vertex is attached to cycle Cn-1.Moreover, it is verified that among n-vertex graphs there exists exactly one irregular graph Jn having a maximal spectral radius and an irregularity index of Ir(Jn)=1.Finally, it is also shown that by using the irregularity index Ir(G) a classification of n-vertex trees into (n-2) disjoint subsets can be performed.