For each integer $k\ge 6$ and each finite graph $L$, we construct a Coxeter group $W$ and a non positively curved polygonal complex $A$ on which $W$ acts properly cocompactly, such that each polygon of $A$ has $k$ edges, and the link of each vertex of $A$ is isomorphic to $L$. If $L$ is a “generalized $m$-gon”, then $A$ is a Tits building modelled on a reflection group of the hyperbolic plane. We give a condition on $\mathrm{Aut}\left(L\right)$ for $\mathrm{Aut}\left(A\right)$ to be non enumerable (which is satisfied if $L$ is a thick classical generalized $m$-gon). On the other hand,...

For an ordered set $W=\{w_1,w_2,\cdots ,w_k\}$ of vertices and a vertex $v$ in a connected graph $G$, the (metric) representation of $v$ with respect to $W$ is the $k$-vector $r\left(v\right|W)=(d(v,w_1),d(v,w_2),\cdots ,d(v,w_k))$, where $d(x,y)$ represents the distance between the vertices $x$ and $y$. The set $W$ is a resolving set for $G$ if distinct vertices of $G$ have distinct representations with respect to $W$. A resolving set of minimum cardinality is called a minimum resolving set or a basis and the cardinality of a basis for $G$ is its dimension $dimG$. A set $S$ of vertices in $G$ is a dominating set...

A directed Cayley graph $C(\Gamma ,X)$ is specified by a group $\Gamma$ and an identity-free generating set $X$ for this group. Vertices of $C(\Gamma ,X)$ are elements of $\Gamma$ and there is a directed edge from the vertex $u$ to the vertex $v$ in $C(\Gamma ,X)$ if and only if there is a generator $x\in X$ such that $ux=v$. We study graphs $C(\Gamma ,X)$ for the direct product $Z_m\times Z_n$ of two cyclic groups $Z_m$ and $Z_n$, and the generating set $X=\left\{\right(0,1),(1,0),(2,0),\cdots ,(p,0\left)\right\}$. We present resolving sets which yield upper bounds on the metric dimension of these graphs for $p=2$ and $3$.

We analyse the spectral phase diagram of Schrödinger operators $T+\lambda V$ on regular tree graphs, with $T$ the graph adjacency operator and $V$ a random potential given by $iid$ random variables. The main result is a criterion for the emergence of absolutely continuous $\left(ac\right)$ spectrum due to fluctuation-enabled resonances between distant sites. Using it we prove that for unbounded random potentials $ac$ spectrum appears at arbitrarily weak disorder $(\lambda \ll 1)$ in an energy regime which extends beyond the spectrum of$\sim T$. Incorporating...

Let G = (V,E) be a graph. A set S ⊆ V is a restrained dominating set if every vertex in V-S is adjacent to a vertex in S and to a vertex in V-S. The restrained domination number of G, denoted by ${\gamma }_r\left(G\right)$, is the minimum cardinality of a restrained dominating set of G. A unicyclic graph is a connected graph that contains precisely one cycle. We show that if U is a unicyclic graph of order n, then ${\gamma }_r\left(U\right)\ge ⎡n/3⎤$, and provide a characterization of graphs achieving this bound.

For any nontrivial connected graph $F$ and any graph $G$, the $F$-degree of a vertex $v$ in $G$ is the number of copies of $F$ in $G$ containing $v$. $G$ is called $F$-continuous if and only if the $F$-degrees of any two adjacent vertices in $G$ differ by at most 1; $G$ is $F$-regular if the $F$-degrees of all vertices in $G$ are the same. This paper classifies all $P_4$-continuous graphs with girth greater than 3. We show that for any nontrivial connected graph $F$ other than the star $K_{1,k}$, $k\ge 1$, there exists a regular graph that is not...

This paper analyzes the proof-theoretic strength of an infinite version of several theorems from algorithmic graph theory. In particular, theorems on reachability matrices, shortest path matrices, topological sorting, and minimal spanning trees are considered.