Search

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 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]

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]