Transitivity on subclasses of chordal graphs

DOI10.1007/978-3-031-25211-2_30MaRDI QIDQ6132554zbMATH OpenOpenAlexFDO

Authors S. Paul, Kamal Santra

Publication date 17 August 2023

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

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)

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.

Cites work

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

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)