Dirac showed that in a -connected graph there is a path through all the k vertices. The k-path-connectivity of a graph G, which is a generalization of Dirac's notion, was introduced by Hager in 1986. Denote by the lexicographic product of two graphs G and H. In this paper, we prove that for any two connected graphs G and H. Moreover, the bound is sharp. We also derive an upper bound of , that is, .
18 September 2015 in Journal of Combinatorial Optimization
Building upon the notion of the Gutman index , Mao and Das recently introduced the Steiner Gutman index by incorporating Steiner distance for a connected graph G. The Steiner Gutman k-index of G is defined by , in which is the Steiner distance of S and is the degree of v in G. In this paper, we derive new sharp upper and lower bounds on , and then investigate the Nordhaus-Gaddum-type results for the parameter . We obtain sharp upper and lower bounds of and for a connected graph G of order n, m edges, maximum degree and minimum degree .