## 3 Linear Programming Approach
Now note that the greedy algorithm will be forced to pick the vertices \(s_{p},s_{p-1},\ldots,s_{1}\), in that order, but the minimum dominating set in \(G\) is \(\{t_{1},t_{2}\}\) and \(\Delta=2^{p}+p+1\)._

## References

* (1) [PERSON] Two Theorems in Graph Theory. _Proc. Natl. Acad. Sci. USA_**1957**, 43, 842-844. [CrossRef] [PubMed]
* (2) [PERSON]; [PERSON]; [PERSON] _Graphs and Digraphs_; CRC Press: Boca Raton, FL, USA, 2010. * (3) [PERSON]; [PERSON]; [PERSON]; [PERSON] _Introduction to Algorithms_; MIT Press: Cambridge, MA, USA, 1990. * (4) [PERSON] _Theory of Linear and Integer Programming_; John Wiley & Sons: Hoboken, NJ, USA, 1998. * (5) [PERSON]; [PERSON]; [PERSON] _Fundamentals of Domination in Graphs_; CRC Press: Boca Raton, FL, USA, 1988. * (6) [PERSON]; [PERSON]; [PERSON] Unit disk graphs. _Discret. Math._**1990**, _86_, 165-177. [CrossRef]
* (7) [PERSON]; [PERSON] Analytical approach to parallel repetition. In _Symposium on Theory of Computing_; 2014; pp. 624-633. Available online: [[https://www.dsteurer.org/talk/productgames.pdf](https://www.dsteurer.org/talk/productgames.pdf)]([https://www.dsteurer.org/talk/productgames.pdf](https://www.dsteurer.org/talk/productgames.pdf)) (accessed on 9 December 2020). * (8) [PERSON] An Order-based Algorithm for Minimum Dominating Set with Application in Graph Mining. _Inf. Sci._**2018**, _426_, 101-116. [CrossRef]
* (9) [PERSON]; [PERSON]; [PERSON] Fast Dominating Set Algorithms for Social Networks. In _MAICS_; 2015. Available online: [[http://ceur-ws.org/Vol-1353/paper_16.pdf](http://ceur-ws.org/Vol-1353/paper_16.pdf)]([http://ceur-ws.org/Vol-1353/paper_16.pdf](http://ceur-ws.org/Vol-1353/paper_16.pdf)) (accessed on 9 December 2020). * (10) [PERSON]; [PERSON]; [PERSON]; [PERSON]; [PERSON] Structural and Algorithmic Aspects of Massive Social Networks. 2004; pp. 718-727. Available online: [[http://citeseer.ist.psu.edu/viewdoc/download?doi=10.1.1.214.2097&rep=rep1&type=pdf](http://citeseer.ist.psu.edu/viewdoc/download?doi=10.1.1.214.2097&rep=rep1&type=pdf)]([http://citeseer.ist.psu.edu/viewdoc/download?doi=10.1.1.214.2097&rep=rep1&type=pdf](http://citeseer.ist.psu.edu/viewdoc/download?doi=10.1.1.214.2097&rep=rep1&type=pdf)) (accessed on 9 December 2020). * (11) [PERSON] Experimental Analysis of Heuristic Algorithms for the Dominating Set Problem. _Algorithmica_**2002**, _33_, 3-18. [CrossRef]
* (12) [PERSON] Greedy domination on biclique-free graphs. _Inf. Process. Lett._**2019**, _145_, 64-67 [CrossRef]
* (13) [PERSON]; [PERSON] Tight approximation bounds for dominating set on graphs of bounded arboricity. _Inf. Process. Lett._**2017**, _122_, 21-24. [CrossRef]
* (14) [PERSON] On distance r-dominating and 2r-independent sets in sparse graphs. _J. Graph Theory_**2017**. Available online: [[https://arxiv.org/pdf/1710.10010.pdf](https://arxiv.org/pdf/1710.10010.pdf)]([https://arxiv.org/pdf/1710.10010.pdf](https://arxiv.org/pdf/1710.10010.pdf)) (accessed on 9 December 2020). * (15) [PERSON]. Decomposition of finite graphs into forests. _J. Lond. Math. Soc._**1964**, _1_-39, 12. [CrossRef]
* (16) [PERSON]; [PERSON] Forests, frames, and games: Algorithms for matroid sums and applications. _Algorithmica_**1992**, \(7\), 465-497. [CrossRef]
* (17) [PERSON] A greedy heuristic for the set-covering problem. _Math. Oper. Res._**1979**, \(4\), 233-235. [CrossRef]
* (18) [PERSON] On the Ratio of Optimal Integral and Fractional Covers. _Discret. Math._**1975**, _13_, 383-390. [CrossRef]* (19) [PERSON]; [PERSON] Almost Optimal Set Covers in Finite VC-Dimension. _Discret. Comput. Geom._**1995**, _14_, 463-479. [CrossRef]
* (20) [PERSON] Reducibility among Combinatorial Problems. In _Complexity of Computer Computations_; [PERSON], [PERSON], [PERSON], Eds. ; Plenum: New York, NY, USA, 1972; pp. 85-103. * (21) [PERSON] Constant-factor approximation of domination number in sparse graphs. _Eur. J. Comb._**2013**, _34_, 833-840. [CrossRef]
* (22) [PERSON]; [PERSON] Domination, packing and excluded minors. _Electron. J. Comb._**2003**, _10_, N9.