A generalization of Stiebitz-type results on graph decomposition (Q2034069)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | A generalization of Stiebitz-type results on graph decomposition |
scientific article |
Statements
A generalization of Stiebitz-type results on graph decomposition (English)
0 references
21 June 2021
0 references
This article investigates under which conditions a multigraph of a given minimum degree can be partitioned into two induced subgraphs of given minimum degrees generalizing a result of \textit{M. Liu} and \textit{B. Xu} [Discrete Appl. Math. 295, 25--31 (2021; Zbl 1460.05157)] to a larger class of multigraphs. To state the result of the article we need some notation: For a vertex \(v\) of a multigraph \(G\) let \(\mu_G(v)=\max\{\mu_G(u,v):u\in V(G)\setminus{v}\}\), where \(\mu_G(u,v)\) is the number of edges joining \(u\) and \(v\) in \(G\). For a subset \(S\subseteq V(G)\) let \(d_S(v)\) be the number of vertices in \(S\) adjacent to \(v\). Liu and Xu proved in [loc. cit.] the following theorem for triangle-free multigraphs in which no two quadrilaterals share an edge: For any two functions \(a,b:V(G)\rightarrow \mathbb N\setminus\{0,1\}\) with \(d_G(v)\geq a(v)+b(v)+2\mu_G(v)-3\) for each \(v\in V(G)\), there exists a partition \((X,Y)\) of \(V(G)\) such that \(d_X(v)\geq a(v)\) for all \(v\in X\) and \(d_Y(v)\geq b(v)\) for all \(v\in Y\). The authors show that the theorem of Liu and Xu [loc. cit.] also holds for graphs with triangles in which no quadrilateral shares an edge with another quadrilateral or with a triangle.
0 references
vertex partition
0 references
multigraph decomposition
0 references