Name
Abstract | ||
|---|---|---|
In 1996, Michael Stiebitz proved that if G is a simple graph with δ(G)≥s+t+1 and s,t∈Z0, then V(G) can be partitioned into two sets A and B such that δ(G[A])≥s and δ(G[B])≥t. In 2016, Amir Ban proved a similar result for weighted graphs. Let G be a simple graph with at least two vertices, let w:E(G)→R>0 be a weight function, let s,t∈R≥0, and let W=maxe∈E(G)w(e). If δ(G)≥s+t+2W, then V(G) can be partitioned into two sets A and B such that δ(G[A])≥s and δ(G[B])≥t. This motivated us to consider this partition problem for multigraphs, or equivalently for weighted graphs (G,w) with w:E(G)→Z≥1. We prove that if s,t∈Z≥0 and δ(G)≥s+t+2W−1≥1, then V(G) can be partitioned into two sets A and B such that δ(G[A])≥s and δ(G[B])≥t. We also prove a variable version of this result and show that for K4−-free graphs, the bound on the minimum degree can be decreased. |
Year | DOI | Venue |
|---|---|---|
2019 | 10.1016/j.dam.2018.10.016 | Discrete Applied Mathematics |
Keywords | Field | DocType |
Multigraph decomposition,Vertex partition,Vertex degree | Partition problem,Discrete mathematics,Graph,Combinatorics,Weight function,Vertex (geometry),Mathematics | Journal |
Volume | ISSN | Citations |
257 | 0166-218X | 0 |
PageRank | References | Authors |
0.34 | 6 | 2 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| thomas schweser | 1 | 0 | 2.37 |
| Michael Stiebitz | 2 | 207 | 30.08 |