umu.sePublications
Change search
CiteExportLink to record
Permanent link

Direct link
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)≥δ(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
URN: urn:nbn:se:umu:diva-125915DOI: 10.1007/978-3-319-29516-9_28ISBN: 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)
Opponent
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

Other links

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
Discrete Mathematics

Search outside of DiVA

GoogleGoogle Scholar

doi
isbn
urn-nbn

Altmetric score

doi
isbn
urn-nbn
Total: 358 hits
CiteExportLink to record
Permanent link

Direct link
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