# Effect of edge-subdivision on vertex-domination in a graph

• Volume: 22, Issue: 2, page 335-347
• ISSN: 2083-5892

top

## Abstract

top
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

## How to cite

top

Amitava Bhattacharya, and Gurusamy Rengasamy Vijayakumar. "Effect of edge-subdivision on vertex-domination in a graph." Discussiones Mathematicae Graph Theory 22.2 (2002): 335-347. <http://eudml.org/doc/270539>.

@article{AmitavaBhattacharya2002,
abstract = {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},
author = {Amitava Bhattacharya, Gurusamy Rengasamy Vijayakumar},
journal = {Discussiones Mathematicae Graph Theory},
keywords = {domination number; subdivision number; matching},
language = {eng},
number = {2},
pages = {335-347},
title = {Effect of edge-subdivision on vertex-domination in a graph},
url = {http://eudml.org/doc/270539},
volume = {22},
year = {2002},
}

TY - JOUR
AU - Amitava Bhattacharya
AU - Gurusamy Rengasamy Vijayakumar
TI - Effect of edge-subdivision on vertex-domination in a graph
JO - Discussiones Mathematicae Graph Theory
PY - 2002
VL - 22
IS - 2
SP - 335
EP - 347
AB - 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
LA - eng
KW - domination number; subdivision number; matching
UR - http://eudml.org/doc/270539
ER -

## References

top
1. [1] N. Alon and J. H. Spencer, The Probabilistic Method, Second Edition, John Wiley and Sons Inc. (Tel Aviv and New York, 2000). Zbl0996.05001
2. [2] R. Diestel, Graph Theory, Second Edition (Springer-Verlag, New York, 2000).
3. [3] T.W. Haynes, S.M. Hedetniemi and S.T. Hedetniemi, Domination and independence subdivision numbers of graphs, Discuss. Math. Graph Theory 20 (2000) 271-280, doi: 10.7151/dmgt.1126. Zbl0984.05066
4. [4] T.W. Haynes, S.M. Hedetniemi, S.T. Hedetniemi, D.P. Jacobs, J. Knisely and L.C. van der Merwe, Domination Subdivision Numbers, preprint. Zbl1006.05042
5. [5] T.W. Haynes, S.T. Hedetniemi and P.J. Slater, Fundamentals of Domination in Graphs (Dekker, New York, 1998). Zbl0890.05002
6. [6] S. Velammal, Studies in Graph Theory: Covering, Independence, Domination and Related Topics, Ph.D. Thesis (Manonmaniam Sundaranar University, Tirunelveli, 1997).

## NotesEmbed?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.