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.

It is a well-known fact that a graph of diameter d has at least d + 1 eigenvalues (A.E. Brouwer, W.H. Haemers (2012) [2] ). A graph is d-extremal (resp. d S L -extremal) if it has diameter d and exactly d + 1 distinct eigenvalues (resp. signless Laplacian eigenvalues), and a graph is split if its vertex set can be partitioned into a clique and a stable set. Such graphs have diameter at most three. If all vertex degrees in a split graph are either d ˜ or d ˆ , then we say it is ( d ˜ , d ˆ ) -bidegreed. In this paper, we present a complete classification of the connected bidegreed 3 S L -extremal split graphs using the association of split graphs with combinatorial designs.

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]).

An even factor of a graph G is a spanning subgraph in G such that the degree of each vertex is a positive even integer. In this paper, we show that for any induced claw of simple graph G of order at least 10, if there exists at least a pair of vertices out of the claw such that they are the common neighbors of nonadjacent vertices of the claw, then G has an even factor if and only if $$\delta (G)\ge 2$$ and every odd branch-bond of G contains a branch of length 1. The even factor of claw-heavy graphs was also characterized.

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.

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 connectivity. The connectivity κ (G) of a connected graph G is the least positive integer κ such that there is S ⊂ V, |S| = κ and G–S is disconnected or reduces to the trivial graph K1. The edge connectivity λ(G) of G is similarly defined. It is well known that κ (G) ≤ λ (G) ≤ δ (G). A graph G is called maximally (edge) connected if κ (G) = δ (G)( λ (G) = δ (G)), max-κ (max-λ) for simply. A connected graph G = (V, E) is called supper- κ (resp. super-λ) if every minimum vertex cut (edge cut) of G is the set of neighbors of some vertex in G. We introduce a new kind of network called k-split network. A network based on a graph G = (X1 U X2 U … ⊂ Xk, I, E) is called a k-split network, if its vertex set V can be partitioned into κ + 1 stable sets I, X1, X2, …, Xκ such that X1 U X2 U … U Xκ induces a complete k-partite graph and an independent set I. In this note, we show that: G = (X1UX2 … UXκ, I, E) is a non-complete connected κ-split graph with κ ≥ 3 and |X1| ≤ |X2| ≤ … ≤ |Xκ|. Then we have (1) If |X1 U X2 … U Xκ–1| ≥ δ(G), then κ (G) = δ (G). (2) If |X1 U X2 … U Xκ–1|δ, then G is super-κ. (5) G is super-λ.

Let G = (V (G),E(G)) be a graph. Gould and Hynds (1999) showed a well-known characterization of G by its line graph L(G) that has a 2-factor. In this paper, by defining two operations, we present a characterization for a graph G to have a 2-factor in its line graph L(G). A graph G is called N 2-locally connected if for every vertex x ∈ V (G), G[{y ∈ V (G); 1 ⩽ dist G (x, y) ⩽ 2}] is connected. By applying the new characterization, we prove that every claw-free graph in which every edge lies on a cycle of length at most five and in which every vertex of degree two that lies on a triangle has two N 2-locally connected adjacent neighbors, has a 2-factor. This result generalizes the previous results in papers: Li, Liu (1995) and Tian, Xiong, Niu (2012), and is the best possible.

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.

Let k>=2 be an integer, a k-decomposition(G"1,G"2,...,G"k) of a graph G is a partition of its edge set to form k spanning subgraphs G"1,G"2,...,G"k. The hyper-Wiener index WW is one of the recently conceived distance-based graph invariants (Randi 1993 [15]): WW=WW(G):=12W(G)+12W"2(G), where W is the Wiener index (Wiener 1947 [18]) and W"2 is the sum of squares of distance of all pairs of vertices in G. In this paper, we investigate the Nordhaus-Gaddum-type inequality of a 3-decomposition of K"n for the hyper-Wiener index: 7n2@?WW(G"1)+WW(G"2)+WW(G"3)@?2n+24+n2+4(n-1). The corresponding extremal graphs are characterized.

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.

Let Kn be the complete graph of order n, and k ≥ 2 any fixed integer. Assume (G1, G2,…,Gk) is a decomposition of Kn such that Gi is connected for each i = 1,…, k. We show that for any sufficiently large n, [Formula: see text], and that the bounds are best possible.

The authors Milicevic et al. introduced the reformulated Zagreb indices [1], which is a generalization of classical Zagreb indices of chemical graph theory. In this paper, we mainly consider the maximum and minimum for the first reformulated index of graphs with connectivity at most k. The corresponding extremal graphs are characterized.

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.