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