2-(Ddge-)Connected Edge Domination Number and Matching Number

Hengzhe Li, Ankang Wei, Shenggui Zhang

Research output: Contribution to journalArticlepeer-review

1 Scopus citations

Abstract

A k-connected (resp. k-edge-connected) edge dominating set D of a connected graph G is a subset of E(G) such that G[D] is k-connected (resp. k-edge-connected) and each e∈ E(G) \ D has at least one neighbor in D. The k-connected edge domination number (resp. k-edge-connected edge domination number) of a graph G is the minimum size of a k-connected (resp. k-edge-connected) edge dominating set of G, and denoted by γk(G) (resp. γk′(G)). In this paper, we investigate the relationship between matching number and 2-connected (resp. 2-edge-connected) edge domination number, and prove that for a graph G, if it is 2-edge-connected, then γ2′(G)≤5α′(G)-2, and if it is 2-connected, then γ2(G) ≤ 4 α(G) - 1 , where α(G) is the matching number of G.

Original languageEnglish
Article number31
JournalGraphs and Combinatorics
Volume39
Issue number2
DOIs
StatePublished - Apr 2023

Keywords

  • Connected edge dominating set
  • Edge dominating set
  • Maximal matching

Fingerprint

Dive into the research topics of '2-(Ddge-)Connected Edge Domination Number and Matching Number'. Together they form a unique fingerprint.

Cite this