The forgotten topological index of a (molecule) graph is the sum of cubes of all its vertex degrees, which plays a significant role in measuring the branching of the carbon atom skeleton. It is meaningful and difficult to explore sufficient conditions for a given graph keeping certain properties in graph theory. In this paper, we mainly explore sufficient conditions in terms of the forgotten topological index for a graph to be ℓ-connected, ℓ-deficient, ℓ-Hamiltonian and ℓ−-independent, respectively. The conditions cannot be dropped.
Let \(G\) be a graph with at least \(l+1\) vertices. If for any subset \(S\subseteq V(G)\) with \(|S|=l\) there always exists a spanning tree \(T\) in \(G\) such that \(S\) is precisely the set of leaves of \(T\), then we say that the graph \(G\) is \(l\)-leaf-connected. Exploring sufficient conditions for graphs that possesses certain properties is a significant and interesting problem in graph theory. In this paper, we present several sufficient conditions in terms of the inverse degree, the reciprocal product-degree distance, and the multiplicative version of the first Zagreb index for a graph to be \(l\)-leaf-connected.
It is a well-known fact that a graph of diameter d has at least eigenvalues. A graph is d-extremal (resp. -extremal) if it has diameter d and exactly distinct eigenvalues (resp. -eigenvalues), and a graph is split if its vertex set can be partitioned into a clique and a stable set. Such graphs have a diameter of at most three. If all vertex degrees in a split graph are either or , then we say it is -bidegreed. In this paper, we present a complete classification of the connected bidegreed -extremal split graphs using the association of split graphs with combinatorial designs. This result is a natural generalization of Theorem 4.6 proved by Goldberg et al. and Proposition 3.8 proved by Song et al., respectively.
20 January 2020 in Advances and Applications in Discrete Mathematics
Fault tolerance is especially important for interconnection networks, since the growing size of networks increases their vulnerability to component failures. A classical measure for the fault tolerance of a network in the case of vertex failures is its connectivities. A network based on a graph G = (X1X2... Xk,I,E) is called a k-multisplit network, if its vertex set V can be partitioned into k+1 stable sets I,X1,X2,...,Xk such that X1 X2...Xk induces a complete k-partite graph and I is an independent set. In this note, we first show that: for any non-complete connected k-multisplit graph G = (X1X2...Xk,I,E) with k ≥ 3 and |X1| ≤ |X2| ≤...≤ |Xk|, each of the following holds (1) If |X1X2...Xk-1| ≥ δ, then k(G) = δ(G). (2) If |X1X2...Xk-1| < δ, then k(G)≥ |X1 X2... Xk-1|. (3) λ(G) = δ(G). (4) If |X1X2...Xk-1| > δ with respect to |X1| ≥ 2 and δ ≥ 2, then G is super-k. (5) G is super-λ. In addition, we present sufficient conditions for digraphs to be maximally edge-connected and super-edge connected in terms of the zeroth-order general Randić index of digraphs.