Balanced graphs with minimum degree constraints
type: Item
instance of: scholarly article
title: Balanced graphs with minimum degree constraints
zbMATH Open document ID: 0770.05094
DOI: 10.1016/0012-365X(92)90123-W
published in: Discrete Mathematics
publication date: 1992-09-27T00:00:00Z
review text: Let \(G\) be a graph of order \(n\) with minimum vertex degree \(\delta(G)\) or shortly \(\delta\), \(n\equiv\delta\pmod 2\). If \(X\subseteq V(G)\) then \(\langle X\rangle\) is the induced subgraph of \(G\) with vertex set \(X\). Suppose that \(0\leq\delta\leq n-2\), \(0\leq i\leq\left\lfloor{1\over 2}\delta\right\rfloor\). By an \((i,\delta)\)-partition of \(G\) the author means a partition \((X,Y)\) of \(V(G)\) with (i) \(| X|=\left\lceil{1\over 2}n\right\rceil+i\), \(| Y|=\left\lfloor{1\over 2}n\right\rfloor-i\), and (ii) \(\delta(\langle X\rangle)\geq\left\lceil{1\over 2}\delta\right\rceil+i\), \(\delta(\langle Y\rangle)\geq\left\lfloor{1\over 2}\delta\right\rfloor-i\). It is shown that if \(G\) is connected then \(G\) possesses an \((i,\delta)\)-partition for some \(i, 0\leq i\leq\left\lfloor{1\over 2}\delta\right\rfloor-1\). The context of the paper under review was discussed in the author's earlier paper [Discrete Math. 68, No. 2/3, 299-307 (1988; Zbl 0644.05030)].
reviewed by: J.Sedláček
Mathematics Subject Classification ID: 05C99
Mathematics Subject Classification ID: 05C35
zbMATH DE Number: 64639
zbMATH Keywords: balanced graphs
zbMATH Keywords: minimum vertex degree
zbMATH Keywords: partition
author: J. Sheehan
MaRDI profile type: Publication
cites work: Vertex colorings without isolates
cites work: Graph decomposition with constraints in the minimum degree
cites work: The binding number of a graph and its Anderson number
full work available at URL: 0012-365x(92)90123-w
OpenAlex ID: W1973975855
description: scientific article; zbMATH DE number 64639