Blocks and cut vertices of the Buneman graph

DOI10.1137/090764360MaRDI QIDQ3225161zbMATH OpenOpenAlexFDO

Authors Andreas W. M. Dress, Katharina T. Huber, Jack H. Koolen, Vincent Moulton

Publication date 15 March 2012

Published in SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

\(X\)-treeblockBuneman graphcompatible partitionscut vertexmedian graphphylogeneticsSplit

Mathematics Subject Classification ID

Trees (05C05) Connectivity (05C40) Applications of graph theory (05C90) Taxonomy, cladistics, statistics in mathematical biology (92B10) Problems related to evolution (92D15)

Abstract: Given a set $Sg$ of bipartitions of some finite set $X$ of cardinality at least 2, one can associate to $Sg$ a canonical $X$-labeled graph $B(Sg)$, called the Buneman graph. This graph has several interesting mathematical properties - for example, it is a median network and therefore an isometric subgraph of a hypercube. It is commonly used as a tool in studies of DNA sequences gathered from populations. In this paper, we present some results concerning the {em cut vertices} of $B(Sg)$, i.e., vertices whose removal disconnect the graph, as well as its {em blocks} or 2-{em connected components} - results that yield, in particular, an intriguing generalization of the well-known fact that $B(Sg)$ is a tree if and only if any two splits in $Sg$ are compatible.

Recommendations

• On the number of vertices and edges of the Buneman graph
• Some variations on a theme by Buneman
• Injective split systems
• The relation graph
• Computing the blocks of a quasi-median graph

Cited in

(12)

• On the number of vertices and edges of the Buneman graph
• Some variations on a theme by Buneman
• The relation graph
• The polytopal structure of the tight-span of a totally split-decomposable metric
• Block-cutvertex trees and block-cutvertex partitions
• Replacing cliques by stars in quasi-median graphs
• Uprooted phylogenetic networks
• Counting vertices and cubes in median graphs of circular split systems
• Computing the blocks of a quasi-median graph
• scientific article; zbMATH DE number 1905103 (Why is no real title available?)
• The numbers of cut-vertices and end-blocks in 4-regular graphs
• Injective split systems

This page was built for publication: Blocks and cut vertices of the Buneman graph

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