Transitivity on subclasses of bipartite graphs

DOI10.1007/S10878-022-00954-YarXiv2204.13148MaRDI QIDQ6397644FDOQ6397644

Kamal Santra, S. Paul

Publication date: 27 April 2022

Abstract: Let $G=(V,E)$ be a graph where $V$ and $E$ are the vertex and edge set, respectively. For two disjoint subsets $A$ and $B$, we say $A$ dominates $B$ if every vertex of $B$ is adjacent to at least one vertex of $A$. A vertex partition $pi=V_1,V_2,ldots,V_k$ of $G$ is called a emph{transitive $k$-partition} if $V_i$ dominates $V_j$ for all $i,j$ where $1leqi<jleqk$. The maximum integer $k$ for which the above partition exists is called emph{transitivity} of $G$ and it is denoted by $Tr(G)$. The extsc{Maximum Transitivity Problem} is to find a transitive partition of a given graph with the maximum number of partitions. It was known that the decision version of extsc{Maximum Transitivity Problem} is NP-complete for general graphs, which was proved by Hedetniemi et al. [Iterated colorings of graphs, emph{Discrete Mathematics}, 278, 2004]. This paper first strengthens the NP-completeness result by showing that this problem remains NP-complete for perfect elimination bipartite graphs. On the other hand, we propose a linear-time algorithm for finding the transitivity of a given bipartite chain graph. We then characterize graphs with transitivity at least $t$ for any integer $t$. This result answers two open questions posed by J. T. Hedetniemi and S. T. Hedetniemi [The transitivity of a graph, emph{J. Combin. Math. Combin. Comput}, 104, 2018].

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Combinatorial optimization (90C27)

This page was built for publication: Transitivity on subclasses of bipartite graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6397644)