Graphical decompositions
type: Item
instance of: scholarly article
title: Graphical decompositions
zbMATH Open document ID: 0795.05079
DOI: 10.1016/0012-365X(94)90176-7
published in: Discrete Mathematics
publication date: 1994-05-05T00:00:00Z
review text: Suppose the vertices of the \(k\)-regular connected graph \(G_ n\) can be partitioned into two sets \(X\) and \(Y\) such that all vertex-degrees in the subgraphs induced by \(X\) and \(Y\) are at least \(\lceil k/2 \rceil\) and \(\lfloor k/2 \rfloor\), respectively. Let \(W_ k(G_ n)\) denote the minimum value of \(\| X |-| Y \|\) over all such partitions of the vertices of \(G_ n\) and let \(W_ k (n)\) denote the maximum value of \(W_ k (G_ n)\) over all such graphs \(G_ n\). The author obtains the value of or upper bounds for \(W_ k (n)\) for \(1 \leq k \leq 7\) and \(n\) sufficiently large, among other things. For example, he shows that \(W_ 7(n) \leq (17n + 356)/33\) if \(n \geq 24\) and \(n\) is even.
Mathematics Subject Classification ID: 05C35
zbMATH DE Number: 562679
zbMATH Keywords: graphical decompositions
zbMATH Keywords: vertex partitions
zbMATH Keywords: regular graphs
zbMATH Keywords: upper bounds
author: J. Sheehan
reviewed by: J. W. Moon
MaRDI profile type: Publication
cites work: Advances in graph theory
cites work: Size Ramsey numbers involving stars
cites work: Q5530470
cites work: Vertex colorings without isolates
cites work: Q3737465
cites work: Graph decomposition with constraints in the minimum degree
cites work: Balanced graphs with edge density constraints
cites work: Balanced graphs with minimum degree constraints
cites work: Graph decomposition with constraints on the connectivity and minimum degree
full work available at URL: 0012-365x(94)90176-7
OpenAlex ID: W2914963856
Recommended article: Q3983103
Recommended article: Q4390607
Recommended article: Q3998644
Recommended article: On decomposition of graphs
Recommended article: Q4735214
Recommended article: Q5251981
Recommended article: Q4852861
Recommended article: Decomposition of multigraphs
Recommended article: Q4876959
Recommended article: Q3029040
description: scientific article; zbMATH DE number 562679