Informacja

Drogi użytkowniku, aplikacja do prawidłowego działania wymaga obsługi JavaScript. Proszę włącz obsługę JavaScript w Twojej przeglądarce.

English (EN)·Polski (PL)·Yкраїнський (UK)
Przejdź do strony domowej biblioteki Centralna Biblioteka Wojskowa Link otwiera się w nowym oknie Logo biblioteki Prolib Integro - strona głównaCentralna Biblioteka Wojskowa

Wyszukujesz frazę "Hamiltonian" wg kryterium: Temat

  Lista filtrów
Wyrównaj
Wyświetlanie 1-15 z 97
Tytuł:
On Vertices Enforcing a Hamiltonian Cycle
Autorzy:
Fabrici, Igor
Hexel, Erhard
Jendrol’, Stanislav
Powiązania:
https://bibliotekanauki.pl/articles/30146856.pdf
Data publikacji:
2013-03-01
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
cycle
hamiltonian
1-hamiltonian
Opis:
A nonempty vertex set X ⊆ V (G) of a hamiltonian graph G is called an H-force set of G if every X-cycle of G (i.e. a cycle of G containing all vertices of X) is hamiltonian. The H-force number h(G) of a graph G is defined to be the smallest cardinality of an H-force set of G. In the paper the study of this parameter is introduced and its value or a lower bound for outerplanar graphs, planar graphs, k-connected graphs and prisms over graphs is determined.
Źródło:
Discussiones Mathematicae Graph Theory; 2013, 33, 1; 71-89
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
Improved Sufficient Conditions for Hamiltonian Properties
Autorzy:
Bode, Jens-P.
Fricke, Anika
Kemnitz, Arnfried
Powiązania:
https://bibliotekanauki.pl/articles/31339476.pdf
Data publikacji:
2015-05-01
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
Hamiltonian
traceable
Hamiltonian-connected
Opis:
In 1980 Bondy [2] proved that a (k+s)-connected graph of order n ≥ 3 is traceable (s = −1) or Hamiltonian (s = 0) or Hamiltonian-connected (s = 1) if the degree sum of every set of k+1 pairwise nonadjacent vertices is at least ((k+1)(n+s−1)+1)/2. It is shown in [1] that one can allow exceptional (k+1)-sets violating this condition and still implying the considered Hamiltonian property. In this note we generalize this result for s = −1 and s = 0 and graphs that fulfill a certain connectivity condition.
Źródło:
Discussiones Mathematicae Graph Theory; 2015, 35, 2; 329-334
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
On the Hamiltonian Number of a Plane Graph
Autorzy:
Lewis, Thomas M.
Powiązania:
https://bibliotekanauki.pl/articles/31343593.pdf
Data publikacji:
2019-02-01
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
Hamiltonian cycle
Hamiltonian walk
Hamiltonian number
Hamiltonian spectrum
Grinberg’s theorem
planar graph
Opis:
The Hamiltonian number of a connected graph is the minimum of the lengths of the closed spanning walks in the graph. In 1968, Grinberg published a necessary condition for the existence of a Hamiltonian cycle in a plane graph, formulated in terms of the degrees of its faces. We show how Grinberg’s theorem can be adapted to provide a lower bound on the Hamiltonian number of a plane graph.
Źródło:
Discussiones Mathematicae Graph Theory; 2019, 39, 1; 171-181
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
A conjecture on the prevalence of cubic bridge graphs
Autorzy:
Filar, Jerzy
Haythorpe, Michael
Nguyen, Giang
Powiązania:
https://bibliotekanauki.pl/articles/744564.pdf
Data publikacji:
2010
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
Hamiltonian graph
non-Hamiltonian graph
cubic bridge graph
Opis:
Almost all d-regular graphs are Hamiltonian, for d ≥ 3 [8]. In this note we conjecture that in a similar, yet somewhat different, sense almost all cubic non-Hamiltonian graphs are bridge graphs, and present supporting empirical results for this prevalence of the latter among all connected cubic non-Hamiltonian graphs.
Źródło:
Discussiones Mathematicae Graph Theory; 2010, 30, 1; 175-179
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
Decomposing the Complete Graph Into Hamiltonian Paths (Cycles) and 3-Stars
Autorzy:
Lee, Hung-Chih
Chen, Zhen-Chun
Powiązania:
https://bibliotekanauki.pl/articles/31521539.pdf
Data publikacji:
2020-08-01
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
decomposition
complete graph
Hamiltonian path
Hamiltonian cycle
star
Opis:
Let H be a graph. A decomposition of H is a set of edge-disjoint subgraphs of H whose union is H. A Hamiltonian path (respectively, cycle) of H is a path (respectively, cycle) that contains every vertex of H exactly once. A k-star, denoted by Sk, is a star with k edges. In this paper, we give necessary and sufficient conditions for decomposing the complete graph into α copies of Hamiltonian path (cycle) and β copies of S3.
Źródło:
Discussiones Mathematicae Graph Theory; 2020, 40, 3; 823-839
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
On k-Path Pancyclic Graphs
Autorzy:
Bi, Zhenming
Zhang, Ping
Powiązania:
https://bibliotekanauki.pl/articles/31339488.pdf
Data publikacji:
2015-05-01
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
Hamiltonian
panconnected
pancyclic
path Hamiltonian
path pancyclic
Opis:
For integers k and n with 2 ≤ k ≤ n − 1, a graph G of order n is k-path pancyclic if every path P of order k in G lies on a cycle of every length from k + 1 to n. Thus a 2-path pancyclic graph is edge-pancyclic. In this paper, we present sufficient conditions for graphs to be k-path pancyclic. For a graph G of order n ≥ 3, we establish sharp lower bounds in terms of n and k for (a) the minimum degree of G, (b) the minimum degree-sum of nonadjacent vertices of G and (c) the size of G such that G is k-path pancyclic
Źródło:
Discussiones Mathematicae Graph Theory; 2015, 35, 2; 271-281
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
On the Edge-Hyper-Hamiltonian Laceability of Balanced Hypercubes
Autorzy:
Cao, Jianxiang
Shi, Minyong
Feng, Lihua
Powiązania:
https://bibliotekanauki.pl/articles/31340774.pdf
Data publikacji:
2016-11-01
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
balanced hypercubes
hyper-Hamiltonian laceability
edge- hyper-Hamiltonian laceability
Opis:
The balanced hypercube BHn, defined by Wu and Huang, is a variant of the hypercube network Qn, and has been proved to have better properties than Qn with the same number of links and processors. For a bipartite graph G = (V0 ∪ V1,E), we say G is edge-hyper-Hamiltonian laceable if it is Hamiltonian laceable, and for any vertex v ∈ Vi, i ∈ {0, 1}, any edge e ∈ E(G − v), there is a Hamiltonian path containing e in G − v between any two vertices of V1−i. In this paper, we prove that BHn is edge-hyper- Hamiltonian laceable.
Źródło:
Discussiones Mathematicae Graph Theory; 2016, 36, 4; 805-817
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
Chvátal-Erdös type theorems
Autorzy:
Faudree, Jill
Faudree, Ralph
Gould, Ronald
Jacobson, Michael
Magnant, Colton
Powiązania:
https://bibliotekanauki.pl/articles/744255.pdf
Data publikacji:
2010
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
Hamiltonian
Hamiltonian-connected
Chvátal-Erdös condition
independence number
Opis:
The Chvátal-Erdös theorems imply that if G is a graph of order n ≥ 3 with κ(G) ≥ α(G), then G is hamiltonian, and if κ(G) > α(G), then G is hamiltonian-connected. We generalize these results by replacing the connectivity and independence number conditions with a weaker minimum degree and independence number condition in the presence of sufficient connectivity. More specifically, it is noted that if G is a graph of order n and k ≥ 2 is a positive integer such that κ(G) ≥ k, δ(G) > (n+k²-k)/(k+1), and δ(G) ≥ α(G)+k-2, then G is hamiltonian. It is shown that if G is a graph of order n and k ≥ 3 is a positive integer such that κ(G) ≥ 4k²+1, δ(G) > (n+k²-2k)/k, and δ(G) ≥ α(G)+k-2, then G is hamiltonian-connected. This result supports the conjecture that if G is a graph of order n and k ≥ 3 is a positive integer such that κ(G) ≥ k, δ(G) > (n+k²-2k)/k, and δ(G) ≥ α(G)+k-2, then G is hamiltonian-connected, and the conjecture is verified for k = 3 and 4.
Źródło:
Discussiones Mathematicae Graph Theory; 2010, 30, 2; 245-256
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
Pancyclism and small cycles in graphs
Autorzy:
Faudree, Ralph
Favaron, Odile
Flandrin, Evelynei
Li, Hao
Powiązania:
https://bibliotekanauki.pl/articles/972039.pdf
Data publikacji:
1996
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
cycle
hamiltonian
pancyclic
Opis:
We first show that if a graph G of order n contains a hamiltonian path connecting two nonadjacent vertices u and v such that d(u)+d(v) ≥ n, then G is pancyclic. By using this result, we prove that if G is hamiltonian with order n ≥ 20 and if G has two nonadjacent vertices u and v such that d(u)+d(v) ≥ n+z, where z = 0 when n is odd and z = 1 otherwise, then G contains a cycle of length m for each 3 ≤ m ≤ max (d_C(u,v)+1, [(n+19)/13]), $d_C(u,v)$ being the distance of u and v on a hamiltonian cycle of G.
Źródło:
Discussiones Mathematicae Graph Theory; 1996, 16, 1; 27-40
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
Problems remaining NP-complete for sparse or dense graphs
Autorzy:
Schiermeyer, Ingo
Powiązania:
https://bibliotekanauki.pl/articles/972006.pdf
Data publikacji:
1995
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
Computational Complexity
NP-Completeness
Hamiltonian Circuit
Hamiltonian Path
Independent Set
Opis:
For each fixed pair α,c > 0 let INDEPENDENT SET ($m ≤ cn^α$) and INDEPENDENT SET ($m ≥ (ⁿ₂) - cn^α$) be the problem INDEPENDENT SET restricted to graphs on n vertices with $m ≤ cn^α$ or $m ≥ (ⁿ₂) - cn^α$ edges, respectively. Analogously, HAMILTONIAN CIRCUIT ($m ≤ n + cn^α$) and HAMILTONIAN PATH ($m ≤ n + cn^α$) are the problems HAMILTONIAN CIRCUIT and HAMILTONIAN PATH restricted to graphs with $m ≤ n + cn^α$ edges. For each ϵ > 0 let HAMILTONIAN CIRCUIT (m ≥ (1 - ϵ)(ⁿ₂)) and HAMILTONIAN PATH (m ≥ (1 - ϵ)(ⁿ₂)) be the problems HAMILTONIAN CIRCUIT and HAMILTONIAN PATH restricted to graphs with m ≥ (1 - ϵ)(ⁿ₂) edges.
We prove that these six restricted problems remain NP-complete. Finally, we consider sufficient conditions for a graph to have a Hamiltonian circuit. These conditions are based on degree sums and neighborhood unions of independent vertices, respectively. Lowering the required bounds the problem HAMILTONIAN CIRCUIT jumps from 'easy' to 'NP-complete'.
Źródło:
Discussiones Mathematicae Graph Theory; 1995, 15, 1; 33-41
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
Hamiltonian Extendable Graphs
Autorzy:
Yang, Xiaojing
Xiong, Liming
Powiązania:
https://bibliotekanauki.pl/articles/32304150.pdf
Data publikacji:
2022-08-01
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
Hamiltonian extendable
forbidden subgraph
Opis:
A graph is called Hamiltonian extendable if there exists a Hamiltonian path between any two nonadjacent vertices. In this paper, we give an explicit formula of the minimum number of edges for Hamiltonian extendable graphs and we also characterize the degree sequence for Hamiltonian extendable graphs with minimum number of edges. Besides, we completely characterize the pairs of forbidden subgraphs for 2-connected graphs to be Hamiltonian extendable.
Źródło:
Discussiones Mathematicae Graph Theory; 2022, 42, 3; 843-859
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
On Uniquely Hamiltonian Claw-Free and Triangle-Free Graphs
Autorzy:
Seamone, Ben
Powiązania:
https://bibliotekanauki.pl/articles/31339495.pdf
Data publikacji:
2015-05-01
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
Hamiltonian cycle
uniquely Hamiltonian graphs
claw-free graphs
triangle-free graphs
Opis:
A graph is uniquely Hamiltonian if it contains exactly one Hamiltonian cycle. In this note, we prove that claw-free graphs with minimum degree at least 3 are not uniquely Hamiltonian. We also show that this is best possible by exhibiting uniquely Hamiltonian claw-free graphs with minimum degree 2 and arbitrary maximum degree. Finally, we show that a construction due to Entringer and Swart can be modified to construct triangle-free uniquely Hamiltonian graphs with minimum degree 3.
Źródło:
Discussiones Mathematicae Graph Theory; 2015, 35, 2; 207-214
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
Graphs maximal with respect to absence of hamiltonian paths
Autorzy:
Zelinka, Bohdan
Powiązania:
https://bibliotekanauki.pl/articles/744225.pdf
Data publikacji:
1998
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
Hamiltonian path
block graph
Opis:
Two classes of graphs which are maximal with respect to the absence of Hamiltonian paths are presented. Block graphs with this property are characterized.
Źródło:
Discussiones Mathematicae Graph Theory; 1998, 18, 2; 205-208
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
Matchings Extend to Hamiltonian Cycles in 5-Cube
Autorzy:
Wang, Fan
Zhao, Weisheng
Powiązania:
https://bibliotekanauki.pl/articles/31342429.pdf
Data publikacji:
2018-02-01
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
hypercube
Hamiltonian cycle
matching
Opis:
Ruskey and Savage asked the following question: Does every matching in a hypercube Qn for n ≥ 2 extend to a Hamiltonian cycle of Qn? Fink confirmed that every perfect matching can be extended to a Hamiltonian cycle of Qn, thus solved Kreweras’ conjecture. Also, Fink pointed out that every matching can be extended to a Hamiltonian cycle of Qn for n ∈ {2, 3, 4}. In this paper, we prove that every matching in Q5 can be extended to a Hamiltonian cycle of Q5.
Źródło:
Discussiones Mathematicae Graph Theory; 2018, 38, 1; 217-231
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
Arc-Disjoint Hamiltonian Cycles in Round Decomposable Locally Semicomplete Digraphs
Autorzy:
Li, Ruijuan
Han, Tingting
Powiązania:
https://bibliotekanauki.pl/articles/31342322.pdf
Data publikacji:
2018-05-01
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
locally semicomplete digraph
local tournament
round decomposable
arc-disjoint
Hamiltonian cycle
Hamiltonian path
Opis:
Let D = (V,A) be a digraph; if there is at least one arc between every pair of distinct vertices of D, then D is a semicomplete digraph. A digraph D is locally semicomplete if for every vertex x, the out-neighbours of x induce a semicomplete digraph and the in-neighbours of x induce a semicomplete digraph. A locally semicomplete digraph without 2-cycle is a local tournament. In 2012, Bang-Jensen and Huang [J. Combin Theory Ser. B 102 (2012) 701–714] concluded that every 2-arc-strong locally semicomplete digraph which is not the second power of an even cycle has two arc-disjoint strong spanning subdigraphs, and proposed the conjecture that every 3-strong local tournament has two arc-disjoint Hamiltonian cycles. According to Bang-Jensen, Guo, Gutin and Volkmann, locally semicomplete digraphs have three subclasses: the round decomposable; the non-round decomposable which are not semicomplete; the non-round decomposable which are semicomplete. In this paper, we prove that every 3-strong round decomposable locally semicomplete digraph has two arc-disjoint Hamiltonian cycles, which implies that the conjecture holds for the round decomposable local tournaments. Also, we characterize the 2-strong round decomposable local tournaments each of which contains a Hamiltonian path P and a Hamiltonian cycle arc-disjoint from P.
Źródło:
Discussiones Mathematicae Graph Theory; 2018, 38, 2; 477-490
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Wyświetlanie 1-15 z 97

Ta witryna wykorzystuje pliki cookies do przechowywania informacji na Twoim komputerze. Pliki cookies stosujemy w celu świadczenia usług na najwyższym poziomie, w tym w sposób dostosowany do indywidualnych potrzeb. Korzystanie z witryny bez zmiany ustawień dotyczących cookies oznacza, że będą one zamieszczane w Twoim komputerze. W każdym momencie możesz dokonać zmiany ustawień dotyczących cookies