Temat: closure - Katalog OPAC zbiorów

Skocz do pozycji: 1.

Tytuł:: On the Independence Number of Traceable 2-Connected Claw-Free Graphs
Autorzy:: Wang, Shipeng
Xiong, Liming
Powiązania:: https://bibliotekanauki.pl/articles/31343185.pdf
Data publikacji:: 2019-11-01
Wydawca:: Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:: traceability
independence number
matching number
trail
closure
Opis:: A well-known theorem by Chvátal-Erdőos [A note on Hamilton circuits, Discrete Math. 2 (1972) 111–135] states that if the independence number of a graph G is at most its connectivity plus one, then G is traceable. In this article, we show that every 2-connected claw-free graph with independence number α(G) ≤ 6 is traceable or belongs to two exceptional families of well-defined graphs. As a corollary, we also show that every 2-connected claw-free graph with independence number α(G) ≤ 5 is traceable.
Źródło:: Discussiones Mathematicae Graph Theory; 2019, 39, 4; 925-937
2083-5892
Pojawia się w:: Discussiones Mathematicae Graph Theory
Dostawca treści:: Biblioteka Nauki

Artykuł

Skocz do pozycji: 2.

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ł

Skocz do pozycji: 3.

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ł

Informacja