Domination and total domination in complementary prisms

被引:0
作者
Teresa W. Haynes
Michael A. Henning
Lucas C. van der Merwe
机构
[1] East Tennessee State University,Department of Mathematics
[2] University of KwaZulu-Natal,School of Mathematical Sciences
[3] University of Tennessee at Chattanooga,Department of Mathematics
来源
Journal of Combinatorial Optimization | 2009年 / 18卷
关键词
Cartesian product; Complementary prism; Domination; Total domination;
D O I
暂无
中图分类号
学科分类号
摘要
Let G be a graph and \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}${\overline {G}}$\end{document} be the complement of G. The complementary prism \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$G{\overline {G}}$\end{document} of G is the graph formed from the disjoint union of G and \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}${\overline {G}}$\end{document} by adding the edges of a perfect matching between the corresponding vertices of G and \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}${\overline {G}}$\end{document} . For example, if G is a 5-cycle, then \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$G{\overline {G}}$\end{document} is the Petersen graph. In this paper we consider domination and total domination numbers of complementary prisms. For any graph G, \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$\max\{\gamma(G),\gamma({\overline {G}})\}\le \gamma(G{\overline {G}})$\end{document} and \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$\max\{\gamma_{t}(G),\gamma_{t}({\overline {G}})\}\le \gamma_{t}(G{\overline {G}})$\end{document} , where γ(G) and γt(G) denote the domination and total domination numbers of G, respectively. Among other results, we characterize the graphs G attaining these lower bounds.
引用
收藏
页码:23 / 37
页数:14
相关论文
共 5 条
[1]  
Haynes TW(2007)The complementary product of two graphs Bull Inst Comb Appl 51 21-30
[2]  
Henning MA(2000)Graphs with large total domination number J Graph Theory 35 21-45
[3]  
Slater PJ(undefined)undefined undefined undefined undefined-undefined
[4]  
van der Merwe LC(undefined)undefined undefined undefined undefined-undefined
[5]  
Henning MA(undefined)undefined undefined undefined undefined-undefined