Bounds on the Connected Forcing Number of a Graph

Randy Davila; Michael A. Henning; Colton Magnant; Ryan Pepper

doi:10.1007/s00373-018-1957-x

Bounds on the Connected Forcing Number of a Graph

Randy Davila, Michael A. Henning, Colton Magnant, Ryan Pepper

Mathematics and Applied Mathematics

Research output: Contribution to journal › Article › peer-review

12 Citations (Scopus)

Abstract

In this paper, we study (zero) forcing sets which induce connected subgraphs of a graph. The minimum cardinality of such a set is called the connected forcing number of the graph. We provide sharp upper and lower bounds on the connected forcing number in terms of the minimum degree, maximum degree, girth, and order of the graph.

Original language	English
Pages (from-to)	1159-1174
Number of pages	16
Journal	Graphs and Combinatorics
Volume	34
Issue number	6
DOIs	https://doi.org/10.1007/s00373-018-1957-x
Publication status	Published - 1 Nov 2018

Keywords

Connected dominating sets
Connected domination number
Girth
Zero forcing number
Zero forcing sets

ASJC Scopus subject areas

Theoretical Computer Science
Discrete Mathematics and Combinatorics

Access to Document

10.1007/s00373-018-1957-x

Cite this

@article{c9a771c4160946bb9008ac65aaa663ad,

title = "Bounds on the Connected Forcing Number of a Graph",

abstract = "In this paper, we study (zero) forcing sets which induce connected subgraphs of a graph. The minimum cardinality of such a set is called the connected forcing number of the graph. We provide sharp upper and lower bounds on the connected forcing number in terms of the minimum degree, maximum degree, girth, and order of the graph.",

keywords = "Connected dominating sets, Connected domination number, Girth, Zero forcing number, Zero forcing sets",

author = "Randy Davila and Henning, {Michael A.} and Colton Magnant and Ryan Pepper",

note = "Publisher Copyright: {\textcopyright} 2018, Springer Japan KK, part of Springer Nature.",

year = "2018",

month = nov,

day = "1",

doi = "10.1007/s00373-018-1957-x",

language = "English",

volume = "34",

pages = "1159--1174",

journal = "Graphs and Combinatorics",

issn = "0911-0119",

publisher = "Springer Japan",

number = "6",

}

TY - JOUR

T1 - Bounds on the Connected Forcing Number of a Graph

AU - Davila, Randy

AU - Henning, Michael A.

AU - Magnant, Colton

AU - Pepper, Ryan

PY - 2018/11/1

Y1 - 2018/11/1

N2 - In this paper, we study (zero) forcing sets which induce connected subgraphs of a graph. The minimum cardinality of such a set is called the connected forcing number of the graph. We provide sharp upper and lower bounds on the connected forcing number in terms of the minimum degree, maximum degree, girth, and order of the graph.

AB - In this paper, we study (zero) forcing sets which induce connected subgraphs of a graph. The minimum cardinality of such a set is called the connected forcing number of the graph. We provide sharp upper and lower bounds on the connected forcing number in terms of the minimum degree, maximum degree, girth, and order of the graph.

KW - Connected dominating sets

KW - Connected domination number

KW - Girth

KW - Zero forcing number

KW - Zero forcing sets

UR - http://www.scopus.com/inward/record.url?scp=85054762421&partnerID=8YFLogxK

U2 - 10.1007/s00373-018-1957-x

DO - 10.1007/s00373-018-1957-x

M3 - Article

AN - SCOPUS:85054762421

SN - 0911-0119

VL - 34

SP - 1159

EP - 1174

JO - Graphs and Combinatorics

JF - Graphs and Combinatorics

IS - 6

ER -

Bounds on the Connected Forcing Number of a Graph

Abstract

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this