Extremal Values of Second Zagreb Index of Unicyclic Graphs Having Maximum Cycle Length: Two New Algorithms

It is well-known that the necessary and sufficient condition for a connected graph to be unicyclic is that its omega invariant, a recently introduced graph invariant useful in combinatorial and topological calculations, is zero. This condition could be stated as the condition that the order and the size of the graph are equal. Using a recent result saying that the length of the unique cycle could be any integer between 1 and n − a 1 where a 1 is the number of pendant vertices in the graph, two explicit labeling algorithms are provided that attain these extremal values of the first and second Zagreb indices by means of an application of the well-known rearrangement inequality. When the cycle has the maximum length, we obtain the situation where all the pendant vertices are adjacent to the support vertices, the neighbors of the pendant vertices, which are placed only on the unique cycle. This makes it easy to calculate the second Zagreb index, as the contribution of the pendant edges to such indices is fixed, implying that we can only calculate these indices for the edges on the cycle.