Search

Let s be a positive integer. A graph is s-transitive if its automorphism group is transitive on s-arcs but not on (s + 1)-arcs. In this paper, we study all tetravalent s-transitive graphs of order 6p2. [ABSTRACT FROM AUTHOR]

A graphoid is a mixed multigraph with multiple directed and/or undirected edges, loops, and semiedges. A covering projection of graphoids is an onto mapping between two graphoids such that at each vertex, the mapping restricts to a local bijection on incoming edges and outgoing edges. Naturally, as it appears, this definition displays unusual behaviour since the projection of the corresponding underlying graphs is not necessarily a graph covering. Yet, it is still possible to grasp such coverings algebraically in terms of the action of the fundamental monoid and combinatorially in terms of voltage assignments on arcs. In the present paper, the existence theorem is formulated and proved in terms of the action of the fundamental monoid. A more conventional formulation in terms of the weak fundamental group is possible because the action of the fundamental monoid is permutational. The standard formulation in terms of the fundamental group holds for a restricted class of coverings, called homogeneous. Further, the existence of the universal covering and the problems related to decomposing regular coverings via regular coverings are studied in detail. It is shown that with mild adjustments in the formulation, all the analogous theorems that hold in the context of graphs are still valid in this wider setting. [ABSTRACT FROM AUTHOR]

A graphoid is a mixed multigraph with multiple directed and/or undirected edges, loops, and semiedges. A covering projection of graphoids is an onto mapping between two graphoids such that at each vertex, the mapping restricts to a local bijection on incoming edges and outgoing edges. Naturally, as it appears, this definition displays unusual behaviour since the projection of the corresponding underlying graphs is not necessarily a graph covering. Yet, it is still possible to grasp such coverings algebraically in terms of the action of the fundamental monoid and combinatorially in terms of voltage assignments on arcs. In the present paper, the existence theorem is formulated and proved in terms of the action of the fundamental monoid. A more conventional formulation in terms of the weak fundamental group is possible because the action of the fundamental monoid is permutational. The standard formulation in terms of the fundamental group holds for a restricted class of coverings, called homogeneous. Further, the existence of the universal covering and the problems related to decomposing regular coverings via regular coverings are studied in detail. It is shown that with mild adjustments in the formulation, all the analogous theorems that hold in the context of graphs are still valid in this wider setting.

A proper edge coloring of a graph is strong if it creates no bichromatic path of length three. It is well known that for a strong edge coloring of a k $k$‐regular graph at least 2k−1 $2k-1$ colors are needed. We show that a k $k$‐regular graph admits a strong edge coloring with 2k−1 $2k-1$ colors if and only if it covers the Kneser graph K(2k−1,k−1) $K(2k-1,k-1)$. In particular, a cubic graph is strongly 5‐edge‐colorable whenever it covers the Petersen graph. One of the implications of this result is that a conjecture about strong edge colorings of subcubic graphs proposed by Faudree et al. is false. [ABSTRACT FROM AUTHOR]

We study a natural generalization of inverse systems of finite regular covering spaces. A limit of such a system is a fibration whose fibres are profinite topological groups. However, as shown in Conner et al. (Topol Appl 239:234–243, 2018), there are many fibrations whose fibres are profinite groups, which are far from being inverse limits of coverings. We characterize profinite fibrations among a large class of fibrations and relate the profinite topology on the fundamental group of the base with the action of the fundamental group on the fibre, and develop a version of the Borel construction for fibrations whose fibres are profinite groups. [ABSTRACT FROM AUTHOR]

Let p: X → X be a regular covering projection of connected graphs, where CTp denotes the group of covering transformations. Suppose that a group G ≤ Aut X lifts along p to a group G ≤ Aut X. The corresponding short exact sequence id → CTp → G → G → id is split sectional over a G-invariant subset of vertices Ω ⊆ V (X) if there exists a sectional complement, that is, a complement G to CTp with a G-invariant section Ω ⊂ V (X) over Ω. Such lifts do not split just abstractly but also permutationally in the sense that they enable a nice combinatorial description. Sectional complements are characterized from several viewpoints. The connection between the number of sectional complements and invariant sections on one side, and the structure of the split extension itself on the other, is analyzed. In the case when CTp is abelian and the covering projection is given implicitly in terms of a voltage assignment on the base graph X, an efficient algorithm for testing whether G has a sectional complement is presented. Efficiency resides on avoiding explicit reconstruction of the covering graph and the lifted group. The method extends to the case when CTp is solvable. [ABSTRACT FROM AUTHOR]

A covering projection from a graph G onto a graph H is a mapping of the vertices of G onto the vertices of H such that, for every vertex v of G , the neighborhood of v is mapped bijectively onto the neighborhood of its image. Moreover, if G and H are multigraphs, then this local bijection has to preserve multiplicities of the neighbors as well. The notion of covering projection stems from topology, but has found applications in areas such as the theory of local computation and construction of highly symmetric graphs. It provides a restrictive variant of the constraint satisfaction problem with additional symmetry constraints on the behavior of the homomorphisms of the structures involved. We investigate the computational complexity of the problem of deciding the existence of a covering projection from an input graph G to a fixed target graph H . Among other partial results this problem has been shown NP-hard for simple regular graphs H of valency greater than 2, and a full characterization of computational complexity has been shown for target multigraphs with 2 vertices. We extend the previously known results to the ternary case, i.e., we give a full characterization of the computational complexity in the case of multigraphs with 3 vertices. We show that even in this case a P/NP-completeness dichotomy holds. [ABSTRACT FROM AUTHOR]

Given a connected graph X and a group G of its automorphisms we first introduce an approach for constructing all pairwise nonequivalent connected solvable regular coverings ℘ : X ˜ → X (that is, with a solvable group of covering transformations CT ( ℘ ) ) along which G lifts, up to a prescribed order n of X ˜ . Next, given a connected solvable regular covering ℘ : X ˜ → X by means of voltages and a group G ≤ Aut ( X ) that lifts along ℘, we consider algorithms for testing whether the lifted group G ˜ is a split extension of CT ( ℘ ) . In computational group theory, methods for testing whether a given extension of permutation groups splits are known. However, in order to apply the existing algorithms, X ˜ together with CT ( ℘ ) and G ˜ need to be constructed in the first place, which is far from optimal. Recently, an algorithm avoiding such explicit constructions has been proposed by Malnič and Požar (submitted for publication) . We here provide additional details about this algorithm and investigate its performance compared to the one using explicit constructions. To this end, a concrete dataset of solvable regular covers of graphs has been generated by the algorithm mentioned in the first paragraph. [ABSTRACT FROM AUTHOR]

We study the behaviour of fibre maps under exponentiation, i.e. given a fibration p : E → B we ask for which spaces X is the induced map between mapping spaces p ⁎ : E X → B X also a fibration. If X is a locally compact space, the positive answer follows easily by the exponential law so in this paper we consider more general spaces and show that the preservation of fibrations is related to the local homotopy properties of the space X . For example, if p is a Dold fibration and X admits a deformation retraction on a compactly generated space, then the induced map p ⁎ is also a Dold fibration. Similar results hold for Hurewicz fibrations with unique path-lifting and for covering spaces, and can be furthermore extended to spaces that admit some numerable cover, whose elements preserve fibration property. [ABSTRACT FROM AUTHOR]

A function f : V → {−1, 1} is a signed dominating function (SDF) of a directed graph D ([4]) if for every vertex v ∈ V, f(N−[v]) = ... f(u) ≥ 1. In this paper, we introduce the concept of signed efficient dominating function (SEDF) for directed graphs. A SDF of a directed graph D is said to be SEDF if for every vertex v ∈ V, f(N−[v]) = 1 when |N−[v]| is odd and f(N−[v]) = 2 when |N−[v]| is even. We study the signed domatic number dS(D) of directed graphs. Actually, we give a lower bound for signed domination number γs(G) and an upper bound for dS(G). Also we characterize some classes of directed circulant graphs for which dS(D) = δ−(D) + 1. Further, we find a necessary and sufficient condition for the existence of SEDF in circulant graphs in terms of covering projection. [ABSTRACT FROM AUTHOR]

Abstract: Efficient open dominating sets in bipartite Cayley graphs are characterized in terms of covering projections. Necessary and sufficient conditions for the existence of efficient open dominating sets in certain circulant Harary graphs are given. Chains of efficient dominating sets, and of efficient open dominating sets, in families of circulant graphs are described as an application. [Copyright &y& Elsevier]

Abstract: In this paper we deal with upper bounds on the -number of graphs of the form , where is one of the standard graph products—the direct, Cartesian, strong, and the lexicographic product. -labelling of products of graphs has been investigated by a number of authors, especially in connection with the well-known conjecture , where is the maximum degree of a graph . Up to some degenerate cases, this conjecture was verified for the Cartesian and the lexicographic product by Shao and Yeh (2005) , and for the direct and the strong product by Klavžar and Špacapan (2006)  and by Shao et al. (2008) . If one of the factors of the Cartesian or the direct product has maximum degree one, only higher upper bounds than the one following from the conjecture are currently known. We derive alternative upper bounds on the -number of graphs for the standard products mentioned above, with the role of the maximum degree taken over by the -number of the graph . Methods include lifts along graph covering projections and labellings of -sums constructed by Georges and Mauro (2002) . In most cases, our upper bounds are tighter than those currently known. [Copyright &y& Elsevier]

Abstract: Let be a regular covering projection of connected graphs with the group of covering transformations isomorphic to N. If N is an elementary abelian p-group, then the projection is called p-elementary abelian. The projection is vertex-transitive (edge-transitive) if some vertex-transitive (edge-transitive) subgroup of Aut lifts along , and semisymmetric if it is edge- but not vertex-transitive. The projection is minimal semisymmetric if cannot be written as a composition of two (nontrivial) regular covering projections, where is semisymmetric. Finding elementary abelian covering projections can be grasped combinatorially via a linear representation of automorphisms acting on the first homology group of the graph. The method essentially reduces to finding invariant subspaces of matrix groups over prime fields (see [A. Malnič, D. Marušič, P. Potočnik, Elementary abelian covers of graphs, J. Algebraic Combin. 20 (2004) 71–97]). In this paper, all pairwise nonisomorphic minimal semisymmetric elementary abelian regular covering projections of the Möbius–Kantor graph, the Generalized Petersen graph , are constructed. No such covers exist for . Otherwise, the number of such covering projections is equal to and in cases and , respectively, and to and in cases and , respectively. For each such covering projection the voltage rules generating the corresponding covers are displayed explicitly. [Copyright &y& Elsevier]