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
2
k
−
1 $2k-1$ colors ...are needed. We show that a
k $k$‐regular graph admits a strong edge coloring with
2
k
−
1 $2k-1$ colors if and only if it covers the Kneser graph
K
(
2
k
−
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.
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.
Geometry of compact lifting spaces Conner, Gregory R.; Herfort, Wolfgang; Pavešić, Petar
Monatshefte für Mathematik,
11/2020, Volume:
193, Issue:
3
Journal Article
Peer reviewed
Open access
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.
Let p\colon \tilde {X} \to X be a regular covering projection of connected graphs, where \hbox {{\rm CT}}_{\wp } denotes the group of covering transformations. Suppose that a group G \leq {\rm Aut} ...\,X lifts along \wp to a group \tilde {G} \leq {\rm Aut} \,\tilde {X}. The corresponding short exact sequence {\rm id} \to \hbox {{\rm CT}}_{\wp } \to \tilde {G} \to G \to \rm {id} is split sectional over a G-invariant subset of vertices \Omega \subseteq V(X) if there exists a sectional complement , that is, a complement \overline {G} to \hbox {{\rm CT}}_{\wp } with a \overline {G}-invariant section \overline {\Omega } \subset V(\tilde {X}) over \Omega . 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 \hbox {{\rm CT}}_{\wp } 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 \tilde {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 \hbox {{\rm CT}}_{\wp } is solvable.
Let U be a finitely presented group with a normal subgroup F, and let H be a finite group. We present an effective method for constructing all U-stable epimorphisms from F onto H; that is, ...epimorphisms whose kernels are normal in U. Our strategy is an adaptation of the algorithm for determining all epimorphisms from a finitely presented group onto a finite group. As an application, we construct all admissible regular graph covering projections with a given deck transformation group.
Given a path-connected space X and H≤π1(X,x0), there is essentially only one construction of a map pH:(X˜H,x˜0)→(X,x0) with connected and locally path-connected domain that can possibly have the ...following two properties: (pH)#π1(X˜H,x˜0)=H and pH has the unique lifting property. X˜H consists of equivalence classes of paths starting at x0, appropriately topologized, and pH is the endpoint projection. For pH to have these two properties, T1 fibers are necessary and unique path lifting is sufficient. However, pH always admits the standard lifts of paths.
We show that pH has unique path lifting if it has continuous (standard) monodromies toward a T1 fiber over x0. Assuming, in addition, that H is locally quasinormal (e.g., if H is normal) we show that X is homotopically path Hausdorff relative to H. We show that pH is a fibration if X is locally path connected, H is locally quasinormal, and all (standard) monodromies are continuous.
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.
Efficient open domination in Cayley graphs Tamizh Chelvam, T.; Mutharasu, Sivagnanam
Applied mathematics letters,
October 2012, 2012-10-00, 20121001, Volume:
25, Issue:
10
Journal Article
Peer reviewed
Open access
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.
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.
PDF
