The induced subgraph order on unlabelled graphs
type: Item
instance of: scholarly article
title: The induced subgraph order on unlabelled graphs
zbMATH Open document ID: 1110.06008
author: Craig A. Sloss
published in: The Electronic Journal of Combinatorics
publication date: 2007-03-12T00:00:00Z
full work available at URL: https://eudml.org/doc/127216
full work available at URL: v13i1n17.html
review text: 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.
Mathematics Subject Classification ID: 06A07
zbMATH DE Number: 5132829
zbMATH Keywords: differential poset
zbMATH Keywords: unlabelled graphs
zbMATH Keywords: walk enumeration
zbMATH Keywords: poset of induced subgraphs
MaRDI profile type: Publication
description: scientific article; zbMATH DE number 5132829