The induced subgraph order on unlabelled graphs
Summary: A differential poset is a partially ordered set with raising and lowering operators \(U\) and \(D\) which satisfy the commutation relation \(DU-UD=rI\) for some constant \(r\). This notion may be generalized to deal with the case in which there exist sequences of constants \(\{q_n\}_{n\geq0}\) and \(\{r_n\}_{n\geq 0}\) such that for any poset element \(x\) of rank \(n\), \(DU(x) = q_n UD(x) + r_nx\). Here, we introduce natural raising and lowering operators such that the set of unlabelled graphs, ordered by \(G\leq H\) if and only if \(G\) is isomorphic to an induced subgraph of \(H\), is a generalized differential poset with \(q_n=2\) and \(r_n = 2^n\). This allows one to apply a number of enumerative results regarding walk enumeration to the poset of induced subgraphs.
This page was built for publication: The induced subgraph order on unlabelled graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q870042)
