ON TOTAL DOMINATION IN THE CARTESIAN PRODUCT OF GRAPHS

被引：5

作者：

Bresar, Bostjan ^{[1
]}

Hartinger, Tatiana Romina ^{[2
,3
]}

Kos, Tim ^{[4
]}

Milanic, Martin ^{[2
,3
]}

机构：

[1] Univ Maribor, Slovenia Inst Math Phys & Mech, Fac Nat Sci & Math, Ljubljana, Slovenia

[2] Univ Primorska, UP IAM, Muzejski Trg 2, SI-6000 Koper, Slovenia

[3] Univ Primorska, UP FAMNIT, Glagoljaka 8, SI-6000 Koper, Slovenia

[4] Inst Math Phys & Mech, Ljubljana, Slovenia

来源：

DISCUSSIONES MATHEMATICAE GRAPH THEORY | 2018年 / 38卷 / 04期

关键词：

total domination; Cartesian product; total domination quotient; NUMBER; TREES;

D O I：

10.7151/dmgt.2039

中图分类号：

O1 [数学];

学科分类号：

0701 ; 070101 ;

摘要：

Ho proved in [A note on the total domination number, Util. Math. 77 (2008) 97-100] that the total domination number of the Cartesian product of any two graphs with no isolated vertices is at least one half of the product of their total domination numbers. We extend a result of Lu and Hou from [Total domination in the Cartesian product of a graph and K-2 or C-n, Util. Math. 83 (2010) 313--322] by characterizing the pairs of graphs G and H for which gamma(t)(G square H) = 1/2 gamma(t)(G)gamma(t)(H), whenever gamma(t)(H)=2. In addition, we present an infinite family of graphs Gn with gamma(t)(G(n))=2n, which asymptotically approximate the equality in gamma(t)(G(n)square G(n)) >= 1/2 gamma(t)(G(n))(2).

引用

页码：963 / 976

页数：14

共 11 条

[1]

Bresar B., 2005, Electronic Notes in Discrete Mathematics, V22, P233

[2] Vizing's conjecture: a survey and recent results [J].

Bresar, Bostjan ;

Dorbec, Paul ;

Goddard, Wayne ;

Hartnell, Bert L. ;

Henning, Michael A. ;

Klavzar, Sandi ;

Rall, Douglas F. .

JOURNAL OF GRAPH THEORY, 2012, 69 (01) :46-76

[3]

Brigham R.C., 2000, J COMBIN COMPUT COMB, V34, P81

[4] Construction of trees and graphs with equal domination parameters [J].

Dorfling, Michael ;

Goddard, Wayne ;

Henning, Michael A. ;

Mynhardt, C. M. .

DISCRETE MATHEMATICS, 2006, 306 (21) :2647-2654

[5]

Goddard W, 2008, UTILITAS MATHEMATICA, V75, P193

[6]

Henning M.A., 2013, Springer Monographs in Mathematics, pxiv + 178

[7] On the total domination number of Cartesian products of graphs [J].

Henning, MA ;

Rall, DF .

GRAPHS AND COMBINATORICS, 2005, 21 (01) :63-69

[8]

Henning MA, 2001, UTILITAS MATHEMATICA, V60, P99

[9] A survey of selected recent results on total domination in graphs [J].

Henning, Michael A. .

DISCRETE MATHEMATICS, 2009, 309 (01) :32-63

[10]

Ho PT, 2008, UTILITAS MATHEMATICA, V77, P97

← 1 2 →