Remarks on partially square graphs, hamiltonicity and circumference
Hamamache Kheddouci
Discussiones Mathematicae Graph Theory, Tome 21 (2001), p. 255-266 / Harvested from The Polish Digital Mathematics Library
Access to full text
Full (PDF)

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 NG(x)⊆NG[u]∪NG[v], where NG[x]=NG(x)∪x. In the case where G is a claw-free graph, G* is equal to G². We define σ°ₜ=min∑x∈SdG(x):SisanindependentsetinG*and|S|=t. We give for hamiltonicity and circumference new sufficient conditions depending on σ° and we improve some known results.

Publié le : 2001-01-01
EUDML-ID : urn:eudml:doc:270370 
@article{bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1148,
     author = {Hamamache Kheddouci},
     title = {Remarks on partially square graphs, hamiltonicity and circumference},
     journal = {Discussiones Mathematicae Graph Theory},
     volume = {21},
     year = {2001},
     pages = {255-266},
     zbl = {1002.05046},
     language = {en},
     url = {http://dml.mathdoc.fr/item/bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1148}
}

Hamamache Kheddouci. Remarks on partially square graphs, hamiltonicity and circumference. Discussiones Mathematicae Graph Theory, Tome 21 (2001) pp. 255-266. http://gdmltest.u-ga.fr/item/bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1148/

[000] [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. | Zbl 0770.05070

[001] [2] A. Ainouche and M. Kouider, Hamiltonism and partially square graph, Graphs and Combinatorics 15 (1999) 257-265, doi: 10.1007/s003730050059. | Zbl 0933.05096

[002] [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.

[003] [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).

[004] [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. | Zbl 0576.05035