A Fan-type heavy pair od subgraphs for pancyclicity of 2-connected graphs
Author(s) -
Wojciech Wideł
Publication year - 2015
Publication title -
discussiones mathematicae graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.476
H-Index - 19
eISSN - 2083-5892
pISSN - 1234-3099
DOI - 10.7151/dmgt.1840
Subject(s) - mathematics , combinatorics , type (biology) , biology , paleontology
Let G be a graph on n vertices and let H be a given graph. We say that G is pancyclic, if it contains cycles of all lengths from 3 up to n, and that it is H-f1-heavy, if for every induced subgraph K of G isomorphic to H and every two vertices u, v ∈ V (K), dK(u, v) = 2 implies min{dG(u),dG(v)}≥n+12$\min \{ d_G (u),d_G (v)\} \ge {{n + 1} \over 2}$. In this paper we prove that every 2-connected {K1,3, P5}-f1-heavy graph is pancyclic. This result completes the answer to the problem of finding f1-heavy pairs of subgraphs implying pancyclicity of 2-connected graphs
Accelerating Research
Robert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom
Address
John Eccles HouseRobert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom