Eylem Seç
Problems in Extremal Graph Theory
Başlık:
Problems in Extremal Graph Theory
Yazar:
Popielarz, Kamil Krzesimir, author.
ISBN:
9780355984187
Yazar Ek Girişi:
Fiziksel Tanımlama:
1 electronic resource (116 pages)
Genel Not:
Source: Dissertation Abstracts International, Volume: 79-10(E), Section: B.
Advisors: Béla Bollobás Committee members: Paul Balister; Béla Bollobás; James T. Campbell; Ebenezer O. George; David Grynkiewicz.
Özet:
This dissertation consists of six chapters concerning a variety of topics in extremal graph theory. Chapter 1 is dedicated to the results in the papers with Antonio Girao, Gabor Meszaros, and Richard Snyder. We say that a graph is path-pairable if for any pairing of its vertices there exist edge disjoint paths joining the vertices in each pair. We study the extremal behavior of maximum degree and diameter in some classes of path-pairable graphs. In particular we show that a path-pairable planar graph must have a vertex of linear degree. In Chapter 2 we present a joint work with Antonio Girao and Teeradej Kittipassorn. Given graphs G and H, we say that a graph F is H-saturated in G if F is H-free subgraph of G, but addition of any edge from E(G) to F creates a copy of H. Here we deal with the case when G is a complete k-partite graph with n vertices in each class, and H is a complete graph on r vertices. We prove bounds, which are tight for infinitely many values of k and r, on the minimal number of edges in a H-saturated graph in G, for this choice of G and H, answering questions of Ferrara, Jacobson, Pfender, and Wenger; and generalizing a result of Roberts. Chapter 3 is about a joint paper with Antonio Girao and Teeradej Kittipassorn. A coloring of the vertices of a digraph D is called majority coloring if no vertex of D receives the same color as more than half of its outneighbours. This was introduced by van der Zypen in 2016. Recently, Kreutzer, Oum, Seymour, van der Zypen, and Wood posed a number of problems related to this notion: here we solve several of them. In Chapter 4 we present a joint work with Antonio Girao. We show that given any integer k there exist functions g1(k), g2(k) such that the following holds. For any graph G with maximum degree Delta one can remove fewer than g1(k) Delta
{1/2}vertices from G so that the remaining graph H has k vertices of the same degree at least Delta(H) --- g2(k). It is an approximate version of conjecture of Caro and Yuster; and Caro, Lauri, and Zarb, who conjectured that g2(k) = 0. Chapter 5 concerns results obtained together with Kazuhiro Nomoto, Julian Sahasrabudhe, and Richard Snyder. We study a graph parameter, the graph burning number, which is supposed to measure the speed of the spread of contagion in a graph. We prove tight bounds on the graph burning number of some classes of graphs and make a progress towards a conjecture of Bonato, Janssen, and Roshanbin about the upper bound of graph burning number of connected graphs. In Chapter 6 we present a joint work with Teeradej Kittipassorn. We study the set of possible numbers of triangles a graph on a given number of vertices can have. Among other results, we determine the asymptotic behavior of the smallest positive integer m such that there is no graph on n vertices with exactly m copies of a triangle. We also prove similar results when we replace triangle by any fixed connected graph.
Notlar:
School code: 1194
Konu Başlığı:
Tüzel Kişi Ek Girişi:
Mevcut:*
Yer Numarası | Demirbaş Numarası | Shelf Location | Lokasyon / Statüsü / İade Tarihi |
---|---|---|---|
XX(679338.1) | 679338-1001 | Proquest E-Tez Koleksiyonu | Arıyor... |
On Order
Liste seç
Bunu varsayılan liste yap.
Öğeler başarıyla eklendi
Öğeler eklenirken hata oldu. Lütfen tekrar deneyiniz.
:
Select An Item
Data usage warning: You will receive one text message for each title you selected.
Standard text messaging rates apply.