The Wiener index $W(G)$ of a graph $G$ is one of the most well-known topological indices, which is defined as the sum of distances between all pairs of vertices of $G$. The diameter $D(G)$ of $G$ is the maximum distance between all pairs of vertices of $G$, and the conditional diameter $D(G;s)$ is the maximum distance between all pairs of vertex subsets with cardinality $s$ of $G$. When $s=1$, the conditional diameter $D(G;s)$ is just the diameter $D(G)$. The authors in ^[18] characterized the graphs with the maximum Wiener index among all graphs with diameter $D(G)=n-c$, where $1\le c\le 4$. In this paper, we will characterize the graphs with the maximum Wiener index among all graphs with conditional diameter $D(G;s)=n-2s-c$ ( $-1\le c\le 1$), which extends partial results above.

Let D=(V(D),A(D)) be a digraph of order n. The digraph D is called a strong block if D is strongly connected and its underlying graph has no cut-vertex. D is called a minimally strong block, if D is a strong block, but D−a is not a strong block for every arc a of A(D). For u,v ∈ V(D), the local connectivity ${\kappa }_D$(u,v) from u to v is the maximum number of internally disjoint directed (u,v)-paths in D. The average connectivity of D is $\overline{\kappa }\left(D\right)=\frac{1}{n\left(n-1\right)}\left[{\displaystyle \sum _{\left(u,v\right)\in V\left(D\right)\times V\left(D\right)}\kappa D\left(u,v\right)}\right]$. By using the method of degree sequence and ear decomposition, this paper determine some upper bounds of average connectivity among minimally strong blocks in terms of their orders, and conjecture that it is strictly less than 3/2.

In 2010, Mader conjectured that for any tree T of order m, every k-connected graph G with minimum degree at least $\lfloor \frac{3k}{2}\rfloor$+m-1 contains a subtree $T^{\prime }\cong T$ such that G−V(T′) is still k-connected. For bipartite graphs, we proposed a similar conjecture as follows: for every positive integer k and every finite tree T with bipartition X and Y (denote t = max{|X|, |Y|}), every k-connected bipartite graph G with minimum degree at least k+t contains a subtree $T^{\prime }\cong T$ such that G−V (T′) is still k-connected. In this paper, we confirm this conjecture for all caterpillars whose internal vertices is at most 3 when k=1 and k=2.

A graph G is super connected, or simply super-κ, if every minimum vertex-cut isolates a vertex. The Kronecker product G₁ × G₂ of graphs G₁ and G₂ is the graph with vertex set V (G₁ × G₂) = V(G₁) × V (G₂) and edge set E(G₁ × G₂) = {(u₁,v₁)(u₂,v₂): u₁u₂ ∈ E(G₁),v₁v₂ ∈ E(G₂)}. In this paper, we prove that P_m × C_n is super-κ for m≥4, n≥3 and n is odd; C_m × C_n is super-κ for m≥5, n≥3 and n is odd.

For two graphs G and H, the direct product G×H is the graph with vertex set V(G)×V(H) and two vertices (g₁,h₁) and (g₂,h₂) are adjacent whenever g₁g₂ is an edge in G and h₁h₂ is an edge in H. The Wiener index of a connected graph G, denoted by W(G), is the sum of the distances between all unordered pairs of vertices of G. In this paper, we obtain the Wiener index of the direct product of a path and a generalized Petersen graph P(m,3).