2021/09/14 by Anna Lindeberg, Lindeberg, Anna, Marc Hellmuth +1
Computer Science · Mathematics · #Advanced Graph Theory Research #Combinatorics (math.CO) #Complexity and Algorithms in Graphs #Data Structures and Algorithms (cs.DS) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #Limits and Structures in Graph Theory
paper · pdf · doi:10.48550/arxiv.2109.06755
openalex publication_date 2021/09/14 · openalex created_date 2022/07/25 · openalex updated_date 2026/07/28
A k-matching M of a graph G=(V,E) is a subset M\⊆ E such that\neach connected component in the subgraph F = (V,M) of G is either a\nsingle-vertex graph or k-regular, i.e., each vertex has degree k. In this\ncontribution, we are interested in k-matchings within the four standard graph\nproducts: the Cartesian, strong, direct and lexicographic product.\n As we shall see, the problem of finding non-empty k-matchings (k\≥ 3)\nin graph products is NP-complete. Due to the general intractability of this\nproblem, we focus on distinct polynomial-time constructions of k-matchings in\na graph product G\⋆ H that are based on kG-matchings MG and\nkH-matchings MH of its factors G and H, respectively. In particular,\nwe are interested in properties of the factors that have to be satisfied such\nthat these constructions yield a maximum k-matching in the respective\nproducts. Such constructions are also called "well-behaved" and we provide\nseveral characterizations for this type of k-matchings.\n Our specific constructions of k-matchings in graph products satisfy the\nproperty of being weak-homomorphism preserving, i.e., constructed matched edges\nin the product are never "projected" to unmatched edges in the factors. This\nleads to the concept of weak-homomorphism preserving k-matchings. Although\nthe specific k-matchings constructed here are not always maximum\nk-matchings of the products, they have always maximum size among all\nweak-homomorphism preserving k-matchings. Not all weak-homomorphism\npreserving k-matchings, however, can be constructed in our manner. We will,\ntherefore, determine the size of maximum-sized elements among all\nweak-homomorphims preserving k-matching within the respective graph products,\nprovided that the matchings in the factors satisfy some general assumptions.\n