http://www.tu-ilmenau.de

Logo TU Ilmenau


Arbeitsgruppe
Diskrete Mathematik und Algebra


Ansprechpartner

Univ.-Prof. Dr. rer. nat. habil. Matthias Kriesell

Fachgebietsleiter

Telefon +49 3677 69-3633

E-Mail senden


Ihre Position

INHALTE

Publikationsliste seit 1990

Anzahl der Treffer: 361
Erstellt: Fri, 20 Oct 2017 23:07:01 +0200 in 0.9334 sec


Brause, Christoph; Kemnitz, Arnfried; Marangio, Massimiliano; Pruchnewski, Anja; Voigt, Margit
Sum choice number of generalized [theta]-graphs. - In: Discrete mathematics. - Amsterdam [u.a.] : Elsevier, Bd. 340 (2017), 11, S. 2633-2640
https://doi.org/10.1016/j.disc.2016.11.028
Kriesell, Matthias
Degree sequences and edge connectivity. - In: Abhandlungen aus dem Mathematischen Seminar der Universität Hamburg. - Berlin [u.a.] : Springer, ISSN 18658784, Bd. 87 (2017), 2, S. 343-355
https://doi.org/10.1007/s12188-016-0171-0
Kriesell, Matthias
Unique colorability and clique minors. - In: Journal of graph theory. - New York, NY [u.a.] : Wiley, ISSN 10970118, Bd. 85 (2017), 1, S. 207-216
https://doi.org/10.1002/jgt.22056
Stiebitz, Michael
A relaxed version of the Erd˝os-Lovász Tihany conjecture. - In: Journal of graph theory. - New York, NY [u.a.] : Wiley, ISSN 10970118, Bd. 85 (2017), 1, S. 278-287
https://doi.org/10.1002/jgt.22060
Schweser, Thomas; Stiebitz, Michael
Degree choosable signed graphs. - In: Discrete mathematics. - Amsterdam [u.a.] : Elsevier, Bd. 340 (2017), 5, S. 882-891
http://dx.doi.org/10.1016/j.disc.2017.01.007
Bang-Jensen, Jørgen; Bessy, Stéphane; Jackson, Bill; Kriesell, Matthias
Antistrong digraphs. - In: Journal of combinatorial theory / B. - Orlando, Fla : Academic Press, Bd. 122 (2017), S. 68-90
http://dx.doi.org/10.1016/j.jctb.2016.05.004
Mehlhorn, Kurt; Neumann, Adrian; Schmidt, Jens M.
Certifying 3-edge-connectivity. - In: Algorithmica : an international journal in computer science. - New York, NY : Springer, ISSN 14320541, Bd. 77 (2017), 2, S. 309-335
http://dx.doi.org/10.1007/s00453-015-0075-x
Harant, Jochen; Fabrici, Igor; Jendrol', Stanislav
On longest cycles in essentially 4-connected planar graphs. - In: Electronic notes in discrete mathematics. - Amsterdam : Elsevier Science, ISSN 15710653, Bd. 55 (2016), S. 143-146
https://doi.org/10.1016/j.endm.2016.10.036
Alt, Helmut; Payne, Michael S.; Schmidt, Jens M.; Wood, David R.
Thoughts on Barnette's conjecture. - In: The Australasian journal of combinatorics. - Queensland : Centre for Discrete Mathematics and Computing, Univ. of Queensland, ISSN 10344942, Bd. 64 (2016), S. 354-365
http://ajc.maths.uq.edu.au/pdf/64/ajc_v64_p354.pdf
Schmidt, Jens M.
Mondshein sequences (a.k.a. (2,1)-orders). - In: SIAM journal on computing : a publication of the Society for Industrial and Applied Mathematics. - Philadelphia, Pa : SIAM, ISSN 10957111, Bd. 45 (2016), 6, S. 1985-2003
http://dx.doi.org/10.1137/15M1030030
Mnich, Matthias; Rutter, Ignaz; Schmidt, Jens M.
Linear-time recognition of map graphs with outerplanar witness. - In: 15th Scandinavian Symposium and Workshops on Algorithm Theory : SWAT 2016, June 22-24, 2016, Reykjavik, Iceland. - Saarbrücken/Wadern, Germany : Schloss Dagstuhl - Leibniz-Zentrum für Informatik GmbH, Dagstuhl Publishing / Scandinavian Symposium and Workshops on Algorithm Theory ; 15 (Reykjavik) : 2016.06.22-24., ISBN 978-3-95977-011-8, (2016), Seite 5:1-5:14

http://dx.doi.org/10.4230/LIPIcs.SWAT.2016.5
Bang-Jensen, Jørgen; Kriesell, Matthias; Maddaloni, Alessandro; Simonsen, Sven
Arc-disjoint directed and undirected cycles in digraphs. - In: Journal of graph theory. - New York, NY [u.a.] : Wiley, ISSN 10970118, Bd. 83 (2016), 4, S. 406-420
http://dx.doi.org/10.1002/jgt.22006
Adamaszek, Anna; Adamaszek, Michal; Mnich, Matthias; Schmidt, Jens M.
Lower bounds for locally highly connected graphs. - In: Graphs and combinatorics. - Tokyo : Springer-Verl. Tokyo, ISSN 14355914, Bd. 32 (2016), 5, S. 1641-1650
http://dx.doi.org/10.1007/s00373-016-1686-y
Harant, Jochen; Kemnitz, Arnfried
Lower bounds on the sum choice number of a graph. - In: Electronic notes in discrete mathematics. - Amsterdam : Elsevier Science, ISSN 15710653, Bd. 53 (2016), S. 421-431
http://dx.doi.org/10.1016/j.endm.2016.05.036
Fabrici, Igor; Harant, Jochen; Jendrol', Stanislav
On longest cycles in essentially 4-connected planar graphs. - In: Discussiones mathematicae / Graph theory. - Warsaw : De Gruyter Open, ISSN 20835892, Bd. 36 (2016), 3, S. 565-575
http://dx.doi.org/10.7151/dmgt.1875
Przybyło, Jakub; Schreyer, Jens; Škrabul'áková, Erika
On the facial Thue choice number of plane graphs via entropy compression method. - In: Graphs and combinatorics. - Tokyo : Springer-Verl. Tokyo, ISSN 14355914, Bd. 32 (2016), 3, S. 1137-1153
http://dx.doi.org/10.1007/s00373-015-1642-2
Harant, Jochen; Mohr, Samuel
Maximum weighted induced subgraphs. - In: Discrete mathematics. - Amsterdam [u.a.] : Elsevier, Bd. 339 (2016), 7, S. 1954-1559
http://dx.doi.org/10.1016/j.disc.2015.07.013
Axenovich, Maria; Harant, Jochen; Przybyło, Jaromir; Soták, Roman; Voigt, Margit; Weidelich, Jenny
A note on adjacent vertex distinguishing colorings of graphs. - In: Discrete applied mathematics. - [S.l.] : Elsevier, Bd. 205 (2016), S. 1-7
http://dx.doi.org/10.1016/j.dam.2015.12.005
Biedl, Therese; Schmidt, Jens M.
Small-area orthogonal drawings of 3-connected graphs. - In: Graph drawing and network visualization : 23rd international symposium, GD 2015, Los Angeles, CA, USA, September 24-26, 2015 : revised selected papers. - Cham : Springer / GD ; 23 (Los Angeles, Calif.) : 2015.09.24-26., ISBN 978-3-319-27261-0, (2015), S. 153-165

http://dx.doi.org/10.1007/978-3-319-27261-0_13
Schreyer, Jens; Škrabulьáková, Erika
Total Thue colourings of graphs. - In: European journal of mathematics. - Berlin [u.a.] : Springer, ISSN 21996768, Bd. 1 (2015), 1, S. 186-197
http://dx.doi.org/10.1007/s40879-014-0016-24201
Biedl, Therese; Schmidt, Jens M.
Small-area orthogonal drawings of 3-connected graphs. - In: De.arxiv.org. - [S.l.] : Arxiv.org, (2015), insges. 13 S.
http://arxiv.org/abs/1510.02322
Schmid, Andreas; Schmidt, Jens M.
Computing 2-walks in polynomial time. - In: 32nd International Symposium on Theoretical Aspects of Computer Science : STACS '15, March 4 - 7, 2015, Garching, Germany. - Saarbrücken/Wadern : Schloss Dagstuhl - Leibniz-Zentrum für Informatik / STACS ; 32 (Garching) : 2015.03.04-07., ISBN 978-3-939897-78-1, (2015), S. 676-688

http://dx.doi.org/10.4230/LIPIcs.STACS.2015.676
Stiebitz, Michael; Voigt, Margit
List-colourings. - In: Topics in chromatic graph theory : . - Cambridge : Cambridge Univ. Press, ISBN 978-1-107-03350-4, (2015), S. 114-136

Stiebitz, Michael; Toft, Bjarne
Brooks's theorem. - In: Topics in chromatic graph theory : . - Cambridge : Cambridge Univ. Press, ISBN 978-1-107-03350-4, (2015), S. 36-55

Kriesell, Matthias; Pedersen, Anders Sune
On graphs double-critical with respect to the colouring number. - In: Discrete mathematics and theoretical computer science : DMTCS : an electronic journal. - Nancy [u.a.] : [LORIA [u.a.], ISSN 13658050, Bd. 17 (2015), 2, S. 49-62
http://www.db-thueringen.de/servlets/DocumentServlet?id=26780
Miltzow, Tillmann; Schmidt, Jens M.; Xia, Mingji
Counting K 4 -subdivisions. - In: Discrete mathematics. - Amsterdam [u.a.] : Elsevier, Bd. 338 (2015), 12, S. 2387-2392
http://dx.doi.org/10.1016/j.disc.2015.06.004
Harant, Jochen; Niebling, Julia; Richter, Sebastian
Eigenvalue conditions for induced subgraphs. - In: Discussiones mathematicae / Graph theory. - Warsaw : De Gruyter Open, ISSN 20835892, Bd. 35 (2015), 2, S. 355-363
http://dx.doi.org/10.7151/dmgt.1790
Harant, Jochen; Richter, Sebastian
A new eigenvalue bound for independent sets. - In: Discrete mathematics. - Amsterdam [u.a.] : Elsevier, Bd. 338 (2015), 10, S. 1763-1765
http://dx.doi.org/10.1016/j.disc.2014.12.008
Kemnitz, Arnfried; Marangio, Massimiliano; Pruchnewski, Anja; Voigt, Margit
(P,Q)-total (r,s)-colorings of graphs. - In: Discrete mathematics. - Amsterdam [u.a.] : Elsevier, Bd. 338 (2015), 10, S. 1722-1729
http://dx.doi.org/10.1016/j.disc.2014.09.012
Stiebitz, Michael; Tuza, Zsolt; Voigt, Margit
Orientations of graphs with prescribed weighted out-degrees. - In: Graphs and combinatorics. - Tokyo : Springer-Verl. Tokyo, ISSN 14355914, Bd. 31 (2015), 1, S. 265-280
http://dx.doi.org/10.1007/s00373-013-1382-0
Schmidt, Jens M.; Valtr, Pavel
Cubic plane graphs on a given point set. - In: Computational geometry : theory and applications. - Amsterdam : Elsevier, Bd. 48 (2015), 1, S. 1-13
http://dx.doi.org/10.1016/j.comgeo.2014.06.001
Sukjit, Panchalee; Kubek, Mario; Böhme, Thomas; Unger, Herwig
PDSearch: using pictures as queries. - In: Recent advances in information and communication technology : proceedings of the 10th International Conference on Computing and Information Technology (IC2IT2014). - Cham : Springer International Publishing / International Conference on Computing and Information Technology (Phuket) : 2014.05.08-09., ISBN 978-3-319-06538-0, (2014), S. 255-262

http://dx.doi.org/10.1007/978-3-319-06538-0_25
Bang-Jensen, Jørgen; Kriesell, Matthias; Maddaloni, Alessandro; Simonsen, Sven
Vertex-disjoint directed and undirected cycles in general digraphs. - In: Journal of combinatorial theory / B. - Orlando, Fla : Academic Press, Bd. 106 (2014), S. 1-14
http://dx.doi.org/10.1016/j.jctb.2013.10.005
Miltzow, Tillmann; Schmidt, Jens M.; Xia, Mingji
Counting K 4 -subdivisions. - In: De.arxiv.org. - [S.l.] : Arxiv.org, (2014), insges. 11 S.
http://arxiv.org/abs/1411.4819
Fabrici, Igor; Jendrolь, Stanislav; Harant, Jochen; Soták, Roman
A note on vertex colorings of plane graphs. - In: Discussiones mathematicae / Graph theory. - Warsaw : De Gruyter Open, ISSN 20835892, Bd. 34 (2014), 4, S. 849-855
http://dx.doi.org/10.7151/dmgt.1771
Doerr, Carola; Ramakrishna, G.; Schmidt, Jens M.
Computing minimum cycle bases in weighted partial 2-trees in linear time. - In: Journal of graph algorithms and applications : JGAA. - [S.l.], ISSN 15261719, Bd. 18 (2014), 3, S. 325-346
http://dx.doi.org/10.7155/jgaa.00325
Schmidt, Jens M.
The Mondshein sequence. - In: Automata, languages, and programming : 41st international colloquium, ICALP 2014, Copenhagen, Denmark, July 8 - 11, 2014 ; proceedings, part I. - Berlin [u.a.] : Springer / ICALP ; 41 (Copenhagen) : 2014.07.08-11., ISBN 978-3-662-43948-7, (2014), S. 967-978

http://dx.doi.org/10.1007/978-3-662-43948-7_80
Brandt, Stephan; Harant, Jochen; Naumann, Steffi
On degree sums of a triangle-free graph. - In: Discrete mathematics. - Amsterdam [u.a.] : Elsevier, Bd. 337 (2014), S. 76-82
http://dx.doi.org/10.1016/j.disc.2014.08.010
Harant, Jochen; Richter, Sebastian
A new eigenvalue bound for independent sets. - Chemnitz : Technische Universität, Fakultät für Mathematik. - 6 Seiten. - (Preprint. - 2014,8)
Unterschiede zwischen dem gedruckten Dokument und der elektronischen Ressource können nicht ausgeschlossen werden
Harant, Jochen; Niebling, Julia; Richter, Sebastian
Eigenvalue conditions for induced subgraphs. - Chemnitz : Technische Universität, Fakultät für Mathematik. - 9 Seiten. - (Preprint. - 2014,12)
Unterschiede zwischen dem gedruckten Dokument und der elektronischen Ressource können nicht ausgeschlossen werden
Payne, Michael S.; Schmidt, Jens M.; Wood, David R.
Which point sets admit a k-angulation?. - In: Journal of computational geometry : JoCG. - [S.l.], ISSN 1920180X, Bd. 5 (2014), 1, S. 41-55
http://www.db-thueringen.de/servlets/DocumentServlet?id=24187
Czap, Július; Harant, Jochen; Hudák, Dávid
An upper bound on the sum of powers of the degrees of simple 1-planar graphs. - In: Discrete applied mathematics. - [S.l.] : Elsevier, Bd. 165 (2014), S. 146-151
http://dx.doi.org/10.1016/j.dam.2012.11.001
Ando, Kiyoshi; Egawa, Yoshimi; Kriesell, Matthias
The average degree of minimally contraction-critically 5-connected graphs. - In: Journal of graph theory. - New York, NY [u.a.] : Wiley, ISSN 10970118, Bd. 75 (2014), 4, S. 331-354
http://dx.doi.org/10.1002/jgt.21741
Harant, Jochen
A note on Barnette's conjecture. - In: Discussiones mathematicae / Graph theory. - Warsaw : De Gruyter Open, ISSN 20835892, Bd. 33 (2013), 1, S. 133-137
http://dx.doi.org/10.7151/dmgt.1643
Kriesell, Matthias
Minimal connectivity. - In: , ISBN 978-0-521-80231-4, (2013), S. 71-99

http://site.ebrary.com/lib/alltitles/docDetail.action?docID=10740543
Girlich, Franz; Roßberg, Michael; Schäfer, Günter; Böhme, Thomas; Schreyer, Jens
Bounds for the security of the Vivaldi network coordinate system. - In: 2013 Conference on Networked Systems (NetSys) : 11 - 15 March 2013, Stuttgart, Germany. - Piscataway, NJ : IEEE / International Conference on Networked Systems ; 1 (Stuttgart) : 2013.03.11-15., ISBN 978-1-4673-5645-9, (2013), S. 66-75

http://dx.doi.org/10.1109/NetSys.2013.21
Fabrici, Igor; Hexel, Erhard; Jendrolь, Stanislav
On vertices enforcing a Hamiltonian cycle. - In: Discussiones mathematicae / Graph theory. - Warsaw : De Gruyter Open, ISSN 20835892, Bd. 33 (2013), 1, S. 71-89
http://dx.doi.org/10.7151/dmgt.1653
Harant, Jochen; Richter, Sebastian; Sachs, Horst
Packing of induced subgraphs. - Chemnitz : Techn. Univ., Fak. Mathematik. - Online-Ressource (PDF-Datei: 15 S., 352 KB). - ([Preprintreihe der Fakultät Mathematik. - 2013,14])
http://edok01.tib.uni-hannover.de/edoks/e01fn14/782044271.pdf
Fleischner, Herbert; Stiebitz, Michael
Some remarks on the cycle plus triangles problem. - In: The mathematics of Paul Erdös : . - New York [u.a.] : Springer, ISBN 978-1-4614-7253-7, (2013), S. 119-125

Bruhn, Henning; Diestel, Reinhard; Kriesell, Matthias; Pendavingh, Rudi; Wollan, Paul
Axioms for infinite matroids. - In: Advances in mathematics. - Amsterdam [u.a.] : Elsevier, ISSN 10902082, Bd. 239 (2013), S. 18-46
http://dx.doi.org/10.1016/j.aim.2013.01.011
Göring, Frank; Harant, Jochen
Prescribed edges and forbidden edges for a cycle in a planar graph. - In: Discrete applied mathematics. - [S.l.] : Elsevier, Bd. 161 (2013), 12, S. 1734-1738
http://dx.doi.org/10.1016/j.dam.2011.08.020
Scheide, Diego; Stiebitz, Michael
The maximum chromatic index of multigraphs with given [Delta] and [mu]. - In: Graphs and combinatorics. - Tokyo : Springer-Verl. Tokyo, ISSN 14355914, Bd. 28 (2012), 5, S. 717-722
http://dx.doi.org/10.1007/s00373-011-1068-4
Cranston, Daniel W.; Pruchnewski, Anja; Tuza, Zsolt; Voigt, Margit
List colorings of K5-minor-free graphs with special list assignments. - In: Journal of graph theory. - New York, NY [u.a.] : Wiley, ISSN 10970118, Bd. 71 (2012), 1/2, S. 18-30
http://dx.doi.org/10.1002/jgt.20628
Borowiecki, Piotr; Göring, Frank; Harant, Jochen; Rautenbach, Dieter
The potential of greed for independence. - In: Journal of graph theory. - New York, NY [u.a.] : Wiley, ISSN 10970118, Bd. 71 (2012), 3/4, S. 245-259
http://dx.doi.org/10.1002/jgt.20644
Pruchnewski, Anja; Voigt, Margit
Weights of induced subgraphs in K1,r-free graphs. - In: Discrete mathematics. - Amsterdam [u.a.] : Elsevier, Bd. 312 (2012), 16, S. 2429-2432
http://dx.doi.org/10.1016/j.disc.2012.04.025
Harant, Jochen; Kemnitz, Arnfried; Saito, Akira; Schiermeyer, Ingo
Closures, cycles, and paths. - In: Journal of graph theory. - New York, NY [u.a.] : Wiley, ISSN 10970118, Bd. 69 (2012), 3, S. 314-323
http://dx.doi.org/10.1002/jgt.20584
Schreyer, Jens; Škrabul'áková, Erika
On the facial Thue choice index of plane graphs. - In: Discrete mathematics. - Amsterdam [u.a.] : Elsevier, Bd. 312 (2012), 10, S. 1713-1721
http://dx.doi.org/10.1016/j.disc.2012.01.023
Kostochka, Alexandr V.; Rabern, Landon; Stiebitz, Michael
Graphs with chromatic number close to maximum degree. - In: Discrete mathematics. - Amsterdam [u.a.] : Elsevier, Bd. 312 (2012), 6, S. 1273-1281
http://dx.doi.org/10.1016/j.disc.2011.12.014
Harant, Jochen; Jendrol', Stanislav
Nonrepetitive vertex colorings of graphs. - In: Discrete mathematics. - Amsterdam [u.a.] : Elsevier, Bd. 312 (2012), 2, S. 374-380
http://dx.doi.org/10.1016/j.disc.2011.09.027
Stiebitz, Michael; Scheide, Diego; Toft, Bjarne; Favrholdt, Lene M.
Graph edge coloring : Vizing's theorem and Goldberg's conjecture. - Hoboken, NJ : Wiley. - XIV, 321 S.. - (Wiley series in discrete mathematics and optimization)
ISBN 111809137X = 978-1-118-09137-1
"Written by world authorities on graph theory, this book features many new advances and applications in graph edge coloring, describes how the results are interconnected, and provides historial context throughout. Chapter coverage includes an introduction to coloring preliminaries and lower and upper bounds; the Vizing fan; the Kierstead path; simple graphs and line graphs of multigraphs; the Tashkinov tree; Goldberg's conjecture; extreme graphs; generalized edge coloring; and open problems. It serves as a reference for researchers interested in discrete mathematics, graph theory, operations research, theoretical computer science, and combinatorial optimization, as well as a graduate-level course book for students of mathematics, optimization, and computer science"-- Provided by publisher

"This book provides an overview of this development as well as describes how the many different results are related"--


http://www.gbv.de/dms/ilmenau/toc/670551414.PDF
Böhme, Thomas; Schreyer, Jens; Škrabul'áková, Erika
A note on semi-steady states in stochastic cellular automata. - In: Autonomous systems: developments and trends / Workshop on Autonomous Systems (Mallorca) : 2011.. : . - Berlin [u.a.] : Springer, ISBN 978-3-642-24805-4, (2011), S. 313-323

Löwenstein, Christian; Rautenbach, Dieter
Cohabitation of independent sets and dominating sets in trees. - In: Utilitas mathematicaUtilitas mathematica : an international journal of discrete and combinatorial mathematics. - Durban : Department of Mathematics and Applied Mathematics, Univ. of KwaZulu-Natal : an international journal of discrete and combinatorial mathematics. - Durban : Department of Mathematics and Applied Mathematics, Univ. of KwaZulu-Natal, ISSN 03153681, Bd. 85 (2011), S. 299-308
Harant, Jochen; Jendrol, Stanislav; Madaras, Tomáš
Upper bounds on the sum of powers of the degrees of a simple planar graph. - In: Journal of graph theory. - New York, NY [u.a.] : Wiley, ISSN 10970118, Bd. 67 (2011), 2, S. 112-123
http://dx.doi.org/10.1002/jgt.20519
Böhme, Thomas; Kostochka, Alexander; Thomason, Andrew
Minors in graphs with high chromatic number. - In: Combinatorics, probability & computing : CPC. - Cambridge : Cambridge Univ. Press, ISSN 14692163, Bd. 20 (2011), 4, S. 513-518
http://dx.doi.org/10.1017/S0963548311000174
Harant, Jochen
A lower bound on independence in terms of degrees. - In: Discrete applied mathematics. - [S.l.] : Elsevier, Bd. 159 (2011), 10, S. 966-970
http://dx.doi.org/10.1016/j.dam.2011.03.003
Kostochka, Alexandr V.; Stiebitz, Michael; Woodall, Douglas R.
Ohba's conjecture for graphs with independence number five. - In: Discrete mathematics. - Amsterdam [u.a.] : Elsevier, Bd. 311 (2011), 12, S. 996-1005
http://dx.doi.org/10.1016/j.disc.2011.02.026
Löwenstein, Christian; Pedersen, Anders Sune; Rautenbach, Dieter; Regen, Friedrich
Independence, odd girth, and average degree. - In: Journal of graph theory. - New York, NY [u.a.] : Wiley, ISSN 10970118, Bd. 67 (2011), 2, S. 96-111
http://dx.doi.org/10.1002/jgt.20518
Regen, Friedrich
On cycles and independence in graphs. - Online-Ressource (PDF-Datei: 84 S., 1166 KB)
Ilmenau : Techn. Univ., Diss., 2010

Das erste Fachkapitel ist der Berechnung von Kreispackungszahlen, d.h. der maximalen Größe kanten- bzw. eckendisjunkter Kreispackungen, gewidmet. Da diese Probleme bekanntermaßen sogar für subkubische Graphen schwer sind, behandelt der erste Abschnitt die Komplexität des Packens von Kreisen einer festen Länge l in Graphen mit Maximalgrad Delta. Dieses für l=3 von Caprara und Rizzi gelöste Problem wird hier auf alle größeren Kreislängen l verallgemeinert. Der zweite Abschnitt beschreibt die Struktur von Graphen, für die die Kreispackungszahlen einen vorgegebenen Abstand zur zyklomatischen Zahl haben. Die 2-zusammenhängenden Graphen mit dieser Eigenschaft können jeweils durch Anwendung einer einfachen Erweiterungsregel auf eine endliche Menge von Graphen erzeugt werden. Aus diesem Strukturergebnis wird ein fpt-Algorithmus abgeleitet. Das zweite Fachkapitel handelt von der Größenordnung der minimalen Anzahl von Kreislängen in einem Hamiltongraph mit q Sehnen. Eine Familie von Beispielen zeigt, dass diese Unterschranke höchstens die Wurzel von q+1 ist. Dem Hauptsatz dieses Kapitels zufolge ist die Zahl der Kreislängen eines beliebigen Hamiltongraphen mit q Sehnen mindestens die Wurzel von 4/7*q. Der Beweis beruht auf einem Lemma von Faudree et al., demzufolge der Graph, der aus einem Weg mit Endecken x und y und q gleichlangen Sehnen besteht, x-y-Wege von mindestens q/3 verschiedenen Längen enthält. Der erste Abschnitt enthält eine Korrektur des ursprünglich fehlerhaften Beweises und zusätzliche Schranken. Der zweite Abschnitt leitet daraus die Unterschranke für die Anzahl der Kreislängen ab. Das letzte Fachkapitel behandelt Unterschranken für den Unabhängigkeitsquotienten, d.h. den Quotienten aus Unabhängigkeitszahl und Ordnung eines Graphen, für Graphen gegebener Dichte. In der Einleitung werden bestmögliche Schranken für die Klasse aller Graphen sowie für große zusammenhängende Graphen aus bekannten Ergebnissen abgeleitet. Danach wird die Untersuchung auf durch das Verbot kleiner ungerader Kreise eingeschränkte Graphenklassen ausgeweitet. Das Hauptergebnis des ersten Abschnitts ist eine Verallgemeinerung eines Ergebnisses von Heckman und Thomas, das die bestmögliche Schranke für zusammenhängende dreiecksfreie Graphen mit Durchschnittsgrad bis zu 10/3 impliziert und die extremalen Graphen charakterisiert. Der Rest der ersten beiden Abschnitte enthält Vermutungen ähnlichen Typs für zusammenhängende dreiecksfreie Graphen mit Durchschnittsgrad im Intervall [10/3, 54/13] und für zusammenhängende Graphen mit ungerader Taillenweite 7 mit Durchschnittsgrad bis zu 14/5. Der letzte Abschnitt enthält analoge Beobachtungen zum Bipartitionsquotienten. Die Arbeit schließt mit Vermutungen zu Unterschranken und die zugehörigen Klassen extremaler Graphen für den Bipartitionsquotienten.


http://www.db-thueringen.de/servlets/DocumentServlet?id=18161
Harant, Jochen; Jendrol, Stanislav
Facial non-repetitive vertex colouring of some families of 2-connected plane graphs. - Ilmenau : Techn. Univ., Inst. für Mathematik. - Online-Ressource (PDF-Datei: 11 S., 177,7 KB). - (Preprint. - M11,04)
http://www.db-thueringen.de/servlets/DocumentServlet?id=17632
Harant, Jochen; Rautenbach, Dieter
Independence in connected graphs. - In: Discrete applied mathematics. - [S.l.] : Elsevier, Bd. 159 (2011), 1, S. 79-86
http://dx.doi.org/10.1016/j.dam.2010.08.029
Artmann, Sarah; Harant, Jochen
Random procedures for dominating sets in bipartite graphs. - In: Discussiones mathematicae / Graph theory. - Warsaw : De Gruyter Open, ISSN 20835892, Bd. 30 (2010), 2, S. 277-288
http://dx.doi.org/10.7151/dmgt.1494
Henning, Michael A.; Löwenstein, Christian; Rautenbach, Dieter
Partitioning a graph into a dominating set, a total dominating set, and something else. - In: Discussiones mathematicae / Graph theory. - Warsaw : De Gruyter Open, ISSN 20835892, Bd. 30 (2010), 4, S. 563-574
http://dx.doi.org/10.7151/dmgt.1514
Dourado, Mitre C.; Protti, Fábio; Rautenbach, Dieter; Szwarcfiter, Jayme L.
On the Hull number of triangle-free graphs. - In: SIAM journal on discrete mathematics. - Philadelphia, Pa : Soc, ISSN 10957146, Bd. 23 (2010), 4, S. 2163-2172
http://dx.doi.org/10.1137/090751797
Brandt, Stephan; Miškuf, Jozef; Rautenbach, Dieter; Regen, Friedrich; Ruzsa, Imre Z.
Edge-injective and edge-surjective vertex labellings. - In: SIAM journal on discrete mathematics. - Philadelphia, Pa : Soc, ISSN 10957146, Bd. 24 (2010), 2, S. 666-683
http://dx.doi.org/10.1137/080723065
Scheide, Diego; Stiebitz, Michael
Vizing's coloring algorithm and the fan number. - In: Journal of graph theory. - New York, NY [u.a.] : Wiley, ISSN 10970118, Bd. 65 (2010), 2, S. 115-138
http://dx.doi.org/10.1002/jgt.20469
Boßecker, Anett; Rautenbach, Dieter
Interpolating between bounds on the independence number. - In: Discrete mathematics. - Amsterdam [u.a.] : Elsevier, Bd. 310 (2010), 17/18, S. 2398-2403
http://dx.doi.org/10.1016/j.disc.2010.05.026
Brandt, Stephan
A note on generalized pentagons. - In: Discrete mathematics. - Amsterdam [u.a.] : Elsevier, Bd. 310 (2010), 20, S. 2766-2767
http://dx.doi.org/10.1016/j.disc.2010.04.017
Böhme, Thomas; Kostochka, Alexandr; Thomason, Andrew
Hadwiger numbers and over-dominating colourings. - In: Discrete mathematics. - Amsterdam [u.a.] : Elsevier, Bd. 310 (2010), 20, S. 2662-2665
http://dx.doi.org/10.1016/j.disc.2010.03.024
Löwenstein, Christian; Rautenbach, Dieter
Pairs of disjoint dominating sets and the minimum degree of graphs. - In: Graphs and combinatorics. - Tokyo : Springer-Verl. Tokyo, ISSN 14355914, Bd. 26 (2010), 3, S. 407-424
http://dx.doi.org/10.1007/s00373-010-0918-9
Löwenstein, Christian; Rautenbach, Dieter; Schiermeyer, Ingo
Cycle length parities and the chromatic number. - In: Journal of graph theory. - New York, NY [u.a.] : Wiley, ISSN 10970118, Bd. 64 (2010), 3, S. 210-218
http://dx.doi.org/10.1002/jgt.20450
Brandt, Stephan; Müttel, Janina; Rautenbach, Dieter; Regen, Friedrich
Minimum degree and density of binary sequences. - In: European journal of combinatorics. - London : Academic Press, Bd. 31 (2010), 7, S. 1936-1945
http://dx.doi.org/10.1016/j.ejc.2010.01.005
Henning, Michael A.; Löwenstein, Christian; Rautenbach, Dieter; Southey, Justin
Disjoint dominating and total dominating sets in graphs. - In: Discrete applied mathematics. - [S.l.] : Elsevier, Bd. 158 (2010), 15, S. 1615-1523
http://dx.doi.org/10.1016/j.dam.2010.06.004
Kostochka, Alexandr V.; Král', Daniel; Sereni, Jean-Sébastien; Stiebitz, Michael
Graphs with bounded tree-width and large odd-girth are almost bipartite. - In: Journal of combinatorial theory / B. - Orlando, Fla : Academic Press, Bd. 100 (2010), 6, S. 554-559
http://dx.doi.org/10.1016/j.jctb.2010.04.004
Girlich, Franz; Roßberg, Michael; Schäfer, Günter; Böhme, Thomas; Schreyer, Jens
Scrubbing the Vivaldi network coordinate system. - In: Crossing borders within the ABC : automation, biomedical engineering and computer science ; proceedings ; 55. IWK Internationales Wissenschaftliches Kolloquium ; 13 - 17 September 2010. - Ilmenau : Verl. ISLE / Internationales Wissenschaftliches Kolloquium. Technische Universität Ilmenau ; 55 (Ilmenau) : 2010.09.13-17., ISBN 978-3-938843-53-6, (2010), S. 754-760

http://www.db-thueringen.de/servlets/DocumentServlet?id=17361
Harant, Jochen
A lower bound on independence in terms of degrees. - Ilmenau : Techn. Univ., Inst. für Mathematik. - Online-Ressource (PDF-Datei: 6 S., 173,1 KB). - (Preprint. - M10,08)
http://www.db-thueringen.de/servlets/DocumentServlet?id=16418
Löwenstein, Christian
In the complement of a dominating set. - Online-Ressource (PDF-Datei: 101 S.,793 KB)
Ilmenau : Techn. Univ., Diss., 2010

Eine Menge von Ecken D eines Graphen G=(V,E) ist eine Dominanzmenge, falls jede Ecke aus V\D mindestens einen Nachbarn in D hat. Die disjunkte Dominazzahl eines Graphen G ist die minimale Kardinalität zweier disjunkter Dominanzmengen von G. Wir beweisen untere Schranken für die disjunkte Dominanzzahl für Graphen mit Minimalgrad 2, für Graphen mit großem Minimalgrad und für kubische Graphen.Eine Menge von Ecken T eines Graphen G=(V,E) ist eine totale Dominanzmenge, falls jede Ecke aus V mindestens einen Nachbarn in T hat. Wir charakterisieren Graphen mit Minimalgrad 2 ohne induzierten 5-Kreisen und Graphen mit Minimalgrad mindestens 3, die eine Dominanzmenge, eine totale Dominanzmenge und eine nichtleere Eckenmenge, die paarweise disjunkt sind, haben.Eine Menge von Ecken I eines Graphen G=(V,E) ist eine unabhängige Menge, falls alle Ecken aus I paarweise in G nicht benachbart sind. Wir geben eine konstruktive Charakterisierung für Bäume an, die eine maximale unabhänige Menge und eine dazu disjunkte minimale Dominanzmenge haben und wir zeigen, dass das zugehörige Entscheidungsproblem für allgemene Graphen NP-schwer ist. Zusätzlich zeigen wir mehrere strukturelle Ergebnisse und Komplexitätsergebnisse betreffend Paare disjunkter Mengen, die dominierend, unabhängig oder beides sind. Weiter beweisen wir untere Schranken für die maximale Kardinalität einer unabhängigen Menge von Graphen, die einen kleinen Durchschnittsgrad und keine kurzen Kreise ungerader Länge haben.Ein zusammenhängender Graph G hat spanning tree congestion höchstens s, falls G einen aufspannenden Baum T hat, so dass für jede Kante e von T der Kantenschnitt, der in G definiert ist durch die zwei Komponenten von T-e, höchstens s Kanten enthält. Wir beweisen, dass jeder zusammenhängneder Graph der Ordnung n spanning tree congestion höchstens n^(3/2) hat und wir zeigen, dass das zugehörige Entscheidungsproblem NP-schwer ist.


http://www.db-thueringen.de/servlets/DocumentServlet?id=16280
Brandstädt, Andreas; Le, Van Bang; Rautenbach, Dieter
Exact leaf powers. - In: Theoretical computer science : the journal of the EATCS. - Amsterdam [u.a.] : Elsevier, Bd. 411 (2010), 31/33, S. 2968-2977
http://dx.doi.org/10.1016/j.tcs.2010.04.027
Artmann, Sarah
Über die Dominanzzahl in Graphen unter Nutzung verschiedener Konzepte. - Online-Ressource (PDF-Datei: 81 S., 707 KB)
Ilmenau : Techn. Univ., Diss., 2010

Die Dominanzzahl in Graphen ist die minimale Mächtigkeit einer Knotenpunktmenge D, für die jeder Knoten entweder in D enthalten ist oder einen Nachbarn in D besitzt. Da das zugehörige Entscheidungsproblem NP-vollständig ist, versucht man obere Schranken für die Dominanzzahl in verschiedenen Graphenklassen zu finden und diese zu realisieren. Ein Ansatz, zu solchen Schranken zu kommen, ist die probabilistische Methode nach Alon und Spencer. Hierbei werden Knoten mit einer Wahrscheinlichkeit zwischen Null und Eins zu der Menge hinzugenommen und diese dann zu einer dominierenden Menge ergänzt. Mit Hilfe sogenannter Abstiegsverfahren kann man dann für die einzelnen Knoten zu den "realisierenden" Wahrscheinlichkeiten Null und Eins übergehen. Die dabei erzielten Verbesserungen werden bestimmt und so neue Schranken für reguläre und allgemeine Graphen gewonnen. Diese hängen jedoch von der Mächtigkeit einer Menge von Knoten (oder Schranken für diese) ab, die paarweise einen gewissen Abstand voneinander haben. Weiter wird ein verallgemeinerter Ansatz für die Bestimmung der Verbesserung von Schranken für die Dominanzzahl durch Abstiegsverfahren entwickelt. Der in diesem Zusammenhang beschriebene Algorithmus für allgemeine bzw. bipartite Graphen kann für viele multilineare Funktionen, die eine obere Schranke für die Dominanzzahl bilden, angewandt werden und liefert in jedem Fall neue, verbesserte Ergebnisse gegenüber der Ausgangsschranke. Durch die Verallgemeinerung der Methode von Alon und Spencer können zudem direkt bessere Schranken für die Dominanzzahl allgemeiner Graphen erreicht werden. Auf bipartiten Graphen, für die bisher nur wenige eigenständige Schranken bekannt sind, werden weitere Verbesserungen erzielt. Die Resultate werden numerisch ausgewertet und bekannten Schranken gegenüber gestellt.


http://www.db-thueringen.de/servlets/DocumentServlet?id=15940
Göring, Frank; Harant, Jochen
Hamiltonian cycles through prescribed edges of 4-connected maximal planar graphs. - In: Discrete mathematics. - Amsterdam [u.a.] : Elsevier, Bd. 310 (2010), 9, S. 1491-1494
http://dx.doi.org/10.1016/j.disc.2009.10.005
Harant, Jochen; Rautenbach, Dieter; Recht, Peter; Regen, Friedrich
Packing edge-disjoint cycles in graphs and the cyclomatic number. - In: Discrete mathematics. - Amsterdam [u.a.] : Elsevier, Bd. 310 (2010), 9, S. 1456-1462
http://dx.doi.org/10.1016/j.disc.2009.07.017
Harant, Jochen; Rautenbach, Dieter; Recht, Peter; Schiermeyer, Ingo; Sprengel, Eva-Maria
Packing disjoint cycles over vertex cuts. - In: Discrete mathematics. - Amsterdam [u.a.] : Elsevier, Bd. 310 (2010), 13/14, S. 1974-1978
http://dx.doi.org/10.1016/j.disc.2010.03.009
Draque Penso, Lucia; Rautenbach, Dieter; Szwarcfiter, Jayme Luiz
Cycles, paths, connectivity and diameter in distance graphs. - In: Graph theoretic concepts in computer science : 35th international workshop, WG 2009, Montpellier, France, June 24 - 26, 2009 ; revised papers. - Berlin [u.a.] : Springer / WG ; 35 (Montpellier) : 2009.06.24-26., ISBN 978-3-642-11409-0, (2010), S. 320-328

http://dx.doi.org/10.1007/978-3-642-11409-0
Dourado, Mitre C.; Protti, Fábio; Rautenbach, Dieter; Szwarcfiter, Jayme L.
Some remarks on the geodetic number of a graph. - In: Discrete mathematics. - Amsterdam [u.a.] : Elsevier, Bd. 310 (2010), 4, S. 832-837
http://dx.doi.org/10.1016/j.disc.2009.09.018
Scheide, Diego
Graph edge colouring: Tashkinov trees and Goldberg's conjecture. - In: Journal of combinatorial theory / B. - Orlando, Fla : Academic Press, Bd. 100 (2010), 1, S. 68-96
http://dx.doi.org/10.1016/j.jctb.2009.04.001
Brandt, Stephan; Budajová, Kristína; Rautenbach, Dieter; Stiebitz, Michael
Edge colouring by total labellings. - In: Discrete mathematics. - Amsterdam [u.a.] : Elsevier, Bd. 310 (2010), 2, S. 199-205
http://dx.doi.org/10.1016/j.disc.2008.09.013
Brandt, Stephan
Triangle-free graphs whose independence number equals the degree. - In: Discrete mathematics. - Amsterdam [u.a.] : Elsevier, Bd. 310 (2010), 3, S. 662-669
http://dx.doi.org/10.1016/j.disc.2009.05.021
Henning, Michael A.; Löwenstein, Christian; Rautenbach, Dieter
An independent dominating set in the complement of a minimum dominating set of a tree. - In: Applied mathematics letters. - Amsterdam [u.a.] : Elsevier Sci, Bd. 23 (2010), 1, S. 79-81
http://dx.doi.org/10.1016/j.aml.2009.08.008
Král', Daniel; Sereni, Jean-Sébastien; Stiebitz, Michael
A new lower bound on the number of perfect matchings in cubic graphs. - In: SIAM journal on discrete mathematics. - Philadelphia, Pa : Soc, ISSN 10957146, Bd. 23 (2009), 3, S. 1465-1483
http://dx.doi.org/10.1137/080723843
Artmann, Sarah; Pruchnewski, Anja
Constructing a dominating set for bipartite graphs in several rounds. - Ilmenau : Techn. Univ., Inst. für Mathematik. - Online-Ressource (PDF-Datei: 7 S., 167,9 KB). - (Preprint. - M09,37)
http://www.db-thueringen.de/servlets/DocumentServlet?id=14792
Scheide, Diego
Edge colourings of multigraphs. - Online-Ressource (PDF-Datei: 112 S., 2666 KB)
Ilmenau : Techn. Univ., Diss., 2009

Das Kantenfärbungsproblem besteht darin, den chromatischen Index eines (Multi-)Graphen G zu ermitteln, d.h. die minimale Anzahl an Farben, mit denen man die Kanten von G so färben kann, dass keine zwei benachbarten Kanten die gleiche Farbe erhalten. Kantenfärbungsprobleme treten in verschiedenen Scheduling-Anwendungen auf, typischerweise in Verbindung mit Task-Processing oder Netzwerk-Kommunikation. Da das Kantenfärbungsproblem NP-schwer ist, sind gute Approximationsalgorithmen gefordert. In dieser Dissertation werden verschiedene Färbungstechniken erweitert und neue Färbungsalgorithmen entworfen. Ausgehend von einem klassischen Resultat von Vizing, wird ein neuer Graphenparameter - die Fächerzahl - vorgestellt. Dies führt zu einem Färbungsalgorithmus, der durch eine spezielle Kantensortierung Vizings Fächer in bestmöglicher Weise nutzen kann. Eines der größten bisher ungelösten Probleme auf dem Gebiet der Kantenfärbungen ist Goldbergs Vermutung. Goldberg (und unabhängig davon auch Andersen und Seymour) vermutete eine obere Schranke für den chromatischen Index chi', die vom Maximalgrad Delta und einer maximalen Dichte w abhängt, und zwar chi'<=max{Delta+1,w}. Da Delta und w beides untere Schranken für chi' sind, hat Goldbergs Schranke somit eine absolute Abweichung von höchstens 1 vom Optimum. In dieser Dissertation werden einige neue obere Schranken für chi' entwickelt, die die Lücke zwischen den bereits bekannten Schranken und Goldbergs vermuteter Schranke verkleinert. Die beiden wichtigsten neuen Schranken sind max{Delta+1+(Delta-2)/14,w} und max{Delta+sqrt((Delta-1)/2),w}. Die Laufzeiten der zugehörigen Färbungsalgorithmen sind polynomiell beschränkt bzgl. der Eckenzahl und der Kantenzahl des zu färbenden Graphen. Da aber ein Graph einfach durch Angabe der Ecken und Kantenvielfachheiten beschrieben werden kann, sind die genannten Algorithmen somit keine echten Polynomialzeitalgorithmen. Im letzten Kapitel der Dissertation wird allerdings gezeigt, wie sich durch alternative Datenstrukturen und ein ivide-and-Conquer-Verfahren diese Algorithmen auch als Polynomialzeitalgorithmen implementieren lassen.


http://www.db-thueringen.de/servlets/DocumentServlet?id=13785
Rautenbach, Dieter; Schäfer, Philipp Matthias
Null-homotopic graphs and triangle-completions of spanning trees. - Ilmenau : Techn. Univ., Inst. für Mathematik. - Online-Ressource (PDF-Datei: 4 S., 144,3 KB). - (Preprint. - M09,35)
http://www.db-thueringen.de/servlets/DocumentServlet?id=14440
Rautenbach, Dieter; Schäfer, Philipp Matthias
Finite sholander trees, trees, and their betweennesses. - Ilmenau : Techn. Univ., Inst. für Mathematik. - Online-Ressource (PDF-Datei: 8 S., 204,6 KB). - (Preprint. - M09,34)
http://www.db-thueringen.de/servlets/DocumentServlet?id=14439
Rautenbach, Dieter; Schäfer, Philipp Matthias
Strict betweennesses induced by posets as well as by graphs. - Ilmenau : Techn. Univ., Inst. für Mathematik. - Online-Ressource (PDF-Datei: 8 S., 185,9 KB). - (Preprint. - M09,33)
http://www.db-thueringen.de/servlets/DocumentServlet?id=14426
Löwenstein, Christian; Pedersen, Anders Sune; Rautenbach, Dieter; Regen, Friedrich
Independence, odd girth, and average degree. - Ilmenau : Techn. Univ., Inst. für Mathematik. - Online-Ressource (PDF-Datei: 15 S., 232,7 KB). - (Preprint. - M09,32)
http://www.db-thueringen.de/servlets/DocumentServlet?id=14425
Harant, Jochen; Rautenbach, Dieter
Independence in connected graphs. - Ilmenau : Techn. Univ., Inst. für Mathematik. - Online-Ressource (PDF-Datei: 10 S., 193,9 KB). - (Preprint. - M09,31)
http://www.db-thueringen.de/servlets/DocumentServlet?id=14424
Henning, Michael A.; Löwenstein, Christian; Rautenbach, Dieter
Remarks about disjoint dominating sets. - In: Discrete mathematics. - Amsterdam [u.a.] : Elsevier, Bd. 309 (2009), 23/24, S. 6451-6458
http://dx.doi.org/10.1016/j.disc.2009.06.017
Bartoschek, Christoph; Held, Stephan; Rautenbach, Dieter; Vygen, Jens
Fast buffering for optimizing worst slack and resource consumption in repeater trees. - In: Proceedings of the 2009 ACM International Symposium on Physical Design / ACM International Symposium on Physical Design (San Diego, Calif.) : 2009.03.29-04.01. - New York, NY : ACM, ISBN 978-1-60558-449-2, (2009), S. 43-50

Peyer, Sven; Rautenbach, Dieter; Vygen, Jens
A generalization of Dijkstra's shortest path algorithm with applications to VLSI routing. - In: Journal of discrete algorithms : JDA. - Amsterdam [u.a.] : Elsevier, Bd. 7 (2009), 4, S. 377-390
http://dx.doi.org/10.1016/j.jda.2007.08.003
Böhme, Thomas; Schreyer, Jens
A game theoretic approach to graph problems. - In: / I2CS ; 9 (Jena) : 2009.06.15-17., ISBN 978-3-88579-242-0, (2009), S. 149-156

Maßberg, Jens; Rautenbach, Dieter
Binary trees with choosable edge lengths. - In: Information processing letters : devoted to the rapid publication of short contributions to information processing. - Amsterdam [u.a.] : Elsevier, Bd. 109 (2009), 18, S. 1087-1092
http://dx.doi.org/10.1016/j.ipl.2009.07.002
Boßecker, Anett; Rautenbach, Dieter
Interpolating between bounds on the independence number. - Ilmenau : Techn. Univ., Inst. für Mathematik. - Online-Ressource (PDF-Datei: 9 S., 169,8 KB). - (Preprint. - M09,26)
http://www.db-thueringen.de/servlets/DocumentServlet?id=13756
Henning, Michael A.; Löwenstein, Christian; Rautenbach, Dieter
Partitioning a graph into a dominating set, a total dominating set, and something else. - Ilmenau : Techn. Univ., Inst. für Mathematik. - Online-Ressource (PDF-Datei: 11 S., 331,5 KB). - (Preprint. - M09,25)
http://www.db-thueringen.de/servlets/DocumentServlet?id=13714
Henning, Michael A.; Löwenstein, Christian; Rautenbach, Dieter
An independent dominating set in the complement of a minimum dominating set of a tree. - Ilmenau : Techn. Univ., Inst. für Mathematik. - Online-Ressource (PDF-Datei: 4 S., 142,9 KB). - (Preprint. - M09,24)
http://www.db-thueringen.de/servlets/DocumentServlet?id=13707
Bartoschek, Christoph; Held, Stephan; Maßberg, Jens; Rautenbach, Dieter; Vygen, Jens
The repeater tree construction problem. - Ilmenau : Techn. Univ., Inst. für Mathematik. - Online-Ressource (PDF-Datei: 9 S., 193,8 KB). - (Preprint. - M09,23)
http://www.db-thueringen.de/servlets/DocumentServlet?id=13706
Brandt, Stephan; Müttel, Janina; Rautenbach, Dieter; Regen, Friedrich
Minimum degree and density of binary sequences. - Ilmenau : Techn. Univ., Inst. für Mathematik. - Online-Ressource (PDF-Datei: 16 S., 224,4 KB). - (Preprint. - M09,22)
http://www.db-thueringen.de/servlets/DocumentServlet?id=13705
Mörig, Marc; Rautenbach, Dieter; Smid, Michiel; Tusch, Jan
An [Omega] (n log n) lower bound for computing the sum of even-ranked elements. - In: Information processing letters : devoted to the rapid publication of short contributions to information processing. - Amsterdam [u.a.] : Elsevier, Bd. 109 (2009), 16, S. 955-956
http://dx.doi.org/10.1016/j.ipl.2009.05.004
Brandt, Stephan; Ribe-Baumann, Elizabeth
Graphs of odd girth 7 with large degree. - In: Electronic notes in discrete mathematics. - Amsterdam : Elsevier Science, ISSN 15710653, Bd. 34 (2009), S. 89-93
http://dx.doi.org/10.1016/j.endm.2009.07.015
Harant, Jochen; Senitsch, Stefan
A generalization of Tutte's theorem on Hamiltonian cycles in planar graphs. - In: Discrete mathematics. - Amsterdam [u.a.] : Elsevier, Bd. 309 (2009), 15, S. 4949-4951
http://dx.doi.org/10.1016/j.disc.2008.04.038
Stiebitz, Michael; Tuza, Zsolt; Voigt, Margit
On list critical graphs. - In: Discrete mathematics. - Amsterdam [u.a.] : Elsevier, Bd. 309 (2009), 15, S. 4931-4941
http://dx.doi.org/10.1016/j.disc.2008.05.021
Scheide, Diego; Stiebitz, Michael
On Vizing's bound for the chromatic index of a multigraph. - In: Discrete mathematics. - Amsterdam [u.a.] : Elsevier, Bd. 309 (2009), 15, S. 4920-4925
http://dx.doi.org/10.1016/j.disc.2008.04.046
Pruchnewski, Anja; Voigt, Margit
Precoloring extension for K4-minor-free graphs. - In: Journal of graph theory. - New York, NY [u.a.] : Wiley, ISSN 10970118, Bd. 60 (2009), 4, S. 284-294
http://dx.doi.org/10.1002/jgt.20358
Böhme, Thomas; Göring, Frank; Tuza, Zsolt; Unger, Herwig
Learning of winning strategies for terminal games with linear-size memory. - In: International journal of game theory. - Berlin : Springer, ISSN 14321270, Bd. 38 (2009), 2, S. 155-168
http://dx.doi.org/10.1007/s00182-008-0142-5
Henn, Mark-Alexander; Mehl, Christian; Trunk, Carsten
Hyponormal and strongly hyponormal matrices in inner product spaces. - Ilmenau : Techn. Univ., Inst. für Mathematik. - Online-Ressource (PDF-Datei: 30 S., 277,6 KB). - (Preprint. - M09,06)
http://www.db-thueringen.de/servlets/DocumentServlet?id=12959
Balogh, József; Kostochka, Alexandr V.; Prince, Noah; Stiebitz, Michael
The Erdös-Lovász Tihany conjecture for quasi-line graphs. - In: Discrete mathematics. - Amsterdam [u.a.] : Elsevier, Bd. 309 (2009), 12, S. 3985-3991
http://dx.doi.org/10.1016/j.disc.2008.11.016
Brandstädt, Andreas; Le, Van Bang; Rautenbach, Dieter
A forbidden induced subgraph characterization of distance-hereditary 5-leaf powers. - In: Discrete mathematics. - Amsterdam [u.a.] : Elsevier, Bd. 309 (2009), 12, S. 3843-3852
http://dx.doi.org/10.1016/j.disc.2008.10.025
Brandt, Stephan; Miskuf, Jozef; Rautenbach, Dieter
Edge irregular total labellings for graphs of linear size. - In: Discrete mathematics. - Amsterdam [u.a.] : Elsevier, Bd. 309 (2009), 12, S. 3786-3792
http://dx.doi.org/10.1016/j.disc.2008.10.009
Rautenbach, Dieter; Regen, Friedrich
On packing shortest cycles in graphs. - In: Information processing letters : devoted to the rapid publication of short contributions to information processing. - Amsterdam [u.a.] : Elsevier, Bd. 109 (2009), 14, S. 816-821
http://dx.doi.org/10.1016/j.ipl.2009.04.001
Harant, Jochen; Rautenbach, Dieter; Recht, Peter; Schiermeyer, Ingo; Schulte-Loh, Eva-Maria
Packing disjoint cycles over vertex cuts. - Ilmenau : Techn. Univ., Inst. für Mathematik. - Online-Ressource (PDF-Datei: 9 S., 166,5 KB). - (Preprint. - M09,17)
http://www.db-thueringen.de/servlets/DocumentServlet?id=12995
Mörig, Marc; Rautenbach, Dieter; Smid, Michiel; Tusch, Jan
An [Omega] (n log n) lower bound for computing the sum of even-ranked elements. - Ilmenau : Techn. Univ., Inst. für Mathematik. - Online-Ressource (PDF-Datei: 3 S., 136,5 KB). - (Preprint. - M09,16)
http://www.db-thueringen.de/servlets/DocumentServlet?id=12993
Dourado, Mitre C.; Protti, Fábio; Rautenbach, Dieter; Szwarcfiter, Jayme Luiz
Some remarks on the geodetic number of a graph. - Ilmenau : Techn. Univ., Inst. für Mathematik. - Online-Ressource (PDF-Datei: 10 S., 184,5 KB). - (Preprint. - M09,15)
http://www.db-thueringen.de/servlets/DocumentServlet?id=12992
Dourado, Mitre C.; Protti, Fábio; Rautenbach, Dieter; Szwarcfiter, Jayme Luiz
On the convexity number of graphs. - Ilmenau : Techn. Univ., Inst. für Mathematik. - Online-Ressource (PDF-Datei: 14 S., 340,1 KB). - (Preprint. - M09,14)
http://www.db-thueringen.de/servlets/DocumentServlet?id=12991
Dourado, Mitre C.; Protti, Fábio; Rautenbach, Dieter; Szwarcfiter, Jayme Luiz
On the hull number of triangle-free graphs. - Ilmenau : Techn. Univ., Inst. für Mathematik. - Online-Ressource (PDF-Datei: 12 S., 223,7 KB). - (Preprint. - M09,13)
http://www.db-thueringen.de/servlets/DocumentServlet?id=12990
Löwenstein, Christian; Rautenbach, Dieter; Regen, Friedrich
On spanning tree congestion. - In: Discrete mathematics. - Amsterdam [u.a.] : Elsevier, Bd. 309 (2009), 13, S. 4653-4655
http://dx.doi.org/10.1016/j.disc.2009.01.012
Böhme, Thomas; Kawarabayashi, Ken-ichi; Maharry, John; Mohar, Bojan
Linear connectivity forces large complete bipartite minors. - In: Journal of combinatorial theory / B. - Orlando, Fla : Academic Press, Bd. 99 (2009), 3, S. 557-582
http://dx.doi.org/10.1016/j.jctb.2008.07.006
Draque Penso, Lucia; Rautenbach, Dieter; Szwarcfiter, Jayme Luiz
Connectivity and diameter in distance graphs. - Ilmenau : Techn. Univ., Inst. für Mathematik. - Online-Ressource (PDF-Datei: 17 S., 177 KB). - (Preprint. - M09,12)
http://www.db-thueringen.de/servlets/DocumentServlet?id=12976
Draque Penso, Lucia; Rautenbach, Dieter; Szwarcfiter, Jayme Luiz
Long cycles and paths in distance graphs. - Ilmenau : Techn. Univ., Inst. für Mathematik. - Online-Ressource (PDF-Datei: 12 S., 242 KB). - (Preprint. - M09,11)
http://www.db-thueringen.de/servlets/DocumentServlet?id=12973
Lin, Min Chih; Rautenbach, Dieter; Soulignac, Francisco Juan; Szwarcfiter, Jayme Luiz
Powers of cycles, powers of paths, and distance graphs. - Ilmenau : Techn. Univ., Inst. für Mathematik. - Online-Ressource (PDF-Datei: 13 S., 183,6 KB). - (Preprint. - M09,10)
http://www.db-thueringen.de/servlets/DocumentServlet?id=12969
Löwenstein, Christian; Rautenbach, Dieter
Pairs of disjoint dominating sets and the minimum degree of graphs. - Ilmenau : Techn. Univ., Inst. für Mathematik. - Online-Ressource (PDF-Datei: 19 S., 193,5 KB). - (Preprint. - M09,09)
http://www.db-thueringen.de/servlets/DocumentServlet?id=12978
Rautenbach, Dieter; Regen, Friedrich
Graphs with many vertex-disjoint cycles. - Ilmenau : Techn. Univ., Inst. für Mathematik. - Online-Ressource (PDF-Datei: 10 S., 156,4 KB). - (Preprint. - M09,08)
http://www.db-thueringen.de/servlets/DocumentServlet?id=12963
Rautenbach, Dieter; Regen, Friedrich
On packing shortest cycles in graphs. - Ilmenau : Techn. Univ., Inst. für Mathematik. - Online-Ressource (PDF-Datei: 9 S., 183,6 KB). - (Preprint. - M09,07)
http://www.db-thueringen.de/servlets/DocumentServlet?id=12960
Rautenbach, Dieter; Volkmann, Lutz
On the existence of edge cuts leaving several large components. - In: Discrete mathematics. - Amsterdam [u.a.] : Elsevier, Bd. 309 (2009), 6, S. 1703-1707
http://dx.doi.org/10.1016/j.disc.2008.02.014
Böhme, Thomas; Kostochka, Alexandr
Many disjoint dense subgraphs versus large k-connected subgraphs in large graphs with given edge density. - In: Discrete mathematics. - Amsterdam [u.a.] : Elsevier, Bd. 309 (2009), 4, S. 997-1000
http://dx.doi.org/10.1016/j.disc.2008.01.010
Meer, Klaus; Rautenbach, Dieter
On the OBDD size for graphs of bounded tree- and clique-width. - In: Discrete mathematics. - Amsterdam [u.a.] : Elsevier, Bd. 309 (2009), 4, S. 843-851
http://dx.doi.org/10.1016/j.disc.2008.01.022
Harant, Jochen; Rautenbach, Dieter
Domination in bipartite graphs. - In: Discrete mathematics. - Amsterdam [u.a.] : Elsevier, Bd. 309 (2009), 1, S. 113-122
http://dx.doi.org/10.1016/j.disc.2007.12.051
Fabrici, Igor; Harant, Jochen; Jendrol&softcy;, Stanislav
Paths of low weight in planar graphs. - In: Discussiones mathematicae / Graph theory. - Warsaw : De Gruyter Open, ISSN 20835892, Bd. 28 (2008), 1, S. 121-135
http://dx.doi.org/10.7151/dmgt.1396
Böhme, Thomas; Gerlach, Tobias; Stiebitz, Michael
Ordered and linked chordal graphs. - In: Discussiones mathematicae / Graph theory. - Warsaw : De Gruyter Open, ISSN 20835892, Bd. 28 (2008), 2, S. 367-373
http://dx.doi.org/10.7151/dmgt.1412
Harant, Jochen; Jendrol', Stanislav; Walther, Hansjoachim
On long cycles through four prescribed vertices of a polyhedral graph. - In: Discussiones mathematicae / Graph theory. - Warsaw : De Gruyter Open, ISSN 20835892, Bd. 28 (2008), 3, S. 441-451
http://dx.doi.org/10.7151/dmgt.1418
Král, Daniel; Sereni, Jean-Sébastien; Stiebitz, Michael
A new lower bound on the number of perfect matchings in cubic graphs. - Praha : Charles Univ.. - 27 S.. - (KAM-DIMATIA series. - 867)
Rautenbach, Dieter; Reed, Bruce
Domination in cubic graphs of large girth. - In: Computational geometry and graph theory : international conference, KyotoCGGT 2007, Kyoto, Japan, June 11 - 15, 2007 ; revised selected papers. - Berlin : Springer / KyotoCGGT (Kyoto) : 2007.06.11-15., ISBN 978-3-540-89550-3, (2008), S. 186-190

http://dx.doi.org/10.1007/978-3-540-89550-3_20
Löwenstein, Christian; Rautenbach, Dieter
Domination in graphs of minimum degree at least two and large girth. - In: Graphs and combinatorics. - Tokyo : Springer-Verl. Tokyo, ISSN 14355914, Bd. 24 (2008), 1, S. 37-46
http://dx.doi.org/10.1007/s00373-007-0770-8
Rautenbach, Dieter; Szegedy, Christian; Werber, Jürgen
On the cost of optimal alphabetic code trees with unequal letter costs. - In: European journal of combinatorics. - London : Academic Press, Bd. 29 (2008), 2, S. 386-394
http://dx.doi.org/10.1016/j.ejc.2007.02.014
Rautenbach, Dieter
A note on domination, girth and minimum degree. - In: Discrete mathematics. - Amsterdam [u.a.] : Elsevier, Bd. 308 (2008), 11, S. 2325-2329
http://dx.doi.org/10.1016/j.disc.2006.09.055
Brandt, Stephan; Miskuf, Jozef; Rautenbach, Dieter
On a conjecture about edge irregular total labelings. - In: Journal of graph theory. - New York, NY [u.a.] : Wiley, ISSN 10970118, Bd. 57 (2008), 4, S. 333-343
http://dx.doi.org/10.1002/jgt.20287
Rautenbach, Dieter
A conjecture of Borodin and a coloring of Grünbaum. - In: Journal of graph theory. - New York, NY [u.a.] : Wiley, ISSN 10970118, Bd. 58 (2008), 2, S. 139-147
http://dx.doi.org/10.1002/jgt.20299
Diudea, Mircea V.; Cigher, Simona; John, Peter E.
Omega and related counting polynomials. - In: MatchMatch : communications in mathematical and in computer chemistry. - Kragujevac : [Univ. [u.a.] : communications in mathematical and in computer chemistry. - Kragujevac : [Univ. [u.a.], ISSN 03406253, Bd. 60 (2008), 1, S. 237-250
Kostochka, Alexandr V.; Stiebitz, Michael
Partitions and edge colourings of multigraphs. - In: The journal of combinatorics : a print version of the electronic journal of combinatorics. - Cambridge, Mass. : Internat. Press : ., ISSN 10971440, Bd. 15Bd. 15.2008, 1, N25, insges. 4 S.
Harant, Jochen; Henning, Michael A.
A realization algorithm for double domination in graphs. - In: Utilitas mathematicaUtilitas mathematica : an international journal of discrete and combinatorial mathematics. - Durban : Department of Mathematics and Applied Mathematics, Univ. of KwaZulu-Natal : an international journal of discrete and combinatorial mathematics. - Durban : Department of Mathematics and Applied Mathematics, Univ. of KwaZulu-Natal, ISSN 03153681, Bd. 76 (2008), S. 11-24
Hladký, Jan; Kráal, Daniel; Sereni, Jean-Sébastien; Stiebitz, Michael
List colorings with measurable sets. - In: Journal of graph theory. - New York, NY [u.a.] : Wiley, ISSN 10970118, Bd. 59 (2008), 3, S. 229-238
http://dx.doi.org/10.1002/jgt.20335
Harant, Jochen; Henning, Michael A.; Rautenbach, Dieter; Schiermeyer, Ingo
The independence number in graphs of maximum degree three. - In: Discrete mathematics. - Amsterdam [u.a.] : Elsevier, Bd. 308 (2008), 23, S. 5829-5833
http://dx.doi.org/10.1016/j.disc.2007.10.029
Rautenbach, Dieter; Volkmann, Lutz
Some remarks on [lambda]p,q-connectedness. - In: Discrete mathematics. - Amsterdam [u.a.] : Elsevier, Bd. 308 (2008), 23, S. 5562-5569
http://dx.doi.org/10.1016/j.disc.2007.10.008
Rautenbach, Dieter; Volkmann, Lutz
Cyclic sums, network sharing and restricted edge cuts in graphs with long cycles. - In: Networks : an international journal. - New York, NY : Wiley-Interscience, ISSN 10970037, Bd. 52 (2008), 4, S. 252-255
http://dx.doi.org/10.1002/net.20243
Rautenbach, Dieter; Szegedy, Christian
A class of problems for which cyclic relaxation converges linearly. - In: Computational optimization and applications : an international journal. - New York, NY [u.a.] : Springer Science + Business Media B.V, ISSN 15732894, Bd. 41 (2008), 1, S. 53-60
http://dx.doi.org/10.1007/s10589-007-9094-0
Dahme, Franz; Rautenbach, Dieter; Volkmann, Lutz
[alpha]-Domination perfect trees. - In: Discrete mathematics. - Amsterdam [u.a.] : Elsevier, Bd. 308 (2008), 15, S. 3187-3198
http://dx.doi.org/doi:10.1016/j.disc.2007.06.043
Harant, Jochen; Rautenbach, Dieter; Regen, Friedrich; Recht, Peter
Packing edge-disjoint cycles in graphs and the cyclomatic number. - Ilmenau : Techn. Univ., Inst. für Mathematik. - Online-Ressource (PDF-Datei: 11 S., 183,1 KB). - (Preprint. - M08,25)
http://www.db-thueringen.de/servlets/DocumentServlet?id=11839
Löwenstein, Christian; Rautenbach, Dieter
Pairs of disjoint dominating sets and the minimum degree of graphs. - Ilmenau : Techn. Univ., Inst. für Mathematik. - Online-Ressource (PDF-Datei: 19 S., 193,5 KB). - (Preprint. - M08,26)
http://www.db-thueringen.de/servlets/DocumentServlet?id=11841
Löwenstein, Christian; Rautenbach, Dieter; Schiermeyer, Ingo
Cycle length parities and the chromatic number. - Ilmenau : Techn. Univ., Inst. für Mathematik. - Online-Ressource (PDF-Datei: 8 S., 199,4 KB). - (Preprint. - M08,27)
http://www.db-thueringen.de/servlets/DocumentServlet?id=11842
Löwenstein, Christian; Rautenbach, Dieter; Regen, Friedrich
On spanning tree congestion. - Ilmenau : Techn. Univ., Inst. für Mathematik. - 4 S. = 129,3 KB, Text. - (Preprint. - M08,18)
http://www.db-thueringen.de/servlets/DocumentServlet?id=10904
Brandt, Stephan; Miškuf, Jozef; Rautenbach, Dieter; Regen, Friedrich
Edge-injective and edge-surjective vertex labellings. - Ilmenau : Techn. Univ., Inst. für Mathematik. - 20 S. = 224,8 KB, Text. - (Preprint. - M08,17)
http://www.db-thueringen.de/servlets/DocumentServlet?id=10902
Löwenstein, Christian; Rautenbach, Dieter
Cohabitation of independent sets and dominating sets in trees. - Ilmenau : Techn. Univ., Inst. für Mathematik. - 9 S. = 146,3 KB, Text. - (Preprint. - M08,11)
http://www.db-thueringen.de/servlets/DocumentServlet?id=10404
Artmann, Sarah; Göring, Frank; Harant, Jochen; Rautenbach, Dieter; Schiermeyer, Ingo
Random procedures for dominating sets in graphs. - Ilmenau : Techn. Univ., Inst. für Mathematik. - 14 S. = 209,1 KB, Text. - (Preprint. - M08,10)
http://www.db-thueringen.de/servlets/DocumentServlet?id=10403
Henning, Michael A.; Löwenstein, Christian; Rautenbach, Dieter
Remarks about disjoint dominating sets. - Ilmenau : Techn. Univ., Inst. für Mathematik. - 13 S. = 203,8 KB, Text. - (Preprint. - M08,09)
http://www.db-thueringen.de/servlets/DocumentServlet?id=10402
Scheide, Diego
Graph edge coloring: Tashkinov trees and Goldberg's conjecture. - Ilmenau : Techn. Univ., Inst. für Mathematik. - 40 S. = 342,2 KB, Text. - (Preprint. - M08,07)
http://www.db-thueringen.de/servlets/DocumentServlet?id=10382
Löwenstein, Christian; Rautenbach, Dieter; Regen, Friedrich
Chiraptophobic cockroaches evading a torch light. - Ilmenau : Techn. Univ., Inst. für Mathematik. - 10 S. = 223 KB, Text. - (Preprint. - M08,02)
http://www.db-thueringen.de/servlets/DocumentServlet?id=9917
John, Peter E.; Khadikar, Padmakar V.; Singh, Jyoti
A method of computing the PI index of benzenoid hydrocarbons using orthogonal cuts. - In: Journal of mathematical chemistry. - Dordrecht [u.a.] : Springer Science + Business Media B.V, ISSN 15728897, Bd. 42 (2007), 1, S. 37-45
http://dx.doi.org/10.1007/s10910-006-9100-2
Rautenbach, Dieter
Dominating and large induced trees in regular graphs. - In: Discrete mathematics. - Amsterdam [u.a.] : Elsevier, Bd. 307 (2007), 24, S. 3177-3186
http://dx.doi.org/10.1016/j.disc.2007.03.043
Harant, Jochen; Jendrol, Stanislav
On the existence of specific stars in planar graphs. - In: Graphs and combinatorics. - Tokyo : Springer-Verl. Tokyo, ISSN 14355914, Bd. 23 (2007), 5, S. 529-543
http://dx.doi.org/10.1007/s00373-007-0747-7
John, Peter E.; Vizitiu, Aniela E.; Cigher, Simona; Diudea, Mircea V.
CI index in tubular nanostructures. - In: MatchMatch : communications in mathematical and in computer chemistry. - Kragujevac : [Univ. [u.a.] : communications in mathematical and in computer chemistry. - Kragujevac : [Univ. [u.a.], ISSN 03406253, Bd. 57 (2007), 2, S. 479-484
Werber, Jürgen; Rautenbach, Dieter; Szegedy, Christian
Timing optimization by restructuring long combinatorial paths. - In: IEEE/ACM International Conference on Computer-Aided Design, 2007 : ICCAD 2007 ; 4 - 8 Nov. 2007, Double Tree Hotel, San Jose, CA ; digest of technical papers. - Piscataway, NJ : IEEE Service Center / IEEE/ACM International Conference on Computer-Aided Design ; 25 (San Jose, Calif.) : 2007.11.04-08., ISBN 978-1-4244-1381-2, (2007), S. 536-543

http://dx.doi.org/10.1109/ICCAD.2007.4397320
Pruchnewski, Anja; Voigt, Margit
Precoloring extension for K4-minor-free graphs. - Ilmenau : Techn. Univ., Inst. für Mathematik. - 13 S. = 185,3 KB, Text. - (Preprint. - M07,26)
http://www.db-thueringen.de/servlets/DocumentServlet?id=9798
Lozin, Vadim; Rautenbach, Dieter
The relative clique-width of a graph. - In: Journal of combinatorial theory / B. - Orlando, Fla : Academic Press, Bd. 97 (2007), 5, S. 846-858
http://dx.doi.org/10.1016/j.jctb.2007.04.001
Rautenbach, Dieter
Regular weighted graphs without positive cuts. - In: Ars combinatoriaArs combinatoria. - Winnipeg, Manitoba : Charles Babbage Research Centre : . - Winnipeg, Manitoba, ISSN 03817032, Bd. 84 (2007), 3, S. 13-22
Korte, Bernhard; Rautenbach, Dieter; Vygen, Jens
BonnTools : mathematical innovation for layout and timing closure of systems on a chip. - In: Proceedings of the IEEE. - New York, NY [u.a.] : Inst, ISSN 00189219, Bd. 95 (2007), 3, S. 555-572
http://dx.doi.org/10.1109/JPROC.2006.889373
Harant, Jochen; Henning, Michael A.; Rautenbach, Dieter; Schiermeyer, Ingo
The independence number in graphs of maximum degree three. - Ilmenau : Techn. Univ., Inst. für Mathematik. - 7 S. = 130,9 KB, Text. - (Preprint. - M07,15)
http://www.db-thueringen.de/servlets/DocumentServlet?id=9407
Göring, Frank; Harant, Jochen; Rautenbach, Dieter; Schiermeyer, Ingo
Locally dense independent sets in regular graphs of large girth. - Ilmenau : Techn. Univ., Inst. für Mathematik. - 21 S. = 219,4 KB, Text. - (Preprint. - M07,14)
http://www.db-thueringen.de/servlets/DocumentServlet?id=9401
Brandt, Stephan; Miskuf, Jozef; Rautenbach, Dieter
Edge irregular total labellings for graphs of linear size. - Ilmenau : Techn. Univ., Inst. für Mathematik. - 10 S. = 163,3 KB, Text. - (Preprint. - M07,12)
http://www.db-thueringen.de/servlets/DocumentServlet?id=9399
Rautenbach, Dieter; Volkmann, Lutz
Some remarks on [lambda]p,q-connectedness. - Ilmenau : Techn. Univ., Inst. für Mathematik. - 13 S. = 203,3 KB, Text. - (Preprint. - M07,11)
http://www.db-thueringen.de/servlets/DocumentServlet?id=9398
Rautenbach, Dieter; Volkmann, Lutz
On the existence of edge cuts leaving several large components. - Ilmenau : Techn. Univ., Inst. für Mathematik. - 8 S. = 171,8 KB, Text. - (Preprint. - M07,10)
http://www.db-thueringen.de/servlets/DocumentServlet?id=9397
Löwenstein, Christian; Rautenbach, Dieter
Domination in graphs of minimum degree at least two and large girth. - Ilmenau : Techn. Univ., Inst. für Mathematik. - 10 S. = 164,4 KB, Text. - (Preprint. - M07,09)
http://www.db-thueringen.de/servlets/DocumentServlet?id=9374
Harant, Jochen; Rautenbach, Dieter
Domination in bipartite graphs. - Ilmenau : Techn. Univ., Inst. für Mathematik. - 13 S. = 261,7 KB, Text. - (Preprint. - M07,08)
Literaturverz. S. 12 - 13
http://www.db-thueringen.de/servlets/DocumentServlet?id=9373
Rautenbach, Dieter; Reed, Bruce
Domination in cubic graphs of large girth. - Ilmenau : Techn. Univ., Inst. für Mathematik. - 6 S. = 133,9 KB, Text. - (Preprint. - M07,07)
http://www.db-thueringen.de/servlets/DocumentServlet?id=9353
Rautenbach, Dieter; Volkmann, Lutz
Cyclic sums, network sharing and restricted edge cuts in graphs with long cycles. - Ilmenau : Techn. Univ., Inst. für Mathematik. - 9 S. = 165,8 KB, Text. - (Preprint. - M07,06)
http://www.db-thueringen.de/servlets/DocumentServlet?id=9352
Göring, Frank; Harant, Jochen; Rautenbach, Dieter; Schiermeyer, Ingo
On F-independence in graphs. - Ilmenau : Techn. Univ., Inst. für Mathematik. - 7 S. = 145,8 KB. - (Preprint. - M07,05)
http://www.db-thueringen.de/servlets/DocumentServlet?id=9351
John, Peter E.; Sachs, Horst
Spectra of toroidal graphs. - Ilmenau : Techn. Univ., Inst. für Mathematik. - 44 S. = 811 KB. - (Preprint. - M07,04)
http://www.db-thueringen.de/servlets/DocumentServlet?id=9350
Brandt, Stephan; Rautenbach, Dieter; Stiebitz, Michael
Edge colouring by total labellings. - Ilmenau : Techn. Univ., Inst. für Mathematik. - 13 S. = 181,5 KB, Text. - (Preprint. - M07,03)
http://www.db-thueringen.de/servlets/DocumentServlet?id=9347
Schreyer, Jens; Walther, Hansjoachim; Mel'nikov, Leonid S.
Vertex-oblique graphs. - In: Discrete mathematics. - Amsterdam [u.a.] : Elsevier, Bd. 307 (2007), 11/12, S. 1538-1544

Let x be a vertex of a simple graph G. The vertex-type of x is the lexicographically ordered degree sequence of its neighbors. We call the graph G vertex-oblique if there are no two vertices in V(G) which are of the same vertex-type. We will show that the set of vertex-oblique graphs of arbitrary connectivity is infinite.


http://dx.doi.org/10.1016/j.disc.2005.11.091
Rautenbach, Dieter; Volkmann, Lutz
New bounds on the k-domination number and the k-tuple domination number. - In: Applied mathematics letters. - Amsterdam [u.a.] : Elsevier Sci, Bd. 20 (2007), 1, S. 98-102
http://dx.doi.org/10.1016/j.aml.2006.03.006
Maffray, Frédéric; Rautenbach, Dieter
Small step-dominating sets in trees. - In: Discrete mathematics. - Amsterdam [u.a.] : Elsevier, Bd. 307 (2007), 9/10, S. 1212-1215
http://dx.doi.org/10.1016/j.disc.2006.07.038
Rautenbach, Dieter; Szegedy, Christian; Werber, Jürgen
The delay of circuits whose inputs have specified arrival times. - In: Discrete applied mathematics. - [S.l.] : Elsevier, Bd. 155 (2007), 10, S. 1233-1243
http://dx.doi.org/10.1016/j.dam.2006.10.013
Henning, Michael A.; Rautenbach, Dieter
On the irregularity of bipartite graphs. - In: Discrete mathematics. - Amsterdam [u.a.] : Elsevier, Bd. 307 (2007), 11/12, S. 1467-1472
http://dx.doi.org/10.1016/j.disc.2006.09.038
Caro, Yair; Rautenbach, Dieter
Reconstructing graphs from size and degree properties of their induced k-subgraphs. - In: Discrete mathematics. - Amsterdam [u.a.] : Elsevier, Bd. 307 (2007), 6, S. 694-703
http://dx.doi.org/10.1016/j.disc.2006.06.031
Gerlach, Tobias; Harant, Jochen
On a cycle through a specified linear forest of a graph. - In: Discrete mathematics. - Amsterdam [u.a.] : Elsevier, Bd. 307 (2007), 7/8, S. 892-895
http://dx.doi.org/10.1016/j.disc.2005.11.043
Hexel, Erhard
On short paths through prescribed vertices of a graph. - In: Discrete mathematics. - Amsterdam [u.a.] : Elsevier, Bd. 307 (2007), 7/8, S. 905-910
http://dx.doi.org/10.1016/j.disc.2005.11.040
Schreyer, Jens
Almost every graph is vertex-oblique. - In: Discrete mathematics. - Amsterdam [u.a.] : Elsevier, Bd. 307 (2007), 7/8, S. 983-989
http://dx.doi.org/10.1016/j.disc.2005.11.054
Diudea, Mircea V.; Stefu, Monica; John, Peter E.; Graovac, Ante
Generalized operations on maps. - In: Croatica chemica acta : . - Zagreb : Društvo, ISSN 00111643, Bd. 79 (2006), 3, S. 355-362
Diudea, Mircea V.; Cigher, Simona; Vizitiu, Aniela E.; Ursu, Oleg; John, Peter E.
Omega polynomial in tubular nanostructures. - In: Croatica chemica acta : . - Zagreb : Društvo, ISSN 00111643, Bd. 79 (2006), 3, S. 445-448
Harant, Jochen; Schiermeyer, Ingo
A lower bound on the independence number of a graph in terms of degrees. - In: Discussiones mathematicae / Graph theory. - Warsaw : De Gruyter Open, ISSN 20835892, Bd. 26 (2006), 3, S. 431-437
http://dx.doi.org/10.7151/dmgt.1335
Brandt, Stephan; Broersma, Hajo; Diestel, Reinhard; Kriesell, Matthias
Global connectivity and expansion: long cycles and factors in f-connected graphs. - In: Combinatorica : an international journal on combinatorics and the theory of computing. - Berlin : Springer, ISSN 14396912, Bd. 26 (2006), 1, S. 17-36
http://dx.doi.org/10.1007/s00493-006-0002-5
Rautenbach, Dieter; Schiermeyer, Ingo
Extremal problems for imbalanced edges. - In: Graphs and combinatorics. - Tokyo : Springer-Verl. Tokyo, ISSN 14355914, Bd. 22 (2006), 1, S. 103-111
http://dx.doi.org/10.1007/s00373-005-0643-y
Favaron, Odile; Laskar, Renu; Rautenbach, Dieter
t-partitions and s-complete t-partitions of a graph. - In: The Australasian journal of combinatoricsThe Australasian journal of combinatorics. - Queensland : Combinatorial Mathematics Soc. of Australasia : . - Queensland : University of Queensland, ISSN 10344942, Bd. 36 (2006), S. 295-302
Dobrynin, A. A.; Melnikov, L. S.; Valter, Ch.; Šrejer, J.
Čislo kosych poli&ptbov;edral&softcy;nych grafov s malym čislom veršin. - In: : ., (2006), S. 34-41

The paper considers polyhedral graphs (graphs of polyhedron or planar 3-connected graphs). A face $\alpha$ of size $k$ of a polyhedral graph is of type $<a_1,a_2,...,a_k>$ if the vertices incident with $\alpha$ in cyclic order have degrees $a_1,a_2,...,a_k$ and this sequence is lexicographically minimal. A polyhedral graph is oblique if it has no two faces of the same type. The number of polyhedral graphs with up to 12 vertices is found. Some additional properties of such graphs are also considered.


Rautenbach, Dieter; Brandstädt, Andreas; Le, Van Bang
Distance-hereditary 5-leaf powers. - In: Electronic notes in discrete mathematics. - Amsterdam : Elsevier Science - Amsterdam : Elsevier Science, ISSN 15710653, Bd. 27 (2006), S. 85-86
http://dx.doi.org/10.1016/j.endm.2006.08.068
Rautenbach, Dieter; Szegedy, Christian; Werber, Jürgen
Delay optimization of linear depth boolean circuits with prescribed input arrival times. - In: Journal of discrete algorithms : JDA. - Amsterdam [u.a.] : Elsevier, Bd. 4 (2006), 4, S. 526-537
http://dx.doi.org/10.1016/j.jda.2005.06.006
Voigt, Margit
List colourings of planar graphs. - In: Discrete mathematics. - Amsterdam [u.a.] : Elsevier, Bd. 306 (2006), 10/11, S. 1076-1079
http://dx.doi.org/10.1016/j.disc.2006.03.027
Gerlach, Tobias; Göring, Frank; Harant, Jochen; Tkáč, Michal
On cycles through specified vertices. - In: Discrete mathematics. - Amsterdam [u.a.] : Elsevier, Bd. 306 (2006), 8/9, S. 831-835
http://dx.doi.org/10.1016/j.disc.2005.12.021
Böhme, Thomas; Knor, Martin; Niepel, L'udovít
Linkability in iterated line graphs. - In: Discrete mathematics. - Amsterdam [u.a.] : Elsevier, Bd. 306 (2006), 7, S. 666-669
http://dx.doi.org/10.1016/j.disc.2005.11.018
John, Peter E.
An eigenvalue conjecture of P. C. Müller (University of Wuppertal). - Ilmenau : Techn. Univ., Inst. für Mathematik. - 4 S. = 114,8 KB. - (Preprint. - M06,07)
http://www.db-thueringen.de/servlets/DocumentServlet?id=6253
John, Peter E.; Khadikar, Padmakar V.; Singh, Jyoti
A method of computing the PI index of Benzenoid hydrocarbons using orthogonal cuts. - Ilmenau : Techn. Univ., Inst. für Mathematik. - 13 S. = 306,8 KB. - (Preprint. - M06,04)
http://www.db-thueringen.de/servlets/DocumentServlet?id=5669
Böhme, Thomas
Innovative internet community systems : 4th international workshop, IICS 2004, Guadalajara, Mexico, June 21 - 23, 2004 ; revised papers. - Berlin [u.a.] : Springer. - XI, 306 S.. - (Lecture notes in computer science. - 3473)
ISBN 3540288805 = 978-3-540-28880-0
Literaturangaben
http://www.gbv.de/dms/bsz/toc/bsz252759273inh.pdf
Stiebitz, Michael; Skrekovski, Riste
A map colour theorem for the union of graphs. - In: Journal of combinatorial theory / B. - Orlando, Fla : Academic Press, Bd. 96 (2006), 1, S. 20-37
http://dx.doi.org/10.1016/j.jctb.2005.06.003
Fajtlowicz, Siemion; John, Peter E.; Sachs, Horst
On maximum matchings and eigenvalues of benzenoid graphs. - In: Croatica chemica acta : . - Zagreb : Društvo, ISSN 00111643, Bd. 78 (2005), 2, S. 195-201
Hexel, Erhard
On short cycles through prescribed vertices of a polyhedral graph. - In: Discussiones mathematicae / Graph theory. - Warsaw : De Gruyter Open, ISSN 20835892, Bd. 25 (2005), 3, S. 419-426
http://dx.doi.org/10.7151/dmgt.1293
Harant, Jochen; Henning, Michael A.
On double domination in graphs. - In: Discussiones mathematicae / Graph theory. - Warsaw : De Gruyter Open, ISSN 20835892, Bd. 25 (2005), 1/2, S. 29-34
http://dx.doi.org/10.7151/dmgt.1256
Göring, Frank; Harant, Jochen
On domination in graphs. - In: Discussiones mathematicae / Graph theory. - Warsaw : De Gruyter Open, ISSN 20835892, Bd. 25 (2005), 1/2, S. 7-12
http://dx.doi.org/10.7151/dmgt.1254
John, Peter E.; Diudea, Mircea V.
Counting Kekulé numbers in torenes : a conjecture. - In: Nanostructures - New York : Nova Science Publ., (2005), S. 167-174

Witschel, Hans Friedrich; Böhme, Thomas
Evaluating profiling and query expansion methods for P2P information retrieval. - In: / ACM Workshop on Information Retrieval in Peer-to-Peer Networks ; 2 (Bremen) : 2005.11.04., (2005), S. 1-8

Kohl, Anja; Schreyer, Jens; Tuza, Zsolt; Voigt, Margit
List version of L(d,s)-labelings. - In: Theoretical computer science : the journal of the EATCS. - Amsterdam [u.a.] : Elsevier, Bd. 349 (2005), 1, S. 92-98
http://dx.doi.org/10.1016/j.tcs.2005.09.032
Fajtlowicz, Siemion; John, Peter E.; Sachs, Horst
On maximum matchings and eigenvalues of Benzenoid graphs. - Ilmenau : Techn. Univ., Inst. für Mathematik. - 16 S. = 683,8 KB. - (Preprint. - M05,07)
http://www.db-thueringen.de/servlets/DocumentServlet?id=5485
Aksionov, V. A.; Borodin, O. V.; Mel&softcy;nikov, L. S.; Sabidussi, G.; Stiebitz, Michael; Toft, B.
Deeply asymmetric planar graphs. - In: Journal of combinatorial theory / B. - Orlando, Fla : Academic Press, Bd. 95 (2005), 1, S. 68-78
http://dx.doi.org/10.1016/j.jctb.2005.03.002
Füredi, Zoltan; Kostochka, Alexandr V.; Skrekovski, Riste; Stiebitz, Michael; West, Douglas B.
Nordhaus-Gaddum-type theorems for decompositions into many parts. - In: Journal of graph theory. - New York, NY [u.a.] : Wiley, ISSN 10970118, Bd. 50 (2005), 4, S. 273-292
http://dx.doi.org/10.1002/jgt.20113
Böhme, Thomas; Kostochka, Alexandr
Disjoint Kr-minors in large graphs with given average degree. - In: European journal of combinatorics. - London : Academic Press, Bd. 26 (2005), 3, S. 289-292
http://dx.doi.org/10.1016/j.ejc.2003.12.017
Schreyer, Jens
Oblique graphs. - Online-Ressource (PDF-Datei: 69 S., 470 KB)
Ilmenau : Techn. Univ., Diss., 2005

Gegenstand der Arbeit ist die Untersuchung asymmetrischer Strukturen in Graphen. Dabei wird insbesondere betrachtet, inwieweit solche Strukturen in Graphen beliebiger Größe auftreten können. Nach einem Satz von Wright sind fast alle Graphen asymmetrisch. Auf der anderen Seite zeigen viele Resultate der Ramsey-Theorie, dass bei wachsenden Strukturen gewisse Regularitäten oder Ähnlichkeiten oft unvermeidlich sind. Der Begriff der Asymmetrie wird dahingehend erweitert, dass auch lokale Ähnlichkeiten ausgeschlossen werden. Graphen mit dieser hochgradigen Asymmetrieeigenschaft werden schräge Graphen (oblique graphs) genannt. Im ersten Teil der Arbeit werden asymmetrische Strukturen in Polyedergraphen untersucht. Für diese Graphenklasse sind Symmetrieeigenschaften in der Vergangenheit bereits oft untersucht worden. In dieser Arbeit werden verschiedene Typdefinitionen für die Flächen und Kanten eines Polyedergraphen vorgestellt. Ein Polyedergraph ist schräg bezüglich einer solchen Definition, wenn keine zwei Flächen beziehungsweise Kanten den gleichen Typ haben. Die Hauptresultate dieses Teils der Arbeit sind Sätze, die die Endlichkeit der Menge solcher schräger Graphen zeigen. Darüber hinaus kann in manchen Fällen gezeigt werden, dass jeder hinreichend große Polyedergraph mehr als z Kanten oder Flächen eines gemeinsamen Typs enthalten muss, wobei z eine beliebige natürliche Zahl ist. Im weiteren Verlauf werden die Endlichkeitsresultate über schräge Polyedergraphen auf Landkarten auf Flächen höheren Geschlechts übertragen. Im zweiten Teil der Arbeit werden schließlich asymmetrische Strukturen in allgemeinen Graphen untersucht. Ein schlichter Graph wird eckenschräg genannt, wenn sich je zwei Ecken in der Gradfolge ihrer Nachbarecken unterscheiden. Es wird gezeigt, dass es selbst unter verschiedenen zusätzlichen einschränkenden Bedingungen unendlich viele solche Graphen gibt. Im letzten Abschnitt der Arbeit werden schließlich Zufallsgraphen betrachtet. Es wird gezeigt, dass mit wachsender Eckenzahl die Wahrscheinlichkeit eines Zufallsgraphen, eckenschräg zu sein, gegen 1 konvergiert. Das heißt, fast jeder Graph ist eckenschräg, falls sich die Wahrscheinlichkeit dafür, dass eine bestimmte Kante im Zufallsgraphen auftritt, innerhalb gewisser, vorgegebener Grenzen bewegt.


http://www.db-thueringen.de/servlets/DocumentServlet?id=3604
Kirby, Edward C.; Klein, Douglas J.; Mallion, Roger B.; Pollak, Paul; Sachs, Horst
A theorem for counting spanning trees in general chemical graphs and its particular application to toroidal fullerenes. - In: Croatica chemica acta : . - Zagreb : Društvo, ISSN 00111643, Bd. 77 (2004), 1/2, S. 263-278
Diudea, Mircea V.; Stefu, Monica; Pârv, Basil; John, Peter E.
Wiener index of armchair polyhex nanotubes. - In: Croatica chemica acta : . - Zagreb : Društvo, ISSN 00111643, Bd. 77 (2004), 1/2, S. 111-115
John, Peter E.; Diudea, Mircea V.
Wiener index of zig-zag polyhex nanotubes. - In: Croatica chemica acta : . - Zagreb : Društvo, ISSN 00111643, Bd. 77 (2004), 1/2, S. 127-132
Gerlach, Tobias
Toughness and Hamiltonicity of a class of planar graphs. - In: Discrete mathematics. - Amsterdam [u.a.] : Elsevier, Bd. 286 (2004), 1/2, S. 61-65
http://dx.doi.org/10.1016/j.disc.2003.11.046
Gyárfás, Andras; Jensen, Tommy; Stiebitz, Michael
On graphs with strongly independent color-classes. - In: Journal of graph theory. - New York, NY [u.a.] : Wiley, ISSN 10970118, Bd. 46 (2004), 1, S. 1-14
http://dx.doi.org/10.1002/jgt.10165
Bang-Jensen, Jorgen; Brandt, Stephan
Subgraphs in vertex neighborhoods of Kr-free graphs. - In: Journal of graph theory. - New York, NY [u.a.] : Wiley, ISSN 10970118, Bd. 47 (2004), 1, S. 29-38
http://dx.doi.org/10.1002/jgt.20014
Brandt, Stephan; Wozniák, Mariusz
On cyclic packing of a tree. - In: Graphs and combinatorics. - Tokyo : Springer-Verl. Tokyo, ISSN 14355914, Bd. 20 (2004), 4, S. 435-442
http://dx.doi.org/10.1007/s00373-004-0583-y
Harant, Jochen
On paths and cycles through specified vertices. - In: Discrete mathematics. - Amsterdam [u.a.] : Elsevier, Bd. 286 (2004), 1/2, S. 95-98
http://dx.doi.org/10.1016/j.disc.2003.11.059
Schreyer, Jens; Walther, Hansjoachim
Edge-oblique polyhedral graphs. - In: Discrete applied mathematics. - [S.l.] : Elsevier, Bd. 136 (2004), 2/3, S. 315-327

Let G=G(V;E;F) be a polyhedral graph with vertex set V, edge set E and face set F. e=(x,y,alpha,beta) in E(G) denotes an edge incident with the two vertices x, y in V(G) with d(x)<=d(y), and incident with the two faces alpha, beta in F(G) with d(alpha)<=d(beta). - [d(x),d(y);d(alpha),d(beta)] is the type of the face e=(x,y;alpha,beta). A graph which contains no two edges of a common edge-type is called edge-oblique and if it contains at most z faces of each type it is called z-edge-oblique. In this work we shall prove, that there is only a finite number of edge-oblique and z-edge-oblique graphs. For the first case some bounds for the maximum degree and the number of edges are given.


http://dx.doi.org/10.1016/S0166-218X(03)00447-5
Göring, Frank; Harant, Jochen; Hexel, Erhard; Tuza, Zsolt
On short cycles through prescribed vertices of a graph. - In: Discrete mathematics. - Amsterdam [u.a.] : Elsevier, Bd. 286 (2004), 1/2, S. 67-74
http://dx.doi.org/10.1016/j.disc.2003.11.047
Böhme, Thomas; Mohar, Bojan; Krekovski, Riste; Stiebitz, Michael
Subdivisions of large complete bipartite graphs and long induced paths in k-connected graphs. - In: Journal of graph theory. - New York, NY [u.a.] : Wiley, ISSN 10970118, Bd. 45 (2004), 4, S. 270-274
http://dx.doi.org/10.1002/jgt.10161
Pruchnewski, Anja
Das graphentheoretische Dominanzproblem als stetiges Optimierungsproblem. - Online-Ressource (PDF-Datei: 79 S., 395 KB)
Ilmenau : Techn. Univ., Diss., 2004

Unter dem Dominanzproblem verstehen wir die Bestimmung der Dominanzzahl eines Graphen. Das zugehörige Entscheidungsproblem ist NP-vollständig. Somit ist man sowohl an guten oberen Schranken für die Dominanzzahl als auch an (möglichst effizienten) Algorithmen interessiert, die eine dominierende Menge liefern, deren Kardinalität diese Schranke nicht übersteigt.- In dieser Arbeit gelingt es, mit Mitteln der wahrscheinlichkeitstheoretischen Methode stetige Optimierungsprobleme für die Dominanzzahl, die Vektordominanzzahl, die totale Dominanzzahl bzw. die totale Vektordominanzzahl sowie die Überdeckungszahl (und damit auch für die Unabhängigkeitszahl) aufzustellen. Davon ausgehend werden Methoden zur Gewinnung oberer Schranken für die Dominanzzahlen der untersuchten Konzepte angegeben. Es werden Algorithmen vorgestellt, die für eine vorgegebene Schranke eine Knotenmenge berechnen, deren Kardinalität diese Schranke nicht übersteigt und die im entsprechenden Sinn dominierend ist. Die Algorithmen erweisen sich als polynomial für die Dominanz und die totale Dominanz, im Falle beschränkter Maximalvalenz auch für die Vektordominanz und die totale Vektordominanz. - Eine geeignete Einschränkung des zulässigen Bereiches liefert für paare Graphen explizit berechenbare Schranken in Abhängigkeit von den Minimalvalenzen in den Partitionsklassen. Diese Schranken sind gegenüber den aus der Literatur bekannten Schranken verbessert. Die Betrachtung verallgemeinerter Bipartitionen für nicht notwendig paare Graphen ermöglicht ebenfalls die Berechnung verbesserter Schranken und zudem die Berücksichtigung weiterer Graphenparameter bei der Schrankenberechnung.


http://www.db-thueringen.de/servlets/DocumentServlet?id=2608
Gerlach, Tobias
Über Kreise durch vorgeschriebene Elemente eines Graphen. - 1,96 MB, Text
Ilmenau : Techn. Univ., Diss., 2004

Ein linear forest ist ein kreisloser Graph mit einer Maximalvalenz von höchstens zwei. Damit besteht ein linear forest lediglich aus (isolierten) Knotenpunkten und/oder Wegen.Inhalt der vorliegenden Arbeit sind hinreichende Zusammenhangs- und Toughnessvoraussetzungen für die Existenz eines Kreises durch einen vorgeschriebenen linear forest eines Graphen. Es werden die Fälle betrachtet, daß der vorgeschriebene linear forest aus allen Knotenpunkten des Graphen (Hamiltonkreise, speziell in sep-chordalen planaren Graphen), aus einigen Knotenpunkten des Graphen bzw. aus einigen Knotenpunkten und einigen Kanten des Graphen besteht. Darauf aufbauend wird die Fragestellung nach der Existenz eines Kreises durch einige vorgeschriebene Knotenpunkte und einige vorgeschriebene Kanten mit einer zusätzlich vorgeschriebenen Durchlaufungsreihenfolge (speziell in chordalen Graphen) untersucht. -


http://www.db-thueringen.de/servlets/DocumentServlet?id=1904
Diudea, Mircea V.; John, Peter E.; Graovac, Ante; Primorac, Miljenko; Pisanski, Tomaž
Leapfrog and related operations on toroidal fullerenes. - In: Croatica chemica acta : . - Zagreb : Društvo, ISSN 00111643, Bd. 76 (2003), 2, S. 153-159
Plummer, Michael D.; Stiebitz, Michael; Toft, Bjarne
On a special case of Hadwiger's conjecture. - In: Discussiones mathematicae / Graph theory. - Warsaw : De Gruyter Open, ISSN 20835892, Bd. 23 (2003), 2, S. 333-363
http://dx.doi.org/10.7151/dmgt.1206
Diudea, Mircea V.; Parv, Basil; John, Peter E.; Ursu, Oleg; Graovac, Ante
Distance counting in tori. - In: MatchMatch : communications in mathematical and in computer chemistry. - Kragujevac : [Univ. [u.a.] : communications in mathematical and in computer chemistry. - Kragujevac : [Univ. [u.a.], ISSN 03406253, Bd. 49 (2003), S. 23-36
Gerlach, Tobias; Harant, Jochen
On cycles through a set of specified vertices. - In: Studies of the University of ŽilinaStudies of the University of Žilina / Matematical series. - Žilina : Univ. - Žilina : Univ., ISSN 1336149x, Bd. 16 (2003), 1, S. 35-46
Kostochka, Alexandr V.; Stiebitz, Michael
A new lower bound on the number of edges in colour-critical graphs and hypergraphs. - In: Journal of combinatorial theory / B. - Orlando, Fla : Academic Press, Bd. 87 (2003), 2, S. 374-402
http://dx.doi.org/10.1016/S0095-8956(02)00035-7
Brandt, Stephan
On the structure of graphs with bounded clique number. - In: Combinatorica : an international journal on combinatorics and the theory of computing. - Berlin : Springer, ISSN 14396912, Bd. 23 (2003), 4, S. 693-696
http://dx.doi.org/10.1007/s00493-003-0042-z
Stiebitz, Michael; Škrekovski, Riste
A map colour theorem for the union of graphs. - Praha : Charles Univ.. - 23 S. - (KAM-DIMATIA series. - 634)
Böhme, Thomas; Mohar, Bojan
Domination, packing and excluded minors. - In: The journal of combinatoricsThe journal of combinatorics : a print version of the electronic journal of combinatorics. - Cambridge, Mass. : Internat. Press : a print version of the electronic journal of combinatorics. - Cambridge, Mass. : Internat. Press, ISSN 10971440, Bd. 10Bd. 10.2003, 1, N9, insges. 6 S.
John, Peter E.; Ortlepp, Thomas
Note on cospectral graphs with simple eigenvalues. - In: MatchMatch : communications in mathematical and in computer chemistry. - Kragujevac : [Univ. [u.a.] : communications in mathematical and in computer chemistry. - Kragujevac : [Univ. [u.a.], ISSN 03406253, Bd. 48 (2003), S. 49-53
Böhme, Thomas; Heyer, Gerhard; Unger, Herwig
Innovative internet community systems : third international workshop ; revised papers. - Berlin [u.a.] : Springer. - VIII, 262 S. - (Lecture notes in computer science. - 2877)
ISBN 3540204369
Includes bibliographical references and index
http://external.dandelon.com/download/attachments/dandelon/ids/DEAGI2F7EE.pdf
Gerlach, Tobias; Harant, Jochen
A note on domination in bipartite graphs. - In: Discussiones mathematicae / Graph theory. - Warsaw : De Gruyter Open, ISSN 20835892, Bd. 22 (2002), 2, S. 229-231
http://dx.doi.org/10.7151/dmgt.1171
Göring, Frank
A proof of Menger's theorem by contraction. - In: Discussiones mathematicae / Graph theory. - Warsaw : De Gruyter Open, ISSN 20835892, Bd. 22 (2002), 1, S. 111-112
http://dx.doi.org/10.7151/dmgt.1161
Fowler, Patrick W.; John, Peter E.
Dürer polyhedra: the dark side of Melancholia. - In: Discussiones mathematicae / Graph theory. - Warsaw : De Gruyter Open, ISSN 20835892, Bd. 22 (2002), 1, S. 101-109
http://dx.doi.org/10.7151/dmgt.1160
Dobrynin, Andrey A.; Melnikov, Leonid S.; Schreyer, Jens; Walther, Hansjoachim
Some news about oblique graphs. - In: Discussiones mathematicae / Graph theory. - Warsaw : De Gruyter Open, ISSN 20835892, Bd. 22 (2002), 1, S. 39-50

A k-gon alpha of a polyhedral graph G(V,E,F) is of type <b1,b2,...,bk> if the vertices incident with alpha in cyclic order have degrees b1, b2,...,bk and <b1,b2,...,bk>$ is the lexicographic minimum of all such sequences available for alpha. A polyhedral graph G is oblique if it has no two faces of the same type. Among others it is shown that an oblique graph contains vertices of degree 3.


http://dx.doi.org/10.7151/dmgt.1157
Kostochka, Alexandr V.; Stiebitz, Michael
A list version of Dirac's theorem on the number of edges in colour-critical graphs. - In: Journal of graph theory. - New York, NY [u.a.] : Wiley, ISSN 10970118, Bd. 39 (2002), 3, S. 165-177
http://dx.doi.org/10.1002/jgt.998
Fabrici, Igor
On vertex-degree restricted subgraphs in polyhedral graphs. - In: Discrete mathematics. - Amsterdam [u.a.] : Elsevier, Bd. 256 (2002), 1/2, S. 105-114
http://dx.doi.org/10.1016/S0012-365X(01)00368-5
Brandt, Stephan
A 4-colour problem for dense triangle-free graphs. - In: Discrete mathematics. - Amsterdam [u.a.] : Elsevier, Bd. 251 (2002), 1/3, S. 33-46
http://dx.doi.org/10.1016/S0012-365X(01)00340-5
Göring, Frank
On 2-regular subgraphs in polyhedral graphs. - In: Discrete mathematics. - Amsterdam [u.a.] : Elsevier, Bd. 251 (2002), 1/3, S. 97-102
http://dx.doi.org/10.1016/S0012-365X(01)00329-6
Voigt, Margit; Walther, Hansjoachim
Polyhedral graphs with restricted number of faces of the same type. - In: Discrete mathematics. - Amsterdam [u.a.] : Elsevier, Bd. 244 (2002), 1/3, S. 473-478
http://dx.doi.org/10.1016/S0012-365X(01)00103-0
Tuza, Zsolt; Voigt, Margit
A note on planar 5-list colouring: non-extendability at distance 4. - In: Discrete mathematics. - Amsterdam [u.a.] : Elsevier, Bd. 251 (2002), 1/3, S. 169-172
http://dx.doi.org/10.1016/S0012-365X(01)00338-7
Hexel, Erhard
On light graphs in the family of 4-connected planar graphs. - In: Discrete mathematics. - Amsterdam [u.a.] : Elsevier, Bd. 251 (2002), 1/3, S. 103-107
http://dx.doi.org/10.1016/S0012-365X(01)00330-2
Böhme, Thomas; Mohar, Bojan; Thomassen, Carsten
Long cycles in graphs on a fixed surface. - In: Journal of combinatorial theory / B. - Orlando, Fla : Academic Press, Bd. 85 (2002), 2, S. 338-347
http://dx.doi.org/10.1006/jctb.2001.2108
Ruzsa, I. Z.; Tuza, Zsolt; Voigt, Margit
Distance graphs with finite chromatic number. - In: Journal of combinatorial theory / B. - Orlando, Fla : Academic Press, Bd. 85 (2002), 1, S. 181-187
http://dx.doi.org/10.1006/jctb.2001.2093
Harant, Jochen; Ryjáček, Zdeněk; Schiermeyer, Ingo
Forbidden subgraphs implying the MIN-algorithm gives a maximum independent set. - In: Discrete mathematics. - Amsterdam [u.a.] : Elsevier, Bd. 256 (2002), 1/2, S. 193-201
http://dx.doi.org/10.1016/S0012-365X(02)00571-X
Böhme, Thomas; Mohar, Bojan
Labeled K2,t minors in plane graphs. - In: Journal of combinatorial theory / B. - Orlando, Fla : Academic Press, Bd. 84 (2002), 2, S. 291-300
http://dx.doi.org/10.1006/jctb.2001.2083
Böhme, Thomas; Maharry, John; Mohar, Bojan
Ka,k minors in graphs of bounded tree-width. - In: Journal of combinatorial theory / B. - Orlando, Fla : Academic Press, Bd. 86 (2002), 1, S. 133-147
http://dx.doi.org/10.1006/jctb.2002.2119
Pruchnewski, Anja
On the domination number of a graph. - In: Discrete mathematics. - Amsterdam [u.a.] : Elsevier, Bd. 251 (2002), 1/3, S. 129-136
http://dx.doi.org/10.1016/S0012-365x(01)00334-x
Walther, Hansjoachim
Polyhedral graphs with extreme numbers of types of faces. - In: Discrete applied mathematics. - [S.l.] : Elsevier, Bd. 120 (2002), 1/3, S. 263-274
http://dx.doi.org/10.1016/S0166-218X(01)00295-5
Fabrici, Igor
Leichte Teilgraphen in Polyedergraphen. - 2,63 MB, Text
Ilmenau : Techn. Univ., Diss., 2002
http://www.db-thueringen.de/servlets/DocumentServlet?id=1165
Göring, Frank
Wegesysteme. - Online-Ressource (PDF-Datei: 108 S., 871 KB)
Ilmenau : Techn. Univ., Diss., 2002

Wegesysteme werden als Graphen abstrahiert, sodaß als natürliche Enthaltenseinsrelation von Graphen die topologische Minorenrelation betrachtet wird. Durch das Fixieren bestimmter Knotenpunkte des topologischen Minors im großen Graphen wird diese Ordnungsrelation spezialisiert, sodaß Existenzsätze über Wegesysteme eine einfache Formulierung bekommen. Zu Mengers Theorem über die Existenz eines bestimmten Wegesystems werden drei kurze und neue Beweise gegeben. Einer dieser Beweise liefert sowohl eine neue Version des Theorems, die die Vorschreibbarkeit der Start- und Endknoten eines nicht maximalen Wegesystems für ein maximales Wegesystem beinhaltet, als auch einen leicht implementierbaren linearen Algorithmus zum Auffinden dieses Wegesystems. Es wird gezeigt, daß diese Version bekannte Theoreme der Transversaltheorie wie Halls Heiratssatz und das Theorem über gemeinsame Transversalen von Ford und Fulkerson als Spezialfälle hat. Auch für Maders Theorem über die Zahl unabhängiger H-Wege wird die Vorschreibbarkeit der Startknoten gezeigt. Die neue Version von Mengers Theorem wird darüber hinaus verwendet, um ein Verfahren zu begründen, mit welchem untersucht werden kann, ob aus gewissen Zusammenhangsvoraussetzungen (evtl. kombiniert mit einem gegebenen Wegesystem) in einem Graphen die Existenz eines gesuchten Wegesystems folgt. Das Verfahren ist konstruktiv. Entweder findet es ein Gegenbeispiel, also einen Graphen mit den gegebenen Voraussetzungen, der das gesuchte Wegesystem nicht enthält, oder es liefert einen Algorithmus, welcher linear in der Zahl der Knoten und Kanten des gegebenen Graphen das gesuchte Wegesystem findet. Genauer wird bei Eingabe eines beliebigen Graphen entweder einen Trenner gefunden, der beweist, daß die Zusammenhangsvoraussetzung nicht gegeben ist, oder das gesuchte Wegesystem selbst wird konstruiert. An Beispielen wird die Funktionsweise des Verfahren demonstriert: Es werden zwei Existenzsätze über Kreise durch vorgeschriebene Knoten eines gegebenen Graphen damit hergeleitet.


http://www.db-thueringen.de/servlets/DocumentServlet?id=1138
Unger, Herwig; Böhme, Thomas
Innovative internet computing systems : second international workshop ; proceedings. - Berlin [u.a.] : Springer. - VIII, 249 S. - (Lecture notes in computer science. - 2346)
ISBN 3540437908
Literaturangaben
http://d-nb.info/964389541/04
Böhme, Thomas; Unger, Herwig
Innovative internet computing systems : international workshop IICS 2001, Ilmenau, Germany, June 21 - 22, 2001 ; proceedings. - Berlin : Springer. - Online-Ressource (VIII, 182 S.). - (Lecture notes in computer science. - 2060)
http://www.gbv.de/dms/bowker/toc/9783540422754.pdf
Harant, Jochen; Voigt, Margit; Jendrol', Stanislav; Randerath, Bert; Ryjáček, Zdeněk; Schiermeyer, Ingo
On weights of induced paths and cycles in claw-free and K1,r-free graphs. - In: Journal of graph theory. - New York, NY [u.a.] : Wiley, ISSN 10970118, Bd. 36 (2001), 3, S. 131-143
http://dx.doi.org/10.1002/1097-0118(200103)36:3<131::AID-JGT1001>3.0.CO;2-O
Tuza, Zsolt; Voigt, Margit
Oriented list colorings of graphs. - In: Journal of graph theory. - New York, NY [u.a.] : Wiley, ISSN 10970118, Bd. 36 (2001), 4, S. 217-229
http://dx.doi.org/10.1002/1097-0118(200104)36:4<217::AID-JGT1007>3.0.CO;2-1
Böhme, Thomas; Göring, Frank; Harant, Jochen
Menger's theorem. - In: Journal of graph theory. - New York, NY [u.a.] : Wiley, ISSN 10970118, Bd. 37 (2001), 1, S. 35-36
http://dx.doi.org/10.1002/jgt.1001
Schreyer, Jens; Walther, Hansjoachim
Edge-oblique polyhedral graphs. - In: Electronic notes in discrete mathematics. - Amsterdam : Elsevier Science, ISSN 15710653, Bd. 8 (2001), S. 90-93
http://dx.doi.org/10.1016/S1571-0653(05)80089-7
Harant, Jochen; Pruchnewski, Anja
A note on the domination number of a bipartite graph. - In: Annals of combinatorics : AC. - [Cham (ZG)] : [Springer International Publishing AG], ISSN 02193094, Bd. 5 (2001), 2, S. 175-178
http://dx.doi.org/10.1007/PL00001298
Harant, Jochen; Schiermeyer, Ingo
On the independence number of a graph in terms of order and size. - In: Discrete mathematics. - Amsterdam [u.a.] : Elsevier, Bd. 232 (2001), 1/3, S. 131-138
http://dx.doi.org/10.1016/S0012-365X(00)00298-3
Harant, Jochen; Hornak, Mirko; Skupien, Zdzislaw
Separating 3-cycles in plane triangulations. - In: Discrete mathematics. - Amsterdam [u.a.] : Elsevier, Bd. 239 (2001), 1/3, S. 127-136
http://dx.doi.org/10.1016/S0012-365X(01)00047-4
Unger, Herwig; Wulff, Markus; Böhme, Thomas
Community-based information management : an empiric approach. - In: Rostocker Informatik-BerichteRostocker Informatik-Berichte. - Rostock : Univ., Presse- und Informationsstelle Wissenschaftspublizistik : . - Rostock : Univ., Presse- und Informationsstelle Wissenschaftspublizistik, ISSN 02330784, (2001), 26, S. 89-107
Diudea, Mircea V.; John, Peter E.
Covering polyhedral tori. - In: MatchMatch : communications in mathematical and in computer chemistry. - Kragujevac : [Univ. [u.a.] : communications in mathematical and in computer chemistry. - Kragujevac : [Univ. [u.a.], ISSN 03406253, Bd. 44 (2001), S. 103-116
Schiermeyer, Ingo; Tuza, Zsolt; Voigt, Margit
On-line rankings of graphs. - In: Discrete mathematics. - Amsterdam [u.a.] : Elsevier, Bd. 212 (2000), 1/2, S. 141-147
http://dx.doi.org/10.1016/S0012-365X(99)00215-0
Fabrici, Igor; Owens, Peter J.; Walther, Hansjoachim
Non-hamiltonian polyhedral graphs with two types of faces. - In: Discrete mathematics. - Amsterdam [u.a.] : Elsevier, Bd. 213 (2000), 1/3, S. 105-113
http://dx.doi.org/10.1016/S0012-365X(99)00171-5
John, Peter E.; Sachs, Horst
On a strange observation in the theory of the dimer problem. - In: Discrete mathematics. - Amsterdam [u.a.] : Elsevier, Bd. 216 (2000), 1/3, S. 211-219
http://dx.doi.org/10.1016/S0012-365X(99)00301-5
Göring, Frank
Short proof of Menger's theorem. - In: Discrete mathematics. - Amsterdam [u.a.] : Elsevier, Bd. 219 (2000), 1/3, S. 295-296
http://dx.doi.org/10.1016/S0012-365X(00)00088-1
Harant, Jochen
Some news about the independence number of a graph. - In: Discussiones mathematicae / Graph theory. - Warsaw : De Gruyter Open, ISSN 20835892, Bd. 20 (2000), 1, S. 71-79
http://dx.doi.org/10.7151/dmgt.1107
Voigt, Margit
Algorithmic aspects of partial list colourings. - In: Combinatorics, probability & computingCombinatorics, probability & computing : CPC. - Cambridge : Univ. Press : CPC. - Cambridge : Univ. Pr., ISSN 09635483, Bd. 9 (2000), 4, S. 375-380
Wernicke, Bernd
Über gleichschenklige Tetraeder. - In: Mathematik in der Schule : . - Berlin : Pädagog. Zeitschriftenverl., ISSN 04653750, Bd. 38 (2000), 2, S. 90-95
Fabrici, Igor; Hexel, Erhard; Jendrol, Stanislav; Walther, Hansjoachim
On vertex-degree restricted paths in polyhedral graphs. - In: Discrete mathematics. - Amsterdam [u.a.] : Elsevier, Bd. 212 (2000), 1/2, S. 61-73
http://dx.doi.org/10.1016/S0012-365X(99)00209-5
Borowiecki, Mieczys&lstrok;aw; Mihók, Peter; Tuza, Zsolt; Voigt, Margit
Remarks on the existence of uniquely partitionable planar graphs. - In: Discussiones mathematicae / Graph theory. - Warsaw : De Gruyter Open, ISSN 20835892, Bd. 19 (1999), 2, S. 159-166
http://dx.doi.org/10.7151/dmgt.1092
Nützel, Jürgen; Fengler, Wolfgang; Böhme, Thomas
Objektorientierter Entwurf verteilter eingebetteter Echtzeitsysteme auf Basis hoherer Petri-Netze. - In: Entwicklung und Betrieb komplexer Automatisierungssysteme / Fachtagung. Institut für Regelungs- und Automatisierungstechnik, Technische Universität Braunschweig ; 6 (Braunschweig) : 1999.05.26-28. - Braunschweig : IfRA, (1999), S. 151-170
Böhme, Thomas; Mohar, Bojan; Stiebitz, Michael
Dirac's map-color theorem for choosability. - In: Journal of graph theory. - New York, NY [u.a.] : Wiley, ISSN 10970118, Bd. 32 (1999), 4, S. 327-339
http://dx.doi.org/10.1002/(SICI)1097-0118(199912)32:4<327::AID-JGT2>3.0.CO;2-B
Bartel, Hans-Georg; John, Peter E.
Formalbegriffsanalytische Untersuchung von Struktur-Eigenschaft-Beziehungen an Stannaocanen und Stannatranen unter Verwendung von 119 Sn-NMR-Daten. - In: Zeitschrift für physikalische Chemie : international journal of research in physical chemistry and chemical physics. - Berlin : De Gruyter, ISSN 21967156, Bd. 209 (1999), S. 141-158
http://dx.doi.org/10.1524/zpch.1999.209.Part_1.141
Walther, Hansjoachim
Polyhedral graphs with extreme numbers of types of faces. - In: Electronic notes in discrete mathematics. - Amsterdam : Elsevier Science, ISSN 15710653, Bd. 3 (1999), S. 205-207
http://dx.doi.org/10.1016/S1571-0653(05)80057-5
John, Peter E.
Theoretical organic chemistry, ed. by Cyril Párkányi : Amsterdam [u.a.], Elsevier, 1998. - In: Match. - Kragujevac : [Univ. [u.a.], ISSN 03406253, S. 155-156
Rezension von : Theoretical organic chemistry / Párkányi, Cyril. - Amsterdam [u.a.] : Elsevier, 1998. - XIV, 622 S.. - Theoretical and computational chemistry. - Literaturangaben
Hexel, Erhard; Walther, Hansjoachim
On vertex-degree restricted paths in $4$-connected planar graphs. - In: / Workshop on Cycles and Colourings ; 6 (Stará Lesná) : 1997.09.07-12., (1999), S. 1-13
Harant, Jochen; Jendrol, Stanislav; Tkáč, Michal
On 3-connected plane graphs without triangular faces. - In: Journal of combinatorial theory / B. - Orlando, Fla : Academic Press, Bd. 77 (1999), 1, S. 150-161
http://dx.doi.org/10.1006/jctb.1999.1918
Böhme, Thomas; Harant, Jochen; Tkáč, Michal
More than one tough chordal planar graphs are Hamiltonian. - In: Journal of graph theory. - New York, NY [u.a.] : Wiley, ISSN 10970118, Bd. 32 (1999), 4, S. 405-410
http://dx.doi.org/10.1002/(SICI)1097-0118(199912)32:4<405::AID-JGT8>3.0.CO;2-Z
Böhme, Thomas; Harant, Jochen; Tkáč, Michal
On certain Hamiltonian cycles in planar graphs. - In: Journal of graph theory. - New York, NY [u.a.] : Wiley, ISSN 10970118, Bd. 32 (1999), 1, S. 81-96
http://dx.doi.org/10.1002/(SICI)1097-0118(199909)32:1<81::AID-JGT8>3.0.CO;2-9
Harant, Jochen; Pruchnewski, Anja; Voigt, Margit
On dominating sets and independent sets of graphs. - In: Combinatorics, probability & computing : CPC. - Cambridge : Cambridge Univ. Press, ISSN 14692163, Bd. 8 (1999), 6, S. 547-553
http://dx.doi.org/10.1017/S0963548399004034
Harant, Jochen
Cycles and colourings '97 : proceedings of the 6th Workshop on Cycles and Colourings, Stará Lesná, September 7 - 12, 1997. - Bratislava : Mathematical Inst., Slovak Acad. of Sciences. - 113 S. - (Tatra Mountains mathematical publications. - 18)
Böhme, Thomas
Über Kreise in eingebetteten Graphen. - 96 Bl.
Ilmenau : Techn. Univ., Habil.-Schr., 1999
http://www.gbv.de/dms/ilmenau/toc/303464089.PDF
John, Peter E.; Mallion, Roger B.; Gutman, Ivan
An algorithm for counting spanning trees in labeled molecular graphs homeomorphic to cata-condensed systems. - In: Journal of chemical information and modeling. - Washington, DC : American Chemical Society, ISSN 1549960X, Bd. 38 (1998), 2, S. 108-112
Abstract published in Advance ACS Abstracts, December 15, 1997
https://doi.org/10.1021/ci970425d
John, Peter E.
Kekulé count in toroidal hexagonal carbon cages. - In: Croatica chemica acta : . - Zagreb : Društvo, ISSN 00111643, Bd. 71 (1998), 3, S. 435-447
Mihók, Peter; Bucko, Jozef; Voigt, Margit
On uniquely partitionable planar graphs. - In: Discrete mathematics. - Amsterdam [u.a.] : Elsevier, Bd. 191 (1998), 1/3, S. 149-158
http://dx.doi.org/10.1016/S0012-365X(98)00102-2
Kratochvíl, Jan; Tuza, Zsolt; Voigt, Margit
Complexity of choosing subsets from color sets. - In: Discrete mathematics. - Amsterdam [u.a.] : Elsevier, Bd. 191 (1998), 1/3, S. 139-148
http://dx.doi.org/10.1016/S0012-365X(98)00101-0
Kostochka, Alexandr V.; Stiebitz, Michael
Colour-critical graphs with few edges. - In: Discrete mathematics. - Amsterdam [u.a.] : Elsevier, Bd. 191 (1998), 1/3, S. 125-137
http://dx.doi.org/10.1016/S0012-365X(98)00100-9
Fabrici, Igor; Jendrol', Stanislav
Subgraphs with restricted degrees of their vertices in planar graphs. - In: Discrete mathematics. - Amsterdam [u.a.] : Elsevier, Bd. 191 (1998), 1/3, S. 83-90
http://dx.doi.org/10.1016/S0012-365X(98)00095-8
Kratochvíl, Jan; Tuza, Zsolt; Voigt, Margit
Brooks-type theorems for choosability with separation. - In: Journal of graph theory. - New York, NY [u.a.] : Wiley, ISSN 10970118, Bd. 27 (1998), 1, S. 43-49
http://dx.doi.org/10.1002/(SICI)1097-0118(199801)27:1<43::AID-JGT7>3.0.CO;2-G
Böhme, Thomas; Harant, Jochen
On Hamiltonian cycles in 4- and 5-connected plane triangulations. - In: Discrete mathematics. - Amsterdam [u.a.] : Elsevier, Bd. 191 (1998), 1/3, S. 25-30
http://dx.doi.org/10.1016/S0012-365X(98)00089-2
Harant, Jochen
A lower bound on the independence number of a graph. - In: Discrete mathematics. - Amsterdam [u.a.] : Elsevier, Bd. 188 (1998), 1/3, S. 239-243
http://dx.doi.org/10.1016/S0012-365X(98)00048-X
Böhme, Thomas; Harant, Jochen; Pruchnewski, Anja; Schiermeyer, Ingo
A planarity criterion bipartite graphs. - In: Discrete mathematics. - Amsterdam [u.a.] : Elsevier, Bd. 191 (1998), 1, S. 31-43
http://dx.doi.org/10.1016/S0012-365X(98)00090-9
Voigt, Margit
On list colourings and choosability of graphs. - 130 Bl
Ilmenau : Techn. Univ., Habil.-Schr., 1998
John, Peter; Gutman, Ivan E.
On the calculation of the algebraic structure count of polycyclic conjugated hydrocarbons by means of cell polynomial. - In: Journal of the Serbian Chemical SocietyJournal of the Serbian Chemical Society. - Belgrade : Soc. - Belgrade : Soc., ISSN 03525139, Bd. 62 (1997), 4, S. 319-325
Alon, Noga; Tuza, Zsolt; Voigt, Margit
Choosability and fractional chromatic numbers. - In: Discrete mathematics. - Amsterdam [u.a.] : Elsevier, Bd. 165/166 (1997), S. 31-38
http://dx.doi.org/10.1016/S0012-365X(96)00159-8
Böhme, Thomas; Broersma, Hajo; Göbel, F.; Kostochka, Alexandr V.; Stiebitz, Michael
Spanning trees with pairwise nonadjacent endvertices. - In: Discrete mathematics. - Amsterdam [u.a.] : Elsevier, Bd. 170 (1997), 1/3, S. 219-222
http://dx.doi.org/10.1016/S0012-365X(96)00306-8
Fleischner, Herbert; Stiebitz, Michael
Some remarks on the cycle plus triangles problem. - In: The mathematics of Paul Erdös : . - Berlin [u.a.] : Springer, (1997), S. 136-142

Voigt, Margit; Wirth, B.
On 3-colorable non-4-choosable planar graphs. - In: Journal of graph theory. - New York, NY [u.a.] : Wiley, ISSN 10970118, Bd. 24 (1997), 3, S. 233-235
http://dx.doi.org/10.1002/(SICI)1097-0118(199703)24:3<233::AID-JGT4>3.0.CO;2-Q
Unger, Herwig; Böhme, Thomas
Ein multikriterielles, fuzzybasiertes Lastverteilungssystem. - In: Informatik und Automatisierung im Zeitalter der Informationsgesellschaft ; Bd. 1: [Vortragsreihen : Softwaretechnik/Prozeßinformatik, Computergrafik/Bildverarbeitung, Betriebssysteme/Verteilte Systeme, Datenbanktechnologie ...]. - Ilmenau : Technische Univ., (1997), S. 269-274
John, Peter E.; Mallion, Roger B.
Calculating the number of spanning trees in a labeled planar molecular graph whose inner dual is a tree. - In: International journal of quantum chemistry. - New York, NY : Wiley, ISSN 1097461X, Bd. 60 (1996), 1, S. 59-66
https://doi.org/10.1002/(SICI)1097-461X(1996)60:1<59::AID-QUA6>3.0.CO;2-4
Voigt, Margit
Choosability of planar graphs. - In: Discrete mathematics. - Amsterdam [u.a.] : Elsevier, Bd. 150 (1996), 1/3, S. 457-460
http://dx.doi.org/10.1016/0012-365X(95)00216-J
Walther, Hansjoachim
A nonhamiltonian five-regular multitriangular polyhedral graph. - In: Discrete mathematics. - Amsterdam [u.a.] : Elsevier, Bd. 150 (1996), 1/3, S. 387-392
http://dx.doi.org/10.1016/0012-365X(95)00203-9
Kostochka, Alexandr V.; Stiebitz, Michael; Wirth, B.
The colour theorems of Brooks and Gallai extended. - In: Discrete mathematics. - Amsterdam [u.a.] : Elsevier, Bd. 162 (1996), 1/3, S. 299-303
http://dx.doi.org/10.1016/0012-365X(95)00294-7
Fabrici, Igor; Jendrol', Stanislav
An inequality concerning edges of minor weight in convex 3-polytopes. - In: Discussiones mathematicae / Graph theory. - Warsaw : De Gruyter Open, ISSN 20835892, Bd. 16 (1996), 1, S. 81-87
http://dx.doi.org/10.7151/dmgt.1024
Tuza, Zsolt; Voigt, Margit
Every 2-choosable graph is (2m, m)-choosable. - In: Journal of graph theory. - New York, NY [u.a.] : Wiley, ISSN 10970118, Bd. 22 (1996), 3, S. 245-252
http://dx.doi.org/10.1002/(SICI)1097-0118(199607)22:3<245::AID-JGT5>3.0.CO;2-M
Böhme, Thomas; Broersma, H. J.; Veldman, H. J.
Toughness and longest cycles in 2-connected planar graphs. - In: Journal of graph theory. - New York, NY [u.a.] : Wiley, ISSN 10970118, Bd. 23 (1996), 3, S. 257-263
http://dx.doi.org/10.1002/(SICI)1097-0118(199611)23:3<257::AID-JGT5>3.0.CO;2-R
Stiebitz, Michael
Decomposing graphs under degree constraints. - In: Journal of graph theory. - New York, NY [u.a.] : Wiley, ISSN 10970118, Bd. 23 (1996), 3, S. 321-324
http://dx.doi.org/10.1002/(SICI)1097-0118(199611)23:3<321::AID-JGT12>3.0.CO;2-H
John, Peter E.; Schild, Göran
Calculating the characteristic polynomial and the eigenvectors of a tree. - In: MatchMatch : communications in mathematical and in computer chemistry. - Kragujevac : [Univ. [u.a.] : communications in mathematical and in computer chemistry. - Kragujevac : [Univ. [u.a.], ISSN 03406253, Bd. 34 (1996), S. 217-237
Böhme, Thomas; Harant, Jochen; Tkác, Michal
On the minimal number of separating 3-cycles in non-Hamiltonian maximal planar graphs. - In: / Workshop on Cycles and Colourings ; 3 (Stará Lesná) : 1994.09.04-09., (1996), S. 97-102
Harant, Jochen; Owens, Peter J.; Tkác, Michal; Walther, Hansjoachim
5-regular 3-polytopal graphs with edges of only two types and shortness exponents less than one. - In: Discrete mathematics. - Amsterdam [u.a.] : Elsevier, Bd. 150 (1996), 1/3, S. 143-153
http://dx.doi.org/10.1016/0012-365X(95)00183-W
Harant, Jochen
Cycles and colourings '94 : proceedings of the 3rd Workshop on Cycles and Colourings, Stará Lesná, September 4-9, 1994. - Bratislava : Mathematical Inst., Slovak Acad. of Sciences. - 104 S. - (Tatra Mountains mathematical publications. - 9)
Owens, Peter J.; Walther, Hansjoachim
Hamiltonicity in multitriangular graphs. - In: Discussiones mathematicae / Graph theory. - Warsaw : De Gruyter Open, ISSN 20835892, Bd. 15 (1995), 1, S. 77-88
http://dx.doi.org/10.7151/dmgt.1009
John, Peter E.; Rausch, Wilfried
Beschreibung eines Programms zur Berechnung des charakteristischen Polynoms und der Eigenvektoren eines Graphen. - In: MatchMatch : communications in mathematical and in computer chemistry. - Kragujevac : [Univ. [u.a.] : communications in mathematical and in computer chemistry. - Kragujevac : [Univ. [u.a.], ISSN 03406253, Bd. 32 (1995), S. 237-249
John, Peter E.
Über die Berechnung des Wiener-Index für ausgewählte [delta]-dimensionale Gitterstrukturen. - In: MatchMatch : communications in mathematical and in computer chemistry. - Kragujevac : [Univ. [u.a.] : communications in mathematical and in computer chemistry. - Kragujevac : [Univ. [u.a.], ISSN 03406253, Bd. 32 (1995), S. 207-219
Harant, Jochen; Owens, Peter J.
Non-hamiltonian 5/4-tough maximal planar graphs. - In: Discrete mathematics. - Amsterdam [u.a.] : Elsevier, Bd. 147 (1995), 1/3, S. 301-305
http://dx.doi.org/doi:10.1016/0012-365X(94)00177-K
Stiebitz, Michael
The forest plus stars colouring problem. - In: Discrete mathematics. - Amsterdam [u.a.] : Elsevier, Bd. 126 (1994), 1/3, S. 385-389
http://dx.doi.org/10.1016/0012-365X(94)90282-8
John, Peter E.
ChemInform abstract: Calculating the cell polynomial of catacondensed polycyclic hydrocarbons. - In: ChemInform. - Weinheim : Wiley-VCH, ISSN 15222667, Bd. 25 (1994), 30, insges. 1 S.
http://dx.doi.org/10.1002/chin.199430257
Voigt, Margit; Walther, Hansjoachim
Chromatic number of prime distance graphs. - In: Discrete applied mathematics. - [S.l.] : Elsevier, Bd. 51 (1994), 1/2, S. 197-209
http://dx.doi.org/10.1016/0166-218X(94)90109-0
John, Peter E.
Die Berechnung des Wiener Index für einfache Polybäume. - In: MatchMatch : communications in mathematical and in computer chemistry. - Kragujevac : [Univ. [u.a.] : communications in mathematical and in computer chemistry. - Kragujevac : [Univ. [u.a.], ISSN 03406253, Bd. 31 (1994), S. 123-132
John, Peter E.
Calculating the characteristic polynomial and the eigenvectors of a weighted hexagonal system (benzenoid hydrocarbon with heteroatoms). - In: MatchMatch : communications in mathematical and in computer chemistry. - Kragujevac : [Univ. [u.a.] : communications in mathematical and in computer chemistry. - Kragujevac : [Univ. [u.a.], ISSN 03406253, Bd. 30 (1994), S. 153-169
Harant, Jochen; Walther, Hansjoachim
A lower bound for the shortness coefficient of a class of graphs. - In: Discrete applied mathematics. - [S.l.] : Elsevier, Bd. 51 (1994), 1/2, S. 103-105
http://dx.doi.org/10.1016/0166-218X(94)90098-1
Hexel, Erhard
On paths of greedoids and a minor characterization. - In: European journal of combinatorics. - London : Academic Press, Bd. 15 (1994), 3, S. 239-244
http://dx.doi.org/10.1006/eujc.1994.1025
Stiebitz, Michael; Wessel, Walter
On colouring partial joins of a complete graph and a cycle. - In: Mathematische Nachrichten. - [S.l.] : Wiley-VCH, ISSN 15222616, Bd. 163 (1993), 1, S. 109-116
http://dx.doi.org/10.1002/mana.19931630111
Voigt, Margit
List colourings of planar graphs. - In: Discrete mathematics. - Amsterdam [u.a.] : Elsevier, Bd. 120 (1993), 1/3, S. 215-219
http://dx.doi.org/10.1016/0012-365X(93)90579-I
Harant, Jochen
An upper bound for the radius of a 3-connected graph. - In: Discrete mathematics. - Amsterdam [u.a.] : Elsevier, Bd. 122 (1993), 1/3, S. 335-341
http://dx.doi.org/10.1016/0012-365X(93)90306-E
Harant, Jochen
Toughness and nonhamiltonicity of polyhedral graphs. - In: Discrete mathematics. - Amsterdam [u.a.] : Elsevier, Bd. 113 (1993), 1/3, S. 249-253
http://dx.doi.org/10.1016/0012-365X(93)90519-Y
Stiebitz, Michael
On Hadwiger's number - a problem of the Nordhaus-Gaddum type. - In: Discrete mathematics. - Amsterdam [u.a.] : Elsevier, Bd. 101 (1992), 1/3, S. 307-317
http://dx.doi.org/10.1016/0012-365X(92)90611-I
Sachs, Horst
How to calculate the number of perfect matchings in finite sections of certain infinite plane graphs. - In: Discrete mathematics. - Amsterdam [u.a.] : Elsevier, Bd. 101 (1992), 3, S. 279-284
http://dx.doi.org/10.1016/0012-365X(92)90608-I
Fleischner, Herbert; Stiebitz, Michael
A solution to a colouring problem of P. Erd&dblac;os. - In: Discrete mathematics. - Amsterdam [u.a.] : Elsevier, Bd. 101 (1992), 1/3, S. 39-48
http://dx.doi.org/10.1016/0012-365X(92)90588-7
Wang, Tao; Sachs, Horst
A contribution to the theory of Tutte's V - and W -function. - In: Discrete mathematics. - Amsterdam [u.a.] : Elsevier, Bd. 104 (1992), 3, S. 281-292
http://dx.doi.org/10.1016/0012-365X(92)90450-T
John, Peter E.
Advances in the theory of benzenoid hydrocarbons, 2, with 58 tables, with contributions by J. Brunvoll ... : Berlin [u.a.], Springer, 1992. - In: Zeitschrift für physikalische Chemie. - Berlin : De Gruyter, ISSN 21967156, S. 121-122
Rezension von : with 58 tables / Brunvoll, J.. - Berlin [u.a.] : Springer, 1992. - 226 S.. - Topics in current chemistry ; 162. - Literaturangaben
http://dx.doi.org/10.1524/zpch.1992.177.Part_1.121a
John, Peter E.
Counting perfect matchings in hexagonal chains. - In: Chemical physics letters. - Amsterdam [u.a.] : Elsevier, Bd. 196 (1992), 5, S. 525-528
http://dx.doi.org/10.1016/0009-2614(92)85731-O
John, Peter E.
Two codes for hexagonal systems. - In: MatchMatch : communications in mathematical and in computer chemistry. - Kragujevac : [Univ. [u.a.] : communications in mathematical and in computer chemistry. - Kragujevac : [Univ. [u.a.], ISSN 03406253, Bd. 28 (1992), S. 209-218
John, Peter
Über Anzahlen von Linearfaktoren in hexagonalen Bändern. - In: MatchMatch : communications in mathematical and in computer chemistry. - Kragujevac : [Univ. [u.a.] : communications in mathematical and in computer chemistry. - Kragujevac : [Univ. [u.a.], ISSN 03406253, Bd. 28 (1992), S. 181-208
John, Peter E.
Eine dritte graphentheoretische Bemerkung zur Resonanztheorie benzenoider Kohlenwasserstoffe. - In: MatchMatch : communications in mathematical and in computer chemistry. - Kragujevac : [Univ. [u.a.] : communications in mathematical and in computer chemistry. - Kragujevac : [Univ. [u.a.], ISSN 03406253, Bd. 28 (1992), S. 165-180
Voigt, Margit; Walther, Hansjoachim
On the chromatic number of special distance graphs. - In: Discrete mathematics. - Amsterdam [u.a.] : Elsevier, Bd. 97 (1991), 1/3, S. 395-397
http://dx.doi.org/10.1016/0012-365X(91)90454-A
Unger, Herwig; Böhme, Thomas
Zur Generation von Software aus Petrinetzen auf der Basis der Markenflußanalyse. - In: Internationales wissenschaftliches Kolloquium : IWK. - Ilmenau : Bibliothek der TH, ISSN 03743365, Bd. 36 (1991), 4, S. 781-786