Dominating induced matchings and other graph parameters
| Autor: | A. Mahmoodi, A. Behmaram, T. Došlić, N. Asadi |
|---|---|
| Jazyk: | angličtina |
| Rok vydání: | 2024 |
| Předmět: | |
| Zdroj: | AKCE International Journal of Graphs and Combinatorics, Vol 21, Iss 3, Pp 261-267 (2024) |
| Druh dokumentu: | article |
| ISSN: | 09728600 2543-3474 0972-8600 |
| DOI: | 10.1080/09728600.2024.2342310 |
| Popis: | A matching M in a graph G is an induced matching if the largest degree of the subgraph of G induced by M is equal to one. A dominating induced matching (DIM) of G is an induced matching that dominates every edge of G. It is well known that, if they exist, all dominating induced matchings of G are of the same size. The dominating induced matching number of G, denoted by [Formula: see text], is the size of any dominating induced matching of G. In this paper, we continue the study of dominating induced matchings. We prove that, if G has a DIM, then the induced matching number of G is equal to the independence number of its line graph L(G) and to the edge domination number of G. It is also shown that [Formula: see text], provided that both G and L(G) have a DIM. We also present some bounds on [Formula: see text]. In particular, for a tree T with a DIM we show that [Formula: see text], where l is the number of leaves. Moreover, for a regular graph G we establish some Nordhaus-Gaddum type bounds. |
| Databáze: | Directory of Open Access Journals |
| Externí odkaz: |
|