Abstract polytopes are a combinatorial generalization of convex and skeletal polytopes. Counting how many flag orbits a polytope has under its automorphism group is a way of measuring how symmetric ...it is. Polytopes with one flag orbit are called regular and are very well known. Polytopes with two flag orbits (called 2-orbit polytopes) are, however, way more elusive. There are 2n−1 possible classes of 2-orbit polytopes in rank (dimension) n, but for most of those classes, determining whether or not they are empty is still an open problem. In 2019, in their article An existence result on two-orbit maniplexes, Pellicer, Potočnik and Toledo constructed 2-orbit maniplexes (objects that generalize abstract polytopes and maps) in all these classes, but the question of whether or not they are also polytopes remained open. In this paper we use the results of a previous paper by the author and Hubard to show that some of these 2-orbit maniplexes are, in fact, polytopes. In particular we prove that there are 2-orbit polytopes in all the classes where exactly two kinds of reflections are forbidden. We use this to show that there are at least n2−n+1 classes of 2-orbit polytopes of rank n that are not empty. We also show that the maniplexes constructed with this method in the remaining classes satisfy all but (possibly) one of the properties necessary to be polytopes, therefore we get closer to proving that there are 2-orbit polytopes in all the classes.
We prove that the notion of a voltage graph lift comes from an adjunction between the category of voltage graphs and the category of group labeled graphs.
The theory of voltage graphs has become a standard tool in the study of graphs admitting a semiregular group of automorphisms. We introduce the notion of a cyclic generalised voltage graph to extend ...the scope of this theory to graphs admitting a cyclic group of automorphisms that may not be semiregular. We use this new tool to classify all cubic graphs admitting a cyclic group of automorphisms with at most three vertex-orbits and we characterise vertex-transitivity for each of these classes. In particular, we show that a cubic vertex-transitive graph admitting a cyclic group of automorphisms with at most three orbits on vertices either belongs to one of 5 infinite families or is isomorphic to the well-known Tutte–Coxeter graph.
A theory of orientation on gain graphs (voltage graphs) is developed to generalize the notion of orientation on graphs and signed graphs. Using this orientation scheme, the line graph of a gain graph ...is studied. For a particular family of gain graphs with complex units, matrix properties are established. As with graphs and signed graphs, there is a relationship between the incidence matrix of a complex unit gain graph and the adjacency matrix of the line graph.
Given a group Γ of order at most six, we characterize the graphs that have Γ-antivoltages and also determine the list of minor-minimal graphs that have no Γ-antivoltage. Our characterizations yield ...polynomial-time recognition algorithms for such graphs.
Hamiltonicity of graphs possessing symmetry has been a popular subject of research, with focus on vertex-transitive graphs, and in particular on Cayley graphs. In this paper, we consider the ...Hamiltonicity of another class of graphs with symmetry, namely covering graphs of trees. In particular, we study the problem for covering graphs of trees, where the tree is a voltage graph over a cyclic group. Batagelj and Pisanski were first to obtain such a result, in the special case when the voltage assignment is trivial; in that case, the covering graph is simply a Cartesian product of the tree and a cycle. We consider more complex voltage assignments, and extend the results of Batagelj and Pisanski in two different ways; in these cases the covering graphs cannot be expressed as products. We also provide a linear time algorithm to test whether a given assignment satisfies these conditions.
Let $\mathbb T$ be the multiplicative group of complex units, and let $\mathcal L (\Phi)$ denote a line graph of a $\mathbb{T}$-gain graph $\Phi$. Similarly to what happens in the context of signed ...graphs, the real number $\min Spec(A(\mathcal L (\Phi))$, that is, the smallest eigenvalue of the adjacency matrix of $\mathcal L(\Phi)$, is not less than $-2$. The structural conditions on $\Phi$ ensuring that $\min Spec(A(\mathcal L (\Phi))=-2$ are identified. When such conditions are fulfilled, bases of the $-2$-eigenspace are constructed with the aid of the star complement technique.
Let T 4 = { ± 1 , ± i } be the subgroup of fourth roots of unity inside T , the multiplicative group of complex units. For a T 4 -gain graph Φ = ( Γ , T 4 , φ ) , we introduce gain functions on its ...line graph L ( Γ ) and on its subdivision graph S ( Γ ) . The corresponding gain graphs L ( Φ ) and S ( Φ ) are defined up to switching equivalence and generalize the analogous constructions for signed graphs. We discuss some spectral properties of these graphs and in particular we establish the relationship between the Laplacian characteristic polynomial of a gain graph Φ , and the adjacency characteristic polynomials of L ( Φ ) and S ( Φ ) . A suitably defined incidence matrix for T 4 -gain graphs plays an important role in this context.