DMGT

ISSN 1234-3099 (print version)

ISSN 2083-5892 (electronic version)

IMPACT FACTOR 2018: 0.741

SCImago Journal Rank (SJR) 2018: 0.763

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

Discussiones Mathematicae Graph Theory

THE FLOWER CONJECTURE IN SPECIAL CLASSES OF GRAPHS

 Zdenk Ryjáček Department of Mathematics, University of West Bohemia Americká 42, 306 14 Plze, Czech Republic Ingo Schiermeyer Lehrstuhl C für Mathematik, Rhein.n-Westf. Techn. Hochschule Templergraben 55, D-52062 Aachen, Germany

Abstract

We say that a spanning eulerian subgraph F ⊂ G is a flower in a graph G if there is a vertex u ∈ V(G) (called the center of F) such that all vertices of G except  u  are of the degree exactly 2 in F. A graph G has the flower property if every vertex of G is a center of a flower.

Kaneko conjectured that G has the flower property if and only if G is hamiltonian. In the present paper we prove this conjecture in several special classes of graphs, among others in squares and in a certain subclass of claw-free graphs.

Keywords: hamiltonian graphs, flower conjecture, square, claw-free graphs.

1991 Mathematics Subject Classification: 05C45.

References

 [1] J.A. Bondy and U.S.R. Murty, Graph Theory with Applications (Macmillan, London and Elsevier, New York, 1976). [2] H. Fleischner, The square of every two-connected graph is hamiltonian, J. Combin. Theory (B) 16 (1974) 29-34, doi: 10.1016/0095-8956(74)90091-4. [3] H. Fleischner, In the squares of graphs, hamiltonicity and pancyclicity, hamiltonian connectedness and panconnectedness are equivalent concepts, Monatshefte für Math. 82 (1976) 125-149, doi: 10.1007/BF01305995. [4] A. Kaneko, Research problem, Discrete Math., (to appear). [5] A. Kaneko and K. Ota, The flower property implies 1-toughness and the existence of a 2-factor, Manuscript (unpublished).