Pełnotekstowe zasoby PLDML oraz innych baz dziedzinowych są już dostępne w nowej Bibliotece Nauki.
Zapraszamy na https://bibliotekanauki.pl
Preferencje help
Polish version English version Język
Widoczny [Schowaj] Abstrakt
Liczba wyników

Znaleziono wyników: 9

Liczba wyników na stronie
first rewind previous Strona / 1 next fast forward last

Wyniki wyszukiwania

Wyszukiwano:
w słowach kluczowych:  Hamilton cycle
help Sortuj według:

help Ogranicz wyniki do:
first rewind previous Strona / 1 next fast forward last
1
Content available remote

A Note on Barnette’s Conjecture

100%
Harant J.
Discussiones Mathematicae Graph Theory
|
2013
|
tom 33
|
nr 1
133-137
EN
Barnette conjectured that each planar, bipartite, cubic, and 3-connected graph is hamiltonian. We prove that this conjecture is equivalent to the statement that there is a constant c > 0 such that each graph G of this class contains a path on at least c|V (G)| vertices.
2
Content available remote

A Triple of Heavy Subgraphs Ensuring Pancyclicity of 2-Connected Graphs

100%
Wide W.
Discussiones Mathematicae Graph Theory
|
2017
|
tom 37
|
nr 2
477-499
EN
A graph G on n vertices is said to be pancyclic if it contains cycles of all lengths k for k ∈ {3, . . . , n}. A vertex v ∈ V (G) is called super-heavy if the number of its neighbours in G is at least (n+1)/2. For a given graph H we say that G is H-f1-heavy if for every induced subgraph K of G isomorphic to H and every two vertices u, v ∈ V (K), dK(u, v) = 2 implies that at least one of them is super-heavy. For a family of graphs H we say that G is H-f1-heavy, if G is H-f1-heavy for every graph H ∈H. Let D denote the deer, a graph consisting of a triangle with two disjoint paths P3 adjoined to two of its vertices. In this paper we prove that every 2-connected {K1,3, P7, D}-f1-heavy graph on n ≥ 14 vertices is pancyclic. This result extends the previous work by Faudree, Ryjáček and Schiermeyer.
3
Content available remote

Pancyclicity when each Cycle Must Pass Exactly k Hamilton Cycle Chords

100%
Affif Chaouche F., Rutherford C. G., Whitty R. W.
Discussiones Mathematicae Graph Theory
|
2015
|
tom 35
|
nr 3
533-539
EN
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 ∩(n1/k) on the growth rate.
4
Content available remote

Families of triples with high minimum degree are hamiltonian

100%
Rödl V., Ruciński A.
Discussiones Mathematicae Graph Theory
|
2014
|
tom 34
|
nr 2
361-381
EN
In this paper we show that every family of triples, that is, a 3-uniform hypergraph, with minimum degree at least [...] contains a tight Hamiltonian cycle
5
Content available remote

Hamiltonicity and Generalised Total Colourings of Planar Graphs

100%
Borowiecki M., Broere I.
Discussiones Mathematicae Graph Theory
|
2016
|
tom 36
|
nr 2
243-257
EN
The total generalised colourings considered in this paper are colourings of graphs such that the vertices and edges of the graph which receive the same colour induce subgraphs from two prescribed hereditary graph properties while incident elements receive different colours. The associated total chromatic number is the least number of colours with which this is possible. We study such colourings for sets of planar graphs and determine, in particular, upper bounds for these chromatic numbers for proper colourings of the vertices while the monochromatic edge sets are allowed to be forests. We also prove that if an even planar triangulation has a Hamilton cycle H for which there is no cycle among the edges inside H, then such a graph needs at most four colours for a total colouring as described above. The paper is concluded with some conjectures and open problems.
6
Content available remote

A Fan-Type Heavy Pair Of Subgraphs For Pancyclicity Of 2-Connected Graphs

100%
Wideł W.
Discussiones Mathematicae Graph Theory
|
2016
|
tom 36
|
nr 1
173-184
EN
Let G be a graph on n vertices and let H be a given graph. We say that G is pancyclic, if it contains cycles of all lengths from 3 up to n, and that it is H-f1-heavy, if for every induced subgraph K of G isomorphic to H and every two vertices u, v ∈ V (K), dK(u, v) = 2 implies [...] min⁡{dG(u),dG(v)}≥n+12 $\min \{ d_G (u),d_G (v)\} \ge {{n + 1} \over 2}$ . In this paper we prove that every 2-connected {K1,3, P5}-f1-heavy graph is pancyclic. This result completes the answer to the problem of finding f1-heavy pairs of subgraphs implying pancyclicity of 2-connected graphs.
7
Artykuł dostępny w postaci pełnego tekstu - kliknij by otworzyć plik
Content available

Hamilton cycles in split graphs with large minimum degree

100%
Tan N., Hung L.
Discussiones Mathematicae Graph Theory
|
2004
|
tom 24
|
nr 1
23-40
EN
A graph G is called a split graph if the vertex-set V of G can be partitioned into two subsets V₁ and V₂ such that the subgraphs of G induced by V₁ and V₂ are empty and complete, respectively. In this paper, we characterize hamiltonian graphs in the class of split graphs with minimum degree δ at least |V₁| - 2.
8
Content available remote

Hamilton cycles in almost distance-hereditary graphs

75%
Chen B., Ning B.
Open Mathematics
|
2016
|
tom 14
|
nr 1
19-28
EN
Let G be a graph on n ≥ 3 vertices. A graph G is almost distance-hereditary if each connected induced subgraph H of G has the property dH(x, y) ≤ dG(x, y) + 1 for any pair of vertices x, y ∈ V(H). Adopting the terminology introduced by Broersma et al. and Čada, a graph G is called 1-heavy if at least one of the end vertices of each induced subgraph of G isomorphic to K1,3 (a claw) has degree at least n/2, and is called claw-heavy if each claw of G has a pair of end vertices with degree sum at least n. In this paper we prove the following two theorems: (1) Every 2-connected, claw-heavy and almost distance-hereditary graph is Hamiltonian. (2) Every 3-connected, 1-heavy and almost distance-hereditary graph is Hamiltonian. The first result improves a previous theorem of Feng and Guo [J.-F. Feng and Y.-B. Guo, Hamiltonian cycle in almost distance-hereditary graphs with degree condition restricted to claws, Optimazation 57 (2008), no. 1, 135–141]. For the second result, its connectedness condition is sharp since Feng and Guo constructed a 2-connected 1-heavy graph which is almost distance-hereditary but not Hamiltonian.
9
Artykuł dostępny w postaci pełnego tekstu - kliknij by otworzyć plik
Content available

On constant-weight TSP-tours

51%
Jones S., Kayll P., Mohar B., Wallis W.
Discussiones Mathematicae Graph Theory
|
2003
|
tom 23
|
nr 2
287-307
EN
Is it possible to label the edges of Kₙ with distinct integer weights so that every Hamilton cycle has the same total weight? We give a local condition characterizing the labellings that witness this question's perhaps surprising affirmative answer. More generally, we address the question that arises when "Hamilton cycle" is replaced by "k-factor" for nonnegative integers k. Such edge-labellings are in correspondence with certain vertex-labellings, and the link allows us to determine (up to a constant factor) the growth rate of the maximum edge-label in a "most efficient" injective metric trivial-TSP labelling.
first rewind previous Strona / 1 next fast forward last
JavaScript jest wyłączony w Twojej przeglądarce internetowej. Włącz go, a następnie odśwież stronę, aby móc w pełni z niej korzystać.