PL EN


Preferencje help
Widoczny [Schowaj] Abstrakt
Liczba wyników
2001 | 21 | 2 | 255-266
Tytuł artykułu

Remarks on partially square graphs, hamiltonicity and circumference

Treść / Zawartość
Warianty tytułu
Języki publikacji
EN
Abstrakty
EN
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.
Wydawca
Rocznik
Tom
21
Numer
2
Strony
255-266
Opis fizyczny
Daty
wydano
2001
otrzymano
2000-12-28
poprawiono
2001-05-16
Twórcy
  • LE2I FRE-CNRS 2309, Université de Bourgogne, B.P. 47870, 21078 Dijon Cedex, France
Bibliografia
  • [1] A. Ainouche, An improvement of Fraisse's sufficient condition for hamiltonian graphs, J. Graph Theory 16 (1992) 529-543, doi: 10.1002/jgt.3190160602.
  • [2] A. Ainouche and M. Kouider, Hamiltonism and partially square graph, Graphs and Combinatorics 15 (1999) 257-265, doi: 10.1007/s003730050059.
  • [3] J.C. Bermond, On Hamiltonian Walks, in: C.St.J.A. Nash-Wiliams and J. Sheehan, eds, Proceedings of the Fifth British Combinatorial Conference, Aberdeen, 1975 (Congr. Numerantium XV, Utilitas Math. Publ. Inc., 1975) 41-51.
  • [4] A. Bondy, Longest paths and cycles in graphs of high degree, Research report CORR 80-16 Dept of Combinatorics and Optimization (University of Waterloo, 1980).
  • [5] I. Fournier and P. Fraisse, On a conjecture of Bondy, J. Combin. Theory (B) 39 (1985) 17-26, doi: 10.1016/0095-8956(85)90035-8.
Typ dokumentu
Bibliografia
Identyfikatory
Identyfikator YADDA
bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1148
JavaScript jest wyłączony w Twojej przeglądarce internetowej. Włącz go, a następnie odśwież stronę, aby móc w pełni z niej korzystać.