-
Spectral Methods for Matrix Product Factorization
Abstract: A graph $G$ is factored into graphs $H$ and $K$ via a matrix product if there exist adjacency matrices $A$, $B$, and $C$ of $G$, $H$, and $K$, respectively, such that $A = BC$. In this paper, we study the spectral aspects of the matrix product of graphs, including regularity, bipartiteness, and connectivity. We show that if a graph $G$ is factored into a connected graph $H$ and a graph $K$ with no… ▽ More
Submitted 4 July, 2024; originally announced July 2024.
Comments: Comments are welcome
MSC Class: 05C50; 15A18
-
arXiv:2404.05992 [pdf, ps, other]
Graphs of bounded chordality
Abstract: A hole in a graph is an induced subgraph which is a cycle of length at least four. A graph is chordal if it contains no holes. Following McKee and Scheinerman (1993), we define the chordality of a graph $G$ to be the minimum number of chordal graphs on $V(G)$ such that the intersection of their edge sets is equal to $E(G)$. In this paper we study classes of graphs of bounded chordality. In the 1… ▽ More
Submitted 8 April, 2024; originally announced April 2024.
-
Subgroups arising from connected components in the Morse boundary
Abstract: We study connected components of the Morse boundary and their stabilisers. We introduce the notion of point-convergence and show that if the set of non-singleton connected components of the Morse boundary of a finitely generated group $G$ is point-convergent, then every non-singleton connected component is the (relative) Morse boundary of its stabiliser. The above property only depends on the topo… ▽ More
Submitted 6 March, 2024; originally announced March 2024.
Comments: 18 pages, 5 figures, comments welcome!
MSC Class: 20F65; 20F67
-
On Separating Path and Tree Systems in Graphs
Abstract: We explore the concept of separating systems of vertex sets of graphs. A separating system of a set $X$ is a collection of subsets of $X$ such that for any pair of distinct elements in $X$, there exists a set in the separating system that contains exactly one of the two elements. A separating system of the vertex set of a graph $G$ is called a vertex-separating path (tree) system of $G$ if the ele… ▽ More
Submitted 21 December, 2023; originally announced December 2023.
Comments: 23 page, 3 figures
-
On Matrix Product Factorization of graphs
Abstract: In this paper, we explore the concept of the ``matrix product of graphs," initially introduced by Prasad, Sudhakara, Sujatha, and M. Vinay. This operation involves the multiplication of adjacency matrices of two graphs with assigned labels, resulting in a weighted digraph. Our primary focus is on identifying graphs that can be expressed as the graphical matrix product of two other graphs. Notably,… ▽ More
Submitted 13 December, 2023; originally announced December 2023.
MSC Class: 05C76; 05C25; 15A09
-
arXiv:2303.11124 [pdf, ps, other]
On vertex-transitive graphs with a unique hamiltonian cycle
Abstract: A graph is said to be uniquely hamiltonian if it has a unique hamiltonian cycle. For a natural extension of this concept to infinite graphs, we find all uniquely hamiltonian vertex-transitive graphs with finitely many ends, and also discuss some examples with infinitely many ends. In particular, we show each nonabelian free group $F_n$ has a Cayley graph of degree $2n + 2$ that has a unique hamilt… ▽ More
Submitted 18 April, 2023; v1 submitted 20 March, 2023; originally announced March 2023.
-
arXiv:2204.05484 [pdf, ps, other]
Hamiltonicity in generalized quasi-dihedral groups
Abstract: Witte Morris showed in [21] that every connected Cayley graph of a finite (generalized) dihedral group has a Hamiltonian path. The infinite dihedral group is defined as the free product with amalgamation $\mathbb Z_2 \ast \mathbb Z_2$. We show that every connected Cayley graph of the infinite dihedral group has both a Hamiltonian double ray, and extend this result to all two-ended generalized quas… ▽ More
Submitted 11 April, 2022; originally announced April 2022.
-
arXiv:2203.11017 [pdf, ps, other]
Arc-disjoint hamiltonian paths in Cartesian products of directed cycles
Abstract: We show that if $C_1$ and $C_2$ are directed cycles (of length at least two), then the Cartesian product $C_1 \Box C_2$ has two arc-disjoint hamiltonian paths. (This answers a question asked by J. A. Gallian in 1985.) The same conclusion also holds for the Cartesian product of any four or more directed cycles (of length at least two), but some cases remain open for the Cartesian product of three d… ▽ More
Submitted 22 March, 2022; v1 submitted 21 March, 2022; originally announced March 2022.
Comments: 25 pages, 2 figures
-
arXiv:2003.14203 [pdf, ps, other]
Two characterisations of accessible quasi-transitive graphs
Abstract: We prove two characterisations of accessibility of locally finite quasi-transitive connected graphs. First, we prove that any such graph $G$ is accessible if and only if its set of separations of finite order is an ${\rm Aut}(G)$-finitely generated semiring. The second characterisation says that $G$ is accessible if and only if every process of splittings in terms of tree amalgamations stops after… ▽ More
Submitted 31 March, 2020; originally announced March 2020.
Comments: 15 pages
-
Canonical trees of tree-decompositions
Abstract: We prove that every graph has a canonical tree of tree-decompositions that distinguishes all principal tangles (these include the ends and various kinds of large finite dense structures) efficiently. Here `trees of tree-decompositions' are a slightly weaker notion than `tree-decompositions' but much more well-behaved than `tree-like metric spaces'. This theorem is best possible in the sense that… ▽ More
Submitted 7 April, 2020; v1 submitted 27 February, 2020; originally announced February 2020.
Comments: 22 pages
-
arXiv:1902.02307 [pdf, ps, other]
Splitting groups with cubic Cayley graphs of connectivity two
Abstract: A group $G$ splits over a subgroup $C$ if $G$ is either a free product with amalgamation $A \underset{C}{\ast} B$ or an HNN-extension $G=A \underset{C}{\ast} (t)$. We invoke Bass-Serre theory and classify all infinite groups which admit cubic Cayley graphs of connectivity two in terms of splittings over a subgroup.
Submitted 19 April, 2021; v1 submitted 6 February, 2019; originally announced February 2019.
Comments: The last version of the paper has been replaced
MSC Class: 05C63; 20E06; 20E08
Journal ref: Algebr. Comb,(4)6,971--987, 2021
-
arXiv:1812.06312 [pdf, ps, other]
A Stallings' type theorem for quasi-transitive graphs
Abstract: We consider infinite connected quasi-transitive locally finite graphs and show that every such graph with more than one end is a tree amalgamation of two other such graphs. This can be seen as a graph-theoretical version of Stallings' splitting theorem for multi-ended finitely generated groups and indeed it implies this theorem. It will also lead to a characterisation of accessible graphs in terms… ▽ More
Submitted 18 June, 2019; v1 submitted 15 December, 2018; originally announced December 2018.
Comments: 24 pages
-
arXiv:1812.04866 [pdf, ps, other]
Two-ended quasi-transitive graphs
Abstract: The well-known characterization of two-ended groups says that every two-ended group can be split over finite subgroups which means it is isomorphic to either by a free product with amalgamation $A\ast_C B$ or an HNN-extension $\ast_φ C$, where $C$ is a finite group and $[A:C]=[B:C]=2$ and $φ\in Aut(C)$. In this paper, we show that there is a way in order to spilt two-ended quasi-transitive graphs… ▽ More
Submitted 12 December, 2018; originally announced December 2018.
MSC Class: 05C45; 05C63; 20E06; 20E08
-
arXiv:1708.03476 [pdf, ps, other]
From cycles to circles in Cayley graphs
Abstract: For locally finite infinite graphs the notion of Hamilton cycles can be extended to Hamilton circles, homeomorphic images of $S^1$ in the Freudenthal compactification. In this paper we extend some well-known theorems of the Hamiltonicity of finite Cayley graphs to infinite Cayley graphs.
Submitted 11 August, 2017; originally announced August 2017.
MSC Class: 05C25; 05C45; 05C63; 20E06; 20F05; 37F20
-
arXiv:1612.05803 [pdf, ps, other]
Inverse Limits and Topologies of Infinite Graphs
Abstract: Two of the natural topologies for infinite graphs with edge-ends are Etop and Itop. In this paper, we study and characterize them. We show that Itop can be constructed by inverse limits of inverse systems of graphs with finitely many vertices. Furthermore, as an application of the inverse limit approach, we construct a topological spanning tree in Itop
Submitted 17 December, 2016; originally announced December 2016.
MSC Class: 05C10; 05C63; 57M15; 57M99
-
Hamilton circles in Cayley graphs
Abstract: For locally finite infinite graphs the notion of Hamilton cycles can be extended to Hamilton circles, homeomorphic images of $S^1$ in the Freudenthal compactification. In this paper we prove of a sufficient condition for the existence of Hamilton circles in locally finite Cayley graphs.
Submitted 18 January, 2017; v1 submitted 5 September, 2016; originally announced September 2016.
Comments: 15 pages, 2 figures
MSC Class: 05C25; 05C45; 05C63; 20E06; 20F05; 37F20
-
arXiv:1508.02872 [pdf, ps, other]
Algebraic flow theory of infinite graphs
Abstract: A problem by Diestel is to extend algebraic flow theory of finite graphs to infinite graphs with ends. In order to pursue this problem, we define an A-flow and non-elusive H-flow for arbitrary graphs and for abelian topological Hausdorff groups H and compact subsets A of H. We use these new definitions to extend several well-known theorems of flows in finite graphs to infinite graphs.
Submitted 23 December, 2016; v1 submitted 12 August, 2015; originally announced August 2015.
Journal ref: European Journal of Combinatorics, Volume 62, May 2017, Pages 58-69
-
arXiv:1307.5401 [pdf, ps, other]
A Note on Co-Maximal Ideal Graph of Commutative Rings
Abstract: Let $R$ be a commutative ring with unity. The co-maximal ideal graph of $R$, denoted by $Γ(R)$, is a graph whose vertices are the proper ideals of $R$ which are not contained in the Jacobson radical of $R$, and two vertices $I_1$ and $I_2$ are adjacent if and only if $I_1 + I_2 = R$. We classify all commutative rings whose co-maximal ideal graphs are planar. In 2012 the following question was pose… ▽ More
Submitted 26 October, 2015; v1 submitted 20 July, 2013; originally announced July 2013.