A connected undirected graph is called \emph{geodetic} if for every pair of vertices there is a unique shortest path connecting them. It has been conjectured that for finite groups, the …
A connected undirected graph is called \emph{geodetic} if for every pair of vertices there is a unique shortest path connecting them. It has been conjectured that for finite groups, the only geodetic Cayley graphs which occur are odd cycles and complete graphs. In this article we present a series of theoretical results which contribute to a computer search verifying this conjecture for all groups of size up to 1024. The conjecture is also verified theoretically for several infinite families of groups including dihedral and some families of nilpotent groups. Two key results which enable the computer search to reach as far as it does are: if the center of a group has even order, then the conjecture holds (this eliminates all 2-groups from our computer search); if a Cayley graph is geodetic then there are bounds relating the size of the group, generating set and center (which cuts down the number of generating sets which must be searched significantly).
We call a graph $k$-geodetic, for some $k\geq 1$, if it is connected and between any two vertices there are at most $k$ geodesics. It is shown that any hyperbolic …
We call a graph $k$-geodetic, for some $k\geq 1$, if it is connected and between any two vertices there are at most $k$ geodesics. It is shown that any hyperbolic group with a $k$-geodetic Cayley graph is virtually-free. Furthermore, in such a group the centraliser of any infinite order element is an infinite cyclic group. These results were known previously only in the case that $k=1$. A key tool used to develop the theorem is a new graph theoretic result concerning ``ladder-like structures'' in a $k$-geodetic graph.
We prove that the topological cycle space C(G) of a locally finite graph G is generated by its geodetic topological circles. We further show that, although the finite cycles of …
We prove that the topological cycle space C(G) of a locally finite graph G is generated by its geodetic topological circles. We further show that, although the finite cycles of G generate C(G), its finite geodetic cycles need not generate C(G).
Given a finite group $G$, the generating graph $\Gamma(G)$ of $G$ has as vertices the non-identity elements of $G$ and two vertices are adjacent if and only if they are …
Given a finite group $G$, the generating graph $\Gamma(G)$ of $G$ has as vertices the non-identity elements of $G$ and two vertices are adjacent if and only if they are distinct and generate $G$ as group elements. Let $G$ be a 2-generated finite group. We prove that $\Gamma(G)$ is planar if and only if $G$ is isomorphic to one of the following groups: $C_2, C_3, C_4, C_5, C_6, C_2 \times C_2, D_3, D_4, Q_8, C_4\times C_2, D_6.$
Given a finite group $G$, the generating graph $Γ(G)$ of $G$ has as vertices the non-identity elements of $G$ and two vertices are adjacent if and only if they are …
Given a finite group $G$, the generating graph $Γ(G)$ of $G$ has as vertices the non-identity elements of $G$ and two vertices are adjacent if and only if they are distinct and generate $G$ as group elements. Let $G$ be a 2-generated finite group. We prove that $Γ(G)$ is planar if and only if $G$ is isomorphic to one of the following groups: $C_2, C_3, C_4, C_5, C_6, C_2 \times C_2, D_3, D_4, Q_8, C_4\times C_2, D_6.$
There does not exist a Borel choice of generators for each finitely generated group which has the property that isomorphic groups are assigned isomorphic Cayley graphs.
There does not exist a Borel choice of generators for each finitely generated group which has the property that isomorphic groups are assigned isomorphic Cayley graphs.
We find necessary and sufficient conditions for a finitely generated group with more than one end to have a planar Cayley graph.
We find necessary and sufficient conditions for a finitely generated group with more than one end to have a planar Cayley graph.
This study introduces a new geodetic invariant, the path-induced geodetic number of a connected simple graph G.We investigate its properties and characterize the path-induced geodetic sets of some common graphs.Also, …
This study introduces a new geodetic invariant, the path-induced geodetic number of a connected simple graph G.We investigate its properties and characterize the path-induced geodetic sets of some common graphs.Also, the path-induced geodetic numbers of these graphs are determined.
The classical Cayley map, X --> (I_n-X)/(I_n+X), is a birational isomorphism between the special orthogonal group SO_n and its Lie algebra so_n, which is SO_n-equivariant with respect to the conjugating …
The classical Cayley map, X --> (I_n-X)/(I_n+X), is a birational isomorphism between the special orthogonal group SO_n and its Lie algebra so_n, which is SO_n-equivariant with respect to the conjugating and adjoint actions respectively. We ask whether or not maps with these properties can be constructed for other algebraic groups. We show that the answer is usually "no", with a few exceptions. In particular, we show that a Cayley map for the group SL_n exists if and only if n <= 3. This answers an old question of Luna.
The classical Cayley map, <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="upper X right-arrow from bar left-parenthesis upper I Subscript n Baseline minus upper X right-parenthesis left-parenthesis upper I Subscript n Baseline plus …
The classical Cayley map, <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="upper X right-arrow from bar left-parenthesis upper I Subscript n Baseline minus upper X right-parenthesis left-parenthesis upper I Subscript n Baseline plus upper X right-parenthesis Superscript negative 1"> <mml:semantics> <mml:mrow> <mml:mi>X</mml:mi> <mml:mo stretchy="false">↦<!-- ↦ --></mml:mo> <mml:mo stretchy="false">(</mml:mo> <mml:msub> <mml:mi>I</mml:mi> <mml:mi>n</mml:mi> </mml:msub> <mml:mo>−<!-- − --></mml:mo> <mml:mi>X</mml:mi> <mml:mo stretchy="false">)</mml:mo> <mml:mo stretchy="false">(</mml:mo> <mml:msub> <mml:mi>I</mml:mi> <mml:mi>n</mml:mi> </mml:msub> <mml:mo>+</mml:mo> <mml:mi>X</mml:mi> <mml:msup> <mml:mo stretchy="false">)</mml:mo> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mo>−<!-- − --></mml:mo> <mml:mn>1</mml:mn> </mml:mrow> </mml:msup> </mml:mrow> <mml:annotation encoding="application/x-tex">X \mapsto (I_n-X)(I_n+X)^{-1}</mml:annotation> </mml:semantics> </mml:math> </inline-formula>, is a birational isomorphism between the special orthogonal group <bold>SO</bold><inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="Subscript n"> <mml:semantics> <mml:msub> <mml:mi /> <mml:mi>n</mml:mi> </mml:msub> <mml:annotation encoding="application/x-tex">_n</mml:annotation> </mml:semantics> </mml:math> </inline-formula> and its Lie algebra <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="German s o Subscript n"> <mml:semantics> <mml:msub> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mi mathvariant="fraktur">s</mml:mi> </mml:mrow> <mml:mi>o</mml:mi> </mml:mrow> <mml:mi>n</mml:mi> </mml:msub> <mml:annotation encoding="application/x-tex">{\mathfrak so}_n</mml:annotation> </mml:semantics> </mml:math> </inline-formula>, which is <bold>SO</bold><inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="Subscript n"> <mml:semantics> <mml:msub> <mml:mi /> <mml:mi>n</mml:mi> </mml:msub> <mml:annotation encoding="application/x-tex">_n</mml:annotation> </mml:semantics> </mml:math> </inline-formula>-equivariant with respect to the conjugating and adjoint actions, respectively. We ask whether or not maps with these properties can be constructed for other algebraic groups. We show that the answer is usually “no", with a few exceptions. In particular, we show that a Cayley map for the group <bold>SL</bold><inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="Subscript n"> <mml:semantics> <mml:msub> <mml:mi /> <mml:mi>n</mml:mi> </mml:msub> <mml:annotation encoding="application/x-tex">_n</mml:annotation> </mml:semantics> </mml:math> </inline-formula> exists if and only if <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="n less-than-or-slanted-equals 3"> <mml:semantics> <mml:mrow> <mml:mi>n</mml:mi> <mml:mo>⩽<!-- ⩽ --></mml:mo> <mml:mn>3</mml:mn> </mml:mrow> <mml:annotation encoding="application/x-tex">n \leqslant 3</mml:annotation> </mml:semantics> </mml:math> </inline-formula>, answering an old question of <sc>Luna</sc>.
Let Γ be a finite group with a nonempty subset A. The Cayley graph Cay (Γ, A) of Γ generated by A is defined as the digraph with vertex set …
Let Γ be a finite group with a nonempty subset A. The Cayley graph Cay (Γ, A) of Γ generated by A is defined as the digraph with vertex set Γ and edge set {(x,y) | x -1 y ∈ A}. Cay (Γ, A) can be regarded as an undirected graph if x -1 ∈ A for all x ∈ A. Let [Formula: see text] denote the largest integer M so that there exists a set of integers A = {±1, ±a 2 ;…, ±a k } such that the average distance between all pairs of vertices of Cay (ℤ M ,A) is at most r, where ℤ M is the additive group of residue classes modulo M. It is proved in this paper that [Formula: see text] It is also proved that [Formula: see text]
For two vertices u and v of a graph G, the closed interval I[u, v] consists of u, v, and all vertices lying in some u − v geodesic in …
For two vertices u and v of a graph G, the closed interval I[u, v] consists of u, v, and all vertices lying in some u − v geodesic in G. If S is a set of vertices of G, then I[S] is the union of all sets I[u, v] for u, v ∈ S. If I[S] = V (G), then S is a geodetic set for G. The geodetic number g(G) is the minimum cardinality of a geodetic set. A set S of vertices in a graph G is uniform if the distance between every two distinct vertices of S is the same fixed number. A geodetic set is essential if for every two distinct vertices u, v ∈ S, there exists a third vertex w of G that lies in some u− v geodesic but in no x− y geodesic for x, y ∈ S and {x, y} 6= {u, v}. It is shown that for every integer k ≥ 2, there exists a connected graph G with g(G) = k which contains a uniform, essential minimum geodetic set. A minimal geodetic set S has no proper subset which is a geodetic set. The maximum cardinality of a minimal geodetic set is the upper geodetic number g(G). It is shown that every two integers a and b with 2 ≤ a ≤ b are realizable as the geodetic and upper geodetic numbers, respectively, of some graph and when a < b the minimum order of such a graph is b + 2.
In this paper, we introduce the strongly closed geodetic number of a graph and determine its values for some graphs including graphs that resulted from the join, corona and composition …
In this paper, we introduce the strongly closed geodetic number of a graph and determine its values for some graphs including graphs that resulted from the join, corona and composition of connected graphs. We also solve a realization problem involving geodetic number, strongly closed geodetic number, order and diameter of a graph.
A graph Γ is called locally-primitive if the vertex stabilizer (AutΓ)α is primitive on the neighbor set of α for each vertex α. In this paper, we classify locally-primitive Cayley …
A graph Γ is called locally-primitive if the vertex stabilizer (AutΓ)α is primitive on the neighbor set of α for each vertex α. In this paper, we classify locally-primitive Cayley graphs of dihedral groups, while 2-arc-transitive Cayley graphs of dihedral groups have been classified by a series of papers in the literature.
Permutation groups are one of the oldest topics in algebra. However, their study has recently been revolutionised by new developments, particularly the classification of finite simple groups, but also relations …
Permutation groups are one of the oldest topics in algebra. However, their study has recently been revolutionised by new developments, particularly the classification of finite simple groups, but also relations with logic and combinatorics, and importantly, computer algebra systems have been introduced that can deal with large permutation groups. This book gives a summary of these developments, including an introduction to relevant computer algebra systems, sketch proofs of major theorems, and many examples of applying the classification of finite simple groups. It is aimed at beginning graduate students and experts in other areas, and grew from a short course at the EIDMA institute in Eindhoven.
Journal Article MOORE GEOMETRIES AND RANK 3 GROUPS HAVING μ=1 Get access WILLIAM M. KANTOR WILLIAM M. KANTOR University of OregonEugene, Oregon 97403 U.S.A. Search for other works by this …
Journal Article MOORE GEOMETRIES AND RANK 3 GROUPS HAVING μ=1 Get access WILLIAM M. KANTOR WILLIAM M. KANTOR University of OregonEugene, Oregon 97403 U.S.A. Search for other works by this author on: Oxford Academic Google Scholar The Quarterly Journal of Mathematics, Volume 28, Issue 3, September 1977, Pages 309–328, https://doi.org/10.1093/qmath/28.3.309 Published: 01 September 1977 Article history Received: 13 November 1975 Revision received: 24 September 1976 Published: 01 September 1977
This note treats the existence of connected, undirected graphs homogeneous of degree d and of diameter k, having a number of nodes which is maximal according to a certain definition. …
This note treats the existence of connected, undirected graphs homogeneous of degree d and of diameter k, having a number of nodes which is maximal according to a certain definition. For k = 2 unique graphs exist for d = 2,3,7 and possibly for d = 57 (which is undecided), but for no other degree. For k = 3 a graph exists only for d = 2. The proof exploits the characteristic roots and vectors of the adjacency matrix (and its principal submatrices) of the graph.
Abstract Given a group G and a finite generating set G , we take p G : G → Z to be the function which counts the number of geodesics …
Abstract Given a group G and a finite generating set G , we take p G : G → Z to be the function which counts the number of geodesics for each group element g . This generalizes Pascal's triangle. We compute p G for word hyperbolic and describe generic behaviour in abelian groups.
In this paper, we shall first describe the theory of distance-regular graphs and then apply it to the classification of Moore graphs. The object of the paper is to prove …
In this paper, we shall first describe the theory of distance-regular graphs and then apply it to the classification of Moore graphs. The object of the paper is to prove that there are no Moore graphs (other than polygons) of diameter ≥ 3. An independent proof of this result has been given by Barmai and Ito(1). Taken with the result of (4), this shows that the only possible Moore graphs are the following:
We prove that the groups presented by finite convergent monadic rewriting systems with generators of finite order are exactly the free products of finitely many finite groups, thereby confirming Gilman’s …
We prove that the groups presented by finite convergent monadic rewriting systems with generators of finite order are exactly the free products of finitely many finite groups, thereby confirming Gilman’s conjecture in a special case. We also prove that the finite cyclic groups of order at least three are the only finite groups admitting a presentation by more than one finite convergent monadic rewriting system (up to relabelling), and these admit presentation by exactly two such rewriting systems.
This paper describes a new approach to the problem of generating the class of all geodetic graphs homeomorphic to a given geodetic one. An algorithmic procedure is elaborated to carry …
This paper describes a new approach to the problem of generating the class of all geodetic graphs homeomorphic to a given geodetic one. An algorithmic procedure is elaborated to carry out a systematic finding of such a class of graphs. As a result, the enumeration of the class of geodetic graphs homeomorphic to certain Moore graphs has been performed.
We call a graph k-geodetic, for some [Formula: see text], if it is connected and between any two vertices there are at most k geodesics. It is shown that any …
We call a graph k-geodetic, for some [Formula: see text], if it is connected and between any two vertices there are at most k geodesics. It is shown that any hyperbolic group with a k-geodetic Cayley graph is virtually-free. Furthermore, in such a group the centralizer of any infinite order element is an infinite cyclic group. These results were known previously only in the case that [Formula: see text]. A key tool used to develop the theorem is a new graph theoretic result concerning “ladder-like structures” in a k-geodetic graph.