Temat: Hamiltonian cycle - Prolib Integro

Skocz do pozycji: 1.

Tytuł:: Matchings Extend to Hamiltonian Cycles in 5-Cube
Autorzy:: Wang, Fan
Zhao, Weisheng
Tematy:: hypercube
Hamiltonian cycle
matching; Pokaż więcej
Wydawca:: Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Powiązania:: https://bibliotekanauki.pl/articles/31342429.pdf Link otwiera się w nowym oknie
Opis:: Ruskey and Savage asked the following question: Does every matching in a hypercube Q_n for n ≥ 2 extend to a Hamiltonian cycle of Q_n? Fink confirmed that every perfect matching can be extended to a Hamiltonian cycle of Q_n, thus solved Kreweras’ conjecture. Also, Fink pointed out that every matching can be extended to a Hamiltonian cycle of Q_n for n ∈ {2, 3, 4}. In this paper, we prove that every matching in Q₅ can be extended to a Hamiltonian cycle of Q₅.
Dostawca treści:: Biblioteka Nauki

Artykuł

na półce

Skocz do pozycji: 2.

Tytuł:: Decomposing the Complete Graph Into Hamiltonian Paths (Cycles) and 3-Stars
Autorzy:: Lee, Hung-Chih
Chen, Zhen-Chun
Tematy:: decomposition
complete graph
Hamiltonian path
Hamiltonian cycle
star; Pokaż więcej
Wydawca:: Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Powiązania:: https://bibliotekanauki.pl/articles/31521539.pdf Link otwiera się w nowym oknie
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 S_k, 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 S₃.
Dostawca treści:: Biblioteka Nauki

Artykuł

na półce

Skocz do pozycji: 3.

Tytuł:: Fans condition on induced subgraphs for circumference and pancyclicity
Autorzy:: Wideł, W.
Tematy:: Fan's condition
circumference
hamiltonian cycle
pancyclicity; Pokaż więcej
Wydawca:: Akademia Górniczo-Hutnicza im. Stanisława Staszica w Krakowie. Wydawnictwo AGH
Powiązania:: https://bibliotekanauki.pl/articles/255831.pdf Link otwiera się w nowym oknie
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.
Dostawca treści:: Biblioteka Nauki

Artykuł

na półce

Skocz do pozycji: 4.

Tytuł:: Chvátals Condition cannot hold for both a graph and its complement
Autorzy:: Kostochka, Alexandr
West, Douglas
Tematy:: Hamiltonian cycle
Chvátal's Condition
random graph; Pokaż więcej
Wydawca:: Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Powiązania:: https://bibliotekanauki.pl/articles/743881.pdf Link otwiera się w nowym oknie
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.
Dostawca treści:: Biblioteka Nauki

Artykuł

na półce

Skocz do pozycji: 5.

Tytuł:: On Factorable Bigraphic Pairs
Autorzy:: Yin, Jian-Hua
Li, Sha-Sha
Tematy:: degree sequence
bigraphic pair
Hamiltonian cycle; Pokaż więcej
Wydawca:: Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Powiązania:: https://bibliotekanauki.pl/articles/31515537.pdf Link otwiera się w nowym oknie
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.
Dostawca treści:: Biblioteka Nauki

Artykuł

na półce

Skocz do pozycji: 6.

Tytuł:: Hamiltonian Normal Cayley Graphs
Autorzy:: Montellano-Ballesteros, Juan José
Arguello, Anahy Santiago
Tematy:: Cayley graph
hamiltonian cycle
normal connection set; Pokaż więcej
Wydawca:: Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Powiązania:: https://bibliotekanauki.pl/articles/31343293.pdf Link otwiera się w nowym oknie
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₋₁Sg = 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.
Dostawca treści:: Biblioteka Nauki

Artykuł

na półce

Skocz do pozycji: 7.

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
Tematy:: maximal common subgraph
Dirac's family
Hamiltonian cycle; Pokaż więcej
Wydawca:: Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Powiązania:: https://bibliotekanauki.pl/articles/744168.pdf Link otwiera się w nowym oknie
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.
Dostawca treści:: Biblioteka Nauki

Artykuł

na półce

Skocz do pozycji: 8.

Tytuł:: On Hamiltonian Cycles in Claw-Free Cubic Graphs
Autorzy:: Mohr, Elena
Rautenbach, Dieter
Tematy:: Hamiltonian cycle
claw-free graph
cubic graph; Pokaż więcej
Wydawca:: Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Powiązania:: https://bibliotekanauki.pl/articles/32361735.pdf Link otwiera się w nowym oknie
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.
Dostawca treści:: Biblioteka Nauki

Artykuł

na półce

Skocz do pozycji: 9.

Tytuł:: On the Hamiltonian Number of a Plane Graph
Autorzy:: Lewis, Thomas M.
Tematy:: Hamiltonian cycle
Hamiltonian walk
Hamiltonian number
Hamiltonian spectrum
Grinberg’s theorem
planar graph; Pokaż więcej
Wydawca:: Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Powiązania:: https://bibliotekanauki.pl/articles/31343593.pdf Link otwiera się w nowym oknie
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.
Dostawca treści:: Biblioteka Nauki

Artykuł

na półce

Skocz do pozycji: 10.

Tytuł:: On Uniquely Hamiltonian Claw-Free and Triangle-Free Graphs
Autorzy:: Seamone, Ben
Tematy:: Hamiltonian cycle
uniquely Hamiltonian graphs
claw-free graphs
triangle-free graphs; Pokaż więcej
Wydawca:: Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Powiązania:: https://bibliotekanauki.pl/articles/31339495.pdf Link otwiera się w nowym oknie
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.
Dostawca treści:: Biblioteka Nauki

Artykuł

na półce

Informacja

Wyszukujesz frazę "Hamiltonian cycle" wg kryterium: Temat