On the domination number of permutation graphs and an application to strong fixed points

DOI10.1016/J.DAM.2020.08.021MaRDI QIDQ2208341zbMATH OpenOpenAlexFDO

Authors Theresa Baren, Michael Cory, Mia Friedberg, Peter Gardner, James Hammer, Joshua Harrington, Daniel McGinnis, Riley Waechter, Tony W. H. Wong

Publication date 2 November 2020

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

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

zbMATH Keywords

graph dominationpermutation graphsstrong fixed points

Mathematics Subject Classification ID

Permutations, words, matrices (05A05) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Enumeration in graph theory (05C30)

Abstract: A permutation graph $G_{p}i$ is a simple graph with vertices corresponding to the elements of $pi$ and an edge between $i$ and $j$ when $i$ and $j$ are inverted in $pi$. A set of vertices $D$ is said to dominate a graph $G$ when every vertex in $G$ is either an element of $D$, or adjacent to an element of $D$. The domination number $gamma(G)$ is defined as the cardinality of a minimum dominating set of $G$. A strong fixed point of a permutation $pi$ of order $n$ is an element $k$ such that $p{i}^{-1}(j)<p{i}^{-1}(k)$ for all $j<k$, and $p{i}^{-1}(i)>p{i}^{-1}(k)$ for all $i>k$. In this article, we count the number of connected permutation graphs on $n$ vertices with domination number $1$ and domination number $fracn2$. We further show that for a natural number $kleqfracn2$, there exists a connected permutation graph on $n$ vertices with domination number $k$. We find a closed expression for the number of permutation graphs dominated by a set with two elements, and we find a closed expression for the number of permutation graphs efficiently dominated by any set of vertices. We conclude by providing an application of these results to strong fixed points, proving some conjectures posed on the OEIS.

Recommendations

• scientific article; zbMATH DE number 6749463
• Disjunctive total domination in permutation graphs
• On the broadcast domination number of permutation graphs
• Power domination on permutation graphs
• Regular graphs are not universal fixers

Cites work

• scientific article; zbMATH DE number 1095171 (Why is no real title available?)
• Algorithmic graph theory and perfect graphs
• An optimal algorithm for finding the minimum cardinality dominating set on permutation graphs
• On domination problems for permutation and other graphs
• On graphs having domination number half their order
• Permutation Graphs and Transitive Graphs
• The on-line encyclopedia of integer sequences
• Transitive Orientation of Graphs and Identification of Permutation Graphs

Cited in

(6)

• Regular graphs are not universal fixers
• scientific article; zbMATH DE number 6749463 (Why is no real title available?)
• scientific article; zbMATH DE number 3943870 (Why is no real title available?)
• A new approach for the domination problem on permutation graphs
• On the broadcast domination number of permutation graphs
• Alphabetic points in restricted growth functions

Describes a project that uses

Uses Software

• OEIS

This page was built for publication: On the domination number of permutation graphs and an application to strong fixed points

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