Total forcing versus total domination in cubic graphs

被引：12

作者：

Dayila, Randy ^{[1
,2
]}

Henning, Michael A. ^{[1
]}

机构：

[1] Univ Johannesburg, Dept Pure & Appl Math, ZA-2006 Auckland Pk, South Africa

[2] Univ Houston Downtown, Dept Math & Stat, Houston, TX 77002 USA

来源：

APPLIED MATHEMATICS AND COMPUTATION | 2019年 / 354卷

关键词：

Total forcing set; Total dominating set; Cubic graph; NUMBER; BOUNDS;

D O I：

10.1016/j.amc.2019.02.060

中图分类号：

O29 [应用数学];

学科分类号：

070104 ;

摘要：

A set S of vertices in a graph G is a total dominating set of G if every vertex has a neighbor in S. The total domination number gamma(t)(G), is the minimum cardinality of a total dominating set of G. A total forcing set in a graph G is a forcing set (zero forcing set) in G which induces a subgraph without isolated vertices. The total forcing number of G, denoted F-t(G), is the minimum cardinality of a total forcing set in G. Our main contribution is to show that the total forcing number and the total domination number of a cubic graph are related. More precisely, we prove that if G is a connected cubic graph different from K-3,K-3, then F-t(G) <= 3/2 gamma(t)(G). (C) 2019 Elsevier Inc. All rights reserved.

引用

页码：385 / 395

页数：11

共 29 条

[1] Upper bounds on the k-forcing number of a graph [J].

Amos, David ;

Caro, Yair ;

Davila, Randy ;

Pepper, Ryan .

DISCRETE APPLIED MATHEMATICS, 2015, 181 :1-10

[2]

[Anonymous], THESIS

[3] Some remarks on domination [J].

Archdeacon, D ;

Ellis-Monaghan, J ;

Fisher, D ;

Froncek, D ;

Lam, PCB ;

Seager, S ;

Wei, B ;

Yuster, R .

JOURNAL OF GRAPH THEORY, 2004, 46 (03) :207-210

[4] Zero forcing sets and the minimum rank of graphs [J].

Barioli, Francesco ;

Barrett, Wayne ;

Butler, Steve ;

Cioaba, Sebastian M. ;

Cvetkovic, Dragos ;

Fallat, Shaun M. ;

Godsil, Chris ;

Haemers, Willem ;

Hogben, Leslie ;

Mikkelson, Rana ;

Narayan, Sivaram ;

Pryporova, Olga ;

Sciriha, Irene ;

So, Wasin ;

Stevanovic, Dragan ;

van der Holst, Hein ;

Vander Meulen, Kevin N. ;

Wehe, Amy Wangsness .

LINEAR ALGEBRA AND ITS APPLICATIONS, 2008, 428 (07) :1628-1648

[5] Parameters Related to Tree-Width, Zero Forcing, and Maximum Nullity of a Graph [J].

Barioli, Francesco ;

Barrett, Wayne ;

Fallat, Shaun M. ;

Hall, H. Tracy ;

Hogben, Leslie ;

Shader, Bryan ;

van den Driessche, P. ;

van der Holst, Hein .

JOURNAL OF GRAPH THEORY, 2013, 72 (02) :146-177

[6] Complexity and computation of connected zero forcing [J].

Brimkov, Boris ;

Hicks, Illya V. .

DISCRETE APPLIED MATHEMATICS, 2017, 229 :31-45

[7] Logic circuits from zero forcing [J].

Burgarth, Daniel ;

Giovannetti, Vittorio ;

Hogben, Leslie ;

Severini, Simone ;

Young, Michael .

NATURAL COMPUTING, 2015, 14 (03) :485-490

[8]

Caro Y., 2015, THEORY APPL GRAPHS, V2

[9]

Chekuri C, 2009, LECT NOTES COMPUT SC, V5555, P254, DOI 10.1007/978-3-642-02927-1_22

[10] SMALL TRANSVERSALS IN HYPERGRAPHS [J].

CHVATAL, V ;

MCDIARMID, C .

COMBINATORICA, 1992, 12 (01) :19-26

← 1 2 3 →