A new bound on maximum independent set and minimum connected dominating set in unit disk graphs

Yingfan L. Du () and Hongmin W. Du
Additional contact information
Yingfan L. Du: Highland Park High School
Hongmin W. Du: Highland Park High School

Journal of Combinatorial Optimization, 2015, vol. 30, issue 4, No 22, 1173-1179

Abstract: Abstract It is a conjecture that in any unit disk graph $$G$$ G , $$\alpha (G) \le 3 \cdot \gamma _c(G) + 3$$ α ( G ) ≤ 3 · γ c ( G ) + 3 where $$\alpha (G)$$ α ( G ) is the size of the maximum independent set in $$G$$ G and $$\gamma _c(G)$$ γ c ( G ) is the size of minimum connected dominating set in $$G$$ G . In this paper, we show that in any unit disk graph $$G$$ G , $$\alpha (G) \le 3.399 \cdot \gamma _c(G) + 4.874$$ α ( G ) ≤ 3.399 · γ c ( G ) + 4.874 . Currently, this is the best-known bound.

Keywords: Maximum independent set; Minimum connected dominating set; Unit disk graphs (search for similar items in EconPapers)
Date: 2015
References: View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10878-013-9690-0 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

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:spr:jcomop:v:30:y:2015:i:4:d:10.1007_s10878-013-9690-0

Ordering information: This journal article can be ordered from
https://www.springer.com/journal/10878

DOI: 10.1007/s10878-013-9690-0

Access Statistics for this article

Journal of Combinatorial Optimization is currently edited by Thai, My T.

More articles in Journal of Combinatorial Optimization from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().