Search

For k ≥ 2 , spanning trees T 1 , T 2 , … , T k in a graph G are called to be completely independent if for any two distinct vertices x and y , the paths connecting them in T 1 , T 2 , … , T k are pairwise openly disjoint. We call such spanning trees T 1 , T 2 , … , T k the completely independent spanning trees (CIST for short). Recently, Hong and Zhang (2020) found that a sufficient condition for Hamiltonian graphs also suffices the existence of two CISTs. That is, if G is a graph with n vertices, | N ( x ) ∪ N ( y ) | ≥ n 2 and | N ( x ) ∩ N ( y ) | ≥ 3 for every two non-adjacent vertices x , y of G and n ≥ 5 , then G has two CISTs. More recently, Qin et al. (2020) proposed that the restriction on the number of vertices in the statement should be n ≥ 8 , and then pointed out that the Claim 1 in Hong’s paper is not always true for general case, which was corrected by presenting an amendment. However, there still exists a flaw in the corresponding revised proof (see details from the second part of our paper). Accordingly, we give a new amendment to correct the proof.

Let G = ( V , E ) be a connected graph and P be graph-theoretic property. A network is often modeled by a graph G = ( V , E ) . One fundamental consideration in the design of networks is reliability. The connectivity is an important parameter to measure the fault tolerance and reliability of network. The conditional connectivity λ(G, P) or κ(G, P) is the minimum cardinality of a set of edges or vertices, if it exists, whose deletion disconnects G and each remaining component has property P. Let F be a vertex set or edge set of G and P be the property of with at least k components. Then we have the k-component connectivity cκk(G) and the k-component edge connectivity cλk(G). In this paper, we determine the k-component (edge) connectivity of locally twisted cubes LTQn for small k, and we also prove other properties of LTQn.

For a connected graph G=(V,E), a subset FV is called an Rk-vertex-cut of G if GF is disconnected and each vertex in VF has at least k neighbors in GF. The cardinality of the minimum Rk-vertex-cut is the Rk-vertex-connectivity of G and is denoted by k(G). The conditional connectivity is a measure to explore the structure of networks beyond the vertex-connectivity. Let Sym(n) be the symmetric group on {1,2,,n} and T be a set of transpositions of Sym(n). Denote by G(T) the graph with vertex set {1,2,,n} and edge set {ij:(ij)T}. If G(T) is a wheel graph, then simply denote the Cayley graph Cay(Sym(n),T) by WGn. In this paper, we determine the values of 1 and 2 for Cayley graphs generated by wheel graphs and prove that 1(WGn)=4n6 and 2(WGn)=8n18.

Let G be a connected graph with vertex set V, minimum degree and edge-connectivity . If is a real number, then the zeroth-order general Randi index is defined by xVdeg(x), where deg(x) denotes the degree of the vertex x. A graph is maximally edge-connected if =. In this paper, we present sufficient conditions for connected graphs (resp. connected triangle-free graphs) to be maximally edge-connected in terms of the zeroth-order general Randi index, the order and the minimum degree when (,0) or (1,2] (resp. [1,0)(1,2]).

We investigate the graph with minimal Zeroth-order general Randic index in terms of its order n, pendent number N1 and cyclomatic number γ ? 0. Extremal graphs were completely characterized for cases of γ = 0 , 1 , 2 , which can be directly extended for graphs with cyclomatic number γ ? 3.

For a connected graph with order n and size m, the cyclomatic number (=number of independent cycles) is equal to γ = m - n + 1 . The graphs with γ = 1 are referred to the unicyclic graphs. In this paper, we characterized completely the unicyclic graphs with n vertices having maximum degree resistance distance.

Graph invariants, based on the distances between the vertices of a graph, are widely used in theoretical chemistry. The degree resistance distance of a graph G is defined as D R ( G ) = ∑ { u , v } ⊆ V ( G ) [ d ( u ) + d ( v ) ] R ( u , v ) , where d ( u ) is the degree of the vertex u , and R ( u , v ) the resistance distance between the vertices u and v . Let C a c t ( n ; t ) be the set of all cacti possessing n vertices and t cycles. The elements of C a c t ( n ; t ) with minimum degree resistance distance are characterized.

In this paper, we investigate topological indices of the line graphs of the tadpole graphs, wheel graphs and ladder graphs using the subdivision concept, which generalize the results of Ranjini et al. (2011). In addition, we present the Schur-bound for the general sum-connectivity co-index.

Let G be a connected graph with order n=|V(G)|, minimum degree @[email protected](G) and edge-connectivity @[email protected](G). A graph is said to be maximally edge-connected if @[email protected] In this paper, we present two sufficient conditions for (triangle-free) graphs to be maximally edge-connected in terms of its order and the Zeroth-order general Randic index.

Let $$G$$G be a connected graph with order $$n,$$n, minimum degree $$\delta =\delta (G)$$?=?(G) and edge-connectivity $$\lambda =\lambda (G).$$?=?(G). A graph $$G$$G is maximally edge-connected if $$\lambda =\delta .$$?=?. In this paper, we present two sufficient conditions for graphs to be maximally edge-connected, which generalize two results recently proved by P. Dankelmann, A. Hellwig and L. Volkmann. The extremal graphs are also characterized.

In this contribution, we first investigate sharp bounds for the reciprocal sum-degree distance of graphs with a given matching number. The corresponding extremal graphs are characterized completely. Then we explore the $$k$$k-decomposition for the reciprocal sum-degree distance. Finally, we establish formulas for the reciprocal sum-degree distance of join and the Cartesian product of graphs.

The k-th power of a graph G, denoted by Gk, is a graph with the same set of vertices as G, such that two vertices are adjacent in Gk if and only if their distance in G is at most k. The Harary index H is the sum of the reciprocal distances of all pairs of vertices of the underlying graph. Lower and upper bounds on H(Gk) are obtained. A Nordhaus-Gaddum type inequality for H(Gk) is also established.

In this paper we present an equivalent definition of Co-PI index and then determine the eigenvalues of Co-PI matrices and their Laplacians of Cartesian product graphs, including bounds on the second and third Co-PI spectral moment of a graph. The explicit formulae for the Co-PI index of Cartesian product graphs are also presented.

Let k ≥ 2 be an integer, a k -decomposition ( G 1 , G 2 , … , G k ) of the complete graph K n is a partition of its edge set to form k spanning subgraphs G 1 , G 2 , … , G k . In this contribution, we investigate the Nordhaus–Gaddum-type inequality of a k -decomposition of K n for the general Zagreb index and a 2 -decomposition for the Zagreb co-indices, respectively. The corresponding extremal graphs are characterized.