文章基本信息

标题：Bounds for the Independence Number in k-Step Hamiltonian Graphs
本地全文：下载
作者：Noor A'lawiah Abd Aziz ; Nader Jafari Rad ; Hailiza Kamarulhaili 等
期刊名称：Computer Science Journal of Moldova
印刷版ISSN：1561-4042
出版年度：2018
卷号：26
期号：1
页码：15-28
出版社：Institute of Mathematics and Computer Science
摘要：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.
关键词：Independence number; Hamiltonian graph; $k$-Step Hamiltonian graph.