Two relations for median graphs
type: Item
instance of: scholarly article
title: Two relations for median graphs
zbMATH Open document ID: 0958.05043
DOI: 10.1016/S0012-365X(00)00120-5
author: Riste Škrekovski
published in: Discrete Mathematics
publication date: 2001-03-30T00:00:00Z
review text: A graph \(G\) with a distance function \(d\) is called a median graph, if for any three vertices \(u,v,w\) of \(G\) there is a unique vertex \(x\) such that \(d(u,v)=d(u,x)+d(x,v)\), \(d(u,w)=d(u,x)+d(x,w)\), and \(d(v,w)=d(v,x)+d(x,w)\). Trees and hypercubes are median graphs. The author shows that for median graphs \(\sum_{i\geq 0}(-1)^iq_i=1\), where \(q_i\) denotes the number of subgraphs isomorphic to the hypercube \(Q_i\). This is a generalization of the well-known identity \(n-m=1\) for trees. The author also presents an explicit formula for the number \(k\) of \(\Theta\)-classes in a median graph as \(k=-\sum_{i\geq 0}(-1)^iiq_i\).
reviewed by: Lutz Volkmann
Mathematics Subject Classification ID: 05C12
zbMATH DE Number: 1565951
zbMATH Keywords: median graphs
zbMATH Keywords: hypercubes
Wikidata QID: Q60962158
MaRDI profile type: Publication
Recommended article: A characterization of median graphs
Recommended article: On median graphs and median grid graphs
Recommended article: Graphs with connected medians
Recommended article: Two-ended regular median graphs
Recommended article: Q3781794
Recommended article: On graphs containing a given graphs as median
Recommended article: Q3720634
Recommended article: A new characterization of median graphs
Recommended article: Generalized median graphs and applications
Recommended article: Median graphs, parallelism and posets
description: scientific article; zbMATH DE number 1565951