An Improved Nordhaus–Gaddum-Type Theorem for 2-Rainbow Independent Domination Number

Enqiang Zhu
Additional contact information
Enqiang Zhu: Institute of Computing Science and Technology, Guangzhou University, Guangzhou 510006, China

Mathematics, 2021, vol. 9, issue 4, 1-10

Abstract: For a graph G , its k -rainbow independent domination number, written as ? rik ( G ) , is defined as the cardinality of a minimum set consisting of k vertex-disjoint independent sets V 1 , V 2 , … , V k such that every vertex in V 0 = V ( G ) \ ( ? i = 1 k V i ) has a neighbor in V i for all i ? { 1 , 2 , … , k } . This domination invariant was proposed by Kraner Šumenjak, Rall and Tepeh (in Applied Mathematics and Computation 333(15), 2018: 353–361), which aims to compute the independent domination number of G ? K k (the generalized prism) via studying the problem of integer labeling on G . They proved a Nordhaus–Gaddum-type theorem: 5 ? ? ri 2 ( G ) + ? ri 2 ( G ¯ ) ? n + 3 for any n -order graph G with n ? 3 , in which G ¯ denotes the complement of G . This work improves their result and shows that if G ? C 5 , then 5 ? ? ri 2 ( G ) + ? ri 2 ( G ¯ ) ? n + 2 .

Keywords: k-rainbow independent domination; Nordhaus–Gaddum; bounds (search for similar items in EconPapers)
JEL-codes: C (search for similar items in EconPapers)
Date: 2021
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
https://www.mdpi.com/2227-7390/9/4/402/pdf (application/pdf)
https://www.mdpi.com/2227-7390/9/4/402/ (text/html)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:gam:jmathe:v:9:y:2021:i:4:p:402-:d:501403

Access Statistics for this article

Mathematics is currently edited by Ms. Emma He

More articles in Mathematics from MDPI
Bibliographic data for series maintained by MDPI Indexing Manager ().