On well (edge) dominated and equimatchable strong product graphs

Yixin Cao; Guiqiang Mou; Jianxin Wang

doi:10.1016/j.disc.2025.114718

On well (edge) dominated and equimatchable strong product graphs

Yixin Cao
, Guiqiang Mou
, Jianxin Wang

Department of Computing

Research output: Journal article publication › Journal article › Academic research › peer-review

Abstract

A graph is well-(edge-)dominated if every minimal (edge) dominating set is minimum. A graph is equimatchable if every maximal matching is maximum. We study these concepts on strong product graphs. We fully characterize well-edge-dominated and equimatchable strong product graphs of nontrivial graphs, and identify a large family of graphs whose strong products with any well-dominated graph are well-dominated.

Original language	English
Article number	114718
Pages (from-to)	1--8
Number of pages	8
Journal	Discrete Mathematics
Volume	349
Issue number	1
DOIs	https://doi.org/10.1016/j.disc.2025.114718
Publication status	Published - Jan 2026

Keywords

Equimatchable
Strong product graph
Well-dominated
Well-edge-dominated

ASJC Scopus subject areas

Theoretical Computer Science
Discrete Mathematics and Combinatorics

More information

10.1016/j.disc.2025.114718

Cite this

@article{fc0b8f1010ff4b999f7e36cbc207c3c3,

title = "On well (edge) dominated and equimatchable strong product graphs",

abstract = "A graph is well-(edge-)dominated if every minimal (edge) dominating set is minimum. A graph is equimatchable if every maximal matching is maximum. We study these concepts on strong product graphs. We fully characterize well-edge-dominated and equimatchable strong product graphs of nontrivial graphs, and identify a large family of graphs whose strong products with any well-dominated graph are well-dominated.",

keywords = "Equimatchable, Strong product graph, Well-dominated, Well-edge-dominated",

author = "Yixin Cao and Guiqiang Mou and Jianxin Wang",

note = "Publisher Copyright: {\textcopyright} 2025 Elsevier B.V.",

year = "2026",

month = jan,

doi = "10.1016/j.disc.2025.114718",

language = "English",

volume = "349",

pages = "1----8",

journal = "Discrete Mathematics",

issn = "0012-365X",

publisher = "Elsevier B.V.",

number = "1",

}

TY - JOUR

T1 - On well (edge) dominated and equimatchable strong product graphs

AU - Cao, Yixin

AU - Mou, Guiqiang

AU - Wang, Jianxin

PY - 2026/1

Y1 - 2026/1

N2 - A graph is well-(edge-)dominated if every minimal (edge) dominating set is minimum. A graph is equimatchable if every maximal matching is maximum. We study these concepts on strong product graphs. We fully characterize well-edge-dominated and equimatchable strong product graphs of nontrivial graphs, and identify a large family of graphs whose strong products with any well-dominated graph are well-dominated.

AB - A graph is well-(edge-)dominated if every minimal (edge) dominating set is minimum. A graph is equimatchable if every maximal matching is maximum. We study these concepts on strong product graphs. We fully characterize well-edge-dominated and equimatchable strong product graphs of nontrivial graphs, and identify a large family of graphs whose strong products with any well-dominated graph are well-dominated.

KW - Equimatchable

KW - Strong product graph

KW - Well-dominated

KW - Well-edge-dominated

UR - https://www.scopus.com/pages/publications/105012608669

U2 - 10.1016/j.disc.2025.114718

DO - 10.1016/j.disc.2025.114718

M3 - Journal article

SN - 0012-365X

VL - 349

SP - 1

EP - 8

JO - Discrete Mathematics

JF - Discrete Mathematics

IS - 1

M1 - 114718

ER -

On well (edge) dominated and equimatchable strong product graphs

Abstract

Keywords

ASJC Scopus subject areas

More information

Other files and links

Fingerprint

Cite this