# Remarks on partially square graphs, hamiltonicity and circumference

Discussiones Mathematicae Graph Theory (2001)

- Volume: 21, Issue: 2, page 255-266
- ISSN: 2083-5892

## Access Full Article

top## Abstract

top## How to cite

topHamamache Kheddouci. "Remarks on partially square graphs, hamiltonicity and circumference." Discussiones Mathematicae Graph Theory 21.2 (2001): 255-266. <http://eudml.org/doc/270370>.

@article{HamamacheKheddouci2001,

abstract = {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.},

author = {Hamamache Kheddouci},

journal = {Discussiones Mathematicae Graph Theory},

keywords = {partially square graph; claw-free graph; independent set; hamiltonicity and circumference; Hamiltonicity; circumference},

language = {eng},

number = {2},

pages = {255-266},

title = {Remarks on partially square graphs, hamiltonicity and circumference},

url = {http://eudml.org/doc/270370},

volume = {21},

year = {2001},

}

TY - JOUR

AU - Hamamache Kheddouci

TI - Remarks on partially square graphs, hamiltonicity and circumference

JO - Discussiones Mathematicae Graph Theory

PY - 2001

VL - 21

IS - 2

SP - 255

EP - 266

AB - 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.

LA - eng

KW - partially square graph; claw-free graph; independent set; hamiltonicity and circumference; Hamiltonicity; circumference

UR - http://eudml.org/doc/270370

ER -

## References

top- [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. Zbl0770.05070
- [2] A. Ainouche and M. Kouider, Hamiltonism and partially square graph, Graphs and Combinatorics 15 (1999) 257-265, doi: 10.1007/s003730050059. Zbl0933.05096
- [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. Zbl0576.05035

## NotesEmbed ?

topTo embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.