The connectivities of leaf graphs of 2-connected graphs
type: Item
instance of: scholarly article
title: The connectivities of leaf graphs of 2-connected graphs
zbMATH Open document ID: 0932.05048
author: Atsushi Kaneko
author: Kiyoshi Yoshimoto
published in: Journal of Combinatorial Theory. Series B
publication date: 1999-12-20T00:00:00Z
review text: Given a connected graph \(G=(V,E)\), its leaf graph \(\mathcal G\) has as vertex set the set of all spanning trees of \(G\); two vertices \(S\) and \(T\) of \(\mathcal G\) are adjacent exactly when there exists \(v\in V\) such that \(S-v=T-v\) is a connected subgraph of \(G\). Theorem: If \(G\) is biconnected with least valence \(\delta\), then \(\mathcal G\) is \((2\delta-2)\)-connected. Conjecture: If \(G\) is biconnected with \(\delta\geq 3\), then \(\mathcal G\) is hamiltonian.
Mathematics Subject Classification ID: 05C40
Mathematics Subject Classification ID: 05C05
zbMATH DE Number: 1346957
zbMATH Keywords: spanning tree
zbMATH Keywords: leaf graph
zbMATH Keywords: biconnected
zbMATH Keywords: hamiltonian
reviewed by: Mark E. Watkins
MaRDI profile type: Publication
full work available at URL: jctb.1998.1895
OpenAlex ID: W2007722430
cites work: Q4374709
cites work: On the Tree Graph of a Matroid
cites work: A lower bound on connectivities of matroid base graphs
cites work: A homology theory for spanning tress of a graph
DOI: 10.1006/JCTB.1998.1895
description: scientific article; zbMATH DE number 1346957