On Cylindrical Graph Construction and its Applications

Amir Daneshgar, Mohsen Hejrati, Meysam Madani

Abstract


In this article we introduce the cylindrical construction, as an edge-replacement procedure admitting twists on both ends of the hyperedges, generalizing the concepts of lifts and Pultr templates at the same time. We prove a tensor-hom duality for this construction and we show that not only a large number of well-known graph constructions are cylindrical but also the construction and its dual give rise to some new graph constructions, applications and results. To show the applicability of the main duality we introduce generalized Grötzsch, generalized Petersen-like and Coxeter-like graphs and we prove some coloring properties of these graphs.


Keywords


Graph homomorphism, Cylindrical construction, Generalized Petersen graph, Generalized Mycielski construction, Coxeter-like graphs, Adjoint functor, Category of graphs, Labeled and marked graphs, Extremal problems

Full Text: PDF