Some counting problems in graphs

Erstveröffentlichung
2021-04-26Authors
Mohr, Elena
Referee
Rautenbach, DieterBruhn-Fujimoto, Henning
Dissertation
Faculties
Fakultät für Mathematik und WirtschaftswissenschaftenInstitutions
Institut für Optimierung und Operations ResearchAbstract
This doctoral thesis is based on six research papers. We give upper and lower bounds on
the number of subsets of the vertex set of a graph with certain properties, often we also
characterize the extremal graphs.
The results can be divided in four main parts. In the first part we give upper bounds
on the number of maximum independent sets in connected graphs and trees in terms of
the independence number and the order of a graph. We examine a similar problem for
dominating sets in the second part by giving upper bounds on the number of minimum
(total) dominating sets in forests. We give tight lower bounds on the number of rainbow
triangles in edge colored graphs in terms of the number of colors and the number of edges
of the graph in the third part of the thesis. We also characterize the extremal graphs.
In the last part we give a tight upper bound on the number of Hamiltonian cycles in
claw-free cubic graphs and characterize the set of graphs that fulfill this bound with
equality.
Date created
2020
Cumulative dissertation containing articles
• J. D. Alvarado, S. Dantas, E. Mohr, and D. Rautenbach. “On the maximum number of minimum dominating sets in forests”. In: Discrete Mathematics 342.4 (2019), pp. 934--942. https://doi.org/10.1016/j.disc.2018.11.025
• E. Mohr and D. Rautenbach. “On the maximum number of maximum independent sets in connected graphs”. In: Journal of Graph Theory 96 (2021), pp. 510--521. https://doi.org/10.1002/jgt.22629
• E. Mohr and D. Rautenbach. “On Hamiltonian cycles in claw-free cubic graphs”. In: Discussiones Mathematicae Graph Theory (to appear). https://doi.org/10.7151/dmgt.2249
• S. Ehard and E. Mohr. “Rainbow triangles and cliques in edge-colored graphs”. In: European Journal of Combinatorics 84 (2020), p. 103037. https://doi.org/10.1016/j.ejc.2019.103037
• M. A. Henning, E. Mohr, and D. Rautenbach. “On the maximum number of minimum total dominating sets in forests”. In: Discrete Mathematics & Theoretical Computer Science 21.3 (2019). https://doi.org/10.23638/DMTCS-21-3-3
• E. Mohr and D. Rautenbach. “On the Maximum Number of Maximum Independent Sets”. In: Graphs and Combinatorics 34 (2018), pp. 1729--1740. https://doi.org/10.1007/s00373-018-1969-6
• E. Mohr and D. Rautenbach. “On the maximum number of maximum independent sets in connected graphs”. In: Journal of Graph Theory 96 (2021), pp. 510--521. https://doi.org/10.1002/jgt.22629
• E. Mohr and D. Rautenbach. “On Hamiltonian cycles in claw-free cubic graphs”. In: Discussiones Mathematicae Graph Theory (to appear). https://doi.org/10.7151/dmgt.2249
• S. Ehard and E. Mohr. “Rainbow triangles and cliques in edge-colored graphs”. In: European Journal of Combinatorics 84 (2020), p. 103037. https://doi.org/10.1016/j.ejc.2019.103037
• M. A. Henning, E. Mohr, and D. Rautenbach. “On the maximum number of minimum total dominating sets in forests”. In: Discrete Mathematics & Theoretical Computer Science 21.3 (2019). https://doi.org/10.23638/DMTCS-21-3-3
• E. Mohr and D. Rautenbach. “On the Maximum Number of Maximum Independent Sets”. In: Graphs and Combinatorics 34 (2018), pp. 1729--1740. https://doi.org/10.1007/s00373-018-1969-6
Subject headings
[GND]: Graphentheorie | Dominanzzahl | Rechnen | Hamiltonscher Graph[LCSH]: Graph theory | Counting | Hamiltonian systems
[Free subject headings]: Hamiltonian cycles | Independence number | Domination number | Rainbow triangles
[DDC subject group]: DDC 510 / Mathematics
Metadata
Show full item recordDOI & citation
Please use this identifier to cite or link to this item: http://dx.doi.org/10.18725/OPARU-36784
Mohr, Elena (2021): Some counting problems in graphs. Open Access Repositorium der Universität Ulm und Technischen Hochschule Ulm. Dissertation. http://dx.doi.org/10.18725/OPARU-36784
Citation formatter >