A note on perfect orders

A simplicial vertex of a graph G is one whose neighbors form a clique in G; a cosimplicial vertex has its non-neighbors all independent. The Dilworth number of a graph is the maximum number of vertices that one can have so that no one dominates any other. This paper contains proofs of three propositions two of which are: 1. If a graph has Dilworth number at most 3, then it contains a simplicial vertex or a cosimplicial vertex. 2. A graph has each vertex maximal under dominance ordering cosimplicial if and only if it has no induced subgraph isomorphic to one of 7 small graphs: \(2K^ 2\), \(C^ 5\), \(C/^ 6\), \(C/^ 7\), \(P/^ 7\), \(F/^ 1\), \(F/^ 2\), (/ here means complement, \(F^ 1\) is obtained from \(P^ 7\) by adding an edge from the first to third vertex, and \(F^ 2\) is obtained by adding an edge from the seventh to fifth vertex to \(F^ 1)\).

Recommendations

Cites work

Cited in

(9)

This page was built for publication: A note on perfect orders

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