Bounds for the Independence Number in k-Step Hamiltonian Graphs
Conţinutul numărului revistei
Articolul precedent
Articolul urmator
194 3
Ultima descărcare din IBN:
2020-07-22 11:36
Căutarea după subiecte
similare conform CZU
519.1 (75)
Analiză combinatorică. Teoria grafurilor (74)
SM ISO690:2012
NOOR A’LAWIAH, Abd Aziz; NADER JAFARI, Rad; HAILIZA, Kamarulhaili; ROSLAN, Hasni. Bounds for the Independence Number in k-Step Hamiltonian Graphs. In: Computer Science Journal of Moldova. 2018, nr. 1(76), pp. 15-28. ISSN 1561-4042.
EXPORT metadate:
Google Scholar
Dublin Core
Computer Science Journal of Moldova
Numărul 1(76) / 2018 / ISSN 1561-4042

Bounds for the Independence Number in k-Step Hamiltonian Graphs

CZU: 519.1
MSC 2010: 05C69, 05C78.
Pag. 15-28

Noor A’lawiah Abd Aziz1, Nader Jafari Rad2, Hailiza Kamarulhaili1, Roslan Hasni3
1 Universiti Sains Malaysia,
2 Department of Mathematics, Shahrood University of Technology,
3 School of Informatics and Applied Mathematics, Universiti Malaysia Terengganu
Disponibil în IBN: 4 mai 2018


For a given integer k, a graph G of order n is called k-step Hamiltonian if there is a labeling v1, v2, ..., vn of vertices of G such that d(v1, vn) = d(vi, vi+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.