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

Zverovich [Discuss. Math. Graph Theory 23 (2003), 159-162.] has proved that the domination number and connected domination number are equal on all connected graphs without induced P₅ and C₅. Here we show (with an independent proof) that the following stronger result is also valid: Every P₅-free and C₅-free connected graph contains a minimum-size dominating set that induces a complete subgraph.

Combining the study of the simple random walk on graphs, generating functions (especially Green functions), complex dynamics and general complex analysis we introduce a new method for spectral analysis on self-similar graphs.First, for a rather general, axiomatically defined class of self-similar graphs a graph theoretic analogue to the Banach fixed point theorem is proved. The subsequent results hold for a subclass consisting of “symmetrically” self-similar graphs which however is still more general then...

If X is a geodesic metric space and x 1; x 2; x 3 ∈ X, a geodesic triangle T = {x 1; x 2; x 3} is the union of the three geodesics [x 1 x 2], [x 2 x 3] and [x 3 x 1] in X. The space X is δ-hyperbolic (in the Gromov sense) if any side of T is contained in a δ-neighborhood of the union of the two other sides, for every geodesic triangle T in X. We denote by δ(X) the sharp hyperbolicity constant of X, i.e., δ(X) = inf {δ ≥ 0: X is δ-hyperbolic}. We obtain information about the hyperbolicity constant...

We prove that under appropriate assumptions adding or removing an infinite amount of edges to a given planar graph preserves its non-hyperbolicity, a result which is shown to be false in general. In particular, we make a conjecture that every tessellation graph of ℝ2 with convex tiles is non-hyperbolic; it is shown that in order to prove this conjecture it suffices to consider tessellation graphs of ℝ2 such that every tile is a triangle and a partial answer to this question is given. A weaker version...