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
|
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 |
