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ę "claw-free" wg kryterium: Temat

  Lista filtrów
Wyrównaj
    Wyświetlanie 1-13 z 13
    Tytuł:
    On graphs G for which both g and G̅ are claw-free
    Autorzy:
    Fujita, Shinya
    Powiązania:
    https://bibliotekanauki.pl/articles/744362.pdf
    Data publikacji:
    2005
    Wydawca:
    Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
    Tematy:
    claw-free
    complement
    maximum degree
    Opis:
    Let G be a graph with |V(G)| ≥ 10. We prove that if both G and G̅ are claw-free, then min{Δ(G), Δ(G̅)} ≤ 2. As a generalization of this result in the case where |V(G)| is sufficiently large, we also prove that if both G and G̅ are $K_{1,t}$-free, then min{Δ(G),Δ(G̅)} ≤ r(t- 1,t)-1 where r(t-1,t) is the Ramsey number.
    Źródło:
    Discussiones Mathematicae Graph Theory; 2005, 25, 3; 267-272
    2083-5892
    Pojawia się w:
    Discussiones Mathematicae Graph Theory
    Dostawca treści:
    Biblioteka Nauki
    Artykuł
    Tytuł:
    On the Erdős-Gyárfás conjecture in claw-free graphs
    Autorzy:
    Nowbandegani, Pouria Salehi
    Esfandiari, Hossein
    Haghighi, Mohammad Hassan Shirdareh
    Bibak, Khodakhast
    Powiązania:
    https://bibliotekanauki.pl/articles/30148697.pdf
    Data publikacji:
    2014-08-01
    Wydawca:
    Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
    Tematy:
    Erdős-Gyárfás conjecture
    claw-free graphs
    cycles
    Opis:
    The Erdős-Gyárfás conjecture states that every graph with minimum degree at least three has a cycle whose length is a power of 2. Since this conjecture has proven to be far from reach, Hobbs asked if the Erdős-Gyárfás conjecture holds in claw-free graphs. In this paper, we obtain some results on this question, in particular for cubic claw-free graphs.
    Źródło:
    Discussiones Mathematicae Graph Theory; 2014, 34, 3; 635-640
    2083-5892
    Pojawia się w:
    Discussiones Mathematicae Graph Theory
    Dostawca treści:
    Biblioteka Nauki
    Artykuł
    Tytuł:
    2-factors in claw-free graphs
    Autorzy:
    Chen, Guantao
    Faudree, Jill
    Gould, Ronald
    Saito, Akira
    Powiązania:
    https://bibliotekanauki.pl/articles/743756.pdf
    Data publikacji:
    2000
    Wydawca:
    Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
    Tematy:
    claw-free
    forbidden subgraphs
    2-factors
    cycles
    Opis:
    We consider the question of the range of the number of cycles possible in a 2-factor of a 2-connected claw-free graph with sufficiently high minimum degree. (By claw-free we mean the graph has no induced $K_{1,3}$.) In particular, we show that for such a graph G of order n ≥ 51 with δ(G) ≥ (n-2)/3, G contains a 2-factor with exactly k cycles, for 1 ≤ k ≤ (n-24)/3. We also show that this result is sharp in the sense that if we lower δ(G), we cannot obtain the full range of values for k.
    Źródło:
    Discussiones Mathematicae Graph Theory; 2000, 20, 2; 165-172
    2083-5892
    Pojawia się w:
    Discussiones Mathematicae Graph Theory
    Dostawca treści:
    Biblioteka Nauki
    Artykuł
    Tytuł:
    Potential forbidden triples implying hamiltonicity: for sufficiently large graphs
    Autorzy:
    Faudree, Ralph
    Gould, Ronald
    Jacobson, Michael
    Powiązania:
    https://bibliotekanauki.pl/articles/744366.pdf
    Data publikacji:
    2005
    Wydawca:
    Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
    Tematy:
    hamiltonian
    forbidden subgraph
    claw-free
    induced subgraph
    Opis:
    In [1], Brousek characterizes all triples of connected graphs, G₁,G₂,G₃, with $G_i = K_{1,3}$ for some i = 1,2, or 3, such that all G₁G₂ G₃-free graphs contain a hamiltonian cycle. In [8], Faudree, Gould, Jacobson and Lesniak consider the problem of finding triples of graphs G₁,G₂,G₃, none of which is a $K_{1,s}$, s ≥ 3 such that G₁G₂G₃-free graphs of sufficiently large order contain a hamiltonian cycle. In [6], a characterization was given of all triples G₁,G₂,G₃ with none being $K_{1,3}$, such that all G₁G₂G₃-free graphs are hamiltonian. This result, together with the triples given by Brousek, completely characterize the forbidden triples G₁,G₂,G₃ such that all G₁G₂G₃-free graphs are hamiltonian. In this paper we consider the question of which triples (including $K_{1,s}$, s ≥ 3) of forbidden subgraphs potentially imply all sufficiently large graphs are hamiltonian. For s ≥ 4 we characterize these families.
    Źródło:
    Discussiones Mathematicae Graph Theory; 2005, 25, 3; 273-289
    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ł:
    Forbidden Pairs and (k, m)-Pancyclicity
    Autorzy:
    Crane, Charles Brian
    Powiązania:
    https://bibliotekanauki.pl/articles/31341696.pdf
    Data publikacji:
    2017-08-01
    Wydawca:
    Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
    Tematy:
    hamiltonian
    pancyclic
    forbidden subgraph
    cycle
    claw-free
    Opis:
    A graph G on n vertices is said to be (k,m)-pancyclic if every set of k vertices in G is contained in a cycle of length r for each r ∈ {m, m+1, . . ., n}. This property, which generalizes the notion of a vertex pancyclic graph, was defined by Faudree, Gould, Jacobson, and Lesniak in 2004. The notion of (k, m)-pancyclicity provides one way to measure the prevalence of cycles in a graph. We consider pairs of subgraphs that, when forbidden, guarantee hamiltonicity for 2-connected graphs on n ≥ 10 vertices. There are exactly ten such pairs. For each integer k ≥ 1 and each of eight such subgraph pairs {R, S}, we determine the smallest value m such that any 2-connected {R, S}-free graph on n ≥ 10 vertices is guaranteed to be (k,m)-pancyclic. Examples are provided that show the given values are best possible. Each such example we provide represents an infinite family of graphs.
    Źródło:
    Discussiones Mathematicae Graph Theory; 2017, 37, 3; 649-663
    2083-5892
    Pojawia się w:
    Discussiones Mathematicae Graph Theory
    Dostawca treści:
    Biblioteka Nauki
    Artykuł
    Tytuł:
    The flower conjecture in special classes of graphs
    Autorzy:
    Ryjáček, Zdeněk
    Schiermeyer, Ingo
    Powiązania:
    https://bibliotekanauki.pl/articles/972046.pdf
    Data publikacji:
    1995
    Wydawca:
    Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
    Tematy:
    hamiltonian graphs
    flower conjecture
    square
    claw-free graphs
    Opis:
    We say that a spanning eulerian subgraph F ⊂ G is a flower in a graph G if there is a vertex u ∈ V(G) (called the center of F) such that all vertices of G except u are of the degree exactly 2 in F. A graph G has the flower property if every vertex of G is a center of a flower. Kaneko conjectured that G has the flower property if and only if G is hamiltonian. In the present paper we prove this conjecture in several special classes of graphs, among others in squares and in a certain subclass of claw-free graphs.
    Źródło:
    Discussiones Mathematicae Graph Theory; 1995, 15, 2; 179-184
    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ł:
    On the Numbers of Cut-Vertices and End-Blocks in 4-Regular Graphs
    Autorzy:
    Wang, Dingguo
    Shan, Erfang
    Powiązania:
    https://bibliotekanauki.pl/articles/30148001.pdf
    Data publikacji:
    2014-02-01
    Wydawca:
    Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
    Tematy:
    4-regular graph
    claw-free
    cut-vertices
    end-blocks
    Opis:
    A cut-vertex in a graph G is a vertex whose removal increases the number of connected components of G. An end-block of G is a block with a single cut-vertex. In this paper we establish upper bounds on the numbers of end-blocks and cut-vertices in a 4-regular graph G and claw-free 4-regular graphs. We characterize the extremal graphs achieving these bounds.
    Źródło:
    Discussiones Mathematicae Graph Theory; 2014, 34, 1; 127-136
    2083-5892
    Pojawia się w:
    Discussiones Mathematicae Graph Theory
    Dostawca treści:
    Biblioteka Nauki
    Artykuł
    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ł:
    Remarks on partially square graphs, hamiltonicity and circumference
    Autorzy:
    Kheddouci, Hamamache
    Powiązania:
    https://bibliotekanauki.pl/articles/743495.pdf
    Data publikacji:
    2001
    Wydawca:
    Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
    Tematy:
    partially square graph
    claw-free graph
    independent set
    hamiltonicity and circumference
    Opis:
    Given a graph G, its partially square graph G* is a graph obtained by adding an edge (u,v) for each pair u, v of vertices of G at distance 2 whenever the vertices u and v have a common neighbor x satisfying the condition $N_G(x) ⊆ N_G[u] ∪ N_G[v]$, where $N_G[x] = N_G(x) ∪ {x}$. In the case where G is a claw-free graph, G* is equal to G². We define $σ°ₜ = min{ ∑_{x∈S} d_G(x):S is an independent set in G* and |S| = t}$. We give for hamiltonicity and circumference new sufficient conditions depending on σ° and we improve some known results.
    Źródło:
    Discussiones Mathematicae Graph Theory; 2001, 21, 2; 255-266
    2083-5892
    Pojawia się w:
    Discussiones Mathematicae Graph Theory
    Dostawca treści:
    Biblioteka Nauki
    Artykuł
    Tytuł:
    Total domination versus paired domination
    Autorzy:
    Schaudt, Oliver
    Powiązania:
    https://bibliotekanauki.pl/articles/743224.pdf
    Data publikacji:
    2012
    Wydawca:
    Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
    Tematy:
    total domination
    upper total domination
    paired domination
    upper paired domination
    generalized claw-free graphs
    Opis:
    A dominating set of a graph G is a vertex subset that any vertex of G either belongs to or is adjacent to. A total dominating set is a dominating set whose induced subgraph does not contain isolated vertices. The minimal size of a total dominating set, the total domination number, is denoted by γₜ. The maximal size of an inclusionwise minimal total dominating set, the upper total domination number, is denoted by Γₜ. A paired dominating set is a dominating set whose induced subgraph has a perfect matching. The minimal size of a paired dominating set, the paired domination number, is denoted by γₚ. The maximal size of an inclusionwise minimal paired dominating set, the upper paired domination number, is denoted by Γₚ.
    In this paper we prove several results on the ratio of these four parameters: For each r ≥ 2 we prove the sharp bound γₚ/γₜ ≤ 2 - 2/r for $K_{1,r}$-free graphs. As a consequence, we obtain the sharp bound γₚ/γₜ ≤ 2 - 2/(Δ+1), where Δ is the maximum degree. We also show for each r ≥ 2 that ${C₅,T_r}$-free graphs fulfill the sharp bound γₚ/γₜ ≤ 2 - 2/r, where $T_r$ is obtained from $K_{1,r}$ by subdividing each edge exactly once. We show that all of these bounds also hold for the ratio Γₚ/Γₜ. Further, we prove that a graph hereditarily has an induced paired dominating set if and only if γₚ ≤ Γₜ holds for any induced subgraph. We also give a finite forbidden subgraph characterization for this condition. We exactly determine the maximal value of the ratio γₚ/Γₜ taken over the induced subgraphs of a graph. As a consequence, we prove for each r ≥ 3 the sharp bound γₚ/Γₜ ≤ 2 - 2/r for graphs that do not contain the corona of $K_{1,r}$ as subgraph. In particular, we obtain the sharp bound γₚ/Γₜ ≤ 2 - 2/Δ.
    Źródło:
    Discussiones Mathematicae Graph Theory; 2012, 32, 3; 435-447
    2083-5892
    Pojawia się w:
    Discussiones Mathematicae Graph Theory
    Dostawca treści:
    Biblioteka Nauki
    Artykuł
    Tytuł:
    Some Observations on the Smallest Adjacency Eigenvalue of a Graph
    Autorzy:
    Cioabă, Sebastian M.
    Elzinga, Randall J.
    Gregory, David A.
    Powiązania:
    https://bibliotekanauki.pl/articles/31548045.pdf
    Data publikacji:
    2020-05-01
    Wydawca:
    Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
    Tematy:
    graph spectrum
    smallest eigenvalue
    adjacency matrix
    graph decomposition
    clique partition
    claw-free graphs
    maximum cut
    Opis:
    In this paper, we discuss various connections between the smallest eigenvalue of the adjacency matrix of a graph and its structure. There are several techniques for obtaining upper bounds on the smallest eigenvalue, and some of them are based on Rayleigh quotients, Cauchy interlacing using induced subgraphs, and Haemers interlacing with vertex partitions and quotient matrices. In this paper, we are interested in obtaining lower bounds for the smallest eigenvalue. Motivated by results on line graphs and generalized line graphs, we show how graph decompositions can be used to obtain such lower bounds.
    Źródło:
    Discussiones Mathematicae Graph Theory; 2020, 40, 2; 467-493
    2083-5892
    Pojawia się w:
    Discussiones Mathematicae Graph Theory
    Dostawca treści:
    Biblioteka Nauki
    Artykuł
      Wyświetlanie 1-13 z 13

      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