Graphes équilibrés et arboricité rationnelle. (Balanced graphs and rational arboricity)
type: Item
instance of: scholarly article
title: Graphes équilibrés et arboricité rationnelle. (Balanced graphs and rational arboricity)
zbMATH Open document ID: 0663.05051
DOI: 10.1016/S0195-6698(86)80032-4
author: S. H. Smith
published in: European Journal of Combinatorics
publication date: 1986-01-01T00:00:00Z
review text: The author's main result is a proof of a recent conjecture due to \textit{M. Karoński} and \textit{A. Ruciński} [Problem session, Graphs and other combinatorial topics, Proc. 3rd Czech. Symp., Prague 1982, Teubner-Texte Math. 59 (1983)]. Let \(G_ Y\) be the subgraph of G spanned by the subset Y of the vertex set V. Let \(m(G_ Y)\) be the number of edges of \(G_ Y\). The mean half-degree of \(G_ Y\) is defined as \(d(G_ Y)=m(G_ Y)/| Y|\). When the mean half-degree of each subgraph is at most equal to the mean half-degree of the graph G, the author calls G balanced. Moreover, let \(d_{\max}(G)\) be the maximum mean half-degree for all subgraphs of G. The conjecture that is proved reads: Every connected graph G is a subgraph of a balanced graph whose mean half- degree is \(d_{\max}(G)\).
Mathematics Subject Classification ID: 05C99
zbMATH DE Number: 4083676
zbMATH Keywords: mean half-degree
zbMATH Keywords: connected graph
zbMATH Keywords: subgraph of a balanced graph
MaRDI profile type: Publication
cites work: Q4096964
cites work: Q3097395
cites work: Decomposition of Finite Graphs Into Forests
cites work: On subgraphs as matroid cells
cites work: Minimum partition of a matroid into independent subsets
full work available at URL: s0195-6698(86)80032-4
OpenAlex ID: W2412994226
description: scientific article; zbMATH DE number 4083676