Search

An infinite graph is quasi-transitive if its vertex set has finitely many orbits under the action of its automorphism group. In this paper we obtain a structure theorem for locally finite quasi-transitive graphs avoiding a minor, which is reminiscent of the Robertson-Seymour Graph Minor Structure Theorem. We prove that every locally finite quasi-transitive graph G avoiding a minor has a tree-decomposition whose torsos are finite or planar; moreover the tree-decomposition is canonical, i.e. invariant under the action of the automorphism group of G. As applications of this result, we prove the following. • Every locally finite quasi-transitive graph attains its Hadwiger number, that is, if such a graph contains arbitrarily large clique minors, then it contains an infinite clique minor. This extends a result of Thomassen (1992) [38] who proved it in the (quasi-)4-connected case and suggested that this assumption could be omitted. In particular, this shows that a Cayley graph excludes a finite minor if and only if it avoids the countable clique as a minor. • Locally finite quasi-transitive graphs avoiding a minor are accessible (in the sense of Thomassen and Woess), which extends known results on planar graphs to any proper minor-closed family. • Minor-excluded finitely generated groups are accessible (in the group-theoretic sense) and finitely presented, which extends classical results on planar groups. • The domino problem is decidable in a minor-excluded finitely generated group if and only if the group is virtually free, which proves the minor-excluded case of a conjecture of Ballier and Stein (2018) [7]. [ABSTRACT FROM AUTHOR]

Discovered by Aldous, Diaconis and Shahshahani in the context of card shuffling, the cutoff phenomenon has since then been established for a variety of Markov chains. However, proving cutoff remains a delicate affair, which requires a very detailed knowledge of the chain. Identifying the general mechanisms underlying this phase transition, without having to pinpoint its precise location, remains one of the most fundamental open problems in the area of mixing times. In the present paper, we make a step in this direction by establishing cutoff for all Markov chains with non-negative curvature, under a suitably refined product condition. The result applies, in particular, to the random walk on abelian Cayley expanders satisfying a mild degree assumption, hence to the random walk on almost all abelian Cayley graphs. Our proof relies on a quantitative entropic concentration principle, which we believe to lie behind all cutoff phenomena. [ABSTRACT FROM AUTHOR]

Let G be a graph and F be a connected subgraph of G except for K 1. Let F = { F 1 , F 2 , ... , F k } be a set of subgraphs of G such that each member of F is isomorphic to F. The F -(disjoint)-structure edge-connectivity is the minimum cardinality of F such that E (F) 's removal will disconnect G. If every member of F is isomorphic to a connected subgraph of F , then F -(disjoint)-substructure edge-connectivity is defined similarly. In this paper, we determine the star-(disjoint)-substructure edge-connectivity and star-structure edge-connectivity of an n -regular graph G , and give an upper bound on the star-disjoint-structure edge-connectivity of an n -regular graph G. We derive the F -(disjoint)-substructure edge-connectivity of hypercube-like graphs H L n and Cayley graphs generated by transposition trees Γ n (except for star graphs S n) for F being C 4 and P 4 , and show a lower bound on the F -(disjoint)-structure edge-connectivity of H L n and Γ n (except for S n) for F being C 4 and P 4. As applications, we determine the F -(disjoint)-structure edge-connectivity of crossed cubes C Q n and bubble-sort graphs B n for F being C 4 and P 4 , respectively. Furthermore, we obtain the F -(disjoint)-(sub)structure edge-connectivity of S n for F being C 6 and P 6. [ABSTRACT FROM AUTHOR]

Given a graph G , let S and T be two disjoint vertex subsets of equal size k in G. A many-to-many k -disjoint path cover of G joining S and T is a set of k vertex-disjoint paths between S and T that altogether cover every vertex of the graph. It is said to be paired if each vertex of S must be joined to a designated vertex of T , or unpaired otherwise. Let Γ n be a Cayley graph generated by a transposition tree with bipartition V 0 and V 1. Let S ⊆ V 0 and T ⊆ V 1 be two vertex subsets of equal size two. It is shown in this paper that Γ n has an unpaired many-to-many two-disjoint path cover joining S and T with at most n − 4 faulty edges, where n ≥ 4. The result is optimal with respect to the degree of Γ n. As applications, the edge fault-tolerant two-disjoint path covers for the star network, bubble-sort network and modified bubble-sort network are derived. [ABSTRACT FROM AUTHOR]

An (r , z , k) -mixed graph G has every vertex with undirected degree r , directed in- and out-degree z , and diameter k. In this paper, we study the case r = z = 1 , proposing some new constructions of (1 , 1 , k) -mixed graphs with a large number of vertices N. Our study is based on computer techniques for small values of k and the use of graphs on alphabets for general k. In the former case, the constructions are either Cayley or lift graphs. In the latter case, some infinite families of (1 , 1 , k) -mixed graphs are proposed with diameter of the order of 2 log 2 N. [ABSTRACT FROM AUTHOR]

We study solutions of a quadratic matrix equation arising in Riemannian geometry. Let S be a real symmetric n × n -matrix with zeros on the diagonal and let θ be a real number. We construct nonzero solutions (S , θ) of the set of quadratic equations ∑ k S i , k = 0 and ∑ k S i , k S k , j + S i , j 2 = θ S i , j for i < j. Our solutions relate the equations to strongly regular graphs, to group rings, and to multiplicative characters of finite fields. [ABSTRACT FROM AUTHOR]

In this article we study combinatorial non-positive curvature aspects of various simplicial complexes with natural A ˜ n shaped simplices, including Euclidean buildings of type A ˜ n and Cayley graphs of Garside groups and their quotients by the Garside elements. All these examples fit into the more general setting of lattices with order-increasing Z -actions and the associated lattice quotients proposed in a previous work by the first named author. We show that both the lattice quotients and the lattices themselves give rise to weakly modular graphs, which is a form of combinatorial non-positive curvature. We also show that several other objects fit into this setting of lattices/lattice quotients, including Artin complexes of Artin-Tits groups of type A ˜ n , a class of arc complexes and weak Garside groups arising from a categorical Garside structure in the sense of Bessis. Hence our result also implies to these objects and shows that they give weakly modular graphs. Along the way, we also clarify the relationship between categorical Garside structures, lattices with Z action and different classes of complexes studied this article. We use this point of view to describe the first examples of Garside groups with exotic properties, like non-linearity or rigidity results. [ABSTRACT FROM AUTHOR]

Let s be a positive integer. A graph is s-transitive if its automorphism group is transitive on s-arcs but not on (s + 1)-arcs. In this paper, we study all tetravalent s-transitive graphs of order 6p2. [ABSTRACT FROM AUTHOR]

Consider a unimodular random graph, or just a finitely generated Cayley graph. When does its cycle space have an invariant random generating set of cycles such that every edge is contained in finitely many of the cycles? Generating the free Loop O(1) model as a factor of iid is closely connected to having such a generating set for FK-Ising cluster. We show that geodesic cycles do not always form such a generating set, by showing for a parameter regime of the FK-Ising model on the lamplighter group the origin is contained in infinitely many geodesic cycles. This answers a question by Angel, Ray and Spinka. Then we take a look at how the property of having an invariant locally finite generating set for the cycle space is preserved by Bernoulli percolation, and apply it to the problem of factor of iid presentations of the free Loop O(1) model. [ABSTRACT FROM AUTHOR]

The Swift–Hohenberg equation (SHE) is a partial differential equation that explains how patterns emerge from a spatially homogeneous state. It has been widely used in the theory of pattern formation. Following a recent study by Bramburger and Holzer (SIAM J Math Anal 55(3):2150–2185, 2023), we consider discrete SHE on deterministic and random graphs. The two families of the discrete models share the same continuum limit in the form of a nonlocal SHE on a circle. The analysis of the continuous system, parallel to the analysis of the classical SHE, shows bifurcations of spatially periodic solutions at critical values of the control parameters. However, the proximity of the discrete models to the continuum limit does not guarantee that the same bifurcations take place in the discrete setting in general, because some of the symmetries of the continuous model do not survive discretization. We use the center manifold reduction and normal forms to obtain precise information about the number and stability of solutions bifurcating from the homogeneous state in the discrete models on deterministic and sparse random graphs. Moreover, we present detailed numerical results for the discrete SHE on the nearest-neighbor and small-world graphs. [ABSTRACT FROM AUTHOR]

The asymptotic dimension is an invariant of metric spaces introduced by Gromov in the context of geometric group theory. In this paper, we study the asymptotic dimension of metric spaces generated by graphs and their shortest path metric and show their applications to some continuous spaces. The asymptotic dimension of such graph metrics can be seen as a large scale generalisation of weak diameter network decomposition which has been extensively studied in computer science. We prove that every proper minor-closed family of graphs has asymptotic dimension at most 2, which gives optimal answers to a question of Fujiwara and Papasoglu and (in a strong form) to a problem raised by Ostrovskii and Rosenthal on minor excluded groups. For some special minorclosed families, such as the class of graphs embeddable in a surface of bounded Euler genus, we prove a stronger result and apply this to show that complete Riemannian surfaces have Assouad--Nagata dimension at most 2. Furthermore, our techniques allow us to determine the asymptotic dimension of graphs of bounded layered treewidth and graphs with any fixed growth rate, which are graph classes that are defined by purely combinatorial notions and properly contain graph classes with some natural topological and geometric flavours. [ABSTRACT FROM AUTHOR]

AbstractIn this paper, we construct a family of quasi-strongly regular Cayley graphs which is defined on a finite group G with respect to a proper subgroup H of G and denoted by ΓH(G) . We also compute the full automorphism group and characterize various transitivity properties of ΓH(G) for any group G and for any subgroup H of G. [ABSTRACT FROM AUTHOR]

Based on irreducible representations of generalized quaternion groups, closed‐form formulae of Kirchhoff indices and resistance distances between vertex pairs of Cayley graphs on these groups are given. Closed‐form formulae of Kirchhoff indices and resistance distances between vertex pairs of Cayley graphs on quaternion groups are given by using its irreducible representations. [ABSTRACT FROM AUTHOR]

In this paper we introduce Cayley digraphs associated to finitely generated polygroups, where the vertices correspond to finite products of the generators of polygroups and the edges to multiplication by vertices and generators. We investigate some properties of the Cayley digraphs, emphasizing connectivity and existence of cycles for each vertex of the Cayley digraphs. Particularly, we identify Cayley digraphs on polygroups derived from conjugate classes of dihedral groups. Moreover, we examine some fundamental illustrative examples of Cayley digraphs through the class of gmg-polygroups. [ABSTRACT FROM AUTHOR]

Let G be a finite classical group generated by transvections, i.e., one of SL n (q) , SU n (q) , Sp 2 n (q) , or O 2 n ± (q) (q even) , and let X be a generating set for G containing at least one transvection. Building on work of Garonzi, Halasi, and Somlai, we prove that the diameter of the Cayley graph Cay (G , X) is bounded by (n log ⁡ q) C for some constant C. This confirms Babai's conjecture on the diameter of finite simple groups in the case of generating sets containing a transvection. By combining this with a result of the author and Jezernik it follows that if G is one of SL n (q) , SU n (q) , Sp 2 n (q) and X contains three random generators then with high probability the diameter Cay (G , X) is bounded by n O (log ⁡ q). This confirms Babai's conjecture for non-orthogonal classical simple groups over small fields and three random generators. [ABSTRACT FROM AUTHOR]

We develop a theory of covering digraphs, similar to the theory of covering spaces. By applying this theory to Cayley digraphs, we build a "bridge" between GLMY-theory and group homology theory, which helps to reduce path homology calculations to group homology computations. We show some cases where this approach allows us to fully express path homology in terms of group homology. To illustrate this method, we provide a path homology computation for the Cayley digraph of the additive group of rational numbers with a generating set consisting of inverses to factorials. The main tool in our work is a filtered simplicial set associated with a digraph, which we call the filtered nerve of a digraph. [ABSTRACT FROM AUTHOR]

Given a permutation group 퐺, the derangement graph of 퐺 is the Cayley graph with connection set the derangements of 퐺. The group 퐺 is said to be innately transitive if 퐺 has a transitive minimal normal subgroup. Clearly, every primitive group is innately transitive. We show that, besides an infinite family of explicit exceptions, there exists a function f : N → N such that, if 퐺 is innately transitive of degree 푛 and the derangement graph of 퐺 has no clique of size 푘, then n ≤ f ⁢ (k) . Motivation for this work arises from investigations on Erdős–Ko–Rado type theorems for permutation groups. [ABSTRACT FROM AUTHOR]

Let G be a finite non-abelian simple group, C a non-identity conjugacy class of G, and ΓC the Cayley graph of G based on C ∪ C − 1 . Our main result shows that in any such graph, there is an involution at bounded distance from the identity. [ABSTRACT FROM AUTHOR]

Let Γ be a graph with vertex set V, and let a, b be nonnegative integers. An (a, b)-regular set in Γ is a nonempty proper subset D of V such that every vertex in D has exactly a neighbours in D and every vertex in V \ D has exactly b neighbours in D. In particular, a (1, 1)-regular set is called a total perfect code. Let G be a finite group and S a square-free subset of G closed under conjugation. The Cayley sum graph CayS (G , S) of G is the graph with vertex set G such that two vertices x, y are adjacent if and only if x y ∈ S . A subset (respectively, subgroup) D of G is called an (a, b)-regular set (respectively, subgroup (a, b)-regular set) of G if there exists a Cayley sum graph of G which admits D as an (a, b)-regular set. We obtain two necessary and sufficient conditions for a subgroup of a finite group G to be a total perfect code in a Cayley sum graph of G. We also obtain two necessary and sufficient conditions for a subgroup of a finite abelian group G to be a total perfect code of G. We classify finite abelian groups whose all non-trivial subgroups of even order are total perfect codes of the group, and as a corollary we obtain that a finite abelian group has the property that every non-trivial subgroup is a total perfect code if and only if it is isomorphic to an elementary abelian 2-group. We prove that, for a subgroup H of a finite abelian group G and any pair of positive integers (a, b) within certain ranges depending on H, H is an (a, b)-regular set of G if and only if it is a total perfect code of G. Finally, we give a classification of subgroup total perfect codes of a cyclic group, a dihedral group and a generalized quaternion group. [ABSTRACT FROM AUTHOR]

We endeavored to investigate directed strongly regular Cayley graphs (or DSRCG for short) over dicyclic groups Dic4n = ⟨α, β | αn = β4 = 1, β−1αβ = α −1 ⟩, where n is odd. We derived several DSRCGs over Dic4n for n odd. We then derived a criterion for a certain class of Cayley graph to be directed strongly regular. [ABSTRACT FROM AUTHOR]

Let G be a finite group with the identity e and S be a subset of G ∖︀ { e } such that S = S − 1 . Let m be an integer such that 2 ≤ m ≤ max { o (s) ∣ s ∈ S } , where o (s) is the order of s in G. The m -Cayley hypergraph H of G over S , m - Cay (G , S) , is a hypergraph with vertex set G and an edge set { { s i x ∣ 0 ≤ i ≤ m − 1 } ∣ x ∈ G , s ∈ S }. We discover a necessary and sufficient condition for a subset S of G ∖︀ { e } such that a subgroup H is a perfect code in m - Cay (G , S) and obtain some conditions for a subgroup H that guarantee the existence of a subset S ⊆ G ∖︀ { e } such that H is a perfect code in m - Cay (G , S). [ABSTRACT FROM AUTHOR]

It is proved that for integers b, r such that 3 ≤ b < r ≤ b + 1 2 - 1 , there exists a red/blue edge-colored graph such that the red degree of every vertex is r, the blue degree of every vertex is b, yet in the closed neighbourhood of every vertex there are more blue edges than red edges. The upper bound r ≤ b + 1 2 - 1 is best possible for any b ≥ 3 . We further extend this theorem to more than two colours, and to larger neighbourhoods. A useful result required in some of our proofs, of independent interest, is that for integers r, t such that 0 ≤ t ≤ r 2 2 - 5 r 3 / 2 , there exists an r-regular graph in which each open neighbourhood induces precisely t edges. Several explicit constructions are introduced and relationships with constant linked graphs, (r, b)-regular graphs and vertex transitive graphs are revealed. [ABSTRACT FROM AUTHOR]

The classical Pauli group can be obtained as the central product of the dihedral group of 8 elements with the cyclic group of order 4. Inspired by this characterization, we introduce the notion of central product of Cayley graphs, which allows to regard the Cayley graph of a central product of groups as a quotient of the Cartesian product of the Cayley graphs of the factor groups. We focus our attention on the Cayley graph C a y (P n , S P n ) of the generalized Pauli group P n on n -qubits; in fact, P n may be decomposed as the central product of finite 2-groups, and a suitable choice of the generating set S P n allows us to recognize the structure of central product of graphs in C a y (P n , S P n ). Using this approach, we are able to recursively construct the adjacency matrix of C a y (P n , S P n ) for each n ≥ 1 , and to explicitly describe its spectrum and the associated eigenvectors. It turns out that C a y (P n , S P n ) is a (3 n + 2) -regular bipartite graph on 4 n + 1 vertices, and it has integral spectrum. This is a highly nontrivial property if one considers that, by choosing as a generating set for P 1 the three classical Pauli matrices, one gets the so-called Möbius-Kantor graph, belonging to the class of generalized Petersen graphs, whose spectrum is not integral. [ABSTRACT FROM AUTHOR]

The combinatorial refinement techniques have proven to be an efficient approach to isomorphism testing for particular classes of graphs. If the number of refinement rounds is small, this puts the corresponding isomorphism problem in a low-complexity class. We investigate the round complexity of the two-dimensional Weisfeiler--Leman algorithm on circulant graphs, i.e., on Cayley graphs of the cyclic group Z n , and prove that the number of rounds until stabilization is bounded by O (d (n) log n) , where d (n) is the number of divisors of n. As a particular consequence, isomorphism can be tested in NC for connected circulant graphs of order p ℓ with p an odd prime, ℓ > 3 and vertex degree Δ smaller than p. We also show that the color refinement method (also known as the one-dimensional Weisfeiler--Leman algorithm) computes a canonical labeling for every non-trivial circulant graph with a prime number of vertices after individualization of two appropriately chosen vertices. Thus, the canonical labeling problem for this class of graphs has at most the same complexity as color refinement, which results in a time bound of O (Δ n log n) . Moreover, this provides a first example where a sophisticated approach to isomorphism testing put forward by Tinhofer has a real practical meaning. [ABSTRACT FROM AUTHOR]

In this paper, we focus on studying the non-probability Gibbs measures for a Hard-Core (HC) model on a Cayley tree of order k ≥ 2, where the set of integers ℤ is the set of spin values. It is well known that each Gibbs measure, whether it be a gradient or non-probability measure, of this model corresponds to a boundary law. A boundary law can be thought of as an infinite-dimensional vector function (with strictly positive coordinates) defined at the vertices of the Cayley tree, which satisfies a nonlinear functional equation. Furthermore, every normalizable boundary law corresponds to a Gibbs measure. However, a non-normalizable boundary law can define the gradient or non-probability Gibbs measures. In this paper, we investigate the conditions for uniqueness and non-uniqueness of translation-invariant and periodic non-probability Gibbs measures for the HC model on a Cayley tree of any order k ≥ 2. [ABSTRACT FROM AUTHOR]

It is proved that Tutte's 3-flow conjecture is true for Cayley graphs on groups of order 8p where p is an odd prime. [ABSTRACT FROM AUTHOR]

We investigate some properties of Cayley fuzzy graphs on groups in terms of algebraic structures. And we also discuss the connectedness on it. In this paper, we prove that the Cayley fuzzy graph induced by (Zm × Zn,+, ν) is the disjoint union of Cay(aH, R) provided ν(h) > 0 h H and (h0) = 0 - h0 - Zm ×Zn\H, where H is the cyclic subgroup of order n in Zm × Zn. [ABSTRACT FROM AUTHOR]

Owing to their interesting spectral properties, the synthetic crystals over lattices other than regular Euclidean lattices, such as hyperbolic and fractal ones, have attracted renewed attention, especially from materials and metamaterials research communities. They can be studied under the umbrella of quantum dynamics over Cayley graphs of finitely generated groups. In this work, we investigate numerical aspects related to the quantum dynamics over such Cayley graphs. Using an algebraic formulation of the "periodic boundary condition" due to Lück (Geom Funct Anal 4:455–481, 1994), we devise a practical and converging numerical method that resolves the true bulk spectrum of the Hamiltonians. Exact results on the matrix elements of the resolvent, derived from the combinatorics of the Cayley graphs, give us the means to validate our algorithms and also to obtain new combinatorial statements. Our results open the systematic research of quantum dynamics over Cayley graphs of a very large family of finitely generated groups, which includes the free and Fuchsian groups. [ABSTRACT FROM AUTHOR]

We show that the total variation mixing time is not quasi-isometry invariant, even for Cayley graphs. Namely, we construct a sequence of pairs of Cayley graphs with maps between them that twist the metric in a bounded way, while the ratio of the two mixing times goes to infinity. The Cayley graphs serving as an example have unbounded degrees. For non-transitive graphs, we construct bounded degree graphs for which the mixing time from the worst starting point for one graph is asymptotically smaller than the mixing time from the best starting point of the random walk on a network obtained by increasing some of the edge weights from 1 to $1+o(1)$. [ABSTRACT FROM AUTHOR]

A distance antimagic labeling of graph G = (V, E) of order n is a bijection f: V(G) → {1, 2, . . ., n} with the property that any two distinct vertices x and y satisfy ω(x), ω(y), where ω(x) denotes the open neighborhood sum PΣaN(x)f(a) of a vertex x. In 2013, Kamatchi and Arumugam conjectured that a graph admits a distance antimagic labeling if and only if it contains no two vertices with the same open neighborhood. A circulant graph C(n; S) is a Cayley graph with order n and generating set S, whose adjacency matrix is circulant. This paper provides partial evidence for the conjecture above by presenting distance antimagic labeling for some circulant graphs. In particular, we completely characterized distance antimagic circulant graphs with one generator and distance antimagic circulant graphs C(n; {1, k}) with odd n. [ABSTRACT FROM AUTHOR]

We define biequivalent planar graphs, which are a generalisation of the uniform polyhedron graphs, as planar graphs made out of two families of equivalent nodes. Such graphs are required to identify polyhedral cages with geometries suitable for artificial protein cages. We use an algebraic method, which is followed by an algorithmic method, to determine all such graphs with up to 300 nodes each with valencies ranging between three and six. We also present a graphic representation of every graph found. [ABSTRACT FROM AUTHOR]

"The Union Power Cayley Graph for Cyclic Groups and its Properties" is a technical article that explores the concept of the union power Cayley graph for cyclic groups. The graph combines the power graph and Cayley graph and is important for understanding the algebraic structures of groups. The authors classify the properties of the union power Cayley graphs for cyclic groups with subsets of size two, including connectivity, regularity, completeness, and planarity. They also determine invariants of these graphs, such as clique numbers, vertex chromatic numbers, girths, and diameters. The article provides definitions, theorems, and propositions related to the topic, and references for further reading are provided. [Extracted from the article]

R. Lyons, R. Pemantle and Y. Peres (Ann. Probab. 24 (4), 1996, 1993–2006) conjectured that for a Cayley graph G with a growth rate gr(G) > 1, the speed of a biased random walk exists and is positive for the biased parameter λ ∈ (1, gr(G)). And Gabor Pete (Probability and geometry ´ on groups, Chaper 9, 2024) sheds light on the intricate relationship between the spectral radius of the graph and the speed of the biased random walk. Here, we focus on an example of a Cayley graph, a free product of complete graphs. In this paper, we establish the continuity of the spectral radius of biased random walks with respect to the bias parameter in this class of Cayley graphs. Our method relies on the Kesten-Cheeger-Dodziuk-Mohar theorem and the analysis of generating functions. [ABSTRACT FROM AUTHOR]

In the realm of the four-dimensional Minkowski space L4, the focus is on hypersurfaces classified as right conoids and defined by light-like axes. Matrices associated with the fundamental form, Gauss map, and shape operator, all specifically tailored for these hypersurfaces, are currently undergoing computation. The intrinsic curvatures of these hypersurfaces are determined using the Cayley-Hamilton theorem. The conditions of minimality are addressed by the analysis. The Laplace-Beltrami operator for such hypersurfaces is computed, accompanied by illustrative examples aimed at fostering a more profound understanding of the involved mathematical principles. Additionally, scrutiny is applied to the umbilical condition, and the introduction of the Willmore functional for these hypersurfaces is presented. [ABSTRACT FROM AUTHOR]

Codebooks with small inner-product correlations are desirable in many fields, including compressed sensing, direct spread code division multiple access (CDMA) systems, and space-time codes. The objective of this paper is to present a class of codebooks and explore their applications in strongly regular Cayley graphs. The obtained codebooks are nearly optimal in the sense that their maximum cross-correlation amplitude nearly meets the Welch bound. As far as we know, this construction of codebooks provides new parameters. [ABSTRACT FROM AUTHOR]

We prove universal inequalities for Laplacian eigenvalues with Dirichlet boundary condition on subsets of certain discrete groups. The study of universal inequalities on Riemannian manifolds was initiated by Weyl, Pólya, Yau, and others. Here we focus on a version by Cheng and Yang. Specifically, we prove Yang-type universal inequalities for Cayley graphs of finitely generated amenable groups, as well as for the d-regular tree (simple random walk on the free group). [ABSTRACT FROM AUTHOR]

In this paper the zero forcing number as well as propagation time of Cay(G, Ω), where G is a finite group and Ω ⊂ G\{1} is an inverse closed generator set of G is studied. In particular, it is shown that the propagation time of Cay(G, Ω) is at most two for some special generators. [ABSTRACT FROM AUTHOR]

Cayley graph is a graph that encodes the abstract structure of a group. It gives a way of encoding information about a group in a graph. On the other hand, hypergroup is a generalization of group in which the composition of any two elements is a non-empty set. The purpose of this paper is to find a suitable generalization of Cayley graphs to cover hypergroups. More precisely, we introduce generalized Cayley graphs over hypergroups, study their properties and find a simple tool to construct large connected GCH-graphs from smaller GCH-graphs by using graph product. [ABSTRACT FROM AUTHOR]

In this paper, our focus is on exploring the relative controllability of systems governed by linear fractional differential equations incorporating state delay. We introduce a novel counterpart to the Cayley-Hamilton theorem. Leveraging a delayed perturbation of the Mittag-Leffler function, along with a determining function and an analog of the Cayley-Hamilton theorem, we establish an algebraic Kalman-type rank criterion for assessing the relative controllability of fractional differential equations with state delay. Moreover, we articulate necessary and sufficient conditions for relative controllability criteria concerning linear fractional time-delay systems, expressed in terms of a new α -Gramian matrix and define a control which transfer the system from any initial state to any final state within a given time. The theoretical findings are exemplified through the presentation of illustrative examples. [ABSTRACT FROM AUTHOR]

Let C be a smooth, projective and geometrically integral curve defined over a finite field F. For each closed point P ∞ of C , let R be the ring of functions that are regular outside P ∞ , and let K be the completion at P ∞ of the function field of C. In order to study groups of the form GL 2 (R) , Serre describes the quotient graph GL 2 (R) ﹨ t , where t is the Bruhat-Tits tree defined from SL 2 (K). In this work we describe the associated quotient graph H ﹨ t for the action on t of the group H = { ( a b c d ) ∈ GL 2 (R) : c ≡ 0 (mod I) } , where I is an ideal of R. These groups play, in the function field context, the same role as the Hecke congruence subgroups of SL 2 (Z). To be precise, we give a explicit formula for the cusp number of H ﹨ t. Then, by using Bass-Serre Theory, we describe H as an amalgamated product of simpler groups, and we also describe its abelianization. [ABSTRACT FROM AUTHOR]

A simple undirected regular graph is said to be semisymmetric if it is edge-transitive but not vertex-transitive. For a semisymmetric graph Γ of order 2 p 3 , p a prime, it is well known that Γ is bipartite with two biparts having equal size. The complete classification of such graphs has been given for the full automorphism group Aut (Γ) acting unfaithfully on at least one bipart of Γ , which shows that there is only one infinite family of such graphs with valency p 2. The graphs of this kind have been determined when Aut (Γ) acts faithfully and primitively on at least one bipart of Γ , and thus there is only one remaining case for classifying such graphs of valency p 2 , Aut (Γ) acting faithfully and imprimitively on both biparts of Γ , which is dealt with in this paper. As a result, there is only one infinite family of semisymmetric graphs of order 2 p 3 with valency p 2. [ABSTRACT FROM AUTHOR]

Transposition graph T n is defined as a Cayley graph over the symmetric group generated by all transpositions. It is known that all eigenvalues of T n are integers. Moreover, zero is its eigenvalue for any n ⩾ 4. But the exact distribution of the spectrum of the graph T n is unknown. In this paper we prove that integers from the interval [ − n − 4 2 , n − 4 2 ] lie in the spectrum of T n for any n ⩾ 19. [ABSTRACT FROM AUTHOR]

We show that the category of X-generated E-unitary inverse monoids with greatest group image G is equivalent to the category of G-invariant, finitary closure operators on the set of connected subgraphs of the Cayley graph of G. Analogously, we study F-inverse monoids in the extended signature (· , 1 , - 1 , m) , and show that the category of X-generated F-inverse monoids with greatest group image G is equivalent to the category of G-invariant, finitary closure operators on the set of all subgraphs of the Cayley graph of G. As an application, we show that presentations of F-inverse monoids in the extended signature can be studied by tools analogous to Stephen's procedure in inverse monoids, in particular, we introduce the notions of F-Schützenberger graphs and P-expansions. [ABSTRACT FROM AUTHOR]

We consider a mixed-type model given by the three-state Ising–Potts model on a Cayley tree. A criterion for the existence of limit Gibbs measures for this model on an arbitrary-order Cayley tree is obtained. Translation-invariant Gibbs measures on a second-order Cayley tree are studied. The existence of a phase transition is proved: a range of parameter values is found in which there are one to seven Gibbs measures for the three-state Ising–Potts model. [ABSTRACT FROM AUTHOR]

In this paper, we investigate the spectrum of a class of weighted Laplacians on Cayley graphs and determine under what conditions the corresponding eigenspaces are generically irreducible. Specifically, we analyze the spectrum on left-invariant Cayley graphs endowed with an invariant metric, and we give some criteria for generically irreducible eigenspaces. Additionally, we introduce an operator that is comparable to the Laplacian and show that the same criterion holds. [ABSTRACT FROM AUTHOR]

We study generalizations of Chiswell's theorem that 0-hyperbolic Lyndon length functions on groups always arise as based length functions of the group acting isometrically on a tree. We produce counter-examples to show that this Theorem fails if one replaces 0-hyperbolicity with δ-hyperbolicity. We then propose a set of axioms for the length function on a finitely generated group that ensures the function is bi-Lipschitz equivalent to a (or any) length function of the group acting on its Cayley graph with respect to some finite generating set. [ABSTRACT FROM AUTHOR]

We say that a Hamilton cycle C = (x 1 , ... , x n) in a graph G is k-symmetric, if the mapping x i ↦ x i + n / k for all i = 1 , ... , n , where indices are considered modulo n, is an automorphism of G. In other words, if we lay out the vertices x 1 , ... , x n equidistantly on a circle and draw the edges of G as straight lines, then the drawing of G has k-fold rotational symmetry, i.e., all information about the graph is compressed into a 360 ∘ / k wedge of the drawing. The maximum k for which there exists a k-symmetric Hamilton cycle in G is referred to as the Hamilton compression of G. We investigate the Hamilton compression of four different families of vertex-transitive graphs, namely hypercubes, Johnson graphs, permutahedra and Cayley graphs of abelian groups. In several cases, we determine their Hamilton compression exactly, and in other cases, we provide close lower and upper bounds. The constructed cycles have a much higher compression than several classical Gray codes known from the literature. Our constructions also yield Gray codes for bitstrings, combinations and permutations that have few tracks and/or that are balanced. [ABSTRACT FROM AUTHOR]