On well (edge) dominated and equimatchable strong product graphs

Yixin Cao, Guiqiang Mou, Jianxin WangDiscret. Math 2026 · DOI

TL;DR

This paper delves into the properties of "well-dominated," "well-edge-dominated," and "equimatchable" graphs, specifically when these graphs are formed by taking the strong product of two other graphs. The authors provide complete characterizations for when these complex product graphs exhibit these desirable domination and matching properties, offering a deeper understanding of graph structure in these specific constructions.

What Problem Does This Paper Address?

Graph theory often explores how structural properties of individual graphs combine when those graphs are used to build larger, more complex graphs through various "product" operations. This paper focuses on the strong product of graphs, a specific way of combining two graphs G and H into a new graph G ✉ H. The authors are interested in three particular properties:

  • Well-dominated graphs: Graphs where every minimal dominating set (a smallest set of vertices that "controls" all other vertices) is also a minimum dominating set (the absolute smallest possible size).
  • Well-edge-dominated graphs: The edge-based equivalent of well-dominated graphs, where every minimal edge dominating set is minimum.
  • Equimatchable graphs: Graphs where every maximal matching (a set of edges with no shared vertices, which cannot be extended by adding more edges) is also a maximum matching (the largest possible size).

While these properties have been studied for individual graphs and other graph products (like Cartesian products), their behavior under the strong product construction was less understood. This paper aims to fill that gap by characterizing exactly when the strong product of two graphs will be well-dominated, well-edge-dominated, or equimatchable.

Methods

The paper employs a combination of theoretical graph-theoretic techniques, including:

  • Induction: Particularly strong induction on the sum of matching numbers of the factor graphs is used to prove results about well-edge-dominated strong products.
  • Characterizations: The core of the work involves deriving precise conditions (theorems and propositions) that define when a strong product graph possesses the target properties. This often involves translating properties of the product graph back to properties of its constituent factors.
  • Lemmas and Propositions: The authors build their arguments through a series of smaller, proven statements (lemmas and propositions) that establish intermediate results, such as the relationship between perfect matchings in factors and the well-edge-dominated property of their strong product.
  • Gallai–Edmonds Decomposition: For the equimatchable case, the paper leverages the Gallai–Edmonds decomposition theorem, a fundamental result in matching theory, to analyze the structure of graphs with near-perfect matchings.
  • Case Analysis: The proofs often involve considering different cases, such as when the factors are complete graphs, bipartite graphs, or have specific matching properties.

Datasets

Not discussed in the paper.

Key Insights and Ideas

  • Strong product behavior is specific: The paper highlights that the properties of well-dominated, well-edge-dominated, and equimatchable graphs do not simply "transfer" from the factors to the strong product in a straightforward way. The structure of the strong product imposes unique constraints.
  • Trivially well-dominated factors are key for well-dominated products: A significant result shows that if one factor is "trivially well-dominated" (a specific structural property related to clique partitions of closed neighborhoods), then its strong product with any well-dominated graph is also well-dominated. This provides a constructive way to generate well-dominated strong products.
  • Perfect matchings are crucial for well-edge-dominated products: A key finding is that a strong product of two nontrivial, connected graphs is well-edge-dominated if and only if both factors are simply K₂ (an edge). This is a very strong and specific condition.
  • Equimatchability links to factor-criticality and completeness: For equimatchable strong products, the paper reveals a connection to factor-critical graphs (graphs where removing any vertex leaves a graph with a perfect matching) and complete graphs. The conditions depend on whether the strong product itself has an even or odd number of vertices.
  • Near-perfect matchings are a necessary condition for equimatchable odd-order products: For strong products of odd-order graphs to be equimatchable, both factors must not only be equimatchable but also possess near-perfect matchings.

Key Results

  • Well-dominated strong products: Theorem 1.1 provides a sufficient condition: if G is trivially well-dominated and H is well-dominated, then G ✉ H is well-dominated. Conjecture 2.1 suggests this condition might be close to necessary.
  • Well-edge-dominated strong products: Theorem 1.2 gives a complete characterization: a strong product of two nontrivial and connected graphs is well-edge-dominated if and only if both factors are K₂ (a single edge).
  • Equimatchable strong products: Theorem 1.3 provides a complete characterization based on the parity of the factors and their independence numbers (α) and chromatic numbers (χ):
  • If G and H are even, G ✉ H is equimatchable if and only if it is complete.
  • If G and H are odd, G ✉ H is equimatchable if and only if α(G) + χ(H) ≤ 3 (or vice-versa).

Limitations and Future Work

  • Conjecture on well-dominated graphs: The paper poses Conjecture 2.1, suggesting that if a well-dominated graph is not trivially well-dominated, then there exists another well-dominated graph H such that their strong product is not well-dominated. This remains an open problem.
  • Focus on connected graphs: The study primarily focuses on connected graphs, as strong products are connected if and only if their factors are. The behavior of disconnected graphs is implicitly handled by considering their components.
  • Further exploration of specific graph classes: While the paper provides general characterizations, future work could explore these properties within specific subclasses of graphs (e.g., planar graphs, specific families of bipartite graphs) under the strong product.

Summary updated

BibTeX
@article{cao2026well,
  author = {Yixin Cao and Guiqiang Mou and Jianxin Wang},
  title = {{On well (edge) dominated and equimatchable strong product graphs}},
  journal = {Discret. Math},
  year = {2026},
  doi = {10.1016/j.disc.2025.114718},
}
Figure