On the ascending subgraph decompositions of regular graphs
type: Item
instance of: scholarly article
title: On the ascending subgraph decompositions of regular graphs
zbMATH Open document ID: 0904.05068
author: Huaitang Chen
author: Kejie Ma
published in: Applied Mathematics. Series B (English Edition)
publication date: 1998-11-05T00:00:00Z
review text: Let \(G\) be a graph with \(q\) edges and let \(n\) be a positive integer such that \(\binom{n+1}2\leq q<\binom{n+2}2\). Then \(G\) has an ascending subgraph decomposition if \(G\) can be decomposed into \(n\) subgraphs \(G_1,G_2,\dots,G_n\) without isolated vertices such that \(G_i\) is isomorphic to a proper subgraph of \(G_{i+1}\), \(1\leq i<n\). In the paper it is proved that if \(G\) is an \(r\)-regular graph with \(q=\binom{n+1}2\) edges such that \(r\leq\frac 23(n+\delta_{\Delta(G),\chi'(G)})\), then \(G\) has an ascending subgraph decomposition. (Here \(\delta\) is the Kronecker delta.) Moreover, it is proved that every regular bipartite graph has an ascending subgraph decomposition.
Mathematics Subject Classification ID: 05C70
zbMATH DE Number: 1193543
zbMATH Keywords: ascending subgraph decomposition
zbMATH Keywords: bipartite graph
zbMATH Keywords: induced subgraph
zbMATH Keywords: regular graph
reviewed by: Martin Knor
MaRDI profile type: Publication
full work available at URL: s11766-998-0037-z
OpenAlex ID: W2062533077
cites work: Q3818315
cites work: Q3990416
cites work: Q3792719
cites work: Q4848982
cites work: Q4735216
cites work: Q3974289
cites work: Q4267368
DOI: 10.1007/S11766-998-0037-Z
description: scientific article; zbMATH DE number 1193543