Search

Given a connected graph G , the edge-Szeged index Sz e ( G ) is defined as S z e ( G ) = ∑ e = u v ∈ E m u ( e ) m v ( e ) , where m u ( e ) and m v ( e ) are, respectively, the number of edges of G lying closer to vertex u than to vertex v and the number of edges of G lying closer to vertex v than to vertex u . In this paper, some extremal problems on the edge-Szeged index of unicyclic graphs are considered. All the n -vertex unicyclic graphs with a given diameter having the minimum edge-Szeged index are identified. Using a unified approach we identify the n -vertex unicyclic graphs with the minimum, second minimum, third minimum and fourth minimum edge-Szeged indices. [ABSTRACT FROM AUTHOR]

Metacyclic graphs, which include supertoroids as a subclass, have been shown to possess interesting properties and potential applications in implementing moderate- to large-size parallel processors with fairly small node degrees. Wu, Lakshmivarahan, and Dhall (J. Parallel Distrib. Comput. 60 (2000), pp. 539-565) have described a deterministic, distributed routing scheme for certain subclasses of metacyclic graphs. However, they offer no proof that the scheme is a shortest-path routing algorithm and do not indicate whether or how their scheme may be extended to the entire class of metacyclic graphs. In this paper, we provide a near-shortest-path, deterministic routing algorithm that is applicable to any metacyclic graph and derive a bound for the diameter of such graphs. [ABSTRACT FROM AUTHOR]