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

DOI10.1016/J.DAM.2020.08.021zbMATH Open1451.05115arXiv1810.03409OpenAlexW2895722401MaRDI QIDQ2208341FDOQ2208341

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)

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.

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

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

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)

Cites Work

• The on-line encyclopedia of integer sequences
• Title not available (Why is that?)
• Algorithmic graph theory and perfect graphs
• Transitive Orientation of Graphs and Identification of Permutation Graphs
• On domination problems for permutation and other graphs
• Permutation Graphs and Transitive Graphs
• On graphs having domination number half their order
• An optimal algorithm for finding the minimum cardinality dominating set on permutation graphs

Cited In (6)

• Regular graphs are not universal fixers
• Title not available (Why is that?)
• Title not available (Why is that?)
• A new approach for the domination problem on permutation graphs
• On the broadcast domination number of permutation graphs
• Alphabetic points in restricted growth functions

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)