Characterisation and classification of signatures of spanning trees of the n-cube

zbMATH Open1429.05034arXiv1807.11183MaRDI QIDQ5206928FDOQ5206928

Authors: Howida Adel Alfran, Christopher Tuffley, D. J. W. Simpson 

Publication date: 19 December 2019

Abstract: The signature of a spanning tree $T$ of the $n$-cube $Q_n$ is the $n$-tuple $mathrmsig(T)=(a_1,a_2,dots,a_n)$ such that $a_i$ is the number of edges of $T$ in the $i$th direction. We characterise the $n$-tuples that can occur as the signature of a spanning tree, and classify a signature $mathcalS$ as reducible or irreducible according to whether or not there is a proper nonempty subset $R$ of $[n]$ such that restricting $mathcalS$ to the indices in $R$ gives a signature of $Q_{|R|}$. If so, we say moreover that $mathcalS$ and $T$ reduce over $R$. We show that reducibility places strict structural constraints on $T$. In particular, if $T$ reduces over a set of size $r$ then $T$ decomposes as a sum of $2^r$ spanning trees of $Q_{n-r}$, together with a spanning tree of a contraction of $Q_n$ with underlying simple graph $Q_r$. Moreover, this decomposition is realised by an isomorphism of edge slide graphs, where the edge slide graph of $Q_n$ is the graph $mathcalE(Q_n)$ on the spanning trees of $Q_n$, with an edge between two trees if and only if they are related by an edge slide. An edge slide is an operation on spanning trees of the $n$-cube given by ``sliding an edge of a spanning tree across a $2$-dimensional face of the cube to get a second spanning tree. The signature of a spanning tree is invariant under edge slides, so the subgraph $mathcalE(mathcalS)$ of $mathcalE(Q_n)$ induced by the trees with signature $mathcalS$ is a union of one or more connected components of $mathcalE(Q_n)$. Reducible signatures may be further divided into strictly reducible and quasi-irreducible signatures, and as an application of our results we show that $mathcalE(mathcalS)$ is disconnected if $mathcalS$ is strictly reducible. We conjecture that the converse is also true.

Full work available at URL: https://arxiv.org/abs/1807.11183

Recommendations

• Counting the spanning trees of the 3-cube using edge slides
• On Hamiltonian circuits and spanning trees of hypercubes
• Spanning subgraphs of a hypercube. IV: Rooted trees
• scientific article; zbMATH DE number 568803
• The edge slide graph of the 3-cube

zbMATH Keywords

edge slide graphsirreducible signaturereducible signature

Mathematics Subject Classification ID

Trees (05C05) Signed and weighted graphs (05C22)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Graph theory
• Distances between graphs under edge operations
• Handbook of graph theory
• On the spanning trees of the hypercube and other products of graphs
• Factorizations of some weighted spanning tree enumerators
• A walk through combinatorics. An introduction to enumeration and graph theory. With a foreword by Richard Stanley
• Counting the spanning trees of the 3-cube using edge slides
• The edge slide graph of the 3-cube

Cited In (2)

• The edge slide graph of the 3-cube
• Counting the spanning trees of the 3-cube using edge slides

This page was built for publication: Characterisation and classification of signatures of spanning trees of the \(n\)-cube

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5206928)