Construction of k-matchings in graph products

DOI10.26493/2590-9770.1462.B03MaRDI QIDQ5058206zbMATH OpenOpenAlexFDO

Authors Anna Lindeberg, Marc Hellmuth

Publication date 19 December 2022

Published in The Art of Discrete and Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2109.06755

zbMATH Keywords

\(k\)-factor\(k\)-regular subgraphsgraph productmaximum matchingNP-completenessperfect matching

Mathematics Subject Classification ID

Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph operations (line graphs, products, etc.) (05C76) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Combinatorial optimization (90C27)

Abstract: A $k$-matching $M$ of a graph $G=(V,E)$ is a subset $MsubseteqE$ such that each connected component in the subgraph $F=(V,M)$ of $G$ is either a single-vertex graph or $k$-regular, i.e., each vertex has degree $k$. In this contribution, we are interested in $k$-matchings within the four standard graph products: the Cartesian, strong, direct and lexicographic product. As we shall see, the problem of finding non-empty $k$-matchings ($kgeq3$) in graph products is NP-complete. Due to the general intractability of this problem, we focus on distinct polynomial-time constructions of $k$-matchings in a graph product $GstarH$ that are based on $k_G$-matchings $M_G$ and $k_H$-matchings $M_H$ of its factors $G$ and $H$, respectively. In particular, we are interested in properties of the factors that have to be satisfied such that these constructions yield a maximum $k$-matching in the respective products. Such constructions are also called "well-behaved" and we provide several characterizations for this type of $k$-matchings. Our specific constructions of $k$-matchings in graph products satisfy the property of being weak-homomorphism preserving, i.e., constructed matched edges in the product are never "projected" to unmatched edges in the factors. This leads to the concept of weak-homomorphism preserving $k$-matchings. Although the specific $k$-matchings constructed here are not always maximum $k$-matchings of the products, they have always maximum size among all weak-homomorphism preserving $k$-matchings. Not all weak-homomorphism preserving $k$-matchings, however, can be constructed in our manner. We will, therefore, determine the size of maximum-sized elements among all weak-homomorphims preserving $k$-matching within the respective graph products, provided that the matchings in the factors satisfy some general assumptions.

Recommendations

• scientific article; zbMATH DE number 434908
• On the number of k-matchings in graphs
• Enumeration of perfect matchings of the Cartesian products of graphs
• Integer \(k\)-matchings of graphs
• Enumeration of perfect matchings of a type of Cartesian products of graphs
• Matchings and matching extensions in graphs
• Perfect matchings and genus of some Cartesian products of graphs
• On matchings in graphs
• Product constructions for transitive decompositions of graphs
• Matching and edge covering number on strong product of complete graphs

Cites work

• 1-Factorizations of cartesian products of regular graphs
• A local prime factor decomposition algorithm
• A note on the complexity of finding regular subgraphs
• An algorithm for computing simple \(k\)-factors
• An algorithmic proof of Tutte's f-factor theorem
• An efficient method for decomposition of regular structures using graph products
• Enumeration of perfect matchings of a type of Cartesian products of graphs
• Existence of 3-regular subgraphs in Cartesian product of cycles
• Factoring the Cartesian product of a cubic graph and a triangle
• Fast recognition of partial star products and quasi Cartesian products
• Finding regular subgraphs in both arbitrary and planar graphs
• Graph factors and factorization: 1985--2003: a survey
• Graphs with 1-Factors
• Handbook of product graphs
• scientific article; zbMATH DE number 3817753 (Why is no real title available?)
• scientific article; zbMATH DE number 3487489 (Why is no real title available?)
• Lexicographic product of extendable graphs
• Local algorithms for the prime factorization of strong product graphs
• Matching preclusion for n-grid graphs
• Matching preclusion number in Cartesian product of graphs and its application to interconnection networks.
• Matching preclusion number in product graphs
• Matching theory
• Matrix representation of Husserl's part-whole-foundation theory
• On Edge-Colorability of Cartesian Products of Graphs^*
• On the 1-factors of n-connected graphs
• On the Complexity of General Graph Factor Problems
• One-factors and \(k\)-factors
• Partial star products: a local covering approach for the recognition of approximate Cartesian product graphs
• Paths, Trees, and Flowers
• Perfect matchings after vertex deletions
• Perfect matchings and genus of some Cartesian products of graphs
• Quasi-independence, homology and the unity of type: a topological theory of characters
• Regular subgraphs of hypercubes
• The complexity of regular subgraph recognition
• The Factorization of Linear Graphs
• The Factors of Graphs

Cited in

(1)

• scientific article; zbMATH DE number 2226732 (Why is no real title available?)

Describes a project that uses

Uses Software

• TopoLayout

This page was built for publication: Construction of k-matchings in graph products

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5058206)