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
–
0.13 Mb