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

794

Ultima descărcare din IBN:
2020-07-22 11:36

Căutarea după subiecte
similare conform CZU

519.1 (117)

Analiză combinatorică. Teoria grafurilor (115)

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.

Crossref XML Export

<?xml version='1.0' encoding='utf-8'?>
<doi_batch version='4.3.7' xmlns='http://www.crossref.org/schema/4.3.7' xmlns:xsi='http://www.w3.org/2001/XMLSchema-instance' xsi:schemaLocation='http://www.crossref.org/schema/4.3.7 http://www.crossref.org/schema/deposit/crossref4.3.7.xsd'>
<head>
<doi_batch_id>ibn-61946</doi_batch_id>
<timestamp>1714167186</timestamp>
<depositor>
<depositor_name>Information Society Development Instiute, Republic of Moldova</depositor_name>
<email_address>idsi@asm.md</email_address>
</depositor>
</head>
<body>
<journal>
<journal_metadata>
<full_title>Computer Science Journal of Moldova</full_title>
<issn media_type='print'>15614042</issn>
</journal_metadata>
<journal_issue>
<publication_date media_type='print'>
<year>2018</year>
</publication_date>
<issue>1(76)</issue>
</journal_issue>
<journal_article publication_type='full_text'><titles>
<title>Bounds for the Independence Number in k-Step Hamiltonian Graphs</title>
</titles>
<contributors>
<person_name sequence='first' contributor_role='author'>
<given_name>Abd Aziz</given_name>
<surname>Noor Alawiah</surname>
</person_name>
<person_name sequence='additional' contributor_role='author'>
<given_name>Rad</given_name>
<surname>Nader Jafari</surname>
</person_name>
<person_name sequence='additional' contributor_role='author'>
<given_name>Kamarulhaili</given_name>
<surname>Hailiza</surname>
</person_name>
<person_name sequence='additional' contributor_role='author'>
<given_name>Hasni</given_name>
<surname>Roslan</surname>
</person_name>
</contributors>
<publication_date media_type='print'>
<year>2018</year>
</publication_date>
<pages>
<first_page>15</first_page>
<last_page>28</last_page>
</pages>
</journal_article>
</journal>
</body>
</doi_batch>