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 cycle" wg kryterium: Temat

  Lista filtrów
Wyrównaj
Wyświetlanie 1-15 z 23
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ł:
Fans condition on induced subgraphs for circumference and pancyclicity
Autorzy:
Wideł, W.
Powiązania:
https://bibliotekanauki.pl/articles/255831.pdf
Data publikacji:
2017
Wydawca:
Akademia Górniczo-Hutnicza im. Stanisława Staszica w Krakowie. Wydawnictwo AGH
Tematy:
Fan's condition
circumference
hamiltonian cycle
pancyclicity
Opis:
Let H be a family of simple graphs and k be a positive integer. We say that a graph G of order n ≥ k satisfies Fan's condition with respect to H with constant k, if for every induced subgraph H of G isomorphic to any of the graphs from H the following holds: [formula] If G satisfies the above condition, we write [formula]. In this paper we show that if G is 2-connected and [formula], then G contains a cycle of length at least k, and that if [formula], then G is pancyclic with some exceptions. As corollaries we obtain the previous results by Fan, Benhocine and Wojda, and Ning.
Źródło:
Opuscula Mathematica; 2017, 37, 4; 617-639
1232-9274
2300-6919
Pojawia się w:
Opuscula Mathematica
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
Chvátals Condition cannot hold for both a graph and its complement
Autorzy:
Kostochka, Alexandr
West, Douglas
Powiązania:
https://bibliotekanauki.pl/articles/743881.pdf
Data publikacji:
2006
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
Hamiltonian cycle
Chvátal's Condition
random graph
Opis:
Chvátal's Condition is a sufficient condition for a spanning cycle in an n-vertex graph. The condition is that when the vertex degrees are d₁, ...,dₙ in nondecreasing order, i < n/2 implies that $d_i > i$ or $d_{n-i} ≥ n-i$. We prove that this condition cannot hold in both a graph and its complement, and we raise the problem of finding its asymptotic probability in the random graph with edge probability 1/2.
Źródło:
Discussiones Mathematicae Graph Theory; 2006, 26, 1; 73-76
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
On Factorable Bigraphic Pairs
Autorzy:
Yin, Jian-Hua
Li, Sha-Sha
Powiązania:
https://bibliotekanauki.pl/articles/31515537.pdf
Data publikacji:
2020-08-01
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
degree sequence
bigraphic pair
Hamiltonian cycle
Opis:
Let $S = (a_1,. . ., a_m; b_1, . . ., b_n)$, where $a_1, . . ., a_m$ and $b_1, . . ., b_n$ are two sequences of nonnegative integers. We say that $S$ is a bigraphic pair if there exists a simple bipartite graph $G$ with partite sets ${x_1, x_2, . . ., x_m}$ and ${y_1, y_2, . . ., y_n}$ such that $d_G(x_i) = a_i$ for $1 ≤ i ≤ m$ and $d_G(y_j) = b_j$ for $1 ≤ j ≤ n$. In this case, we say that $G$ is a realization of $S$. Analogous to Kundu’s $k$-factor theorem, we show that if $(a_1, a_2, . . ., a_m; b_1, b_2, . . ., b_n)$ and $(a_1 − e_1, a_2 − e_2, . . ., a_m − e_m; b_1 − f_1, b_2 − f_2, . . ., b_n − f_n)$ are two bigraphic pairs satisfying $k ≤ f_i ≤ k + 1, 1 ≤ i ≤ n$ (or$ k ≤ e_i ≤ k + 1, 1 ≤ i ≤ m$), for some $0 ≤ k ≤ m − 1$ (or $0 ≤ k ≤ n − 1$), then $(a_1, a_2, . . ., a_m; b_1, b_2, . . ., b_n)$ has a realization containing an $(e_1, e_2, . . ., e_m; f_1, f_2, . . ., f_n)$-factor. For $m = n$, we also give a necessary and sufficient condition for an $(k^n; k^n)$-factorable bigraphic pair to be connected $(k^n; k^n)$-factorable when $k ≥ 2$. This implies a characterization of bigraphic pairs with a realization containing a Hamiltonian cycle.
Źródło:
Discussiones Mathematicae Graph Theory; 2020, 40, 3; 787-793
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ł:
A note on maximal common subgraphs of the Diracs family of graphs
Autorzy:
Bucko, Jozef
Mihók, Peter
Saclé, Jean-François
Woźniak, Mariusz
Powiązania:
https://bibliotekanauki.pl/articles/744168.pdf
Data publikacji:
2005
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
maximal common subgraph
Dirac's family
Hamiltonian cycle
Opis:
Let ⁿ be a given set of unlabeled simple graphs of order n. A maximal common subgraph of the graphs of the set ⁿ is a common subgraph F of order n of each member of ⁿ, that is not properly contained in any larger common subgraph of each member of ⁿ. By well-known Dirac's Theorem, the Dirac's family ⁿ of the graphs of order n and minimum degree δ ≥ [n/2] has a maximal common subgraph containing Cₙ. In this note we study the problem of determining all maximal common subgraphs of the Dirac's family $ ^{2n}$ for n ≥ 2.
Źródło:
Discussiones Mathematicae Graph Theory; 2005, 25, 3; 385-390
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
On Hamiltonian Cycles in Claw-Free Cubic Graphs
Autorzy:
Mohr, Elena
Rautenbach, Dieter
Powiązania:
https://bibliotekanauki.pl/articles/32361735.pdf
Data publikacji:
2022-02-01
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
Hamiltonian cycle
claw-free graph
cubic graph
Opis:
We show that every claw-free cubic graph of order $n$ at least 8 has at most $ 2\floor{ \frac{n}{4} } $ Hamiltonian cycles, and we also characterize all extremal graphs.
Źródło:
Discussiones Mathematicae Graph Theory; 2022, 42, 1; 309-313
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
Hamiltonian Normal Cayley Graphs
Autorzy:
Montellano-Ballesteros, Juan José
Arguello, Anahy Santiago
Powiązania:
https://bibliotekanauki.pl/articles/31343293.pdf
Data publikacji:
2019-08-01
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
Cayley graph
hamiltonian cycle
normal connection set
Opis:
A variant of the Lovász Conjecture on hamiltonian paths states that every finite connected Cayley graph contains a hamiltonian cycle. Given a finite group G and a connection set S, the Cayley graph Cay(G, S) will be called normal if for every g ∈ G we have that g−1Sg = S. In this paper we present some conditions on the connection set of a normal Cayley graph which imply the existence of a hamiltonian cycle in the graph.
Źródło:
Discussiones Mathematicae Graph Theory; 2019, 39, 3; 731-740
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
2-Connected Hamiltonian Claw-Free Graphs Involving Degree Sum of Adjacent Vertices
Autorzy:
Tian, Tao
Xiong, Liming
Powiązania:
https://bibliotekanauki.pl/articles/32034090.pdf
Data publikacji:
2020-02-01
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
Hamiltonian cycle
degree sum
dominating closed trail
closure
Opis:
For a graph H, define $\overline{\sigma}_2(H)=min\{d(u)+d(v)|uv∈E(H)\}$. Let $H$ be a 2-connected claw-free simple graph of order $n$ with \(\delta(H) ≥ 3\). In [J. Graph Theory 86 (2017) 193–212], Chen proved that if $\overline{\sigma}_2(H)≥\frac{n}{2}−1$ and $n$ is sufficiently large, then $H$ is Hamiltonian with two families of exceptions. In this paper, we refine the result. We focus on the condition $\overline{\sigma}_2(H)≥\frac{2n}{5}−1$, and characterize non-Hamiltonian 2-connected claw-free graphs $H$ of order $n$ sufficiently large with $\overline{\sigma}_2(H)≥\frac{2n}{5}−1$. As byproducts, we prove that there are exactly six graphs in the family of 2-edge-connected triangle-free graphs of order at most seven that have no spanning closed trail and give an improvement of a result of Veldman in [Discrete Math. 124 (1994) 229–239].
Źródło:
Discussiones Mathematicae Graph Theory; 2020, 40, 1; 85-106
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ł:
Lower Bound on the Number of Hamiltonian Cycles of Generalized Petersen Graphs
Autorzy:
Lu, Weihua
Yang, Chao
Ren, Han
Powiązania:
https://bibliotekanauki.pl/articles/32083755.pdf
Data publikacji:
2020-02-01
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
generalized Petersen graph
Hamiltonian cycle
partition number
1-factor
Opis:
In this paper, we investigate the number of Hamiltonian cycles of a generalized Petersen graph $ P(N, k) $ and prove that $ \Psi(P(N,3)) \ge N \cdot \alpha_N $, where $ \Psi (P(N, 3)) $ is the number of Hamiltonian cycles of $P(N, 3)$ and $ \alpha_N $ satisfies that for any $ \epsilon > 0 $, there exists a positive integer $M$ such that when $ N > M $, $ ((1− \epsilon ) \frac{ (1−r^3) }{6r^3+5r^2+3) }( 1/r )^{N+2} < \alpha_N < ( (1+ɛ) \frac{ (1−r^3) }{6r^3+5r^2+3) }( 1/r )^{N+2} $, where $ 1/r = \text{max} \{ | \frac{1}{r_j} | : j=1,2,…,6 \} $, and each $ r_j $ is a root of equation $ x^6 + x^5 + x^3 − 1 = 0 $, $ r \approx 0.782 $. This shows that $ \Psi (P (N, 3) $ is exponential in $N$ and also deduces that the number of 1-factors of $ P(N, 3)$ is exponential in $N$.
Źródło:
Discussiones Mathematicae Graph Theory; 2020, 40, 1; 297-305
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
Hamiltonian Cycle Problem in Strong k-Quasi-Transitive Digraphs with Large Diameter
Autorzy:
Wang, Ruixia
Powiązania:
https://bibliotekanauki.pl/articles/32083906.pdf
Data publikacji:
2021-05-01
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
quasi-transitive digraph
k -quasi-transitive digraph
Hamiltonian cycle
Opis:
Let k be an integer with k ≥ 2. A digraph is k-quasi-transitive, if for any path x0x1... xk of length k, x0 and xk are adjacent. Let D be a strong k-quasi-transitive digraph with even k ≥ 4 and diameter at least k +2. It has been shown that D has a Hamiltonian path. However, the Hamiltonian cycle problem in D is still open. In this paper, we shall show that D may contain no Hamiltonian cycle with k ≥ 6 and give the sufficient condition for D to be Hamiltonian.
Źródło:
Discussiones Mathematicae Graph Theory; 2021, 41, 2; 685-690
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ł:
The Chvátal-Erdős condition and 2-factors with a specified number of components
Autorzy:
Chen, Guantao
Gould, Ronald
Kawarabayashi, Ken-ichi
Ota, Katsuhiro
Saito, Akira
Schiermeyer, Ingo
Powiązania:
https://bibliotekanauki.pl/articles/743407.pdf
Data publikacji:
2007
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
Chvátal-Erdös condition
2-factor
hamiltonian cycle
Ramsey number
Opis:
Let G be a 2-connected graph of order n satisfying α(G) = a ≤ κ(G), where α(G) and κ(G) are the independence number and the connectivity of G, respectively, and let r(m,n) denote the Ramsey number. The well-known Chvátal-Erdös Theorem states that G has a hamiltonian cycle. In this paper, we extend this theorem, and prove that G has a 2-factor with a specified number of components if n is sufficiently large. More precisely, we prove that (1) if n ≥ k·r(a+4, a+1), then G has a 2-factor with k components, and (2) if n ≥ r(2a+3, a+1)+3(k-1), then G has a 2-factor with k components such that all components but one have order three.
Źródło:
Discussiones Mathematicae Graph Theory; 2007, 27, 3; 401-407
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
On a family of cubic graphs containing the flower snarks
Autorzy:
Fouquet, Jean-Luc
Thuillier, Henri
Vanherpe, Jean-Marie
Powiązania:
https://bibliotekanauki.pl/articles/744266.pdf
Data publikacji:
2010
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
cubic graph
perfect matching
strong matching
counting
hamiltonian cycle
2-factor hamiltonian
Opis:
We consider cubic graphs formed with k ≥ 2 disjoint claws $C_i ~ K_{1,3}$ (0 ≤ i ≤ k-1) such that for every integer i modulo k the three vertices of degree 1 of $C_i$ are joined to the three vertices of degree 1 of $C_{i-1}$ and joined to the three vertices of degree 1 of $C_{i+1}$. Denote by $t_i$ the vertex of degree 3 of $C_i$ and by T the set ${t₁,t₂,...,t_{k-1}}$. In such a way we construct three distinct graphs, namely FS(1,k), FS(2,k) and FS(3,k). The graph FS(j,k) (j ∈ {1,2,3}) is the graph where the set of vertices $⋃_{i = 0}^{i = k-1} V(C_i)∖T$ induce j cycles (note that the graphs FS(2,2p+1), p ≥ 2, are the flower snarks defined by Isaacs [8]). We determine the number of perfect matchings of every FS(j,k). A cubic graph G is said to be 2-factor hamiltonian if every 2-factor of G is a hamiltonian cycle. We characterize the graphs FS(j,k) that are 2-factor hamiltonian (note that FS(1,3) is the "Triplex Graph" of Robertson, Seymour and Thomas [15]). A strong matching M in a graph G is a matching M such that there is no edge of E(G) connecting any two edges of M. A cubic graph having a perfect matching union of two strong matchings is said to be a Jaeger's graph. We characterize the graphs FS(j,k) that are Jaeger's graphs.
Źródło:
Discussiones Mathematicae Graph Theory; 2010, 30, 2; 289-314
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Wyświetlanie 1-15 z 23

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