Sufficient conditions for k-connected graphs and k-leaf-connected graphs

Abstract

A connected graph G is said to be k-connected if it has more than k vertices and remains connected whenever fewer than k vertices are deleted. In this paper, we present a sufficient condition in terms of the number of r-cliques to guarantee the a graph with minimum degree at least δ to be k-connected, which extends the result of Feng et al. [Linear Algebra Appl. 524 (2017) 182–198]. For any integer k ≥ 2, a graph G is called k-leaf-connected, if |V(G)| ≥ k + 1 and given any subset S ⊆ V(G) with |S | = k, G always has a spanning tree T such that S is precisely the set of leaves of T. The forgotten index of a graph is the sum of degree cube of all the vertices in graph. Motivated by the degree sequence condition of Gurgel and Wakabayashi [J. Combin. Theory Ser. B 41 (1986)
1–16], we provide a sufficient condition for a connected graph to be k-leaf-connected in terms of the forgotten index of G, which improve and extend the result of Su et al. [Australas. J. Combin. 77 (2020) 269–284].