DMGT

ISSN 1234-3099 (print version)

ISSN 2083-5892 (electronic version)

https://doi.org/10.7151/dmgt

Discussiones Mathematicae Graph Theory

Journal Impact Factor (JIF 2022): 0.7

5-year Journal Impact Factor (2022): 0.7

CiteScore (2022): 1.9

SNIP (2022): 0.902

Discussiones Mathematicae Graph Theory

Article in volume

Authors:

S. Paul

Subhabrata Paul

Department of Mathematics, Indian Institute of Technology, Patna

email: subhabrata@iitp.ac.in

D. Pradhan

Dinabandhu Pradhan

Department of Mathematics and Computing, Indian Institute of Technology (ISM), Dhanbad

email: dina@iitism.ac.in

S. Verma

Shaily Verma

Indian Institute of Technology, Delhi

email: Shaily.Verma@maths.iitd.ac.in

Title:

Vertex-edge domination in interval and bipartite permutation graphs

PDF

Source:

Discussiones Mathematicae Graph Theory 43(4) (2023) 947-963

Received: 2020-10-07 , Revised: 2021-05-05 , Accepted: 2021-05-15 , Available online: 2021-06-08 , https://doi.org/10.7151/dmgt.2411

Abstract:

Given a graph $G = (V,E)$, a vertex $u \in V$ ve-dominates all edges incident to any vertex of $N_G[u]$. A set $D \subseteq V$ is a vertex-edge dominating set if, for any edge $e\in E$, there exists a vertex $u \in 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

References:

  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
Close