Vertex-Edge Domination in Interval and Bipartite Permutation Graphs

被引：3

作者：

Paul, Subhabrata ^{[1
]}

Pradhan, Dinabandhu ^{[2
]}

Verma, Shaily ^{[3
]}

机构：

[1] Indian Inst Technol, Dept Math, Patna, Bihar, India

[2] Indian Inst Technol ISM, Dept Math & Comp, Dhanbad, Bihar, India

[3] Indian Inst Technol, Dept Math, Delhi, India

来源：

DISCUSSIONES MATHEMATICAE GRAPH THEORY | 2023年 / 43卷 / 04期

关键词：

vertex-edge domination; linear time algorithm; interval graphs; bipartite permutation graphs; NUMBER;

D O I：

10.7151/dmgt.2411

中图分类号：

O1 [数学];

学科分类号：

0701 ; 070101 ;

摘要：

Given a graph G =(V, E), a vertex u is an element of 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 is an element of E, there exists a vertex u is an element of 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.

引用

页码：947 / 963

页数：17

共 20 条

[1] TESTING FOR CONSECUTIVE ONES PROPERTY, INTERVAL GRAPHS, AND GRAPH PLANARITY USING PQ-TREE ALGORITHMS [J].

BOOTH, KS ;

LUEKER, GS .

JOURNAL OF COMPUTER AND SYSTEM SCIENCES, 1976, 13 (03) :335-379

[2] Total vertex-edge domination [J].

Boutrig, Razika ;

Chellali, Mustapha .

INTERNATIONAL JOURNAL OF COMPUTER MATHEMATICS, 2018, 95 (09) :1820-1828

[3] Vertex-edge domination in graphs [J].

Boutrig, Razika ;

Chellali, Mustapha ;

Haynes, Teresa W. ;

Hedetniemi, Stephen T. .

AEQUATIONES MATHEMATICAE, 2016, 90 (02) :355-366

[4] A note on independent vertex edge domination in graphs [J].

Chen, Xue-gang ;

Yin, Kai ;

Gao, Ting .

DISCRETE OPTIMIZATION, 2017, 25 :1-5

[5]

Chitra S., 2012, P INT MATH FORUM, V7, P233

[6]

Haynes T. W., 1998, FUNDAMENTALS DOMINAT

[7] Algorithm and hardness results on hop domination in graphs [J].

Henning, Michael A. ;

Pal, Saikat ;

Pradhan, D. .

INFORMATION PROCESSING LETTERS, 2020, 153

[8]

Jena Sangram K., 2020, Algorithms and Discrete Applied Mathematics. 6th International Conference, CALDAM 2020. Proceedings. Lecture Notes in Computer Science (LNCS 12016), P67, DOI 10.1007/978-3-030-39219-2_6

[9] THE OUTER-CONNECTED VERTEX EDGE DOMINATION NUMBER OF A TREE [J].

Krishnakumari, Balakrishna ;

Venkatakrishnan, Yanamandram Balasubramanian .

COMMUNICATIONS OF THE KOREAN MATHEMATICAL SOCIETY, 2018, 33 (01) :361-369

[10]

Krishnakumari B, 2017, DISCRET MATH ALGORIT, V9, DOI 10.1142/S1793830917500458

← 1 2 →