Geodesic
Vertex-edge domination in interval and bipartite permutation graphs
Discussiones Mathematicae. Graph Theory, Tome 43 (2023) no. 4, pp. 947-963 Cet article a éte moissonné depuis la source Library of Science

Voir la notice de l'article

Given a graph G = (V,E), a vertex u ∈ V ve-dominates all edges incident to any vertex of N_G[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: vertex-edge domination, linear time algorithm, interval graphs, bipartite permutation graphs 
@article{DMGT_2023_43_4_a4,
     author = {Paul, Subhabrata and Pradhan, Dinabandhu and Verma, Shaily},
     title = {Vertex-edge domination in interval and bipartite permutation graphs},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {947--963},
     year = {2023},
     volume = {43},
     number = {4},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2023_43_4_a4/}
}
TY  - JOUR
AU  - Paul, Subhabrata
AU  - Pradhan, Dinabandhu
AU  - Verma, Shaily
TI  - Vertex-edge domination in interval and bipartite permutation graphs
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2023
SP  - 947
EP  - 963
VL  - 43
IS  - 4
UR  - http://geodesic.mathdoc.fr/item/DMGT_2023_43_4_a4/
LA  - en
ID  - DMGT_2023_43_4_a4
ER  - 
%0 Journal Article
%A Paul, Subhabrata
%A Pradhan, Dinabandhu
%A Verma, Shaily
%T Vertex-edge domination in interval and bipartite permutation graphs
%J Discussiones Mathematicae. Graph Theory
%D 2023
%P 947-963
%V 43
%N 4
%U http://geodesic.mathdoc.fr/item/DMGT_2023_43_4_a4/
%G en
%F DMGT_2023_43_4_a4
Paul, Subhabrata; Pradhan, Dinabandhu; Verma, Shaily. Vertex-edge domination in interval and bipartite permutation graphs. Discussiones Mathematicae. Graph Theory, Tome 43 (2023) no. 4, pp. 947-963. http://geodesic.mathdoc.fr/item/DMGT_2023_43_4_a4/

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

[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.1343469

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

[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.002

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

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

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

[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.105872

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

[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/S1793830917500458

[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.c150243

[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.017

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

[14] J.R. Lewis, Vertex-Edge and Edge-Vertex Parameters in Graphs, PhD Thesis, Clemson, University, Clemson} (2007). https://tigerprints.clemson.edu/all_dissertations/103

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

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

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

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

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

[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.112075

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