CN-edge domination in graphs
Author: Alwardi Saleh Anwar, Soner Nandappa D.
Journal: Владикавказский математический журнал @vmj-ru
Article in issue: 2 т.15, 2013.
Free access
Let $G=(V,E)$ be a graph. A subset $D$ of $V$ is called common neighbourhood dominating set (CN-do\-mi\-nating set) if for every $v\in V-D$ there exists a vertex $u\in D$ such that $uv\in E(G)$ and $|\Gamma(u,v)|\geq1$, where $|\Gamma(u,v)|$ is the number of common neighbourhood between the vertices $u$ and $v$. The minimum cardinality of such CN-dominating set denoted by $\gamma_{cn}(G)$ and is called common neighbourhood domination number (CN-edge domination) of $G$. In this paper we introduce the concept of common neighbourhood edge domination (CN-edge domination) and common neighbourhood edge domatic number (CN-edge domatic number) in a graph, exact values for some standard graphs, bounds and some interesting results are established.
Common neighbourhood edge dominating set, common neighbourhood, edge domatic number, common neighbourhood edge domination number
Short address: https://sciup.org/14318417
IDR: 14318417
CN-реберное доминирование в графах
Пусть $G=(V,E)$~--- граф. Подмножество $D$ множества $V$ называется реберно доминирующим множеством с общей окрестностью (CN-реберно доминирующим множеством), если для любой вершины $v\in V-D$ существует вершина $u\in D$ такая, что $uv\in E(G)$ и $|\Gamma(u,v)|\geq 1$, где $|\Gamma(u,v)|$~--- множество общих соседей вершин $u$ и $v$. Наименьшая мощность такого CN-реберно доминирующего множества обозначается $\gamma_{cn}(G)$ и называется реберно доминирующим числом с общей окрестностью (CN-реберно доминирующим числом) графа~$G$. В данной статье вводятся понятия реберно доминирующего числа с общей окрестностью и реберно доматического числа с общей окрестностью (CN-реберно доматического числа) в графе, найдены их точные значения в некоторых стандартных графах, установлены границы и некоторые интересные результаты.
References CN-edge domination in graphs
- Alwardi A., Soner N.D., Ebadi K. On the Common neighbourhood domination number//J. of Computer and Math. Sciences.-2011.-Vol. 2, \No 3.-P. 547-556.
- Bondy J., Murthy U. Graph Theory with Applications.-New York: North Holland, 1976.
- Dharmalingam K. D. Studies in graph theorey-equitable domination and bottleneck domination//Ph. D. Thesis.-2006.
- Godsil C., Royle G. Algebraic Graph Theory.-New York: Springer-Verlag, 2001.-(Ser. Graduate Texts in Math. Vol. 207).
- Harary F. Graph Theory.-Boston: Addison-Wesley, 1969.
- Haynes T. W., Hedetniemi S. T., Slater P. J. Fundamentals of Domination in Graphs.-New York: Marcel Dekker, Inc. 1998.
- Jayaram S. R. Line domination in graphs//Graphs Combin.-1987.-Vol. 3.-P. 357-363.
- Mitchell S., Hedetniemi S. T. Edge domination in trees//Congr. Numer.-1977.-Vol. 19.-P. 489-509.
- Sampathkumar E., Neeralagi P. S. The neighborhood number of a graph//Indian J. Pure and Appl. Math.-1985.-Vol. 16, \No 2.-P. 126-132.
- Walikar H. B., Acharya B. D., Sampathkumar E. Recent Developments in the Theory of Domination in Graphs and Its Applications.-Alahabad: Mehta Research instutute, 1979.-241 p.-(MRI Lecture Notes in Math, Vol. 1).
- Haynes T. W., Hedetniemi S. T., Slater P. J. Fundamentals of Domination in Graphs.-New York: Marcel Dekker, Inc., 1998.
- Hedetneimi S. M., Hedetneimi S. T., Laskar R. C., Markus L., Slater P. J. Disjoint dominating sets in graphs//Proc. Int. Conf. on Disc. Math.-Bangalore: IMI-IISc, 2006.-P. 88-101.
- Kulli V. R., Sigarkanti S. C. Further results on the neighborhood number of a graph//Indian J. Pure and Appl. Math.-1992.-Vol. 23, \No 8.-P. 575-577.
- Sampathkumar E., Neeralagi P. S. The neighborhood number of a graph//Indian J. Pure and Appl. Math.-1985.-Vol. 16, \No 2.-P. 126-132.
