Search

Canonical decompositions, such as the Gallai–Edmonds and Dulmage–Mendelsohn decompositions, are a series of structure theorems that form the foundation of matching theory. The classical Kotzig–Lovász decomposition is a canonical decomposition applicable to a special class of graphs with perfect matchings, called factor-connected graphs, and is famous for its contribution to the studies of perfect matching polytopes and lattices. Recently, this decomposition has been generalized for general graphs with perfect matchings; this generalized decomposition is called the general Kotzig–Lovász decomposition. In fact, this generalized decomposition can be presented as a component of a more composite canonical decomposition called the Basilica decomposition. As such, the general Kotzig–Lovász decomposition has contributed to the derivation of various new results in matching theory, such as an alternative proof of the tight cut lemma and a characterization of maximal barriers in general graphs. Joins in grafts, also known as T -joins in graphs, is a classical concept in combinatorics and is a generalization of perfect matchings in terms of parity. More precisely, minimum joins and grafts are generalizations of perfect matchings and graphs with perfect matchings, respectively. Under the analogy between matchings and joins, analogues of the canonical decompositions for grafts are expected to be strong and fundamental tools for studying joins. In this paper, we provide a generalization of the general Kotzig–Lovász decomposition for arbitrary grafts. Our result also contains Sebö's generalization of the classical Kotzig–Lovász decomposition for factor-connected grafts. From our results in this paper, a generalization of the Dulmage–Mendelsohn decomposition, which is originally a classical canonical decomposition for bipartite graphs, has been obtained for bipartite grafts. This paper is the first of a series of papers that establish a generalization of the Basilica decomposition for grafts. [ABSTRACT FROM AUTHOR]

Strong product G1⊠ G2 of two graphs G1 and G2 has a vertex set V(G1)×V(G2) and two vertices (u1, v1) and (u2, v2) are adjacent whenever u1=u2 and v1 is adjacent to v2 or u1 is adjacent to u2 and v1=v2, or u1 is adjacent to u2 and v1 is adjacent to v2. We investigate the factor-criticality of G1⊠ G2 and obtain the following. Let G1 and G2 be connected m-factor-critical and n-factor-critical graphs, respectively. Then if m≥ 0, n=0, |V(G1)|≥ 2m+2 and |V(G2)|≥ 4, then G1⊠ G2 is (2m+2)-factor-critical; if n=1, |V(G1)|≥ 2m+3 and either m≥ 3 or |V(G2)|≥ 5, then G1⊠ G2 is (2m+4-ε)-factor-critical, where ε=0 if m is even, otherwise ε=1; if m+2 ≤ |V(G1)|≤ 2m+2, or n+2≤ |V(G2)|≤ 2n+2, then G1⊠ G2 is mn-factor-critical; if |V(G1)|≥ 2m+3 and |V(G2)|≥ 2n+3, then G1⊠ G2 is (mn-min{[3m/2]2, [3n/2]2})-factor-critical. [ABSTRACT FROM AUTHOR]

Lexicographic product G ∘ H of two graphs G and H has vertex set V (G) x V (H) and two vertices (u1; v1) and (u2; v2) are adjacent whenever u1u2 ∊ E(G), or u1 = u2 and v1v2 ∊ E(H). If every matching of G of size k can be extended to a perfect matching in G, then G is called k-extendable. In this paper, we study matching extendability in lexicographic product of graphs. The main result is that the lexicographic product of an m-extendable graph and an n-extendable graph is (m + 1)(n + 1)-extendable. In fact, we prove a slightly stronger result. [ABSTRACT FROM AUTHOR]