Bounds for the Independence Number in k-Step Hamiltonian Graphs

Noor A’lawiah Abd Aziz; Nader Jafari Rad; Hailiza Kamarulhaili; Roslan Hasni

Conţinutul numărului revistei

Articolul precedent

Articolul urmator

778

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 Aziz¹, Nader Jafari Rad², Hailiza Kamarulhaili¹, Roslan Hasni³

¹ Universiti Sains Malaysia,
² Department of Mathematics, Shahrood University of Technology,
³ School of Informatics and Applied Mathematics, Universiti Malaysia Terengganu

Disponibil în IBN: 4 mai 2018

Descarcă PDF

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.

Dublin Core Export

<?xml version='1.0' encoding='utf-8'?>
<oai_dc:dc xmlns:dc='http://purl.org/dc/elements/1.1/' xmlns:oai_dc='http://www.openarchives.org/OAI/2.0/oai_dc/' xmlns:xsi='http://www.w3.org/2001/XMLSchema-instance' xsi:schemaLocation='http://www.openarchives.org/OAI/2.0/oai_dc/ http://www.openarchives.org/OAI/2.0/oai_dc.xsd'>
<dc:creator>Noor Alawiah, A.</dc:creator>
<dc:creator>Nader Jafari, R.</dc:creator>
<dc:creator>Hailiza, K.</dc:creator>
<dc:creator>Roslan, H.</dc:creator>
<dc:date>2018-03-31</dc:date>
<dc:description xml:lang='en'><p>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 &minus; 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.</p></dc:description>
<dc:source>Computer Science Journal of Moldova 76 (1) 15-28</dc:source>
<dc:subject>Independence number</dc:subject>
<dc:subject>Hamiltonian graph</dc:subject>
<dc:subject>k-
Step Hamiltonian graph.</dc:subject>
<dc:title>Bounds for the Independence Number in k-Step Hamiltonian Graphs</dc:title>
<dc:type>info:eu-repo/semantics/article</dc:type>
</oai_dc:dc>