In this paper, we construct a class of infinite graphs, called substitution graphs. The vertex set consists of all finite words over a finite alphabet. A directed graph is formed by adding vertical edges connecting each word to its children and horizontal edges defined recursively by two finite directed graphs G and J: edges among vertices with the same parent follow G, while edges between vertices whose parents are horizontally linked follow J. The substitution graph is defined as its underlying graph. Substitution graphs provide a purely combinatorial model of self-similar structures, independent of any underlying geometric structure. Furthermore, we establish a necessary and sufficient condition for substitution graphs to be hyperbolic, formulated in terms of the vanishing of path matrices associated with sufficiently long shortest horizontal paths. Based on this characterization, we further derive several conditions that are either necessary or sufficient for hyperbolicity, depending only on the generators G and J.
The generating graph $\Gamma(G)$ of a group $G$ is the graph whose vertex set is $G$, where two distinct vertices are adjacent if and only if they generate $G$. In this paper, we systematically study the structure of generating graphs of finite abelian groups (non-cyclic) and determine the set of all generating pairs....
In this article, we introduce the notion of connected finite graphs with disjoint cycles in normal form and show that any such graph can be transformed into a normal form graph via a finite sequence of in-splittings and out-splittings. Consequently, we provide number-theoretic criteria for meteor graphs of length three...
We prove that the realization graph of every graphical degree sequence is maximally Hamiltonian: it is Hamilton-laceable when bipartite on more than one vertex, and Hamilton-connected otherwise. This answers Problem P59 of M\"utze's survey of combinatorial Gray codes, and the Hamiltonicity question recorded as open by...
Pseudosimilar vertices are vertices in distinct automorphism orbits whose deletions produce isomorphic graphs. Classical work has studied the existence, group-theoretic origin, and construction of large sets of such vertices. We ask a different recursive question: how long can one repeatedly delete a vertex that is pse...
We study graph products of groups over defining graphs of arbitrary cardinality from two closely related viewpoints. First, we characterize acylindrical hyperbolicity. If the defining graph is irreducible, has at least two vertices, and has a finite star base, then every parabolically full subgroup is either virtually...
Gianluca Paolini, Jean-Luc Rabideau· 0 citations
We use cookies to run the site and, with your consent, for analytics and to show ads.
See our Cookie Policy.
