Graph decomposition with constraints in the minimum degree
type: Item
instance of: scholarly article
title: Graph decomposition with constraints in the minimum degree
zbMATH Open document ID: 0644.05030
DOI: 10.1016/0012-365X(88)90122-7
author: J. Sheehan
published in: Discrete Mathematics
publication date: 1988-01-01T00:00:00Z
review text: In the paper are investigated decompositions of finite simple graph G with minimum degree \(\delta\) (G)\(\geq \delta (n\equiv \delta (mod 2))\) n denotes the cardinality of V(G). Let max(k,G) denote the set of all k- subsets \(A\subseteq V(G)\) such that the number of edges in the induced subgraph \(\) is a maximum. All subsets of max(k,G) are called dense sets. It is proved that for some \(i\in \{0,1,...,1/2\}\) there exists a partition (X,Y) of V(G) such that (i) \(| X| =\lceil (1/2)n\rceil +i\), \(| Y| =\lfloor n/2\rfloor -i,\) (ii) \(\delta (X)\geq \lceil \delta /2\rceil +i\), \(\delta\) (Y)\(\geq \lfloor \delta /2\rfloor -i,\) (iii) X or Y is dense in G. Two subsets of V(G) form a weak (i,\(\delta)\) partition if condition (i) and (ii) are fulfilled. There are formulated some conjectures concerning weak decomposability of graphs.
Mathematics Subject Classification ID: 05C35
Mathematics Subject Classification ID: 05C70
zbMATH DE Number: 4049678
zbMATH Keywords: graph decomposition
zbMATH Keywords: minimum degree
zbMATH Keywords: dense sets
reviewed by: Ludovit Niepel
MaRDI profile type: Publication
cites work: Cycles Modulo k
cites work: Q5422499
cites work: Size Ramsey numbers involving stars
cites work: Partition of graphs with condition on the connectivity and minimum degree
cites work: Graph decompositions without isolates
cites work: Q5530470
cites work: A homology theory for spanning tress of a graph
cites work: Existenz n-fach zusammenhängender Teilgraphen in Graphen genügend großer Kantendichte
cites work: Homomorphieeigenschaften und mittlere Kantendichte von Graphen
cites work: Vertex colorings without isolates
cites work: Q3737465
cites work: Graph decomposition with constraints on the connectivity and minimum degree
cites work: Graph decomposition with applications to subdivisions and path systems modulo k
cites work: Subdivisions of graphs with large minimum degree
full work available at URL: 0012-365x(88)90122-7
OpenAlex ID: W2167211542
description: scientific article; zbMATH DE number 4049678