Advanced Search

The k-rainbow index rxk(G) of a connected graph G was introduced by Chartrand, Okamoto and Zhang in 2010. As a natural counterpart of the k-rainbow index, we introduce the concept of k-vertex-rainbow index rvxk(G) in this paper. In this paper, sharp upper and lower bounds of rvxk(G) are given for a connected graph G of order n, that is, 0 ≤ rvxk(G) ≤ n − 2. We obtain Nordhaus-Gaddum results for 3-vertex-rainbow index of a graph G of order n, and show that rvx3(G) + rvx3(Ḡ) = 4 for n = 4 and 2 ≤...

The generalized k-connectivity κk(G) of a graph G, introduced by Hager in 1985, is a nice generalization of the classical connectivity. Recently, as a natural counterpart, we proposed the concept of generalized k-edge-connectivity λk(G). In this paper, graphs of order n such that [...] for even k are characterized.

The Wiener index W(G) of a connected graph G, introduced by Wiener in 1947, is defined as W(G) =∑u,v∈V (G) dG(u, v), where dG(u, v) is the distance (the length a shortest path) between the vertices u and v in G. For S ⊆ V (G), the Steiner distance d(S) of the vertices of S, introduced by Chartrand et al. in 1989, is the minimum size of a connected subgraph of G whose vertex set contains S. The k-th Steiner Wiener index SWk(G) of G is defined as [...] SWk(G)=∑S⊆V(G)|S|=kd(S) $S{W}_k\left(G\right)={\sum }_{\underset{\left|S\right|=k}{S\subseteq V\left(G\right)}}d\left(S\right)$ . We investigate the...

The Wiener index W(G) of a connected graph G, introduced by Wiener in 1947, is defined as W(G) = ∑u,v∈V(G) d(u, v) where dG(u, v) is the distance between vertices u and v of G. The Steiner distance in a graph, introduced by Chartrand et al. in 1989, is a natural generalization of the concept of classical graph distance. For a connected graph G of order at least 2 and S ⊆ V (G), the Steiner distance d(S) of the vertices of S is the minimum size of a connected subgraph whose vertex set is S. We now...

For a connected graph $G=(V,E)$ and a set $S\subseteq V\left(G\right)$ with at least two vertices, an $S$-Steiner tree is a subgraph $T=(V^{\text{'}},E^{\text{'}})$ of $G$ that is a tree with $S\subseteq V^{\text{'}}$. If the degree of each vertex of $S$ in $T$ is equal to 1, then $T$ is called a pendant $S$-Steiner tree. Two $S$-Steiner trees are if they share no vertices other than $S$ and have no edges in common. For $S\subseteq V\left(G\right)$ and $\left|S\right|\ge 2$, the pendant tree-connectivity ${\tau }_G\left(S\right)$ is the maximum number of internally disjoint pendant $S$-Steiner trees in $G$, and for $k\ge 2$, the $k$-pendant tree-connectivity ${\tau }_k\left(G\right)$ is the minimum value...

We study the generalized $k$-connectivity ${\kappa }_k\left(G\right)$ as introduced by Hager in 1985, as well as the more recently introduced generalized $k$-edge-connectivity ${\lambda }_k\left(G\right)$. We determine the exact value of ${\kappa }_k\left(G\right)$ and ${\lambda }_k\left(G\right)$ for the line graphs and total graphs of trees, unicyclic graphs, and also for complete graphs for the case $k=3$.