Bounds for the Independence Number in k-Step Hamiltonian Graphs
Închide
Conţinutul numărului revistei
Articolul precedent
Articolul urmator
766 3
Ultima descărcare din IBN:
2020-07-22 11:36
Căutarea după subiecte
similare conform CZU
519.1 (116)
Analiză combinatorică. Teoria grafurilor (114)
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

DataCite
Dublin Core
Computer Science Journal of Moldova
Numărul 1(76) / 2018 / ISSN 1561-4042 /ISSNe 2587-4330

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.

Google Scholar Export

<meta name="citation_title" content="Bounds for the Independence Number in k-Step Hamiltonian Graphs">
<meta name="citation_author" content="Noor A’lawiah Abd Aziz">
<meta name="citation_author" content="Nader Jafari Rad">
<meta name="citation_author" content="Hailiza Kamarulhaili">
<meta name="citation_author" content="Roslan Hasni">
<meta name="citation_publication_date" content="2018/03/31">
<meta name="citation_journal_title" content="Computer Science Journal of Moldova">
<meta name="citation_volume" content="76">
<meta name="citation_issue" content="1">
<meta name="citation_firstpage" content="15">
<meta name="citation_lastpage" content="28">
<meta name="citation_pdf_url" content="https://ibn.idsi.md/sites/default/files/imag_file/15-28.pdf">