Extremal Results on ℓ-Connected Graphs or Pancyclic Graphs Based on Wiener-Type Indices - Jing Zeng; Hechao Liu; Lihua You (Mathematics)
A graph of order n is called pancyclic if it contains a cycle of length y for every <semantics>3≤y≤n</semantics>. The connectivity of an incomplete graph G, denoted by <semantics>κ(G)</semantics>, is <semantics>min{|W||W<mspace width="4pt"></mspace>is<mspace width="4pt"></mspace>a<mspace width="4pt"></mspace>vertex<mspace width="4pt"></mspace>cut<mspace width="4pt"></mspace>of<mspace width="4pt"></mspace>G}</semantics>. A graph G is said to be ℓ-connected if the connectivity <semantics>κ(G)≥ℓ</semantics>. The Wiener-type indices of a connected graph G are <semantics>Wg(G)=<mstyle displaystyle="true"><munder>∑{s,t}⊆V(G)</munder></mstyle>g(dG(s,t))</semantics>, where <semantics>g(x)</semantics> is a function and <semantics>dG(s,t)</semantics> is the distance in G between s and t. In this note, we first determine the minimum and maximum values of <semantics>Wg(G)</semantics> for ℓ-connected graphs. Then, we use the Wiener-type indices of graph G, the Wiener-type indices of complement graph <semantics><mover>G¯</mover></semantics> with minimum degree <semantics>δ(G)≥2</semantics> or <semantics>δ(G)≥3</semantics> to give some sufficient conditions for connected graphs to be pancyclic. Our results generalize some existing results of several papers.