Rooted minors and locally spanning subgraphs. - In: Journal of graph theory, ISSN 1097-0118, Bd. 105 (2024), 2, S. 209-229
Results on the existence of various types of spanning subgraphs of graphs are milestones in structural graph theory and have been diversified in several directions. In the present paper, we consider “local” versions of such statements. In 1966, for instance, D. W. Barnette proved that a 3-connected planar graph contains a spanning tree of maximum degree at most 3. A local translation of this statement is that if G is a planar graph, X is a subset of specified vertices of G such that X cannot be separated in G by removing two or fewer vertices of G, then G has a tree of maximum degree at most 3 containing all vertices of X. Our results constitute a general machinery for strengthening statements about k-connected graphs (for 1 ≤ k ≤ 4) to locally spanning versions, that is, subgraphs containing a set X ⊆ V (G) of a (not necessarily planar) graph G in which only X has high connectedness. Given a graph G and X ⊆ V (G), we say M is a minor of G rooted at X, if M is a minor of G such that each bag of M contains at most one vertex of X and X is a subset of the union of all bags. We show that G has a highly connected minor rooted at X if X ⊆ V (G) cannot be separated in G by removing a few vertices of G. Combining these investigations and the theory of Tutte paths in the planar case yields locally spanning versions of six well-known results about degree-bounded trees, Hamiltonian paths and cycles, and 2-connected subgraphs of graphs.
https://doi.org/10.1002/jgt.23012
Complexity of (arc)-connectivity problems involving arc-reversals or deorientations. - In: Theoretical computer science, Bd. 973 (2023), 114097
By a well known theorem of Robbins, a graph G has a strongly connected orientation if and only if G is 2-edge-connected and it is easy to find, in linear time, either a cut edge of G or a strong orientation of G. A result of Durand de Gevigney shows that for every it is NP-hard to decide if a given graph G has a k-strong orientation. Thomassen showed that one can check in polynomial time whether a given graph has a 2-strong orientation. This implies that for a given digraph D we can determine in polynomial time whether we can reorient (=reverse) some arcs of to obtain a 2-strong digraph. This naturally leads to the question of determining the minimum number of such arcs to reverse before the resulting graph is 2-strong. In this paper we show that finding this number is NP-hard. If a 2-connected graph G has no 2-strong orientation, we may ask how many of its edges we may orient so that the resulting mixed graph is still 2-strong. Similarly, we may ask for a 2-edge-connected graph G how many of its edges we can orient such that the resulting mixed graph remains 2-arc-strong. We prove that when restricted to graphs satisfying suitable connectivity conditions, both of these problems are equivalent to finding the minimum number of edges we must double in a 2-edge-connected graph in order to obtain a 4-edge-connected graph. Using this, we show that all these three problems are NP-hard. Finally, we consider the operation of deorienting an arc uv of a digraph D meaning replacing it by an undirected edge between the same vertices. In terms of connectivity properties, this is equivalent to adding the opposite arc vu to D. We prove that for every it is NP-hard to find the minimum number of arcs to deorient in a digraph D in order to obtain an ℓ-strong digraph.
https://doi.org/10.1016/j.tcs.2023.114097
Contractible edges in longest cycles. - In: Journal of graph theory, ISSN 1097-0118, Bd. 103 (2023), 3, S. 542-563
https://doi.org/10.1002/jgt.22935
Globally balancing spanning trees. - In: European journal of combinatorics, Bd. 109 (2023), 103644
https://doi.org/10.1016/j.ejc.2022.103644
On the complexity of finding well-balanced orientations with upper bounds on the out-degrees. - In: Journal of combinatorial optimization, ISSN 1573-2886, Bd. 45 (2023), 1, 30, S. 1-14
https://doi.org/10.1007/s10878-022-00962-y
Reachability in arborescence packings. - In: Discrete applied mathematics, ISSN 1872-6771, Bd. 320 (2022), S. 170-183
Fortier et al. proposed several research problems on packing arborescences and settled some of them. Others were later solved by Matsuoka and Tanigawa and by Gao and Yang. The last open problem is settled in this article. We show how to turn an inductive idea used in the latter two articles into a simple proof technique that allows to relate previous results on arborescence packings. We prove that a strong version of Edmonds’ theorem on packing spanning arborescences implies Kamiyama, Katoh and Takizawa’s result on packing reachability arborescences and that Durand de Gevigney, Nguyen and Szigeti’s theorem on matroid-based packing of arborescences implies Király’s result on matroid-reachability-based packing of arborescences. Further, we deduce a new result on matroid-reachability-based packing of mixed hyperarborescences from a theorem on matroid-based packing of mixed hyperarborescences due to Fortier et al.. Finally, we deal with the algorithmic aspects of the problems considered. We first obtain algorithms to find the desired packings of arborescences in all settings and then apply Edmonds’ weighted matroid intersection algorithm to also find solutions minimizing a given weight function.
https://doi.org/10.1016/j.dam.2022.05.018
Good acyclic orientations of 4-regular 4-connected graphs. - In: Journal of graph theory, ISSN 1097-0118, Bd. 100 (2022), 4, S. 698-720
An st-ordering of a graph G=(V,E) is an ordering v1,v2,…,vn of its vertex set such that s=v1,t=vn and every vertex vi with i=2,3,…,n-1 has both a lower numbered and a higher numbered neighbor. Such orderings have played an important role in algorithms for planarity testing. It is well-known that every 2-connected graph has an st-ordering for every choice of distinct vertices s,t. An st-ordering of a graph G corresponds directly to a so-called bipolar orientation of G, that is, an acyclic orientation D of G in which s is the unique source and t is the unique sink. Clearly every bipolar orientation of a graph has an out-branching rooted at the source vertex and an in-branching rooted at the sink vertex. In this paper, we study graphs which admit a bipolar orientation that contains an out-branching and in-branching which are arc-disjoint (such an orientation is called good). A 2T-graph is a graph whose edge set can be decomposed into two edge-disjoint spanning trees. Clearly a graph has a good orientation if and only if it contains a spanning 2T-graph with a good orientation, implying that 2T-graphs play a central role. It is a well-known result due to Tutte and Nash-Williams, respectively, that every 4-edge-connected graph contains a spanning 2T-graph. Vertex-minimal 2T-graphs with at least two vertices, also known as generic circuits, play an important role in rigidity theory for graphs. Recently with Bessy and Huang we proved that every generic circuit has a good orientation. In fact, we may specify the roots of the two branchings arbitrarily as long as they are distinct. Using this, several results on good orientations of 2T-graphs were obtained. It is an open problem whether there exists a polynomial algorithm for deciding whether a given 2T-graph has a good orientation. Complex constructions of 2T-graphs with no good orientation were given in work by Bang-Jensen, Bessy, Huang and Kriesell (2021) indicating that the problem might be very difficult. In this paper, we focus on so-called quartics which are 2T-graphs where every vertex has degree 3 or 4. We identify a sufficient condition for a quartic to have a good orientation, give a polynomial algorithm to recognize quartics satisfying the condition and a polynomial algorithm to produce a good orientation when this condition is met. As a consequence of these results we prove that every 4-regular and 4-connected graph has a good orientation, where, as for generic circuits, we may specify the roots of the two branchings arbitrarily as long as they are distinct. We also provide evidence that even for quartics it may be difficult to find a characterization of those instances which have a good orientation. We also show that every graph on n≥8 vertices and of minimum degree at least has a good orientation. Finally we pose a number of open problems.
https://doi.org/10.1002/jgt.22803
Checking the admissibility of odd-vertex pairings is hard. - In: Discrete applied mathematics, ISSN 1872-6771, Bd. 317 (2022), S. 42-48
Nash-Williams proved that every graph has a well-balanced orientation. A key ingredient in his proof is admissible odd-vertex pairings. We show that for two slightly different definitions of admissible odd-vertex pairings, deciding whether a given odd-vertex pairing is admissible is co-NP-complete. This resolves a question of Frank. We also show that deciding whether a given graph has an orientation that satisfies arbitrary local arc-connectivity requirements is NP-complete.
https://doi.org/10.1016/j.dam.2022.04.004
Low chromatic spanning sub(di)graphs with prescribed degree or connectivity properties. - In: Journal of graph theory, ISSN 1097-0118, Bd. 99 (2022), 4, S. 615-636
https://doi.org/10.1002/jgt.22755
A note on uniquely 10-colorable graphs. - In: Journal of graph theory, ISSN 1097-0118, Bd. 98 (2021), 1, S. 24-26
Hadwiger conjectured that every graph of chromatic number k admits a clique minor of order k. Here we prove for k ≤ 10, that every graph of chromatic number k with a unique k-coloring (up to the color names) admits a clique minor of order k. The proof does not rely on the Four Color Theorem.
https://doi.org/10.1002/jgt.22679
Good orientations of unions of edge-disjoint spanning trees. - In: Journal of graph theory, ISSN 1097-0118, Bd. 96 (2021), 4, S. 594-618
In this paper, we exhibit connections between the following subjects: Tree packing in graphs and digraphs (both behave completely different), the rigidity matroid of a graph, Henneberg moves on trees, the conjectures of Thomassen and Matthews and Sumner, and (s,t)-orderings of digraphs. We do this by studying graphs which admit acyclic orientations that contain an out-branching and in-branching which are arc-disjoint (such an orientation is called good). A 2T-graph is a graph whose edge set can be decomposed into two edge-disjoint spanning trees. It is a well-known result due to Tutte and Nash-Williams, respectively, that every 4-edge-connected graph contains a spanning 2T-graph. Vertex-minimal 2T-graphs with at least two vertices which are known as generic circuits play an important role in rigidity theory for graphs. We prove that every generic circuit has a good orientation. Using this result we prove that if G is 2T-graph whose vertex set has a partition V1,V2, ,Vk so that each Vi induces a generic circuit Gi of G and the set of edges between different Gi's form a matching in G, then G has a good orientation. We also obtain a characterization for the case when the set of edges between different Gi's form a double tree, that is, if we contract each Gi to one vertex, and delete parallel edges we obtain a tree. All our proofs are constructive and imply polynomial algorithms for finding the desired good orderings and the pairs of arc-disjoint branchings which certify that the orderings are good. We identify a structure which can be used to certify that a given 2T-graph does not have a good orientation.
https://doi.org/10.1002/jgt.22633
Rooted structures in graphs : a project on Hadwiger's conjecture, rooted minors, and Tutte cycles. - Ilmenau : Universitätsbibliothek, 2020. - 1 Online-Ressource (viii, 131 Blätter)
Technische Universität Ilmenau, Dissertation 2020
Hadwigers Vermutung ist eine der anspruchsvollsten Vermutungen für Graphentheoretiker und bietet eine weitreichende Verallgemeinerung des Vierfarbensatzes. Ausgehend von dieser offenen Frage der strukturellen Graphentheorie werden gewurzelte Strukturen in Graphen diskutiert. Eine Transversale einer Partition ist definiert als eine Menge, welche genau ein Element aus jeder Menge der Partition enthält und sonst nichts. Für einen Graphen G und eine Teilmenge T seiner Knotenmenge ist ein gewurzelter Minor von G ein Minor, der T als Transversale seiner Taschen enthält. Sei T eine Transversale einer Färbung eines Graphen, sodass es ein System von kanten-disjunkten Wegen zwischen allen Knoten aus T gibt; dann stellt sich die Frage, ob es möglich ist, die Existenz eines vollständigen, in T gewurzelten Minors zu gewährleisten. Diese Frage ist eng mit Hadwigers Vermutung verwoben: Eine positive Antwort würde Hadwigers Vermutung für eindeutig färbbare Graphen bestätigen. In dieser Arbeit wird ebendiese Fragestellung untersucht sowie weitere Konzepte vorgestellt, welche bekannte Ideen der strukturellen Graphentheorie um eine Verwurzelung erweitern. Beispielsweise wird diskutiert, inwiefern hoch zusammenhängende Teilmengen der Knotenmenge einen hoch zusammenhängenden, gewurzelten Minor erzwingen. Zudem werden verschiedene Ideen von Hamiltonizität in planaren und nicht-planaren Graphen behandelt.
https://nbn-resolving.org/urn:nbn:de:gbv:ilm1-2020000294
Maximal ambiguously k-colorable graphs. - In: Journal of combinatorial theory, Bd. 140 (2020), S. 248-262
https://doi.org/10.1016/j.jctb.2019.05.007
Rooted complete minors in line graphs with a Kempe coloring. - In: Graphs and combinatorics, ISSN 1435-5914, Bd. 35 (2019), 2, S. 551-557
https://doi.org/10.1007/s00373-019-02012-7
Nonseparating K4-subdivisions in graphs of minimum degree at least 4. - In: Journal of graph theory, ISSN 1097-0118, Bd. 89 (2018), 2, S. 194-213
Im Titel ist "4" tiefgestellt
https://doi.org/10.1002/jgt.22247
More on foxes. - In: Journal of graph theory, ISSN 1097-0118, Bd. 89 (2018), 2, S. 101-114
https://doi.org/10.1002/jgt.22243
Sum choice number of generalized [theta]-graphs. - In: Discrete mathematics, Bd. 340 (2017), 11, S. 2633-2640
https://doi.org/10.1016/j.disc.2016.11.028
Degree sequences and edge connectivity. - In: Abhandlungen aus dem Mathematischen Seminar der Universität Hamburg, ISSN 1865-8784, Bd. 87 (2017), 2, S. 343-355
https://doi.org/10.1007/s12188-016-0171-0
Unique colorability and clique minors. - In: Journal of graph theory, ISSN 1097-0118, Bd. 85 (2017), 1, S. 207-216
https://doi.org/10.1002/jgt.22056
Antistrong digraphs. - In: Journal of combinatorial theory. . - Orlando, Fla. : Academic Press, 1971- , ZDB-ID: 1469158-9, Bd. 122 (2017), S. 68-90
http://dx.doi.org/10.1016/j.jctb.2016.05.004
Arc-disjoint directed and undirected cycles in digraphs. - In: Journal of graph theory, ISSN 1097-0118, Bd. 83 (2016), 4, S. 406-420
https://doi.org/10.1002/jgt.22006
On graphs double-critical with respect to the colouring number. - In: Discrete mathematics and theoretical computer science, ISSN 1365-8050, Bd. 17 (2015), 2, S. 49-62
http://www.db-thueringen.de/servlets/DocumentServlet?id=26780
(P,Q)-total (r,s)-colorings of graphs. - In: Discrete mathematics, Bd. 338 (2015), 10, S. 1722-1729
http://dx.doi.org/10.1016/j.disc.2014.09.012
Vertex-disjoint directed and undirected cycles in general digraphs. - In: Journal of combinatorial theory. . - Orlando, Fla. : Academic Press, 1971- , ZDB-ID: 1469158-9, Bd. 106 (2014), S. 1-14
http://dx.doi.org/10.1016/j.jctb.2013.10.005
The average degree of minimally contraction-critically 5-connected graphs. - In: Journal of graph theory, ISSN 1097-0118, Bd. 75 (2014), 4, S. 331-354
https://doi.org/10.1002/jgt.21741
On the cycle spectrum of cubic Hamiltonian graphs. - In: Graphs and combinatorics, ISSN 1435-5914, Bd. 29 (2013), 4, S. 1067-1076
We prove lower bounds on the number of different cycle lengths of cubic Hamiltonian graphs that do not contain a fixed subdivision of a claw as an induced subgraph.
https://doi.org/10.1007/s00373-012-1156-0
Minimal connectivity. - In: Topics in structural graph theory, (2013), S. 71-99
https://ebookcentral.proquest.com/lib/ubilm-ebooks/detail.action?docID=1357324
On vertices enforcing a Hamiltonian cycle. - In: Discussiones mathematicae, ISSN 2083-5892, Bd. 33 (2013), 1, S. 71-89
https://doi.org/10.7151/dmgt.1653
Axioms for infinite matroids. - In: Advances in mathematics, ISSN 1090-2082, Bd. 239 (2013), S. 18-46
https://doi.org/10.1016/j.aim.2013.01.011
List colorings of K5-minor-free graphs with special list assignments. - In: Journal of graph theory, ISSN 1097-0118, Bd. 71 (2012), 1/2, S. 18-30
https://doi.org/10.1002/jgt.20628
Weights of induced subgraphs in K1,r-free graphs. - In: Discrete mathematics, Bd. 312 (2012), 16, S. 2429-2432
http://dx.doi.org/10.1016/j.disc.2012.04.025
On the facial Thue choice index of plane graphs. - In: Discrete mathematics, Bd. 312 (2012), 10, S. 1713-1721
http://dx.doi.org/10.1016/j.disc.2012.01.023
A note on semi-steady states in stochastic cellular automata. - In: Autonomous systems: developments and trends, (2011), S. 313-323
Cohabitation of independent sets and dominating sets in trees. - In: Utilitas mathematica, ISSN 0315-3681, Bd. 85 (2011), S. 299-308
Independence, odd girth, and average degree. - In: Journal of graph theory, ISSN 1097-0118, Bd. 67 (2011), 2, S. 96-111
https://doi.org/10.1002/jgt.20518
On cycles and independence in graphs, 2011. - 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
Random procedures for dominating sets in graphs. - In: The electronic journal of combinatorics, ISSN 1077-8926, Volume 17 (2010), R102, Seite 1-15
https://doi.org/10.37236/374
Partitioning a graph into a dominating set, a total dominating set, and something else. - In: Discussiones mathematicae, ISSN 2083-5892, Bd. 30 (2010), 4, S. 563-574
https://doi.org/10.7151/dmgt.1514
On the Hull number of triangle-free graphs. - In: SIAM journal on discrete mathematics, ISSN 1095-7146, Bd. 23 (2010), 4, S. 2163-2172
https://doi.org/10.1137/090751797
Edge-injective and edge-surjective vertex labellings. - In: SIAM journal on discrete mathematics, ISSN 1095-7146, Bd. 24 (2010), 2, S. 666-683
https://doi.org/10.1137/080723065
A note on generalized pentagons. - In: Discrete mathematics, Bd. 310 (2010), 20, S. 2766-2767
http://dx.doi.org/10.1016/j.disc.2010.04.017
Hadwiger numbers and over-dominating colourings. - In: Discrete mathematics, Bd. 310 (2010), 20, S. 2662-2665
http://dx.doi.org/10.1016/j.disc.2010.03.024
Pairs of disjoint dominating sets and the minimum degree of graphs. - In: Graphs and combinatorics, ISSN 1435-5914, Bd. 26 (2010), 3, S. 407-424
https://doi.org/10.1007/s00373-010-0918-9
Cycle length parities and the chromatic number. - In: Journal of graph theory, ISSN 1097-0118, Bd. 64 (2010), 3, S. 210-218
https://doi.org/10.1002/jgt.20450
Minimum degree and density of binary sequences. - In: European journal of combinatorics, Bd. 31 (2010), 7, S. 1936-1945
https://doi.org/10.1016/j.ejc.2010.01.005
Disjoint dominating and total dominating sets in graphs. - In: Discrete applied mathematics, ISSN 1872-6771, Bd. 158 (2010), 15, S. 1615-1523
https://doi.org/10.1016/j.dam.2010.06.004
Scrubbing the Vivaldi network coordinate system. - In: Crossing borders within the ABC, (2010), S. 754-760
http://www.db-thueringen.de/servlets/DocumentServlet?id=17361
Exact leaf powers. - In: Theoretical computer science, Bd. 411 (2010), 31/33, S. 2968-2977
http://dx.doi.org/10.1016/j.tcs.2010.04.027
Über die Dominanzzahl in Graphen unter Nutzung verschiedener Konzepte, 2010. - Online-Ressource (PDF-Datei: 81 S., 707 KB) : Ilmenau, Techn. Univ., Diss., 2010
Parallel als Druckausg. erschienen
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
Packing edge-disjoint cycles in graphs and the cyclomatic number. - In: Discrete mathematics, Bd. 310 (2010), 9, S. 1456-1462
http://dx.doi.org/10.1016/j.disc.2009.07.017
Packing disjoint cycles over vertex cuts. - In: Discrete mathematics, Bd. 310 (2010), 13/14, S. 1974-1978
http://dx.doi.org/10.1016/j.disc.2010.03.009
Cycles, paths, connectivity and diameter in distance graphs. - In: Graph theoretic concepts in computer science, (2010), S. 320-328
http://dx.doi.org/10.1007/978-3-642-11409-0
Some remarks on the geodetic number of a graph. - In: Discrete mathematics, Bd. 310 (2010), 4, S. 832-837
http://dx.doi.org/10.1016/j.disc.2009.09.018
Edge colouring by total labellings. - In: Discrete mathematics, Bd. 310 (2010), 2, S. 199-205
http://dx.doi.org/10.1016/j.disc.2008.09.013
Triangle-free graphs whose independence number equals the degree. - In: Discrete mathematics, Bd. 310 (2010), 3, S. 662-669
http://dx.doi.org/10.1016/j.disc.2009.05.021
An independent dominating set in the complement of a minimum dominating set of a tree. - In: Applied mathematics letters, Bd. 23 (2010), 1, S. 79-81
http://dx.doi.org/10.1016/j.aml.2009.08.008
Constructing a dominating set for bipartite graphs in several rounds. - Ilmenau : Techn. Univ., Inst. für Mathematik, 2009. - Online-Ressource (PDF-Datei: 7 S., 167,9 KB). - (Preprint ; M09,37)
http://www.db-thueringen.de/servlets/DocumentServlet?id=14792
Null-homotopic graphs and triangle-completions of spanning trees. - Ilmenau : Techn. Univ., Inst. für Mathematik, 2009. - Online-Ressource (PDF-Datei: 4 S., 144,3 KB). - (Preprint ; M09,35)
http://www.db-thueringen.de/servlets/DocumentServlet?id=14440
Finite sholander trees, trees, and their betweennesses. - Ilmenau : Techn. Univ., Inst. für Mathematik, 2009. - Online-Ressource (PDF-Datei: 8 S., 204,6 KB). - (Preprint ; M09,34)
http://www.db-thueringen.de/servlets/DocumentServlet?id=14439
Strict betweennesses induced by posets as well as by graphs. - Ilmenau : Techn. Univ., Inst. für Mathematik, 2009. - Online-Ressource (PDF-Datei: 8 S., 185,9 KB). - (Preprint ; M09,33)
http://www.db-thueringen.de/servlets/DocumentServlet?id=14426
Independence, odd girth, and average degree. - Ilmenau : Techn. Univ., Inst. für Mathematik, 2009. - Online-Ressource (PDF-Datei: 15 S., 232,7 KB). - (Preprint ; M09,32)
http://www.db-thueringen.de/servlets/DocumentServlet?id=14425
Independence in connected graphs. - Ilmenau : Techn. Univ., Inst. für Mathematik, 2009. - Online-Ressource (PDF-Datei: 10 S., 193,9 KB). - (Preprint ; M09,31)
http://www.db-thueringen.de/servlets/DocumentServlet?id=14424
Remarks about disjoint dominating sets. - In: Discrete mathematics, Bd. 309 (2009), 23/24, S. 6451-6458
http://dx.doi.org/10.1016/j.disc.2009.06.017
Fast buffering for optimizing worst slack and resource consumption in repeater trees. - In: Proceedings of the 2009 ACM International Symposium on Physical Design, ISBN 978-1-60558-449-2, (2009), S. 43-50
A generalization of Dijkstra's shortest path algorithm with applications to VLSI routing. - In: Journal of discrete algorithms, Bd. 7 (2009), 4, S. 377-390
http://dx.doi.org/10.1016/j.jda.2007.08.003
A game theoretic approach to graph problems. - In: 9th International Conference on Innovative Internet Community Systems, I2CS 2009, (2009), S. 149-156
Binary trees with choosable edge lengths. - In: Information processing letters, ISSN 1872-6119, Bd. 109 (2009), 18, S. 1087-1092
http://dx.doi.org/10.1016/j.ipl.2009.07.002
Interpolating between bounds on the independence number. - Ilmenau : Techn. Univ., Inst. für Mathematik, 2009. - Online-Ressource (PDF-Datei: 9 S., 169,8 KB). - (Preprint ; M09,26)
http://www.db-thueringen.de/servlets/DocumentServlet?id=13756
Partitioning a graph into a dominating set, a total dominating set, and something else. - Ilmenau : Techn. Univ., Inst. für Mathematik, 2009. - Online-Ressource (PDF-Datei: 11 S., 331,5 KB). - (Preprint ; M09,25)
http://www.db-thueringen.de/servlets/DocumentServlet?id=13714
An independent dominating set in the complement of a minimum dominating set of a tree. - Ilmenau : Techn. Univ., Inst. für Mathematik, 2009. - Online-Ressource (PDF-Datei: 4 S., 142,9 KB). - (Preprint ; M09,24)
http://www.db-thueringen.de/servlets/DocumentServlet?id=13707
The repeater tree construction problem. - Ilmenau : Techn. Univ., Inst. für Mathematik, 2009. - Online-Ressource (PDF-Datei: 9 S., 193,8 KB). - (Preprint ; M09,23)
http://www.db-thueringen.de/servlets/DocumentServlet?id=13706
Minimum degree and density of binary sequences. - Ilmenau : Techn. Univ., Inst. für Mathematik, 2009. - Online-Ressource (PDF-Datei: 16 S., 224,4 KB). - (Preprint ; M09,22)
http://www.db-thueringen.de/servlets/DocumentServlet?id=13705
An [Omega] (n log n) lower bound for computing the sum of even-ranked elements. - In: Information processing letters, ISSN 1872-6119, Bd. 109 (2009), 16, S. 955-956
http://dx.doi.org/10.1016/j.ipl.2009.05.004
Graphs of odd girth 7 with large degree. - In: Electronic notes in discrete mathematics, ISSN 1571-0653, Bd. 34 (2009), S. 89-93
http://dx.doi.org/10.1016/j.endm.2009.07.015
Precoloring extension for K4-minor-free graphs. - In: Journal of graph theory, ISSN 1097-0118, Bd. 60 (2009), 4, S. 284-294
https://doi.org/10.1002/jgt.20358
Learning of winning strategies for terminal games with linear-size memory. - In: International journal of game theory, ISSN 1432-1270, Bd. 38 (2009), 2, S. 155-168
http://dx.doi.org/10.1007/s00182-008-0142-5
Hyponormal and strongly hyponormal matrices in inner product spaces. - Ilmenau : Techn. Univ., Inst. für Mathematik, 2009. - Online-Ressource (PDF-Datei: 30 S., 277,6 KB). - (Preprint ; M09,06)
http://www.db-thueringen.de/servlets/DocumentServlet?id=12959
A forbidden induced subgraph characterization of distance-hereditary 5-leaf powers. - In: Discrete mathematics, Bd. 309 (2009), 12, S. 3843-3852
http://dx.doi.org/10.1016/j.disc.2008.10.025
Edge irregular total labellings for graphs of linear size. - In: Discrete mathematics, Bd. 309 (2009), 12, S. 3786-3792
http://dx.doi.org/10.1016/j.disc.2008.10.009
On packing shortest cycles in graphs. - In: Information processing letters, ISSN 1872-6119, Bd. 109 (2009), 14, S. 816-821
http://dx.doi.org/10.1016/j.ipl.2009.04.001
Packing disjoint cycles over vertex cuts. - Ilmenau : Techn. Univ., Inst. für Mathematik, 2009. - Online-Ressource (PDF-Datei: 9 S., 166,5 KB). - (Preprint ; M09,17)
http://www.db-thueringen.de/servlets/DocumentServlet?id=12995
An [Omega] (n log n) lower bound for computing the sum of even-ranked elements. - Ilmenau : Techn. Univ., Inst. für Mathematik, 2009. - Online-Ressource (PDF-Datei: 3 S., 136,5 KB). - (Preprint ; M09,16)
http://www.db-thueringen.de/servlets/DocumentServlet?id=12993
Some remarks on the geodetic number of a graph. - Ilmenau : Techn. Univ., Inst. für Mathematik, 2009. - Online-Ressource (PDF-Datei: 10 S., 184,5 KB). - (Preprint ; M09,15)
http://www.db-thueringen.de/servlets/DocumentServlet?id=12992
On the convexity number of graphs. - Ilmenau : Techn. Univ., Inst. für Mathematik, 2009. - Online-Ressource (PDF-Datei: 14 S., 340,1 KB). - (Preprint ; M09,14)
http://www.db-thueringen.de/servlets/DocumentServlet?id=12991
On the hull number of triangle-free graphs. - Ilmenau : Techn. Univ., Inst. für Mathematik, 2009. - Online-Ressource (PDF-Datei: 12 S., 223,7 KB). - (Preprint ; M09,13)
http://www.db-thueringen.de/servlets/DocumentServlet?id=12990
On spanning tree congestion. - In: Discrete mathematics, Bd. 309 (2009), 13, S. 4653-4655
http://dx.doi.org/10.1016/j.disc.2009.01.012
Linear connectivity forces large complete bipartite minors. - In: Journal of combinatorial theory. . - Orlando, Fla. : Academic Press, 1971- , ZDB-ID: 1469158-9, Bd. 99 (2009), 3, S. 557-582
http://dx.doi.org/10.1016/j.jctb.2008.07.006
Connectivity and diameter in distance graphs. - Ilmenau : Techn. Univ., Inst. für Mathematik, 2009. - Online-Ressource (PDF-Datei: 17 S., 177 KB). - (Preprint ; M09,12)
http://www.db-thueringen.de/servlets/DocumentServlet?id=12976
Long cycles and paths in distance graphs. - Ilmenau : Techn. Univ., Inst. für Mathematik, 2009. - Online-Ressource (PDF-Datei: 12 S., 242 KB). - (Preprint ; M09,11)
http://www.db-thueringen.de/servlets/DocumentServlet?id=12973
Powers of cycles, powers of paths, and distance graphs. - Ilmenau : Techn. Univ., Inst. für Mathematik, 2009. - Online-Ressource (PDF-Datei: 13 S., 183,6 KB). - (Preprint ; M09,10)
http://www.db-thueringen.de/servlets/DocumentServlet?id=12969
Pairs of disjoint dominating sets and the minimum degree of graphs. - Ilmenau : Techn. Univ., Inst. für Mathematik, 2009. - Online-Ressource (PDF-Datei: 19 S., 193,5 KB). - (Preprint ; M09,09)
http://www.db-thueringen.de/servlets/DocumentServlet?id=12978
Graphs with many vertex-disjoint cycles. - Ilmenau : Techn. Univ., Inst. für Mathematik, 2009. - Online-Ressource (PDF-Datei: 10 S., 156,4 KB). - (Preprint ; M09,08)
http://www.db-thueringen.de/servlets/DocumentServlet?id=12963
On packing shortest cycles in graphs. - Ilmenau : Techn. Univ., Inst. für Mathematik, 2009. - Online-Ressource (PDF-Datei: 9 S., 183,6 KB). - (Preprint ; M09,07)
http://www.db-thueringen.de/servlets/DocumentServlet?id=12960
On the existence of edge cuts leaving several large components. - In: Discrete mathematics, Bd. 309 (2009), 6, S. 1703-1707
http://dx.doi.org/10.1016/j.disc.2008.02.014
Many disjoint dense subgraphs versus large k-connected subgraphs in large graphs with given edge density. - In: Discrete mathematics, Bd. 309 (2009), 4, S. 997-1000
http://dx.doi.org/10.1016/j.disc.2008.01.010
On the OBDD size for graphs of bounded tree- and clique-width. - In: Discrete mathematics, Bd. 309 (2009), 4, S. 843-851
http://dx.doi.org/10.1016/j.disc.2008.01.022
Domination in bipartite graphs. - In: Discrete mathematics, Bd. 309 (2009), 1, S. 113-122
http://dx.doi.org/10.1016/j.disc.2007.12.051
Domination in cubic graphs of large girth. - In: Computational geometry and graph theory, (2008), S. 186-190
http://dx.doi.org/10.1007/978-3-540-89550-3_20
Domination in graphs of minimum degree at least two and large girth. - In: Graphs and combinatorics, ISSN 1435-5914, Bd. 24 (2008), 1, S. 37-46
https://doi.org/10.1007/s00373-007-0770-8
On the cost of optimal alphabetic code trees with unequal letter costs. - In: European journal of combinatorics, Bd. 29 (2008), 2, S. 386-394
https://doi.org/10.1016/j.ejc.2007.02.014
A note on domination, girth and minimum degree. - In: Discrete mathematics, Bd. 308 (2008), 11, S. 2325-2329
http://dx.doi.org/10.1016/j.disc.2006.09.055
On a conjecture about edge irregular total labelings. - In: Journal of graph theory, ISSN 1097-0118, Bd. 57 (2008), 4, S. 333-343
https://doi.org/10.1002/jgt.20287
A conjecture of Borodin and a coloring of Grünbaum. - In: Journal of graph theory, ISSN 1097-0118, Bd. 58 (2008), 2, S. 139-147
https://doi.org/10.1002/jgt.20299
The independence number in graphs of maximum degree three. - In: Discrete mathematics, Bd. 308 (2008), 23, S. 5829-5833
http://dx.doi.org/10.1016/j.disc.2007.10.029
Some remarks on [lambda]p,q-connectedness. - In: Discrete mathematics, Bd. 308 (2008), 23, S. 5562-5569
http://dx.doi.org/10.1016/j.disc.2007.10.008
Cyclic sums, network sharing and restricted edge cuts in graphs with long cycles. - In: Networks, ISSN 1097-0037, Bd. 52 (2008), 4, S. 252-255
http://dx.doi.org/10.1002/net.20243
A class of problems for which cyclic relaxation converges linearly. - In: Computational optimization and applications, ISSN 1573-2894, Bd. 41 (2008), 1, S. 53-60
https://doi.org/10.1007/s10589-007-9094-0
[alpha]-Domination perfect trees. - In: Discrete mathematics, Bd. 308 (2008), 15, S. 3187-3198
http://dx.doi.org/doi:10.1016/j.disc.2007.06.043
Packing edge-disjoint cycles in graphs and the cyclomatic number. - Ilmenau : Techn. Univ., Inst. für Mathematik, 2008. - Online-Ressource (PDF-Datei: 11 S., 183,1 KB). - (Preprint ; M08,25)
http://www.db-thueringen.de/servlets/DocumentServlet?id=11839
Pairs of disjoint dominating sets and the minimum degree of graphs. - Ilmenau : Techn. Univ., Inst. für Mathematik, 2008. - Online-Ressource (PDF-Datei: 19 S., 193,5 KB). - (Preprint ; M08,26)
http://www.db-thueringen.de/servlets/DocumentServlet?id=11841
Cycle length parities and the chromatic number. - Ilmenau : Techn. Univ., Inst. für Mathematik, 2008. - Online-Ressource (PDF-Datei: 8 S., 199,4 KB). - (Preprint ; M08,27)
http://www.db-thueringen.de/servlets/DocumentServlet?id=11842
On spanning tree congestion. - Ilmenau : Techn. Univ., Inst. für Mathematik, 2008. - 4 S. = 129,3 KB, Text. - (Preprint ; M08,18)
http://www.db-thueringen.de/servlets/DocumentServlet?id=10904
Edge-injective and edge-surjective vertex labellings. - Ilmenau : Techn. Univ., Inst. für Mathematik, 2008. - 20 S. = 224,8 KB, Text. - (Preprint ; M08,17)
http://www.db-thueringen.de/servlets/DocumentServlet?id=10902
Cohabitation of independent sets and dominating sets in trees. - Ilmenau : Techn. Univ., Inst. für Mathematik, 2008. - 9 S. = 146,3 KB, Text. - (Preprint ; M08,11)
http://www.db-thueringen.de/servlets/DocumentServlet?id=10404
Random procedures for dominating sets in graphs. - Ilmenau : Techn. Univ., Inst. für Mathematik, 2008. - 14 S. = 209,1 KB, Text. - (Preprint ; M08,10)
http://www.db-thueringen.de/servlets/DocumentServlet?id=10403
Remarks about disjoint dominating sets. - Ilmenau : Techn. Univ., Inst. für Mathematik, 2008. - 13 S. = 203,8 KB, Text. - (Preprint ; M08,09)
http://www.db-thueringen.de/servlets/DocumentServlet?id=10402
Graph edge coloring: Tashkinov trees and Goldberg's conjecture. - Ilmenau : Techn. Univ., Inst. für Mathematik, 2008. - 40 S. = 342,2 KB, Text. - (Preprint ; M08,07)
http://www.db-thueringen.de/servlets/DocumentServlet?id=10382
Chiraptophobic cockroaches evading a torch light. - Ilmenau : Techn. Univ., Inst. für Mathematik, 2008. - 10 S. = 223 KB, Text. - (Preprint ; M08,02)
http://www.db-thueringen.de/servlets/DocumentServlet?id=9917
Dominating and large induced trees in regular graphs. - In: Discrete mathematics, Bd. 307 (2007), 24, S. 3177-3186
http://dx.doi.org/10.1016/j.disc.2007.03.043
Timing optimization by restructuring long combinatorial paths. - In: IEEE/ACM International Conference on Computer-Aided Design, 2007, ISBN 978-1-4244-1381-2, (2007), S. 536-543
http://dx.doi.org/10.1109/ICCAD.2007.4397320
Precoloring extension for K4-minor-free graphs. - Ilmenau : Techn. Univ., Inst. für Mathematik, 2007. - 13 S. = 185,3 KB, Text. - (Preprint ; M07,26)
http://www.db-thueringen.de/servlets/DocumentServlet?id=9798
The relative clique-width of a graph. - In: Journal of combinatorial theory. . - Orlando, Fla. : Academic Press, 1971- , ZDB-ID: 1469158-9, Bd. 97 (2007), 5, S. 846-858
http://dx.doi.org/10.1016/j.jctb.2007.04.001
Regular weighted graphs without positive cuts. - In: Ars combinatoria, ISSN 0381-7032, Bd. 84 (2007), 3, S. 13-22
BonnTools : mathematical innovation for layout and timing closure of systems on a chip. - In: Proceedings of the IEEE, ISSN 1558-2256, Bd. 95 (2007), 3, S. 555-572
http://dx.doi.org/10.1109/JPROC.2006.889373
The independence number in graphs of maximum degree three. - Ilmenau : Techn. Univ., Inst. für Mathematik, 2007. - 7 S. = 130,9 KB, Text. - (Preprint ; M07,15)
http://www.db-thueringen.de/servlets/DocumentServlet?id=9407
Locally dense independent sets in regular graphs of large girth. - Ilmenau : Techn. Univ., Inst. für Mathematik, 2007. - 21 S. = 219,4 KB, Text. - (Preprint ; M07,14)
http://www.db-thueringen.de/servlets/DocumentServlet?id=9401
Edge irregular total labellings for graphs of linear size. - Ilmenau : Techn. Univ., Inst. für Mathematik, 2007. - 10 S. = 163,3 KB, Text. - (Preprint ; M07,12)
http://www.db-thueringen.de/servlets/DocumentServlet?id=9399
Some remarks on [lambda]p,q-connectedness. - Ilmenau : Techn. Univ., Inst. für Mathematik, 2007. - 13 S. = 203,3 KB, Text. - (Preprint ; M07,11)
http://www.db-thueringen.de/servlets/DocumentServlet?id=9398
On the existence of edge cuts leaving several large components. - Ilmenau : Techn. Univ., Inst. für Mathematik, 2007. - 8 S. = 171,8 KB, Text. - (Preprint ; M07,10)
http://www.db-thueringen.de/servlets/DocumentServlet?id=9397
Domination in graphs of minimum degree at least two and large girth. - Ilmenau : Techn. Univ., Inst. für Mathematik, 2007. - 10 S. = 164,4 KB, Text. - (Preprint ; M07,09)
http://www.db-thueringen.de/servlets/DocumentServlet?id=9374
Domination in bipartite graphs. - Ilmenau : Techn. Univ., Inst. für Mathematik, 2007. - Online-Ressource (13 S. = 261,7 KB, Text). - (Preprint ; M07,08)Literaturverz. S. 12 - 13
http://www.db-thueringen.de/servlets/DocumentServlet?id=9373
Domination in cubic graphs of large girth. - Ilmenau : Techn. Univ., Inst. für Mathematik, 2007. - 6 S. = 133,9 KB, Text. - (Preprint ; M07,07)
http://www.db-thueringen.de/servlets/DocumentServlet?id=9353
Cyclic sums, network sharing and restricted edge cuts in graphs with long cycles. - Ilmenau : Techn. Univ., Inst. für Mathematik, 2007. - 9 S. = 165,8 KB, Text. - (Preprint ; M07,06)
http://www.db-thueringen.de/servlets/DocumentServlet?id=9352
On F-independence in graphs. - Ilmenau : Techn. Univ., Inst. für Mathematik, 2007. - 7 S. = 145,8 KB. - (Preprint ; M07,05)
http://www.db-thueringen.de/servlets/DocumentServlet?id=9351
Edge colouring by total labellings. - Ilmenau : Techn. Univ., Inst. für Mathematik, 2007. - 13 S. = 181,5 KB, Text. - (Preprint ; M07,03)
http://www.db-thueringen.de/servlets/DocumentServlet?id=9347
Vertex-oblique graphs. - In: Discrete mathematics, 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
New bounds on the k-domination number and the k-tuple domination number. - In: Applied mathematics letters, Bd. 20 (2007), 1, S. 98-102
http://dx.doi.org/10.1016/j.aml.2006.03.006
Small step-dominating sets in trees. - In: Discrete mathematics, Bd. 307 (2007), 9/10, S. 1212-1215
http://dx.doi.org/10.1016/j.disc.2006.07.038
The delay of circuits whose inputs have specified arrival times. - In: Discrete applied mathematics, ISSN 1872-6771, Bd. 155 (2007), 10, S. 1233-1243
https://doi.org/10.1016/j.dam.2006.10.013
On the irregularity of bipartite graphs. - In: Discrete mathematics, Bd. 307 (2007), 11/12, S. 1467-1472
http://dx.doi.org/10.1016/j.disc.2006.09.038
Reconstructing graphs from size and degree properties of their induced k-subgraphs. - In: Discrete mathematics, Bd. 307 (2007), 6, S. 694-703
http://dx.doi.org/10.1016/j.disc.2006.06.031
On short paths through prescribed vertices of a graph. - In: Discrete mathematics, Bd. 307 (2007), 7/8, S. 905-910
http://dx.doi.org/10.1016/j.disc.2005.11.040
Almost every graph is vertex-oblique. - In: Discrete mathematics, Bd. 307 (2007), 7/8, S. 983-989
http://dx.doi.org/10.1016/j.disc.2005.11.054
Extremal problems for imbalanced edges. - In: Graphs and combinatorics, ISSN 1435-5914, Bd. 22 (2006), 1, S. 103-111
http://dx.doi.org/10.1007/s00373-005-0643-y
t-partitions and s-complete t-partitions of a graph. - In: The Australasian journal of combinatorics, ISSN 1034-4942, Bd. 36 (2006), S. 295-302
Distance-hereditary 5-leaf powers. - In: Electronic notes in discrete mathematics, ISSN 1571-0653, Bd. 27 (2006), S. 85-86
http://dx.doi.org/10.1016/j.endm.2006.08.068
Delay optimization of linear depth boolean circuits with prescribed input arrival times. - In: Journal of discrete algorithms, Bd. 4 (2006), 4, S. 526-537
http://dx.doi.org/10.1016/j.jda.2005.06.006
On short cycles through prescribed vertices of a polyhedral graph. - In: Discussiones mathematicae, ISSN 2083-5892, Bd. 25 (2005), 3, S. 419-426
https://doi.org/10.7151/dmgt.1293
Evaluating profiling and query expansion methods for P2P information retrieval. - In: Proceedings of the 2005 ACM Workshop on Information Retrieval in Peer-to-Peer Networks, (2005), S. 1-8
List version of L(d,s)-labelings. - In: Theoretical computer science, Bd. 349 (2005), 1, S. 92-98
http://dx.doi.org/10.1016/j.tcs.2005.09.032
Disjoint Kr-minors in large graphs with given average degree. - In: European journal of combinatorics, Bd. 26 (2005), 3/4, S. 289-292
Im Titel ist "r" tiefgestellt
https://doi.org/10.1016/j.ejc.2003.12.017
Oblique graphs, 2005. - Online-Ressource (PDF-Datei: 69 S., 470 KB) : Ilmenau, Techn. Univ., Diss., 2005
Parallel als Druckausg. erschienen
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
Edge-oblique polyhedral graphs. - In: Discrete applied mathematics, ISSN 1872-6771, 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.
https://doi.org/10.1016/S0166-218X(03)00447-5
On short cycles through prescribed vertices of a graph. - In: Discrete mathematics, Bd. 286 (2004), 1/2, S. 67-74
http://dx.doi.org/10.1016/j.disc.2003.11.047
Subdivisions of large complete bipartite graphs and long induced paths in k-connected graphs. - In: Journal of graph theory, ISSN 1097-0118, Bd. 45 (2004), 4, S. 270-274
https://doi.org/10.1002/jgt.10161
Das graphentheoretische Dominanzproblem als stetiges Optimierungsproblem, 2004. - Online-Ressource (PDF-Datei: 79 S., 395 KB) : Ilmenau, Techn. Univ., Diss., 2004
Parallel als Druckausg. erschienen
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
Domination, packing and excluded minors. - In: The electronic journal of combinatorics, ISSN 1077-8926, Volume 10 (2003), N9, Seite 1-6
https://doi.org/10.37236/1749
Some news about oblique graphs. - In: Discussiones mathematicae, ISSN 2083-5892, 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.
https://doi.org/10.7151/dmgt.1157
On vertex-degree restricted subgraphs in polyhedral graphs. - In: Discrete mathematics, Bd. 256 (2002), 1/2, S. 105-114
http://dx.doi.org/10.1016/S0012-365X(01)00368-5
Polyhedral graphs with restricted number of faces of the same type. - In: Discrete mathematics, Bd. 244 (2002), 1/3, S. 473-478
http://dx.doi.org/10.1016/S0012-365X(01)00103-0
On light graphs in the family of 4-connected planar graphs. - In: Discrete mathematics, Bd. 251 (2002), 1/3, S. 103-107
http://dx.doi.org/10.1016/S0012-365X(01)00330-2
Labeled K2,t minors in plane graphs. - In: Journal of combinatorial theory. . - Orlando, Fla. : Academic Press, 1971- , ZDB-ID: 1469158-9, Bd. 84 (2002), 2, S. 291-300
http://dx.doi.org/10.1006/jctb.2001.2083
Ka,k minors in graphs of bounded tree-width. - In: Journal of combinatorial theory. . - Orlando, Fla. : Academic Press, 1971- , ZDB-ID: 1469158-9, Bd. 86 (2002), 1, S. 133-147
http://dx.doi.org/10.1006/jctb.2002.2119
On the domination number of a graph. - In: Discrete mathematics, Bd. 251 (2002), 1/3, S. 129-136
http://dx.doi.org/10.1016/S0012-365x(01)00334-x
Polyhedral graphs with extreme numbers of types of faces. - In: Discrete applied mathematics, ISSN 1872-6771, Bd. 120 (2002), 1/3, S. 263-274
https://doi.org/10.1016/S0166-218X(01)00295-5
Leichte Teilgraphen in Polyedergraphen, 2002. - 2,63 MB, Text : Ilmenau, Techn. Univ., Diss., 2002
Parallel als Druckausg. erschienen
http://www.db-thueringen.de/servlets/DocumentServlet?id=1165
Edge-oblique polyhedral graphs. - In: Electronic notes in discrete mathematics, ISSN 1571-0653, Bd. 8 (2001), S. 90-93
http://dx.doi.org/10.1016/S1571-0653(05)80089-7
A note on the domination number of a bipartite graph. - In: Annals of combinatorics, ISSN 0219-3094, Bd. 5 (2001), 2, S. 175-178
http://dx.doi.org/10.1007/PL00001298
Domination, packing and excluded minors. - Ljubljana : Institute of Mathematics, Physics and Mechanics, Department of Mathematics, University of Ljubljana, 2001. - 6 Seiten. - (Preprint series ; 39,734)Literaturverzeichnis: Seite 6
Non-hamiltonian polyhedral graphs with two types of faces. - In: Discrete mathematics, Bd. 213 (2000), 1/3, S. 105-113
http://dx.doi.org/10.1016/S0012-365X(99)00171-5
Über gleichschenklige Tetraeder. - In: Mathematik in der Schule, ISSN 0465-3750, Bd. 38 (2000), 2, S. 90-95
On vertex-degree restricted paths in polyhedral graphs. - In: Discrete mathematics, Bd. 212 (2000), 1/2, S. 61-73
http://dx.doi.org/10.1016/S0012-365X(99)00209-5
Polyhedral graphs with extreme numbers of types of faces. - In: Electronic notes in discrete mathematics, ISSN 1571-0653, Bd. 3 (1999), S. 205-207
http://dx.doi.org/10.1016/S1571-0653(05)80057-5
On vertex-degree restricted paths in $4$-connected planar graphs. - In: Cycles and colourings '97, (1999), S. 1-13
On dominating sets and independent sets of graphs. - In: Combinatorics, probability & computing, ISSN 1469-2163, Bd. 8 (1999), 6, S. 547-553
https://doi.org/10.1017/S0963548399004034
Subgraphs with restricted degrees of their vertices in planar graphs. - In: Discrete mathematics, Bd. 191 (1998), 1/3, S. 83-90
https://doi.org/10.1016/S0012-365X(98)00095-8
A planarity criterion bipartite graphs. - In: Discrete mathematics, Bd. 191 (1998), 1, S. 31-43
http://dx.doi.org/10.1016/S0012-365X(98)00090-9
Subgraphs with restricted degrees of their vertices in planar 3-connected graphs. - In: Graphs and combinatorics, ISSN 1435-5914, Bd. 13 (1997), 3, S. 245-250
We have proved that every 3-connected planar graph G either contains a path on k vertices each of which has degree at most 5k or does not contain any path on k vertices; the bound 5k is the best possible. Moreover, for every connected planar graph H other than a path and for every integer m ≥ 3 there is a 3-connected planar graph G such that each copy of H in G contains a vertex of degree at least m.
https://doi.org/10.1007/BF03353001
A nonhamiltonian five-regular multitriangular polyhedral graph. - In: Discrete mathematics, Bd. 150 (1996), 1/3, S. 387-392
http://dx.doi.org/10.1016/0012-365X(95)00203-9
An inequality concerning edges of minor weight in convex 3-polytopes. - In: Discussiones mathematicae, ISSN 2083-5892, Bd. 16 (1996), 1, S. 81-87
https://doi.org/10.7151/dmgt.1024
5-regular 3-polytopal graphs with edges of only two types and shortness exponents less than one. - In: Discrete mathematics, Bd. 150 (1996), 1/3, S. 143-153
http://dx.doi.org/10.1016/0012-365X(95)00183-W
Chromatic number of prime distance graphs. - In: Discrete applied mathematics, ISSN 1872-6771, Bd. 51 (1994), 1/2, S. 197-209
https://doi.org/10.1016/0166-218X(94)90109-0
A lower bound for the shortness coefficient of a class of graphs. - In: Discrete applied mathematics, ISSN 1872-6771, Bd. 51 (1994), 1/2, S. 103-105
https://doi.org/10.1016/0166-218X(94)90098-1
On paths of greedoids and a minor characterization. - In: European journal of combinatorics, Bd. 15 (1994), 3, S. 239-244
https://doi.org/10.1006/eujc.1994.1025
On colouring partial joins of a complete graph and a cycle. - In: Mathematische Nachrichten, ISSN 1522-2616, Bd. 163 (1993), 1, S. 109-116
http://dx.doi.org/10.1002/mana.19931630111
List colourings of planar graphs. - In: Discrete mathematics, Bd. 120 (1993), 1/3, S. 215-219
http://dx.doi.org/10.1016/0012-365X(93)90579-I
On Hadwiger's number - a problem of the Nordhaus-Gaddum type. - In: Discrete mathematics, Bd. 101 (1992), 1/3, S. 307-317
http://dx.doi.org/10.1016/0012-365X(92)90611-I
How to calculate the number of perfect matchings in finite sections of certain infinite plane graphs. - In: Discrete mathematics, Bd. 101 (1992), 3, S. 279-284
http://dx.doi.org/10.1016/0012-365X(92)90608-I
A solution to a colouring problem of P. Erd˝os. - In: Discrete mathematics, Bd. 101 (1992), 1/3, S. 39-48
http://dx.doi.org/10.1016/0012-365X(92)90588-7
A contribution to the theory of Tutte's V - and W -function. - In: Discrete mathematics, Bd. 104 (1992), 3, S. 281-292
http://dx.doi.org/10.1016/0012-365X(92)90450-T
[Rezension von: Advances in the theory of benzenoid hydrocarbons, 2, with 58 tables, with contributions by J. Brunvoll ...]. - In: Zeitschrift für physikalische Chemie. - Berlin : De Gruyter, ISSN 2196-7156, S. 121-122
, Rezension von : Advances in the theory of benzenoid hydrocarbons ; 2:with 58 tables / Brunvoll, J.. - Berlin [u.a.] : Springer, 1992
http://dx.doi.org/10.1524/zpch.1992.177.Part_1.121a
Counting perfect matchings in hexagonal chains. - In: Chemical physics letters, Bd. 196 (1992), 5, S. 525-528
http://dx.doi.org/10.1016/0009-2614(92)85731-O
Two codes for hexagonal systems. - In: Match, ISSN 0340-6253, Bd. 28 (1992), S. 209-218
Über Anzahlen von Linearfaktoren in hexagonalen Bändern. - In: Match, ISSN 0340-6253, Bd. 28 (1992), S. 181-208
Eine dritte graphentheoretische Bemerkung zur Resonanztheorie benzenoider Kohlenwasserstoffe. - In: Match, ISSN 0340-6253, Bd. 28 (1992), S. 165-180
On the chromatic number of special distance graphs. - In: Discrete mathematics, Bd. 97 (1991), 1/3, S. 395-397
http://dx.doi.org/10.1016/0012-365X(91)90454-A
Zur Generation von Software aus Petrinetzen auf der Basis der Markenflußanalyse. - In: Internationales wissenschaftliches Kolloquium / Technische Hochschule Ilmenau, ISSN 0374-3365, Bd. 36 (1991), 4, S. 781-786