A spanning tree of the \(2^ m\)-dimensional hypercube with maximum number of degree-preserving vertices
type: Item
instance of: scholarly article
title: A spanning tree of the \(2^ m\)-dimensional hypercube with maximum number of degree-preserving vertices
zbMATH Open document ID: 0783.05039
DOI: 10.1016/0012-365X(93)90343-R
author: Sul-young Choi
author: Puhua Guan
published in: Discrete Mathematics
publication date: 1994-03-10T00:00:00Z
review text: The \(n\)-dimensional hypercube \(Q_ n\) is a graph whose vertices are ordered \(n\)-tuples of 0's and 1's, where two vertices are adjacent iff they differ in exactly one coordinate. \(\deg_ G(v)\) denotes the degree of the vertex \(v\) in the graph \(G\). A degree-preserving (DP-)vertex \(v\) in a tree \(T\) of a graph \(G\) is a vertex satisfying \(\deg_ T(v)=\deg_ G(v)\). It is shown that for a hypercube \(Q_ n\) \((n\geq 2)\) the number of DP-vertices of a spanning tree is at most \({2^ n \over n}\), with equality possible if and only if \(n=2^ m\) holds for some positive integer \(m\).
Mathematics Subject Classification ID: 05C05
Mathematics Subject Classification ID: 05C35
zbMATH DE Number: 428016
zbMATH Keywords: \(n\)-dimensional hypercube
zbMATH Keywords: degree-preserving vertex
zbMATH Keywords: tree
zbMATH Keywords: spanning tree
reviewed by: Dietmar Cieslik
MaRDI profile type: Publication
cites work: Q5422499
cites work: The starlike trees which span a hypercube
cites work: Q4146667
description: scientific article; zbMATH DE number 428016