Transitivity on subclasses of chordal graphs

DOI10.1007/978-3-031-25211-2_30arXiv2211.13931OpenAlexW4318023029MaRDI QIDQ6132554FDOQ6132554

Authors: S. Paul, Kamal Santra 

Publication date: 17 August 2023

Published in: Algorithms and Discrete Applied Mathematics (Search for Journal in Brave)

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$ extit{dominates} $B$ if every vertex of $B$ is adjacent to at least one vertex of $A$ in $G$. 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 chordal graphs [Iterated colorings of graphs, emph{Discrete Mathematics}, 278, 2004]. In this paper, we first prove that this problem can be solved in linear time for emph{split graphs} and for the emph{complement of bipartite chain graphs}, two subclasses of chordal graphs. We also discuss Nordhaus-Gaddum type relations for transitivity and provide counterexamples for an open problem posed by J. T. Hedetniemi and S. T. Hedetniemi [The transitivity of a graph, emph{J. Combin. Math. Combin. Comput}, 104, 2018]. Finally, we characterize transitively critical graphs having fixed transitivity.

Full work available at URL: https://arxiv.org/abs/2211.13931

zbMATH Keywords

transitivitysplit graphsNordhaus-Gaddum relationscomplement of bipartite chain graphstransitively critical graphs

Mathematics Subject Classification ID

Algorithms in computer science (68Wxx)

Cites Work

• Some perfect coloring properties of graphs
• Towards a theory of domination in graphs
• Linear-time certifying recognition algorithms and forbidden induced subgraphs
• Results on the Grundy chromatic number of graphs
• The splittance of a graph
• On Complementary Graphs
• On the equality of the partial Grundy and upper ochromatic numbers of graphs
• Title not available (Why is that?)
• The domatic number problem
• The transitivity of a graph
• The transitivity of special graph classes
• Iterated colorings of graphs.
• The upper domatic number of a graph
• Transitivity on subclasses of bipartite graphs
• Grundy coloring in some subclasses of bipartite graphs and their complements

Cited In (1)

• Algorithmic study on 2-transitivity of graphs

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

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