• English
    • Deutsch
  • English 
    • English
    • Deutsch
  • Login
View Item 
  •   Home
  • Universität Ulm
  • Publikationen
  • View Item
  •   Home
  • Universität Ulm
  • Publikationen
  • View Item
JavaScript is disabled for your browser. Some features of this site may not work without it.

Some counting problems in graphs

Thumbnail
Mohr_Dissertation_f. ... (2.042Mb)
Erstveröffentlichung
2021-04-26
Authors
Mohr, Elena
Referee
Rautenbach, Dieter
Bruhn-Fujimoto, Henning
Dissertation


Faculties
Fakultät für Mathematik und Wirtschaftswissenschaften
Institutions
Institut für Optimierung und Operations Research
Abstract
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
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
License
Standard
https://oparu.uni-ulm.de/xmlui/license_v3

Metadata
Show full item record

DOI & 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 >



Policy | kiz service OPARU | Contact Us
Impressum | Privacy statement
 

 

Advanced Search

Browse

All of OPARUCommunities & CollectionsPersonsInstitutionsPublication typesUlm SerialsDewey Decimal ClassesEU projects UlmDFG projects UlmOther projects Ulm

My Account

LoginRegister

Statistics

View Usage Statistics

Policy | kiz service OPARU | Contact Us
Impressum | Privacy statement