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
Enumerative approaches and structural results for selected combinatorial problems
Umeå University, Faculty of Science and Technology, Department of Mathematics and Mathematical Statistics.
2019 (English)Doctoral thesis, comprehensive summary (Other academic)
Place, publisher, year, edition, pages
Umeå: Umeå University , 2019. , p. 8
Keywords [en]
Graph, zero forcing, Latin squares, Youden squares, designs
National Category
Discrete Mathematics Computational Mathematics
Identifiers
URN: urn:nbn:se:umu:diva-158865ISBN: 978-91-7855-086-9 (print)OAI: oai:DiVA.org:umu-158865DiVA, id: diva2:1317629
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
List of papers
1. The Zero Forcing Number of Bijection Graphs
Open this publication in new window or tab >>The Zero Forcing Number of Bijection Graphs
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
Series
Lecture Notes in Computer Science ; 9538
Keywords
Zero forcing set, Zero forcing number, Bijection graph
National Category
Discrete Mathematics
Identifiers
urn:nbn:se:umu:diva-125915 (URN)10.1007/978-3-319-29516-9_28 (DOI)978-3-319-29515-2 (ISBN)978-3-319-29516-9 (ISBN)
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
2. Triples of Orthogonal Latin and Youden Rectangles of small order
Open this publication in new window or tab >>Triples of Orthogonal Latin and Youden Rectangles of small order
2019 (English)In: Journal of combinatorial designs (Print), ISSN 1063-8539, E-ISSN 1520-6610, Vol. 27, no 4, p. 229-250Article in journal (Refereed) Published
Abstract [en]

We have performed a complete enumeration of non-isotopic triples of mutually orthogonal k × n Latin rectangles for k ≤ n ≤ 7. Here we will present a census of such triples, classified by various properties, including the order of the autotopism group of the triple. As part of this we have also achieved the first enumeration of pairwise orthogonal triples of Youden rectangles. We have also studied orthogonal triples of k×8 rectangles which are formed by extending mutually orthogonal triples with non-trivial autotopisms one row at a time, and requiring that the autotopism group is non-trivial in each step. This class includes a triple coming from the projective plane of order 8. Here we find a remarkably symmetrical pair of triples of 4 × 8 rectangles, formed by juxtaposing two   selected copies of complete sets of MOLS of order 4.

National Category
Discrete Mathematics
Identifiers
urn:nbn:se:umu:diva-158857 (URN)10.1002/jcd.21642 (DOI)000459040800001 ()2-s2.0-85059030594 (PubMedID)
Available from: 2019-05-13 Created: 2019-05-13 Last updated: 2019-05-23Bibliographically approved
3. Enumeration of t-tuples of Mutually Orthogonal Latin Rectangles and Finite Geometries
Open this publication in new window or tab >>Enumeration of t-tuples of Mutually Orthogonal Latin Rectangles and Finite Geometries
(English)Manuscript (preprint) (Other academic)
National Category
Discrete Mathematics
Identifiers
urn:nbn:se:umu:diva-159293 (URN)
Available from: 2019-05-23 Created: 2019-05-23 Last updated: 2019-05-23
4. Enumeration of Youden Rectangles of Small Parameters
Open this publication in new window or tab >>Enumeration of Youden Rectangles of Small Parameters
(English)Manuscript (preprint) (Other academic)
National Category
Discrete Mathematics
Identifiers
urn:nbn:se:umu:diva-159292 (URN)
Available from: 2019-05-23 Created: 2019-05-23 Last updated: 2019-05-23

Open Access in DiVA

fulltext(239 kB)24 downloads
File information
File name FULLTEXT06.pdfFile size 239 kBChecksum SHA-512
ac302e8ba5cf4f0e982e42ff57dc0e41ce6947c9b1e671d292ea073360dcb242e57704ea2df029835ae7a550b2bb465b0c13b5d6e5d429bc83a92e608c7268eb
Type fulltextMimetype application/pdf
spikblad(134 kB)12 downloads
File information
File name SPIKBLAD02.pdfFile size 134 kBChecksum SHA-512
1991a9004058c7a127f325fade0e0633ec16f05720cb070b7b4e3499641094f2ccd6ce8b1da21756d4e4bdf686d1da504fe10ec4c51dd1e71b6a169bf7a49ecf
Type spikbladMimetype application/pdf

Search in DiVA

By author/editor
Shcherbak, Denys
By organisation
Department of Mathematics and Mathematical Statistics
Discrete MathematicsComputational Mathematics

Search outside of DiVA

GoogleGoogle Scholar
Total: 26 downloads
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

isbn
urn-nbn

Altmetric score

isbn
urn-nbn
Total: 86 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