Wyszukiwarka
Abstrakt
A set $S$ of vertices in a graph $G$ is a dominating set if every vertex not in $S$ is adjacent to a vertex in~$S$. If, in addition, $S$ is an independent set, then $S$ is an independent dominating set. The independent domination number $i(G)$ of $G$ is the minimum cardinality of an independent dominating set in $G$. The independent domination subdivision number $\sdi(G)$ is the minimum number of edges that must be subdivided (each edge in $G$ can be subdivided at most once) in order to increase the independent domination number. We show that for every connected graph $G$ on at least three vertices, the parameter $\sdi(G)$ is well defined and differs significantly from the well-studied domination subdivision number $\sdg(G)$. For example, if $G$ is a block graph, then $\sdg(G) \le 3$, while $\sdi(G)$ can be arbitrary large. Further we show that there exist connected graph $G$ with arbitrarily large maximum degree~$\Delta(G)$ such that $\sdi(G) \ge 3 \Delta(G) - 2$, in contrast to the known result that $\sdg(G) \le 2 \Delta(G) - 1$ always holds. Among other results, we present a simple characterization of trees $T$ with $\sdi(T) = 1$.
Cytowania
-
1
CrossRef
-
0
Web of Science
-
2
Scopus
Autorzy (4)
-
Ammar Babikir
-
Michael A. Henning
Cytuj jako
Pełna treść
- Wersja publikacji
- Accepted albo Published Version
- Licencja
-
otwiera się w nowej karcie
Słowa kluczowe
Informacje szczegółowe
- Kategoria:
- Publikacja w czasopiśmie
- Typ:
- artykuły w czasopismach
- Opublikowano w:
-
GRAPHS AND COMBINATORICS
nr 37,
strony 691 - 709,
ISSN: 0911-0119 - Język:
- angielski
- Rok wydania:
- 2021
- Opis bibliograficzny:
- Babikir A., Dettlaff M., Henning M. A., Lemańska M.: Independent Domination Subdivision in Graphs// GRAPHS AND COMBINATORICS -Vol. 37,iss. 3 (2021), s.691-709
- DOI:
- Cyfrowy identyfikator dokumentu elektronicznego (otwiera się w nowej karcie) 10.1007/s00373-020-02269-3
- Weryfikacja:
- Politechnika Gdańska
wyświetlono 140 razy