Search

We introduce a new invariant of a cubic graph - its regular defect - which is defined as the smallest number of edges left uncovered by any collection of three perfect matchings that have no edge in common. This invariant is a modification of defect, an invariant introduced by Steffen (J. Graph Theory 78 (2015), 195--206), whose definition does not require the empty intersection condition. In this paper we discuss the relationship of this invariant to the well-known conjectures of Fulkerson (1971) and Fan and Raspaud (1994) and prove that defect and regular defect can be arbitrarily far apart.

A set of vertices of a graph $G$ is said to be decycling if its removal leaves an acyclic subgraph. The size of a smallest decycling set is the decycling number of $G$. Generally, at least $\lceil(n+2)/4\rceil$ vertices have to be removed in order to decycle a cubic graph on $n$ vertices. In 1979, Payan and Sakarovitch proved that the decycling number of a cyclically $4$-edge-connected cubic graph of order $n$ equals $\lceil (n+2)/4\rceil$. In addition, they characterised the structure of minimum decycling sets and their complements. If $n\equiv 2\pmod4$, then $G$ has a decycling set which is independent and its complement induces a tree. If $n\equiv 0\pmod4$, then one of two possibilities occurs: either $G$ has an independent decycling set whose complement induces a forest of two trees, or the decycling set is near-independent (which means that it induces a single edge) and its complement induces a tree. In this paper we strengthen the result of Payan and Sakarovitch by proving that the latter possibility (a near-independent set and a tree) can always be guaranteed. Moreover, we relax the assumption of cyclic $4$-edge-connectivity to a significantly weaker condition expressed through the canonical decomposition of 3-connected cubic graphs into cyclically $4$-edge-connected ones. Our methods substantially use a surprising and seemingly distant relationship between the decycling number and the maximum genus of a cubic graph., Comment: 41 pages, 8 figures

The colouring defect of a cubic graph is the smallest number of edges left uncovered by any set of three perfect matchings. While $3$-edge-colourable graphs have defect $0$, those that cannot be $3$-edge-coloured (that is, snarks) are known to have defect at least $3$. In this paper we focus on the structure and properties of snarks with defect $3$. For such snarks we develop a theory of reductions similar to standard reductions of short cycles and small cuts in general snarks. We prove that every snark with defect $3$ can be reduced to a snark with defect $3$ which is either nontrivial (cyclically $4$-edge-connected and of girth at least $5$) or to one that arises from a nontrivial snark of defect greater than $3$ by inflating a vertex lying on a suitable $5$-cycle to a triangle. The proofs rely on a detailed analysis of Fano flows associated with triples of perfect matchings leaving exactly three uncovered edges. In the final part of the paper we discuss application of our results to the conjectures of Berge and Fulkerson, which provide the main motivation for our research.

A long-standing conjecture of Berge suggests that every bridgeless cubic graph can be expressed as a union of at most five perfect matchings. This conjecture trivially holds for $3$-edge-colourable cubic graphs, but remains widely open for graphs that are not $3$-edge-colourable. The aim of this paper is to verify the validity of Berge's conjecture for cubic graphs that are in a certain sense close to $3$-edge-colourable graphs. We measure the closeness by looking at the colouring defect, which is defined as the minimum number of edges left uncovered by any collection of three perfect matchings. While $3$-edge-colourable graphs have defect $0$, every bridgeless cubic graph with no $3$-edge-colouring has defect at least $3$. In 2015, Steffen proved that the Berge conjecture holds for cyclically $4$-edge-connected cubic graphs with colouring defect $3$ or $4$. Our aim is to improve Steffen's result in two ways. First, we show that all bridgeless cubic graphs with defect $3$ satisfy Berge's conjecture irrespectively of their cyclic connectivity. Second, we prove that if the graph in question is cyclically $4$-edge-connected, then four perfect matchings suffice, unless the graph is the Petersen graph. The result is best possible as there exists an infinite family of cubic graphs with cyclic connectivity $3$ which have defect $3$ but cannot be covered with four perfect matchings.

In the present paper we investigate the faithfulness of certain linear representations of groups of automorphisms of a graph $X$ in the group of symmetries of the Jacobian of $X$. As a consequence we show that if a $3$-edge-connected graph $X$ admits a nonabelian semiregular group of automorphims, then the Jacobian of $X$ cannot be cyclic. In particular, Cayley graphs of degree at least three arising from nonabelian groups have non-cyclic Jacobians. While the size of the Jacobian of $X$ is well-understood - it is equal to the number of spanning trees of $X$ - the combinatorial interpretation of the rank of Jacobian of a graph is unknown. Our paper presents a contribution in this direction.

This paper focuses on the classification of classes of topological equivalence of finite group actions on Riemann surfaces. By the Riemann-Hurwitz bound, there are just finitely many groups that act conformally on a closed orientable surface $\mathcal{S}_g$ of genus $g\geq 2$. With each such action of a group $\mathrm{G}$ on $\mathcal{S}_g$ one can associate the fundamental group $\Gamma=\pi(\mathcal{O})$ of the quotient orbifold $\mathcal{O}=\mathcal{S}_g/\mathrm{G}$, isomorphic to a Fuchsian group determined completely by orbifold's signature. The Riemann existence theorem reduces the problem of the existence of an action of $\mathrm{G}$ on $\mathcal{S}_g$ to a purely group-theoretical problem of deciding whether there is an smooth epimorphism mapping the Fuchsian group $\Gamma$ onto the group $\mathrm{G}$. Using computer algebra systems such as \textsc{Magma} or GAP, together with the library of small groups, the generation of all finite group actions on a surface of fixed small genus $g\geq 2$ becomes almost a routine procedure. The difficult part is to determine the classes of these actions with respect to topological equivalence. To achieve this, one needs to investigate the action of the automorphism group of a Fuchsian group on the set of finite group actions on $\mathcal{S}_g$ with the corresponding signature. In this paper we derive several results on the topological equivalence of finite group actions on Riemann surfaces. As an application, we derive complete lists of finite group actions of genus $g\leq 9$ distinguished up to the topological equivalence. A summary of the actions can be found in Appendix, the reader interested in more details is referred to the web page [22]. It is expected that we will be able to extend the list to higher genera, refreshed partial results are available on the web page. The following text is an extended version of the paper [23].

The computational complexity of the graph isomorphism problem is considered to be a major open problem in theoretical computer science. It is known that testing isomorphism of chordal graphs is polynomial-time equivalent to the general graph isomorphism problem. Every chordal graph can be represented as the intersection graph of some subtrees of a representing tree, and the leafage of a chordal graph is defined to be the minimum number of leaves in a representing tree for it. We prove that chordal graph isomorphism is fixed parameter tractable with leafage as parameter. In the process we introduce the problem of isomorphism testing for higher-order hypergraphs and show that finding the automorphism group of order-$k$ hypergraphs with vertex color classes of size $b$ is fixed parameter tractable for any constant $k$ and $b$ as fixed parameter.

The colouring defect of a cubic graph, introduced by Steffen in 2015, is the minimum number of edges that are left uncovered by any set of three perfect matchings. Since a cubic graph has defect $0$ if and only if it is $3$-edge-colourable, this invariant can measure how much a cubic graph differs from a $3$-edge-colourable graph. Our aim is to examine the relationship of colouring defect to oddness, an extensively studied measure of uncolourability of cubic graphs, defined as the smallest number of odd circuits in a $2$-factor. We show that there exist cyclically $5$-edge-connected snarks (cubic graphs with no $3$-edge-colouring) of oddness $2$ and arbitrarily large colouring defect. This result is achieved by means of a construction of cyclically $5$-edge-connected snarks with oddness $2$ and arbitrarily large girth. The fact that our graphs are cyclically $5$-edge-connected significantly strengthens a similar result of Jin and Steffen (2017), which only guarantees graphs with cyclic connectivity at most $3$. At the same time, our result improves Kochol's original construction of snarks with large girth (1996) in that it provides infinitely many nontrivial snarks of any prescribed girth $g\ge 5$, not just girth at least~$g$.

We investigate a representation of the automorphism group of a connected graph $X$ in the group of unimodular matrices $U_\beta$ of dimension $\beta$, where $\beta$ is the Betti number of graph $X$. We classify the graphs for which the automorphism group does not embed into $U_\beta$. It follows that if $X$ has no pendant vertices and $X$ is not a simple cycle, then the representation is faithful and $\mathrm{Aut}\,X$ acts faithfully on $H_1(X,\mathbb{Z})$. The latter statement can be viewed as a discrete analogue of a classical Hurwitz's theorem on Riemann surfaces of genera greater than one., Comment: Submitted to Discrete Mathematics

By a map we mean a $2$-cell decomposition of a closed compact surface, i.e., an embedding of a graph such that every face is homeomorphic to an open disc. Automorphism of a map can be thought of as a permutation of the vertices which preserves the vertex-edge-face incidences in the embedding. When the underlying surface is orientable, every automorphism of a map determines an angle-preserving homeomorphism of the surface. While it is conjectured that there is no "truly subquadratic" algorithm for testing map isomorphism for unconstrained genus, we present a linear-time algorithm for computing the generators of the automorphism group of a map, parametrized by the genus of the underlying surface. The algorithm applies a sequence of local reductions and produces a uniform map, while preserving the automorphism group. The automorphism group of the original map can be reconstructed from the automorphism group of the uniform map in linear time. We also extend the algorithm to non-orientable surfaces by making use of the antipodal double-cover., Comment: Added funding information

A graph is said to be distance-hereditary if the distance function in every connected induced subgraph is the same as in the graph itself. We prove that the ordinary Weisfeiler-Leman algorithm correctly tests the isomorphism of any two graphs if one of them is distance-hereditary; more precisely, the Weisfeiler-Leman dimension of the class of finite distance-hereditary graphs is equal to $2$. The previously best known upper bound for the dimension was $7$.

A graph is said to be circular-arc if the vertices can be associated with arcs of a circle so that two vertices are adjacent if and only if the corresponding arcs overlap. It is proved that the isomorphism of circular-arc graphs can be tested by the Weisfeiler-Leman algorithm after individualization of two vertices., Comment: Dear reader, recently we have found a problem in the proof of the main theorem. It seems that we will be able to fill in the gap in the arguments, and we are doing our best to do this as soon as possible. We appologize for publishing an unfinished work. The authors

A dessin is a 2-cell embedding of a connected $2$-coloured bipartite graph into an orientable closed surface. A dessin is regular if its group of orientation- and colour-preserving automorphisms acts regularly on the edges. In this paper we study regular dessins whose underlying graph is a complete bipartite graph $K_{m,n}$, called $(m,n)$-complete regular dessins. The purpose is to establish a rather surprising correspondence between $(m,n)$-complete regular dessins and pairs of skew-morphisms of cyclic groups. A skew-morphism of a finite group $A$ is a bijection $\varphi\colon A\to A$ that satisfies the identity $\varphi(xy)=\varphi(x)\varphi^{\pi(x)}(y)$ for some function $\pi\colon A\to\mathbb{Z}$ and fixes the neutral element of~$A$. We show that every $(m,n)$-complete regular dessin $\mathcal{D}$ determines a pair of reciprocal skew-morphisms of the cyclic groups $\mathbb{Z}_n$ and $\mathbb{Z}_m$. Conversely, $\mathcal{D}$ can be reconstructed from such a reciprocal pair. As a consequence, we prove that complete regular dessins, exact bicyclic groups with a distinguished pair of generators, and pairs of reciprocal skew-morphisms of cyclic groups are all in one-to-one correspondence. Finally, we apply the main result to determining all pairs of integers $m$ and $n$ for which there exists, up to interchange of colours, exactly one $(m,n)$-complete regular dessin. We show that the latter occurs precisely when every group expressible as a product of cyclic groups of order $m$ and $n$ is abelian, which eventually comes down to the condition $\gcd(m,\phi(n))=\gcd(\phi(m),n)=1$, where $\phi$ is Euler's totient function., Comment: 19papges

It is well known that the automorphism group of a regular dessin is a two-generator finite group, and the isomorphism classes of regular dessins with automorphism groups isomorphic to a given finite group $G$ are in one-to-one correspondence with the orbits of the action of $\Aut(G)$ on the ordered generating pairs of $G$. If there is only one orbit, then up to isomorphism the regular dessin is uniquely determined by the group $G$ and it is called uniquely regular. In the paper we investigate the classification of uniquely regular dessins with a nilpotent automorphism group. The problem is reduced to the classification of finite maximally automorphic $p$-groups $G$, i.e., the order of the automorphism group of $G$ attains Hall's upper bound. Maximally automorphic $p$-groups of nilpotency class three are classified., Comment: 18papges

A dessin is an embedding of connected bipartite graph into an oriented closed surface. A dessin is regular if its group of colour- and orientation-preserving automorphisms acts transitively on the edges. In the present paper regular dessins with a nilpotent automorphism group are investigated, and attention are paid on those with the highest level of external symmetry. Depending on the algebraic theory of dessins and using group-theoretical methods, we present a classification of nilpotent groups of class two which underly a unique regular dessin., Comment: 14papges

A dessin is a $2$-cell embedding of a connected $2$-coloured bipartite graph into an orientable closed surface. A dessin is regular if its group of colour- and orientation-preserving automorphisms acts regularly on the edges. In this paper we employ group-theoretic method to determine and enumerate the isomorphism classes of regular dessins with the complete bipartite underlying graphs of odd prime power order., Comment: 17papges

We construct a polynomial-time algorithm that given a graph $X$ with $4p$ vertices ($p$ is prime), finds (if any) a Cayley representation of $X$ over the group $C_2\times C_2\times C_p$. This result, together with the known similar result for circulant graphs, shows that recognising and testing isomorphism of Cayley graphs over an abelian group of order $4p$ can be done in polynomial time., Comment: 22 pages

A graph $G$ covers a graph $H$ if there exists a locally bijective homomorphism from $G$ to $H$. We deal with regular covers where this homomorphism is prescribed by the action of a semiregular subgroup of $\textrm{Aut}(G)$. We study computational aspects of regular covers that have not been addressed before. The decision problem RegularCover asks for given graphs $G$ and $H$ whether $G$ regularly covers $H$. When $|H|=1$, this problem becomes Cayley graph recognition for which the complexity is still unresolved. Another special case arises for $|G| = |H|$ when it becomes the graph isomorphism problem. Our main result is an involved FPT algorithm solving RegularCover for planar inputs $G$ in time $O^*(2^{e(H)/2})$ where $e(H)$ denotes the number of edges of $H$. The algorithm is based on dynamic programming and employs theoretical results proved in a related structural paper. Further, when $G$ is 3-connected, $H$ is 2-connected or the ratio $|G|/|H|$ is an odd integer, we can solve the problem RegularCover in polynomial time. In comparison, B\'ilka et al. (2011) proved that testing general graph covers is NP-complete for planar inputs $G$ when $H$ is a small fixed graph such as $K_4$ or $K_5$., Comment: The journal version of the second part of arXiv:1402.3774. arXiv admin note: substantial text overlap with arXiv:1402.3774

Let $G$ be a finite group having a factorisation $G=AB$ into subgroups $A$ and $B$ with $B$ cyclic and $A\cap B=1,$ and let $b$ be a generator of $B$. The associated skew-morphism is the bijective mapping $f:A \to A$ well defined by the equality $baB=f(a)B$ where $a\in A$. In this paper, we shall classify all skew-morphisms of cyclic $p$-groups where $p$ is an odd prime.

A dessin is a 2-cell embedding of a connected bipartite graph into an orientable closed surface. An automorphism of a dessin is a permutation of the edges of the underlying graph which preserves the colouring of the vertices and extends to an orientation-preserving self-homeomorphism of the supporting surface. A dessin is regular if its automorphism group is transitive on the edges, and a regular dessin is totally symmetric if it is invariant under all dessin operations. Thus totally symmetric dessins possesses the highest level of external symmetry. In this paper we present a classification of totally symmetric dessins with a nilpotent automorphism group of class three, Comment: 21papges

A map is a 2-cell decomposition of an orientable closed surface. A dessin is a bipartite map with a fixed colouring of vertices. A dessin is regular if its group of colour- and orientation-preserving automorphisms acts transitively on the edges, and a regular dessin is symmetric if it admits an additional external symmetry transposing the vertex colours. Regular dessins with nilpotent automorphism groups are investigated. We show that each such dessin is a parallel product of regular dessins whose automorphism groups are the Sylow subgroups. Regular and symmetric dessins with abelian automorphism groups are classified and enumerated., Comment: 27pages

We investigate automorphism groups of planar graphs. The main result is a complete recursive description of all abstract groups that can be realized as automorphism groups of planar graphs. The characterization is formulated in terms of inhomogeneous wreath products. In the proof, we combine techniques from combinatorics, group theory, and geometry. This significantly improves the Babai's description (1975)., Comment: Some citations were added

A graph $G$ covers a graph $H$ if there exists a locally bijective homomorphism from $G$ to $H$. We deal with regular coverings in which this homomorphism is prescribed by an action of a semiregular subgroup $\Gamma$ of $\textrm{Aut}(G)$; so $H \cong G / \Gamma$. In this paper, we study the behaviour of regular graph covering with respect to 1-cuts and 2-cuts in $G$. We describe reductions which produce a series of graphs $G = G_0,\dots,G_r$ such that $G_{i+1}$ is created from $G_i$ by replacing certain inclusion minimal subgraphs with colored edges. The process ends with a primitive graph $G_r$ which is either 3-connected, or a cycle, or $K_2$. This reduction can be viewed as a non-trivial modification of reductions of Mac Lane (1937), Trachtenbrot (1958), Tutte (1966), Hopcroft and Tarjan (1973), Cuningham and Edmonds (1980), Walsh (1982), and others. A novel feature of our approach is that in each step all essential information about symmetries of $G$ are preserved. A regular covering projection $G_0\to H_0$ induces regular covering projections $G_i \to H_i$ where $H_i$ is the $i$-th quotient reduction of $H_0$. This property allows to construct all possible quotients $H_0$ of $G_0$ from the possible quotients $H_r$ of $G_r$. By applying this method to planar graphs, we give a proof of Negami's Theorem (1988). Our structural results are also used in subsequent papers for regular covering testing when $G$ is a planar graph and for an inductive characterization of the automorphism groups of planar graphs (see Babai (1973) as well)., Comment: The journal version of the first part of arXiv:1402.3774

A graph $G$ covers a graph $H$ if there exists a locally bijective homomorphism from $G$ to $H$. We deal with regular covers in which this locally bijective homomorphism is prescribed by an action of a subgroup of ${\rm Aut}(G)$. Regular covers have many applications in constructions and studies of big objects all over mathematics and computer science. We study computational aspects of regular covers that have not been addressed before. The decision problem RegularCover asks for two given graphs $G$ and $H$ whether $G$ regularly covers $H$. When $|H|=1$, this problem becomes Cayley graph recognition for which the complexity is still unresolved. Another special case arises for $|G| = |H|$ when it becomes the graph isomorphism problem. Therefore, we restrict ourselves to graph classes with polynomially solvable graph isomorphism. Inspired by Negami, we apply the structural results used by Babai in the 1970's to study automorphism groups of graphs. Our main result is the following FPT meta-algorithm: Let $\cal C$ be a class of graphs such that the structure of automorphism groups of 3-connected graphs in $\cal C$ is simple. Then we can solve RegularCover for $\cal C$-inputs $G$ in time $O^*(2^{e(H)/2})$ where $e(H)$ denotes the number of the edges of $H$. As one example of $\cal C$, this meta-algorithm applies to planar graphs. In comparison, testing general graph covers is known to be NP-complete for planar inputs $G$ even for small fixed graphs $H$ such as $K_4$ or $K_5$. Most of our results also apply to general graphs, in particular the complete structural understanding of regular covers for 2-cuts., Comment: The conference version accepted to ICALP 2014

We classify those 2-groups G which factorise as a product of two disjoint cyclic subgroups A and B, transposed by an automorphism of order 2. The case where G is metacyclic having been dealt with elsewhere, we show that for each e>2 there are exactly three such non-metacyclic groups G with $|A|=|B|=2^e$, and for e=2 there is one. These groups appear in a classification by Berkovich and Janko of 2-groups with one non-metacyclic maximal subgroup; we enumerate these groups, give simpler presentations for them, and determine their automorphism groups., Comment: 20 pages

Although the phenomenon of chirality appears in many investigations of maps and hypermaps no detailed study of chirality seems to have been carried out. Chirality of maps and hypermaps is not merely a binary invariant but can be quantified by two new invariants -- the chirality group and the chirality index, the latter being the size of the chirality group. A detailed investigation of the chirality groups of maps and hypermaps will be the main objective of this paper. The most extreme type of chirality arises when the chirality group coincides with the monodromy group. Such hypermaps are called totally chiral. Examples of them are constructed by considering appropriate ``asymmetric'' pairs of generators for some non-abelian simple groups. We also show that every finite abelian group is the chirality group of some hypermap, whereas many non-abelian groups, including symmetric and dihedral groups, cannot arise as chirality groups., Comment: 23 pages, 0 figures

As previously known, all 3-manifolds of genus two can be represented by edge-coloured graphs uniquely defined by 6-tuples of integers satisfying simple conditions. The present paper describes an ``elementary transformation'' on these 6-tuples which changes the associated graph but does not change the represented manifold. This operation is a useful tool in the classification problem for 3-manifolds of genus two; in fact, it allows to define an equivalence relation on ``admissible'' 6-tuples so that equivalent 6-tuples represent the same manifold. Different equivalence classes can represent the same manifold; however, equivalence classes ``almost always'' contain infinitely many 6-tuples. Finally, minimal representatives of the equivalence classes are described., Comment: 27 pages, 10 figures, to appear on Journal of Combinatorial Theory Series B