Connected permutation graphs

DOI10.1016/J.DISC.2006.11.014MaRDI QIDQ2455587zbMATH OpenOpenAlexFDO

Authors Youngmee Koh, Sangwook Ree

Publication date 25 October 2007

Published in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.disc.2006.11.014

zbMATH Keywords

connected permutation graphs

Mathematics Subject Classification ID

Enumeration in graph theory (05C30)

Review text

A permutation graph is a simple graph associated with a permutation. Let \(c_n\) be the number of connected permutation graphs on \(n\) vertices. Then the sequence \(\{c_n\}\) satisfies a recurrence relation such that it provides a partition of \(n!\).

Recommendations

• Permutation graphs and the weak Bruhat order
• Permutations avoiding connected graphs
• scientific article; zbMATH DE number 4066932
• On permutation graphs
• Interlocked Permutations

Cites work

• Determination of permutation graphs
• Enumerative aspects of certain subclasses of perfect graphs
• scientific article; zbMATH DE number 3577263 (Why is no real title available?)
• scientific article; zbMATH DE number 1033382 (Why is no real title available?)
• scientific article; zbMATH DE number 2079335 (Why is no real title available?)
• scientific article; zbMATH DE number 3259770 (Why is no real title available?)
• Transitive Orientation of Graphs and Identification of Permutation Graphs

Cited in

(14)

• Succinct navigational oracles for families of intersection graphs on a circle
• Permutation graphs and the abelian sandpile model, tiered trees and non-ambiguous binary trees
• Occurrence graphs of patterns in permutations
• Complete edge-colored permutation graphs
• Some families of combination and permutation graphs.
• Permuting Web Graphs
• scientific article; zbMATH DE number 4066932 (Why is no real title available?)
• On the connected components of a random permutation graph with a given number of edges
• Random generation and enumeration of bipartite permutation graphs
• Permutations avoiding connected graphs
• On graphs associated to sets of rankings
• Permutation graphs and the weak Bruhat order
• Characterization and enumeration of 3-regular permutation graphs
• On random trees obtained from permutation graphs

This page was built for publication: Connected permutation graphs

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