Abstract | ||
---|---|---|
Let G be a Hamiltonian graph G of order n and maximum degree Δ, and let C(G) denote the set of cycle lengths occurring in G. It is easy to see that |C(G)| ≥ Δ - 1. In this paper, we prove that if Δ n/2, then |C(G)| ≥ (n + Δ - 3)/2. We also show that for every Δ ≥ 2 there is a graph G of order n ≥ 2Δ such that |C(G)| = Δ - 1, and the lower bound in case Δ n/2 is best possible. |
Year | DOI | Venue |
---|---|---|
2003 | 10.1016/S0012-365X(02)00817-8 | Discrete Mathematics |
Keywords | Field | DocType |
order n,cycles,maximum degree,pancyclic graphs,cycle length,graph g,05c45,hamiltonian graphs,hamiltonian graph,prescribed maximum degree,lower bound | Graph theory,Discrete mathematics,Graph,Combinatorics,Hamiltonian (quantum mechanics),Upper and lower bounds,Hamiltonian path,Cycle graph,Degree (graph theory),Mathematics,Pancyclic graph | Journal |
Volume | Issue | ISSN |
266 | 1-3 | Discrete Mathematics |
Citations | PageRank | References |
3 | 0.45 | 5 |
Authors | ||
2 |
Name | Order | Citations | PageRank |
---|---|---|---|
Antoni Marczyk | 1 | 66 | 10.91 |
Mariusz Woźniak | 2 | 204 | 34.54 |