全部 标题 作者
关键词 摘要

OALib Journal期刊
ISSN: 2333-9721
费用:99美元

查看量下载量

相关文章

更多...

-Tuple Total Restrained Domination in Complementary Prisms

DOI: 10.1155/2013/984549

Full-Text   Cite this paper   Add to My Lib

Abstract:

In a graph with , a -tuple total restrained dominating set is a subset of such that each vertex of?? is adjacent to at least vertices of and also each vertex of is adjacent to at least vertices of?? . The minimum number of vertices of such sets in is the -tuple total restrained domination number of . In [ -tuple total restrained domination/domatic in graphs, BIMS], the author initiated the study of the -tuple total restrained domination number in graphs. In this paper, we continue it in the complementary prism of a graph. 1. Introduction Let be a simple graph with the vertex set?? and the edge set . The order?? and size?? of are denoted by and , respectively. The open neighborhood and the closed neighborhood of a vertex are and , respectively. Also the open neighborhood and the closed neighborhood of a subset are and , respectively. The degree of a vertex is . The minimum and maximum degree of a graph are denoted by and , respectively. If every vertex of has degree , then is called -regular. We write , , and for a complete graph, a cycle and a path of order , respectively, while denotes a complete -partite graph. The complement of a graph is denoted by and is a graph with the vertex set and for every two vertices and , if and only if . For each integer , the -join?? of a graph to a graph of order at least is the graph obtained from the disjoint union of and by joining each vertex of to at least vertices of [1]. Also, denotes the -join such that each vertex of is joined to exact vertices of . The complementary prism?? of is the graph formed from the disjoint union of and by adding the edges of a perfect matching between the corresponding vertices (same label) of and [2]. For example, the graph is the Petersen graph. Also, if , the graph is the corona , where the corona?? of a graph is the graph obtained from by attaching a pendant edge to each vertex of . The research of domination in graphs is an evergreen area of graph theory. Its basic concept is the dominating set. The literature on this subject has been surveyed and detailed in the two books by Haynes et al. [3, 4]. And many variants of the dominating set were introduced and the corresponding numerical invariants were defined for them. For example, the -tuple total dominating set is defined in [1] by Henning and Kazemi, which is an extension of the total dominating set (for more information see [5, 6]). Definition 1 (see [1]). Let be an integer and let be a graph with . A subset is called a -tuple total dominating set, briefly kTDS, in , if for each , . The minimum number of vertices of a -tuple

References

[1]  M. A. Henning and A. P. Kazemi, “ -tuple total domination in graphs,” Discrete Applied Mathematics, vol. 158, no. 9, pp. 1006–1011, 2010.
[2]  T. W. Haynes, M. A. Henning, P. J. Slater, and L. C. van der Merwe, “The complementary product of two graphs,” Bulletin of the Institute of Combinatorics and Its Applications, vol. 51, pp. 21–30, 2007.
[3]  T. W. Haynes, S. T. Hedetniemi, and P. J. Slater, Fundamentals of Domination in Graphs, vol. 208 of Monographs and Textbooks in Pure and Applied Mathematics, Marcel Dekker, New York, NY, USA, 1998.
[4]  T. W. Haynes, S. T. Hedetniemi, and P. J. Slater, Eds., Domination in Graphs: Advanced Topics, Marcel Dekker, New York, NY, USA, 1998.
[5]  M. A. Henning and A. P. Kazemi, “ -tuple total domination in cross products of graphs,” Journal of Combinatorial Optimization, vol. 24, no. 3, pp. 339–346, 2012.
[6]  A. P. Kazemi, “ -tuple total domination in complementary prisms,” ISRN Discrete Mathematics, vol. 2011, Article ID 681274, 13 pages, 2011.
[7]  E. J. Cockayne and S. T. Hedetniemi, “Towards a theory of domination in graphs,” Networks, vol. 7, no. 3, pp. 247–261, 1977.
[8]  E. J. Cockayne, R. M. Dawes, and S. T. Hedetniemi, “Total domination in graphs,” Networks, vol. 10, no. 3, pp. 211–219, 1980.
[9]  S. M. Sheikholeslami and L. Volkmann, “The -tuple total domatic number of a graph,” submitted to. Utilitas Mathematica, http://arxiv.org/abs/1106.5589.
[10]  A. P. Kazemi, “ -tuple total restrained domination/domatic in graphs,” Bulletin of the Iranian Mathematical Sciences, accepted.

Full-Text

Contact Us

service@oalib.com

QQ:3279437679

WhatsApp +8615387084133