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 to be strongly shift equivalent, where a meteor graph of length three is a connected finite essential graph consisting of three disjoint cycles which makes a unique chain of cycles of length three. We then prove that meteor graphs of length three whose cycle lengths are pairwise coprime are shift equivalent if and only if they are strongly shift equivalent, if and only if their corresponding Leavitt path algebras are graded Morita equivalent, if and only if their graded $K$-theories, $K^{gr}_0$, are order-preserving $\mathbb{Z}[x, x^{-1}]$-module isomorphic. As a consequence, Williams'Conjecture and Hazrat's Graded Morita Equivalence Conjecture hold for graphs with disjoint cycles that contain exactly three cycles whose lengths are pairwise coprime.
We initiate a systematic study of Inc-invariant chains of graphs, the combinatorial counterparts of Inc-invariant chains of edge ideals arising in the theory of equivariant Noetherianity. Such a chain consists of graphs on growing vertex sets whose edge sets are compatible with the action of the monoid of strictly incr...
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...
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:...
Qing-Cheng Zeng, Cheng Zeng, Yu-Mei Xue et al.· 0 citations
We prove three theorems on the flow monoids of finite graphs. First, we show that a non-empty finite graph G = (V, E) is connected if and only if its flow monoid contains a constant map on V, equivalently, if and only if it contains all constant maps on V. Second, we give a new characterization of graph minors in terms...
A. Assem, H. Derets, C. Nehaniv· Electronic Proceedings in Th...· 0 citations
A finite simple graph $G$ is called a cograph if it does not contain the path on four vertices $P_4$ as an induced subgraph. It is classically known that the family of cographs are well-quasi-ordered by the induced subgraph relation \cite{D}. In preceding work of Knudsen and the third author \cite[Theorem 7.2]{KR}, it...
Adityo Mamun, Jonathan Nalikka, Eric Ramos· 0 citations
A graph is integral if the spectrum of its adjacency matrix consists entirely of integers. We prove that every simple graph having a pendant path with at least three edges has an eigenvalue in $(1,2\cos(\pi/9)]$ and one in $[-2\cos(\pi/9),-1)$, and hence is not integral. This settles a conjecture of Braga, Del-Vecchio...
R. O. Braga, Jean Carlo Moraes, Matheus C. Santos· 0 citations
We use cookies to run the site and, with your consent, for analytics and to show ads.
See our Cookie Policy.
