In a graph G, a vertex dominates itself and its neighbors. A subset S ⊆ V(G) is a double dominating set of G if S dominates every vertex of G at least twice. The minimum cardinality of a double dominating set of G is the double domination number ${\gamma }_{\times 2}\left(G\right)$. If G ≠ C₅ is a connected graph of order n with minimum degree at least 2, then we show that ${\gamma }_{\times 2}\left(G\right)\le 3n/4$ and we characterize those graphs achieving equality.

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.

An edge-coloured graph G is rainbow connected if any two vertices are connected by a path whose edges have distinct colours. The rainbow connection number of a connected graph G, denoted rc(G), is the smallest number of colours that are needed in order to make G rainbow connected. In this paper we prove that rc(G) = 2 for every connected graph G of order n and size m, where $\left(\genfrac{}{}{0pt}{}{n-1}{2}\right)+1\le m\le \left(\genfrac{}{}{0pt}{}{n}{2}\right)-1$. We also characterize graphs with rainbow connection number two and large clique number.

The additive stretch number $s_{add}\left(G\right)$ of a graph G is the maximum difference of the lengths of a longest induced path and a shortest induced path between two vertices of G that lie in the same component of G.We prove some properties of minimal forbidden configurations for the induced-hereditary classes of graphs G with $s_{add}\left(G\right)\le k$ for some k ∈ N₀ = 0,1,2,.... Furthermore, we derive characterizations of these classes for k = 1 and k = 2.

Let $G$ be a connected graph with vertex set $V\left(G\right)=\{v_1,v_2,...,v_n\}$. The distance matrix $D\left(G\right)={\left(d_{ij}\right)}_{n\times n}$ is the matrix indexed by the vertices of $G$, where $d_{ij}$ denotes the distance between the vertices $v_i$ and $v_j$. Suppose that ${\lambda }_1\left(D\right)\ge {\lambda }_2\left(D\right)\ge \cdots \ge {\lambda }_n\left(D\right)$ are the distance spectrum of $G$. The graph $G$ is said to be determined by its $D$-spectrum if with respect to the distance matrix $D\left(G\right)$, any graph having the same spectrum as $G$ is isomorphic to $G$. We give the distance characteristic polynomial of some graphs with small diameter, and also prove that these graphs are determined...

The eccentricity $e\left(v\right)$ of a vertex $v$ is the distance from $v$ to a vertex farthest from $v$, and $u$ is an eccentric vertex for $v$ if its distance from $v$ is $d(u,v)=e\left(v\right)$. A vertex of maximum eccentricity in a graph $G$ is called peripheral, and the set of all such vertices is the peripherian, denoted $PeriG)$. We use $Cep\left(G\right)$ to denote the set of eccentric vertices of vertices in $C\left(G\right)$. A graph $G$ is called an S-graph if $Cep\left(G\right)=Peri\left(G\right)$. In this paper we characterize S-graphs with diameters less or equal to four, give some constructions of S-graphs and...