We found a match
Your institution may have rights to this item. Sign in to continue.
- Title
On chromatic number and clique number in k-step Hamiltonian graphs.
- Authors
Aziz, Noor A'lawiah Abd; Rad, Nader Jafari; Kamarulhaili, Hailiza; Hasni, Roslan
- Abstract
A graph G of order n is called k-step Hamiltonian for k ≥ 1 if we can label the vertices of G as v1, v2,..., vn such that d(vn, v1) = d(vi, vi+1) = k for i = 1, 2,..., n-1. The (vertex) chromatic number of a graph G is the minimum number of colors needed to color the vertices of G so that no pair of adjacent vertices receive the same color. The clique number of G is the maximum cardinality of a set of pairwise adjacent vertices in G. In this paper, we study the chromatic number and the clique number in k-step Hamiltonian graphs for k ≥ 2. We present upper bounds for the chromatic number in k-step Hamiltonian graphs and give characterizations of graphs achieving the equality of the bounds. We also present an upper bound for the clique number in k-step Hamiltonian graphs and characterize graphs achieving equality of the bound.
- Subjects
HAMILTONIAN graph theory; GEOMETRIC vertices; GRAPH coloring; CARDINAL numbers; MATHEMATICAL bounds
- Publication
Communications in Combinatorics & Optimization, 2024, Vol 9, Issue 1, p37
- ISSN
2538-2128
- Publication type
Article
- DOI
10.22049/cco.2022.27970.1407