1. bookAHEAD OF PRINT
Journal Details
License
Format
Journal
eISSN
2083-5892
First Published
13 Apr 2013
Publication timeframe
4 times per year
Languages
English
access type Open Access

Vertex-Edge Domination in Interval and Bipartite Permutation Graphs

Published Online: 08 Jul 2021
Volume & Issue: AHEAD OF PRINT
Page range: -
Received: 07 Oct 2020
Accepted: 15 May 2021
Journal Details
License
Format
Journal
eISSN
2083-5892
First Published
13 Apr 2013
Publication timeframe
4 times per year
Languages
English
Abstract

Given a graph G =(V, E), a vertex uV ve-dominates all edges incident to any vertex of NG[u]. A set D V is a vertex-edge dominating set if, for any edge e ∈ E, there exists a vertex u ∈ D such that u ve-dominates e. Given a graph G, our goal is to find a minimum cardinality ve-dominating set of G. In this paper, we designed two linear-time algorithms to find a minimum cardinality ve-dominating set for interval and bipartite permutation graphs.

Keywords

MSC 2010

[1] K.S. Booth and G.S. Lueker, Testing for consecutive ones property, interval graphs and graph planarity using PQ-tree algorithms, J. Comput. System. Sci. 13 (1976) 335–379. https://doi.org/10.1016/S0022-0000(76)80045-110.1016/S0022-0000(76)80045-1Search in Google Scholar

[2] R. Boutrig and M. Chellali, Total vertex-edge domination, Int. J. Comput. Math. 95 (2018) 1820–1828. https://doi.org/10.1080/00207160.2017.134346910.1080/00207160.2017.1343469Search in Google Scholar

[3] R. Boutrig, M. Chellali, T.W. Haynes and S.T. Hedetniemi, Vertex-edge domination in graphs, Aequationes Math. 90 (2016) 355–366. https://doi.org/10.1007/s00010-015-0354-210.1007/s00010-015-0354-2Search in Google Scholar

[4] X.G. Chen, K. Yin and T. Gao, A note on independent vertex-edge domination in graphs, Discrete Optim. 25 (2017) 1–5. https://doi.org/10.1016/j.disopt.2017.01.00210.1016/j.disopt.2017.01.002Search in Google Scholar

[5] S. Chitra and R. Sattanathan, Global vertex-edge domination sets in graphs,in: Proc. Int. Math. Forum 7 (2012) 233–240.Search in Google Scholar

[6] T.W. Haynes, S.T. Hedetniemi and P.J. Slater, Fundamentals of Domination in Graphs (Marcel Dekker Inc., New York, 1998).Search in Google Scholar

[7] T.W. Haynes, S.T. Hedetniemi and P.J. Slater, Domination in Graphs: Advanced Topics (Marcel Dekker Inc., New York, 1998).Search in Google Scholar

[8] M.A. Henning, S. Pal and D. Pradhan, Algorithm and hardness results on hop domination in graphs, Inform. Process. Lett. 153 (2020) 105872. https://doi.org/10.1016/j.ipl.2019.10587210.1016/j.ipl.2019.105872Search in Google Scholar

[9] S.K. Jena and G.K. Das, Vertex-edge domination in unit disk graphs,in: Proc. of the 6th International Conference on Algorithms and Discrete Applied Mathematics, Lecture Notes in Comput. Sci. 12016 (2020) 67–78. https://doi.org/10.1007/978-3-030-39219-2_610.1007/978-3-030-39219-2_6Search in Google Scholar

[10] B. Krishnakumari, M. Chellali and Y.B. Venkatakrishnan, Double vertex-edge domination, Discrete Math. Algorithms Appl. 09 (2017) 1750045. https://doi.org/10.1142/S179383091750045810.1142/S1793830917500458Search in Google Scholar

[11] B. Krishnakumari and Y.B. Venkatakrishnan, The outer-connected vertex edge domination number of a tree, Commun. Korean Math. Soc. 33 (2018) 361–369. https://doi.org/10.4134/CKMS.c150243Search in Google Scholar

[12] B. Krishnakumari, Y.B. Venkatakrishnan and M. Krzywkowski, Bounds on the vertex-edge domination number of a tree,C.R.Math. Acad.Sci.Paris 352 (2014) 363–366. https://doi.org/10.1016/j.crma.2014.03.01710.1016/j.crma.2014.03.017Search in Google Scholar

[13] T.H. Lai and S.S. Wei, Bipartite permutation graphs with application to the minimum buffer size problem, Discrete Appl. Math. 74 (1997) 33–55. https://doi.org/10.1016/S0166-218X(96)00014-510.1016/S0166-218X(96)00014-5Search in Google Scholar

[14] J.R. Lewis, Vertex-Edge and Edge-Vertex Parameters in Graphs, PhD Thesis, Clemson, University, Clemson (2007).Search in Google Scholar

[15] J.R. Lewis, S.T. Hedetniemi, T.W. Haynes and G.H. Fricke, Vertex-edge domination, Util. Math. 81 (2010) 193–213.Search in Google Scholar

[16] S. Paul and K. Ranjan, On vertex-edge and independent vertex-edge domination, in: Proc. of the 13th International Conference on Combinatorial Optimization and Applications, (Lecture Notes in Comput. Sci. 11949, 2019) 437–448. https://doi.org/10.1007/978-3-030-36412-0 3510.1007/978-3-030-36412-0Search in Google Scholar

[17] K.W. Peters, Theoretical and Algorithmic Results on Domination and Connectivity, PhD Thesis (Clemson, University Clemson, 1986).Search in Google Scholar

[18] G. Ramalingam and C. Pandu Rangan, A unified approach to domination problems on interval graphs, Inform. Process. Lett. 27 (1998) 271–274. https://doi.org/10.1016/0020-0190(88)90091-910.1016/0020-0190(88)90091-9Search in Google Scholar

[19] J. Spinrad, A. Brandstädt and L. Stewart, Bipartite permutation graphs, Discrete Appl. Math. 18 (1987) 279–292. https://doi.org/10.1016/S0166-218X(87)80003-310.1016/S0166-218X(87)80003-3Search in Google Scholar

[20] R. Ziemann and P. Żyliński, Vertex-edge domination in cubic graphs, Discrete Math. 343 (2020) 112075. https://doi.org/10.1016/j.disc.2020.11207510.1016/j.disc.2020.112075Search in Google Scholar

[21] P. Żyliński, Vertex-edge domination in graphs, Aequationes Math. 93 (2019) 735–742. https://doi.org/10.1007/s00010-018-0609-910.1007/s00010-018-0609-9Search in Google Scholar

Recommended articles from Trend MD

Plan your remote conference with Sciendo