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

  Lista filtrów
Wyrównaj
Wyświetlanie 1-15 z 25
Tytuł:
The Ryjáček Closure and a Forbidden Subgraph
Autorzy:
Saito, Akira
Xiong, Liming
Powiązania:
https://bibliotekanauki.pl/articles/31340869.pdf
Data publikacji:
2016-08-01
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
closure
claw-free graph
Hamiltonian graph
perfect matching
traceable graph
Opis:
The Ryjáček closure is a powerful tool in the study of Hamiltonian properties of claw-free graphs. Because of its usefulness, we may hope to use it in the classes of graphs defined by another forbidden subgraph. In this note, we give a negative answer to this hope, and show that the claw is the only forbidden subgraph that produces non-trivial results on Hamiltonicity by the use of the Ryjáček closure.
Źródło:
Discussiones Mathematicae Graph Theory; 2016, 36, 3; 621-628
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
Research problems from the 18th Workshop '3in1' 2009
Autorzy:
Meszka, M. [ed.]
Powiązania:
https://bibliotekanauki.pl/articles/255619.pdf
Data publikacji:
2010
Wydawca:
Akademia Górniczo-Hutnicza im. Stanisława Staszica w Krakowie. Wydawnictwo AGH
Tematy:
Hamilton-connected graph
hamiltonian graph
dominating cycle
bihomogeneously traceble graph
Opis:
A collection of open problems that were posed at the 18th Workshop '3in1', held on November 26-28, 2009 in Krakow, Poland. The problems are presented by Zdenek Ryjacek in "Does the Thomassen's conjecture imply N=NP?" and "Dominating cycles and hamiltonian prisms", and by Carol T. Zamfirescu in "Two problems on bihomogeneously traceable digraphs".
Źródło:
Opuscula Mathematica; 2010, 30, 4; 527-532
1232-9274
2300-6919
Pojawia się w:
Opuscula Mathematica
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
On the intersection graphs of ideals of direct product of rings
Autorzy:
Rad, Nader
Jafari, Sayyed
Ghosh, Shamik
Powiązania:
https://bibliotekanauki.pl/articles/729199.pdf
Data publikacji:
2014
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
ideal
direct sum
intersection graph
Eulerian
Hamiltonian
Opis:
In this paper we first calculate the number of vertices and edges of the intersection graph of ideals of direct product of rings and fields. Then we study Eulerianity and Hamiltonicity in the intersection graph of ideals of direct product of commutative rings.
Źródło:
Discussiones Mathematicae - General Algebra and Applications; 2014, 34, 2; 191-201
1509-9415
Pojawia się w:
Discussiones Mathematicae - General Algebra and Applications
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ł:
On the H -Force Number of Hamiltonian Graphs and Cycle Extendability
Autorzy:
Hexel, Erhard
Powiązania:
https://bibliotekanauki.pl/articles/31342172.pdf
Data publikacji:
2017-02-01
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
cycle
hamiltonian graph
H -force number
cycle extendability
Opis:
The H-force number h(G) of a hamiltonian graph G is the smallest cardinality of a set A ⊆ V (G) such that each cycle containing all vertices of A is hamiltonian. In this paper a lower and an upper bound of h(G) is given. Such graphs, for which h(G) assumes the lower bound are characterized by a cycle extendability property. The H-force number of hamiltonian graphs which are exactly 2-connected can be calculated by a decomposition formula.
Źródło:
Discussiones Mathematicae Graph Theory; 2017, 37, 1; 79-88
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ł:
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ł
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ł:
Intersection graph of gamma sets in the total graph
Autorzy:
Chelvam, T.
Asir, T.
Powiązania:
https://bibliotekanauki.pl/articles/743214.pdf
Data publikacji:
2012
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
total graph
gamma sets
intersection graph
Hamiltonian
coloring
connectivity
domination number
Opis:
In this paper, we consider the intersection graph $I_{Γ}(ℤₙ)$ of gamma sets in the total graph on ℤₙ. We characterize the values of n for which $I_{Γ}(ℤₙ)$ is complete, bipartite, cycle, chordal and planar. Further, we prove that $I_{Γ}(ℤₙ)$ is an Eulerian, Hamiltonian and as well as a pancyclic graph. Also we obtain the value of the independent number, the clique number, the chromatic number, the connectivity and some domination parameters of $I_{Γ}(ℤₙ)$.
Źródło:
Discussiones Mathematicae Graph Theory; 2012, 32, 2; 341-356
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
Hamiltonian-colored powers of strong digraphs
Autorzy:
Johns, Garry
Jones, Ryan
Kolasinski, Kyle
Zhang, Ping
Powiązania:
https://bibliotekanauki.pl/articles/743288.pdf
Data publikacji:
2012
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
powers of a strong oriented graph
distance-colored digraphs
Hamiltonian-colored digraphs
Hamiltonian coloring exponents
Opis:
For a strong oriented graph D of order n and diameter d and an integer k with 1 ≤ k ≤ d, the kth power $D^k$ of D is that digraph having vertex set V(D) with the property that (u, v) is an arc of $D^k$ if the directed distance $^{→}d_D(u,v)$ from u to v in D is at most k. For every strong digraph D of order n ≥ 2 and every integer k ≥ ⌈n/2⌉, the digraph $D^k$ is Hamiltonian and the lower bound ⌈n/2⌉ is sharp. The digraph $D^k$ is distance-colored if each arc (u, v) of $D^k$ is assigned the color i where $i = ^{→}d_D(u,v)$. The digraph $D^k$ is Hamiltonian-colored if $D^k$ contains a properly arc-colored Hamiltonian cycle. The smallest positive integer k for which $D^k$ is Hamiltonian-colored is the Hamiltonian coloring exponent hce(D) of D. For each integer n ≥ 3, the Hamiltonian coloring exponent of the directed cycle $^{→}Cₙ$ of order n is determined whenever this number exists. It is shown for each integer k ≥ 2 that there exists a strong oriented graph Dₖ such that hce(Dₖ) = k with the added property that every properly colored Hamiltonian cycle in the kth power of Dₖ must use all k colors. It is shown for every positive integer p there exists a a connected graph G with two different strong orientations D and D' such that hce(D) - hce(D') ≥ p.
Źródło:
Discussiones Mathematicae Graph Theory; 2012, 32, 4; 705-724
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ł:
Hamiltonian and Pancyclic Graphs in the Class of Self-Centered Graphs with Radius Two
Autorzy:
Hrnčiar, Pavel
Monoszová, Gabriela
Powiązania:
https://bibliotekanauki.pl/articles/31342283.pdf
Data publikacji:
2018-08-01
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
self-centered graph with radius 2
Hamiltonian graph
pancyclic graph
size of graph
Opis:
The paper deals with Hamiltonian and pancyclic graphs in the class of all self-centered graphs of radius 2. For both of the two considered classes of graphs we have done the following. For a given number n of vertices, we have found an upper bound of the minimum size of such graphs. For n ≤ 12 we have found the exact values of the minimum size. On the other hand, the exact value of the maximum size has been found for every n. Moreover, we have shown that such a graph (of order n and) of size m exists for every m between the minimum and the maximum size. For n ≤ 10 we have found all nonisomorphic graphs of the minimum size, and for n = 11 only for Hamiltonian graphs.
Źródło:
Discussiones Mathematicae Graph Theory; 2018, 38, 3; 661-681
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ł:
Forbidden Subgraphs for Hamiltonicity of 1-Tough Graphs
Autorzy:
Li, Binlong
Broersma, Hajo J.
Zhang, Shenggui
Powiązania:
https://bibliotekanauki.pl/articles/31340596.pdf
Data publikacji:
2016-11-01
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
forbidden subgraph
1-tough graph
H-free graph
hamiltonian graph
Opis:
A graph G is said to be 1-tough if for every vertex cut S of G, the number of components of G − S does not exceed |S|. Being 1-tough is an obvious necessary condition for a graph to be hamiltonian, but it is not sufficient in general. We study the problem of characterizing all graphs H such that every 1-tough H-free graph is hamiltonian. We almost obtain a complete solution to this problem, leaving H = K1 ∪ P4 as the only open case.
Źródło:
Discussiones Mathematicae Graph Theory; 2016, 36, 4; 915-929
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
Extension of several sufficient conditions for Hamiltonian graphs
Autorzy:
Ainouche, Ahmed
Powiązania:
https://bibliotekanauki.pl/articles/744192.pdf
Data publikacji:
2006
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
hamiltonian graph
dual closure
neighborhood closure
Opis:
Let G be a 2-connected graph of order n. Suppose that for all 3-independent sets X in G, there exists a vertex u in X such that |N(X∖{u})|+d(u) ≥ n-1. Using the concept of dual closure, we prove that
1. G is hamiltonian if and only if its 0-dual closure is either complete or the cycle C₇
2. G is nonhamiltonian if and only if its 0-dual closure is either the graph $(K_r ∪ Kₛ ∪ Kₜ) ∨ K₂$, 1 ≤ r ≤ s ≤ t or the graph $((n+1)/2)K₁ ∨ K_{(n-1)/2}$.
It follows that it takes a polynomial time to check the hamiltonicity or the nonhamiltonicity of a graph satisfying the above condition. From this main result we derive a large number of extensions of previous sufficient conditions for hamiltonian graphs. All these results are sharp.
Źródło:
Discussiones Mathematicae Graph Theory; 2006, 26, 1; 23-39
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Wyświetlanie 1-15 z 25

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