Ultragraphs and shift spaces over infinite alphabets

In this paper we further develop the theory of one-sided shift spaces over infinite alphabets, characterizing one-step shifts as edge shifts of ultragraphs and partially answering a conjecture regarding shifts of finite type (we show that there exist shifts of finite type that are not conjugate, via a conjugacy that is eventually finite periodic, to an edge shift of a graph). We also show that there exist edge shifts of ultragraphs that are shifts of finite type, but are not conjugate to a full shift, a result that is not true for edge shifts of graphs. One of the key results needed in the proofs of our conclusions is the realization of a class of ultragraph C*-algebras as partial crossed products, a result of interest on its own.     

Conjugacy separability of 1-acylindrical graphs of free groups

We use the theory of group actions on profinite trees to prove that the fundamental group of a finite, 1-acylindrical graph of free groups with finitely generated edge groups is conjugacy separable. This has several applications: we prove that positive, C′(1/6) one-relator groups are conjugacy separable; we provide a conjugacy separable version of the Rips construction; we use this latter to provide an example of two finitely presented, residually finite groups that have isomorphic profinite completions, such that one is conjugacy separable and the other does not even have solvable conjugacy problem.     

On a graph associated to invariant conjugacy classes of finite groups

LetA andG be finite groups of coprime orders such thatA acts by automorphisms onG. We define theA-invariant conjugacy class graph ofG to be the graph having as vertices the noncentralA-invariant conjugacy classes ofG, and two vertices are connected by an edge if their cardinalities are not coprime. We prove that when the graph is disconnected thenG is solvable.     

On a graph related to permutability in finite groups

For a finite group G we define the graph Γ(G) to be the graph whose vertices are the conjugacy classes of cyclic subgroups of G and two conjugacy classes ${\mathcal {A}, \mathcal {B}}For a finite group G we define the graph Γ(G) to be the graph whose vertices are the conjugacy classes of cyclic subgroups of G and two conjugacy classes A, B{\mathcal {A}, \mathcal {B}} are joined by an edge if for some A ? A, B ? B A{A \in \mathcal {A},\, B \in \mathcal {B}\, A} and B permute. We characterise those groups G for which Γ(G) is complete.     

Subgraph distances in graphs defined by edge transfers

For two edge-induced subgraphs F and H of the same size in a graph G, the subgraph H can be obtained from F by an edge jump if there exist four distinct vertices u, v, w, and x in G such that uv ε E(F), wx ε E(G) - E(F), and H = F - uv + wx. The subgraph F is j-transformed into H if H can be obtained from F by a sequence of edge jumps. Necessary and sufficient conditions are presented for a graph G to have the property that every edge-induced subgraph of a fixed size in G can be j-transformed into every other edge-induced subgraph of that size. The minimum number of edge jumps required to transform one subgraph into another is called the jump distance. This distance is a metric and can be modeled by a graph. The jump graph J(G) of a graph G is defined as that graph whose vertices are the edges of G and where two vertices of J(G) are adjacent if and only if the corresponding edges of G are independent. For a given graph G, we consider the sequence {{J^k(G)}} of iterated jump graphs and classify each graph as having a convergent, divergent, or terminating sequence.     

Bidegreed graphs are edge reconstructible

An edge-deleted subgraph of a graph G is a subgraph obtained from G by the deletion of an edge. The Edge Reconstruction Conjecture asserts that every simple finite graph with four or more edges is determined uniquely, up to isomorphism, by its collection of edge-deleted subgraphs. A class of graphs is said to be edge reconstructible if there is no graph in the class with four or more edges that is not edge reconstructible. This paper proves that bidegreed graphs (graphs whose vertices all have one of two possible degrees) are edge reconstructible. The results are then generalized to show that all graphs that do not have three consecutive integers in their degree sequence are also edge reconstructible.     

The canonical-boundary representation for automorphism groups of locally compact countable state Markov shifts

We introduce the canonical-boundary representation and study its range. This conjugacy invariant homomorphism captures information about the symmetry of the Markov shift near its (canonical) boundary and exhibits which actions on the boundary can be realized by automorphisms. The path-structure at infinity — a relation on the set of orbits of the canonical boundary — is a new conjugacy invariant, which is stronger than the canonical boundary and the periodic data at infinity. Moreover we determine its influence on the range of the canonical-boundary representation and the extendability of automorphisms from subsystems (ascending sequences of shifts os finite type (SFTs) and infinite subsets of periodic points) to the entire Markov shift.     

Shift Automorphisms of the Hyperfinite Factor

For a large class of shift transformations of a LEBESGUE measure space (they have to fulfil some mixing condition) we construct automorphisms of the hyperfinite factor of type II₁. The CONNES -STØRMER entropy of the resulting automorphisms equals the measure theoretic entropy of the corresponding shift transformations. Two such automorphisms are conjugate if the conjugacy between the original measure space shifts can be given by a code with finite expected code length.     

A Structure Theorem for Strong Immersions

A graph H is strongly immersed in G if H is obtained from G by a sequence of vertex splittings (i.e., lifting some pairs of incident edges and removing the vertex) and edge removals. Equivalently, vertices of H are mapped to distinct vertices of G (branch vertices) and edges of H are mapped to pairwise edge‐disjoint paths in G, each of them joining the branch vertices corresponding to the ends of the edge and not containing any other branch vertices. We describe the structure of graphs avoiding a fixed graph as a strong immersion. The theorem roughly states that a graph which excludes a fixed graph as a strong immersion has a tree‐like decomposition into pieces glued together on small edge cuts such that each piece of the decomposition has a path‐like linear decomposition isolating the high degree vertices.     

Edge Partition of Graphs Embeddable in the Projective Plane and the Klein Bottle

In a previous paper by the author joint with Baogang XU published in Discrete Math in 2018, we show that every non-planar toroidal graph can be edge partitioned into a planar graph and an outerplanar graph. This edge partition then implies some results in thickness and outerthickness of toroidal graphs. In particular, if each planar graph has outerthickness at most $2$ (conjectured by Chartrand, Geller and Hedetniemi in 1971 and the confirmation of the conjecture was announced by Gon\c{c}alves in 2005), then the outerthickness of toroidal graphs is at most 3 which is the best possible due to $K_7$. In this paper we continue to study the edge partition for projective planar graphs and Klein bottle embeddable graphs. We show that (1) every non-planar but projective planar graph can be edge partitioned into a planar graph and a union of caterpillar trees; and (2) every non-planar Klein bottle embeddable graph can be edge partitioned into a planar graph and a subgraph of two vertex amalgamation of a caterpillar tree with a cycle with pendant edges. As consequences, the thinkness of projective planar graphs and Klein bottle embeddabe graphs are at most $2$, which are the best possible, and the outerthickness of these graphs are at most $3$.     

Matroidal families of finite connected nonhomeomorphic graphs exist

A matroidal family is a nonempty set ? of connected finite graphs such that for every arbitrary finite graph G the edge sets of the subgraphs of G which are isomorphic to an element of ? form a matroid on the edge set of G. In the present paper the question whether there are any matroidal families besides the four previously described by Simões-Pereira is answered affirmatively. It is shown that for every natural number n ? 2 there is a matroidal family that contains the complete graph with n vertices. For n = 4 this settles Simões-Pereira's conjecture that there is a matroidal family containing all wheels.     

Rectangular and visibility representations of infinite planar graphs

We provide a new method for extending results on finite planar graphs to the infinite case. Thus a result of Ungar on finite graphs has the following extension: Every infinite, planar, cubic, cyclically 4‐edge‐connected graph has a representation in the plane such that every edge is a horizontal or vertical straight line segment, and such that no two edges cross. A result of Tamassia and Tollis extends as follows: Every countably infinite planar graph is a subgraph of a visibility graph. Furthermore, every locally finite, 2‐connected, planar graph is a visibility graph. © 2006 Wiley Periodicals, Inc. J Graph Theory 52: 257–265, 2006     

Characterization of reducible hexagons and fast decomposition of elementary benzenoid graphs

A benzenoid graph is a finite connected plane graph with no cut vertices in which every interior region is bounded by a regular hexagon of a side length one. A benzenoid graph G is elementary if every edge belongs to a 1-factor of G. A hexagon h of an elementary benzenoid graph is reducible, if the removal of boundary edges and vertices of h results in an elementary benzenoid graph. We characterize the reducible hexagons of an elementary benzenoid graph. The characterization is the basis for an algorithm which finds the sequence of reducible hexagons that decompose a graph of this class in O(n²) time. Moreover, we present an algorithm which decomposes an elementary benzenoid graph with at most one pericondensed component in linear time.     

Uniform cyclic edge connectivity in cubic graphs

A cubic graph which is cyclicallyk-edge connected and has the further property that every edge belongs to some cyclick-edge cut is called uniformly cyclicallyk-edge connected(U(k)). We classify theU(5) graphs and show that all cyclically 5-edge connected cubic graphs can be generated from a small finite set ofU(5) graphs by a sequence of defined operations.MATHDAHCOTAGE.AC.NZ     

On the Diameter of a p-Regular Conjugacy Class Graph of Finite Groups II

Abstract

Let Gbe a finite p-solvable group. Let us consider the graph Γ* _p (G) whose vertices are the primes which occur as the divisors of the conjugacy classes of p-regular elements of G and two primes are joined by an edge if there exists such a class whose size is divisible by both primes. Suppose that Γ _p *(G) is a connected graph, then we prove that the diameter of this graph is at most 3 and this is the best bound.     

The Divisibility Graph of finite groups of Lie type

The Divisibility Graph of a finite group G has vertex set the set of conjugacy class sizes of non-central elements in G and two vertices are connected by an edge if one divides the other. We determine the connected components of the Divisibility Graph of the finite groups of Lie type in odd characteristic.     

Decomposing Graphs into Long Paths

It is known that the edge set of a 2-edge-connected 3-regular graph can be decomposed into paths of length 3. W. Li asked whether the edge set of every 2-edge-connected graph can be decomposed into paths of length at least 3. The graphs C ₃, C ₄, C ₅, and K ₄−e have no such decompositions. We construct an infinite sequence {F _i } _i=0 ^∞ of nondecomposable graphs. On the other hand, we prove that every other 2-edge-connected graph has a desired decomposition. This revised version was published online in June 2006 with corrections to the Cover Date.