- Tytuł:
- Effect of edge-subdivision on vertex-domination in a graph
- Autorzy:
-
Bhattacharya, Amitava
Vijayakumar, Gurusamy - Powiązania:
- https://bibliotekanauki.pl/articles/743368.pdf
- Data publikacji:
- 2002
- Wydawca:
- Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
- Tematy:
-
domination number
subdivision number
matching - Opis:
- Let G be a graph with Δ(G) > 1. It can be shown that the domination number of the graph obtained from G by subdividing every edge exactly once is more than that of G. So, let ξ(G) be the least number of edges such that subdividing each of these edges exactly once results in a graph whose domination number is more than that of G. The parameter ξ(G) is called the subdivision number of G. This notion has been introduced by S. Arumugam and S. Velammal. They have conjectured that for any graph G with Δ(G) > 1, ξ(G) ≤ 3. We show that the conjecture is false and construct for any positive integer n ≥ 3, a graph G of order n with ξ(G) > [1/3]log₂ n. The main results of this paper are the following: (i) For any connected graph G with at least three vertices, ξ(G) ≤ γ(G)+1 where γ(G) is the domination number of G. (ii) If G is a connected graph of sufficiently large order n, then ξ(G) ≤ 4√n ln n+5
- Źródło:
-
Discussiones Mathematicae Graph Theory; 2002, 22, 2; 335-347
2083-5892 - Pojawia się w:
- Discussiones Mathematicae Graph Theory
- Dostawca treści:
- Biblioteka Nauki