No Detail Found!

Algorithmic study of d2-transitivity of graphs∗

Author(s)
Subhabrata Paul Department of Mathematics, Indian Institute of Technology Patna,Bihta 801106, Bihar,India
Kamal Santra Department of Mathematics, Indian Institute of Technology Patna,Bihta 801106, Bihar,India
Abstract
Let G = (V; E) be a graph, where V and E are the vertex and edge sets, respectively. For two disjoint subsets A and B of V , we say A dominates B if every vertex of B is adjacent to at least one vertex of A. A vertex partition = fV1; V2; : : : ; Vkg of G is called a transitive partition of size k if Vi dominates Vj for all 1 i < j k. In this article, we initiate the study of a generalization of transitive partition, namely d2-transitive partition. For two disjoint subsets A and B of V , we say A d2dominates B if, for every vertex of B, there exists a vertex in A such that the distance between them is at most two. A vertex partition = fV1; V2; : : : ; Vkg of G is said to be a d2-transitive partition of size k if Vi d2-dominates Vj for all 1 i < j k. The maximum integer k for which d2-transitive partition exists is called d2-transitivity of G, and it is denoted by T rd2 (G). The Maximum d2-Transitivity Problem is to find a d2-transitive partition of a given graph with the maximum number of parts. We show that this problem can be solved in linear time for the complement of bipartite graphs and bipartite chain graphs. On the other side, we prove that the decision version of the Maximum d2-Transitivity Problem is NP-complete for split graphs and bipartite graphs.
Publication Details
Page(s) 13-20
Published Journal: Discrete Mathematics Letters, Volume: 13, Issue: 0, Year: 2024

Request the full text from PASTIC

Keywords
bipartite graphs, d2-transitivity, linear algorithm, NP-completeness, split graphs
References
Chang G. J. .1994 .The domatic number problem. , 125 : 115-122.
Zelinka B. .1983 .On k-domatic numbers of graphs. , 33 : 309-313.
0

Citations

0

Downloads

88

Views