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

Hengzhe Li; Ankang Wei; Shenggui Zhang

doi:10.1007/s00373-023-02626-y

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

Hengzhe Li
, Ankang Wei
, Shenggui Zhang

School of Mathematics and Statistics

Henan Normal University

Research output: Contribution to journal › Article › peer-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 γ₂(G) ≤ 4 α^′(G) - 1 , where α^′(G) is the matching number of G.

Original language	English
Article number	31
Journal	Graphs and Combinatorics
Volume	39
Issue number	2
DOIs	https://doi.org/10.1007/s00373-023-02626-y
State	Published - Apr 2023

Keywords

Connected edge dominating set
Edge dominating set
Maximal matching

Access to Document

10.1007/s00373-023-02626-y

Cite this

@article{dc17d3d0d2a241da9128a5e87c3d6841,

title = "2-(Ddge-)Connected Edge Domination Number and Matching Number",

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) \textbackslash{} 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.",

keywords = "Connected edge dominating set, Edge dominating set, Maximal matching",

author = "Hengzhe Li and Ankang Wei and Shenggui Zhang",

note = "Publisher Copyright: {\textcopyright} 2023, The Author(s), under exclusive licence to Springer Nature Japan KK, part of Springer Nature.",

year = "2023",

month = apr,

doi = "10.1007/s00373-023-02626-y",

language = "英语",

volume = "39",

journal = "Graphs and Combinatorics",

issn = "0911-0119",

publisher = "Springer Japan",

number = "2",

}

TY - JOUR

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

AU - Li, Hengzhe

AU - Wei, Ankang

AU - Zhang, Shenggui

PY - 2023/4

Y1 - 2023/4

N2 - 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.

AB - 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.

KW - Connected edge dominating set

KW - Edge dominating set

KW - Maximal matching

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

U2 - 10.1007/s00373-023-02626-y

DO - 10.1007/s00373-023-02626-y

M3 - 文章

AN - SCOPUS:85150182681

SN - 0911-0119

VL - 39

JO - Graphs and Combinatorics

JF - Graphs and Combinatorics

IS - 2

M1 - 31

ER -

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

Abstract

Keywords

Access to Document

Other files and links

Fingerprint

Cite this