Bounds for the Independence Number in k-Step Hamiltonian Graphs
Închide
Conţinutul numărului revistei
Articolul precedent
Articolul urmator
106 2
Ultima descărcare din IBN:
2018-06-17 12:18
Căutarea după subiecte
similare conform CZU
519.1 (70)
Analiză combinatorică. Teoria grafurilor (69)
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
Crossref
CERIF
BibTeX
DataCite
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


Rezumat

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.

Cuvinte-cheie
Independence number, Hamiltonian graph, k- Step Hamiltonian graph.