Geodesic
The induced subgraph order on unlabelled graphs
The electronic journal of combinatorics, Tome 13 (2006)
Cet article a éte moissonné depuis la source The Electronic Journal of Combinatorics website

Voir la notice de l'article

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\geq 0}$ 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.
DOI : 10.37236/1155
Classification : 06A07
Mots-clés : differential poset, unlabelled graphs, walk enumeration, poset of induced subgraphs 
@article{10_37236_1155,
     author = {Craig A. Sloss},
     title = {The induced subgraph order on unlabelled graphs},
     journal = {The electronic journal of combinatorics},
     year = {2006},
     volume = {13},
     doi = {10.37236/1155},
     zbl = {1110.06008},
     url = {http://geodesic.mathdoc.fr/articles/10.37236/1155/}
}
TY  - JOUR
AU  - Craig A. Sloss
TI  - The induced subgraph order on unlabelled graphs
JO  - The electronic journal of combinatorics
PY  - 2006
VL  - 13
UR  - http://geodesic.mathdoc.fr/articles/10.37236/1155/
DO  - 10.37236/1155
ID  - 10_37236_1155
ER  - 
%0 Journal Article
%A Craig A. Sloss
%T The induced subgraph order on unlabelled graphs
%J The electronic journal of combinatorics
%D 2006
%V 13
%U http://geodesic.mathdoc.fr/articles/10.37236/1155/
%R 10.37236/1155
%F 10_37236_1155
Craig A. Sloss. The induced subgraph order on unlabelled graphs. The electronic journal of combinatorics, Tome 13 (2006). doi: 10.37236/1155

Cité par Sources :