RO  EN
IMI/Publicaţii/CSJM/Ediţii/CSJM v.26, n.1 (76), 2018/

Bounds for the Independence Number in k-Step Hamiltonian Graphs

Authors: Noor A'lawiah Abd Aziz, Nader Jafari Rad, Hailiza Kamarulhaili, Roslan Hasni
Keywords: Independence number, Hamiltonian graph, $k$-Step Hamiltonian graph.

Abstract

For a given integer $k$, a graph $G$ of order $n$ is called $k$-step Hamiltonian if there is a labeling $v_1,v_2,...,v_n$ of vertices of $G$ such that $d(v_1,v_n)=d(v_i,v_{i+1})=k$ for $i=1,2,...,n-1$. The independence number of a graph is the maximum cardinality of a subset of pair-wise non-adjacent vertices. In this paper we study the independence number in $k$-step Hamiltonian graphs. We present sharp upper bounds as well as sharp lower bounds, and then present a construction that produces infinite families of $k$-step Hamiltonian graphs with arbitrarily large independence number.

Noor A’lawiah Abd Aziz
School of Mathematical Sciences, Universiti Sains Malaysia
11800 USM Penang, Malaysia
E-mail:

Nader Jafari Rad
Department of Mathematics, Shahrood University of Technology
Shahrood, Iran
E-mail:

Hailiza Kamarulhaili
School of Mathematical Sciences, Universiti Sains Malaysia
11800 USM Penang, Malaysia
E-mail:

Roslan Hasni
School of Informatics and Applied Mathematics, Universiti Malaysia Terengganu
21030 Kuala Nerus, Terengganu, Malaysia
E-mail:



Fulltext

Adobe PDF document – 0.13 Mb