DMGT

ISSN 1234-3099 (print version)

ISSN 2083-5892 (electronic version)

https://doi.org/10.7151/dmgt

Discussiones Mathematicae Graph Theory

IMPACT FACTOR 2018: 0.741

SCImago Journal Rank (SJR) 2018: 0.763

Rejection Rate (2018-2019): c. 84%

Discussiones Mathematicae Graph Theory

PDF

Discussiones Mathematicae Graph Theory 21(1) (2001) 255-266
DOI: 10.7151/dmgt.1148

REMARKS ON PARTIALLY SQUARE GRAPHS, HAMILTONICITY AND CIRCUMFERENCE

Hamamache Kheddouci

LE2I FRE-CNRS 2309
Université de Bourgogne, B.P. 47870
21078 Dijon Cedex, France
e-mail: kheddouc@u-bourgogne.fr

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 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 G2. We define σtº = min{∑x ∈ SdG(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.

Keywords: partially square graph, claw-free graph, independent set, hamiltonicity and circumference.

2000 Mathematics Subject Classification: 05C45.

References

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

Received 28 December 2000
Revised 16 May 2001