The cube polynomial and its derivatives: The case of median graphs
type: Item
instance of: scholarly article
title: The cube polynomial and its derivatives: The case of median graphs
zbMATH Open document ID: 1020.05035
author: Boštjan Brešar
author: Sandi Klavžar
author: Riste Škrekovski
published in: The Electronic Journal of Combinatorics
publication date: 2003-05-13T00:00:00Z
full work available at URL: v10i1r3.html
review text: For \(i\geq 0\), the \(i\)-cube \(Q_i\) is the graph on \(2^i\) vertices represented by \(i\)-tuples of \(0\)'s and \(1\)'s, where two vertices are adjacent whenever the corresponding \(i\)-tuples differ in exactly one position. Let \(\alpha_i(G)\) be the number of induced \(i\)-cubes of a graph \(G\). Then the cube polynomial \(c(G,x)\) of \(G\) is defined by \(\sum_{i\geq 0} \alpha_i(G)x^i\). The authors give several characterizations of the cube polynomial. In particular, they define the derivation \(\partial G\) of a median graph \(G\) and prove that the cube polynomial is the only function \(c\) with the property \(c'(G,x)= c(\partial G,x)\) provided that \(c(G, 0)=|V(G)|\). The cube polynomial is then used to generalize some of the known results for median graphs.
Mathematics Subject Classification ID: 05C30
Mathematics Subject Classification ID: 05A15
Mathematics Subject Classification ID: 05C12
zbMATH DE Number: 1862495
reviewed by: Jack E. Graver
MaRDI profile type: Publication
description: scientific article; zbMATH DE number 1862495