Temat: extremal graph theory - Katalog OPAC zbiorów

Skocz do pozycji: 1.

Tytuł:: Pancyclicity when each Cycle Must Pass Exactly k Hamilton Cycle Chords
Autorzy:: Affif Chaouche, Fatima
Rutherford, Carrie G.
Whitty, Robin W.
Powiązania:: https://bibliotekanauki.pl/articles/31339337.pdf
Data publikacji:: 2015-08-01
Wydawca:: Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:: extremal graph theory
pancyclic graph
Hamilton cycle
Opis:: It is known that Θ(log n) chords must be added to an n-cycle to produce a pancyclic graph; for vertex pancyclicity, where every vertex belongs to a cycle of every length, Θ(n) chords are required. A possibly ‘intermediate’ variation is the following: given k, 1 ≤ k ≤ n, how many chords must be added to ensure that there exist cycles of every possible length each of which passes exactly k chords? For fixed k, we establish a lower bound of Ω(n^1/k) on the growth rate.
Źródło:: Discussiones Mathematicae Graph Theory; 2015, 35, 3; 533-539
2083-5892
Pojawia się w:: Discussiones Mathematicae Graph Theory
Dostawca treści:: Biblioteka Nauki

Artykuł

Skocz do pozycji: 2.

Tytuł:: A Ramsey-type theorem for multiple disjoint copies of induced subgraphs
Autorzy:: Nakamigawa, Tomoki
Powiązania:: https://bibliotekanauki.pl/articles/30148231.pdf
Data publikacji:: 2014-05-01
Wydawca:: Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:: graph decomposition
induced subgraph
graph Ramsey theory
extremal graph theory
Opis:: Let k and ℓ be positive integers with ℓ ≤ k − 2. It is proved that there exists a positive integer c depending on k and ℓ such that every graph of order (2k−1−ℓ/k)n+c contains n vertex disjoint induced subgraphs, where these subgraphs are isomorphic to each other and they are isomorphic to one of four graphs: (1) a clique of order k, (2) an independent set of order k, (3) the join of a clique of order ℓ and an independent set of order k − ℓ, or (4) the union of an independent set of order ℓ and a clique of order k − ℓ.
Źródło:: Discussiones Mathematicae Graph Theory; 2014, 34, 2; 249-261
2083-5892
Pojawia się w:: Discussiones Mathematicae Graph Theory
Dostawca treści:: Biblioteka Nauki

Artykuł

Skocz do pozycji: 3.

Tytuł:: Vertex-disjoint copies of K¯₄
Autorzy:: Kawarabayashi, Ken-ichi
Powiązania:: https://bibliotekanauki.pl/articles/744487.pdf
Data publikacji:: 2004
Wydawca:: Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:: extremal graph theory
vertex disjoint copy
minimum degree
Opis:: Let G be a graph of order n. Let K¯ₗ be the graph obtained from Kₗ by removing one edge.
In this paper, we propose the following conjecture:
Let G be a graph of order n ≥ lk with δ(G) ≥ (n-k+1)(l-3)/(l-2)+k-1. Then G has k vertex-disjoint K¯ₗ.
This conjecture is motivated by Hajnal and Szemerédi's [6] famous theorem. In this paper, we verify this conjecture for l=4.
Źródło:: Discussiones Mathematicae Graph Theory; 2004, 24, 2; 249-262
2083-5892
Pojawia się w:: Discussiones Mathematicae Graph Theory
Dostawca treści:: Biblioteka Nauki

Artykuł

Skocz do pozycji: 4.

Tytuł:: Remarks on 15-vertex (3,3)-ramsey graphs not containing K₅
Autorzy:: Urbański, Sebastian
Powiązania:: https://bibliotekanauki.pl/articles/972005.pdf
Data publikacji:: 1996
Wydawca:: Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:: Folkman numbers
Kₙ-free graphs
extremal graph theory
generalized Ramsey theory
Opis:: The paper gives an account of previous and recent attempts to determine the order of a smallest graph not containing K₅ and such that every 2-coloring of its edges results in a monochromatic triangle. A new 14-vertex K₄-free graph with the same Ramsey property in the vertex coloring case is found. This yields a new construction of one of the only two known 15-vertex (3,3)-Ramsey graphs not containing K₅.
Źródło:: Discussiones Mathematicae Graph Theory; 1996, 16, 2; 173-179
2083-5892
Pojawia się w:: Discussiones Mathematicae Graph Theory
Dostawca treści:: Biblioteka Nauki

Artykuł

Skocz do pozycji: 5.

Tytuł:: Maximum Cycle Packing in Eulerian Graphs Using Local Traces
Autorzy:: Recht, Peter
Sprengel, Eva-Maria
Powiązania:: https://bibliotekanauki.pl/articles/31339129.pdf
Data publikacji:: 2015-02-01
Wydawca:: Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:: edge-disjoint cycle packing
local traces
extremal problems in graph theory
Opis:: For a graph G = (V,E) and a vertex v ∈ V, let T(v) be a local trace at v, i.e. T(v) is an Eulerian subgraph of G such that every walk W(v), with start vertex v can be extended to an Eulerian tour in T(v). We prove that every maximum edge-disjoint cycle packing Z* of G induces a maximum trace T(v) at v for every v ∈ V. Moreover, if G is Eulerian then sufficient conditions are given that guarantee that the sets of cycles inducing maximum local traces of G also induce a maximum cycle packing of G.
Źródło:: Discussiones Mathematicae Graph Theory; 2015, 35, 1; 121-132
2083-5892
Pojawia się w:: Discussiones Mathematicae Graph Theory
Dostawca treści:: Biblioteka Nauki

Artykuł

Informacja