REAL

On the Number of k-Dominating Independent Sets

Nagy, Zoltán Lóránt (2017) On the Number of k-Dominating Independent Sets. JOURNAL OF GRAPH THEORY, 84 (4). pp. 566-580. ISSN 0364-9024

[img]
Preview
Text
1504.03224.pdf

Download (200kB) | Preview

Abstract

We study the existence and the number of k-dominating independent sets in certain graph families. While the case k=1 namely the case of maximal independent sets-which is originated from Erdos and Moser-is widely investigated, much less is known in general. In this paper we settle the question for trees and prove that the maximum number of k-dominating independent sets in n-vertex graphs is between ck·22kn and ck'·2k+1n if k≥2, moreover the maximum number of 2-dominating independent sets in n-vertex graphs is between c·1.22n and c'·1.246n. Graph constructions containing a large number of k-dominating independent sets are coming from product graphs, complete bipartite graphs, and finite geometries. The product graph construction is associated with the number of certain Maximum Distance Separable (MDS) codes. © 2016 Wiley Periodicals, Inc.

Item Type: Article
Uncontrolled Keywords: Graph theory; Trees (mathematics); Graphic methods; MAXIMAL INDEPENDENT SETS; Domination; Maximal independent set; Finite geometry; MDS code; MDS codes; k-dominating; k-DIS; Hyperoval; (k,n)-arcs;
Subjects: Q Science / természettudomány > Q1 Science (General) / természettudomány általában
SWORD Depositor: MTMT SWORD
Depositing User: MTMT SWORD
Date Deposited: 09 May 2023 14:10
Last Modified: 09 May 2023 14:10
URI: http://real.mtak.hu/id/eprint/165140

Actions (login required)

Edit Item Edit Item