umu.sePublications
Change search

Cite
Citation style
• apa
• ieee
• modern-language-association-8th-edition
• vancouver
• Other style
More styles
Language
• de-DE
• en-GB
• en-US
• fi-FI
• nn-NO
• nn-NB
• sv-SE
• Other locale
More languages
Output format
• html
• text
• asciidoc
• rtf
The Zero Forcing Number of Bijection Graphs
Umeå University, Faculty of Science and Technology, Department of Mathematics and Mathematical Statistics.
Umeå University, Faculty of Science and Technology, Department of Mathematics and Mathematical Statistics.
Umeå University, Faculty of Science and Technology, Department of Mathematics and Mathematical Statistics.
2015 (English)In: Proceedings of 26th International Workshop om Combinatorial Algorithms (IWOCA 2015), Berlin-Heidelberg: Springer, 2015, Vol. 9538, p. 334-345Conference paper, Published paper (Refereed)
##### Abstract [en]

The zero forcing number of a graph is a graph parameter based on a color change process, which starts with a state, where all vertices are colored either black or white. In the next step a white vertex turns black, if it is the only white neighbor of some black vertex, and this step is then iterated. The zero forcing number Z(G) is defined as the minimum cardinality of a set S of black vertices such that the whole vertex set turns black.

In this paper we study Z(G) for the class of bijection graphs, where a bijection graph is a graph on 2n vertices that can be partitioned into two parts with n vertices each, joined by a perfect matching. For this class of graphs we show an upper bound for the zero forcing number and classify the graphs that attain this bound. We improve the general lower bound for the zero forcing number, which is Z(G)&#x2265;&#x03B4;(G)" role="presentation" style="box-sizing: border-box; display: inline-table; line-height: normal; letter-spacing: normal; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; padding: 0px; margin: 0px; position: relative;">Z(G)≥δ(G)Z(G)≥δ(G), for certain bijection graphs and use this improved bound to find the exact value of the zero forcing number for these graphs. This extends and strengthens results of Yi (2012) about the more restricted class of so called permutation graphs.

##### Place, publisher, year, edition, pages
Berlin-Heidelberg: Springer, 2015. Vol. 9538, p. 334-345
##### Series
Lecture Notes in Computer Science ; 9538
##### Keywords [en]
Zero forcing set, Zero forcing number, Bijection graph
##### National Category
Discrete Mathematics
##### Identifiers
ISBN: 978-3-319-29515-2 (print)ISBN: 978-3-319-29516-9 (electronic)OAI: oai:DiVA.org:umu-125915DiVA, id: diva2:972702
##### Conference
26th International Workshop om Combinatorial Algorithms (IWOCA 2015), Verona, Italy, October 5-7, 2015
Available from: 2016-09-22 Created: 2016-09-22 Last updated: 2019-06-26Bibliographically approved
##### In thesis
1. Enumerative approaches and structural results for selected combinatorial problems
Open this publication in new window or tab >>Enumerative approaches and structural results for selected combinatorial problems
2019 (English)Doctoral thesis, comprehensive summary (Other academic)
##### Place, publisher, year, edition, pages
Umeå: Umeå University, 2019. p. 8
##### Keywords
Graph, zero forcing, Latin squares, Youden squares, designs
##### National Category
Discrete Mathematics Computational Mathematics
##### Identifiers
urn:nbn:se:umu:diva-158865 (URN)978-91-7855-086-9 (ISBN)
##### Public defence
2019-06-14, MA121, 10:00 (English)
##### Supervisors
Available from: 2019-05-24 Created: 2019-05-23 Last updated: 2019-05-24Bibliographically approved

#### Open Access in DiVA

No full text in DiVA

Publisher's full text

#### Authority records BETA

Shcherbak, DenysJäger, GeroldÖhman, Lars-Daniel

#### Search in DiVA

##### By author/editor
Shcherbak, DenysJäger, GeroldÖhman, Lars-Daniel
##### By organisation
Department of Mathematics and Mathematical Statistics
##### On the subject
Discrete Mathematics

doi
isbn
urn-nbn

#### Altmetric score

doi
isbn
urn-nbn
Total: 358 hits

Cite
Citation style
• apa
• ieee
• modern-language-association-8th-edition
• vancouver
• Other style
More styles
Language
• de-DE
• en-GB
• en-US
• fi-FI
• nn-NO
• nn-NB
• sv-SE
• Other locale
More languages
Output format
• html
• text
• asciidoc
• rtf