Projects per year
Abstract
A kstar is a complete bipartite graph K_{1,k}. For a graph G, a kstar decomposition of G is a set of kstars in G whose edge sets partition the edge set of G. If we weaken this condition to only demand that each edge of G is in at most one kstar, then the resulting object is a partial kstar decomposition of G. An embedding of a partial kstar decomposition A of a graph G is a partial kstar decomposition B of another graph H such that A ⊆ B and G is a subgraph of H. This paper considers the problem of when a partial kstar decomposition of K_{n} can be embedded in a kstar decomposition of K_{n+s} for a given integer s. We improve a result of Noble and Richardson, itself an improvement of a result of Hoffman and Roberts, by showing that any partial kstar decomposition of K_{n} can be embedded in a kstar decomposition of K_{n+s} for some s such that (formula presented) whenkis odd ands (formula presented) when k is even. For general k, these constants cannot be improved. We also obtain stronger results subject to placing a lower bound on n.
Original language  English 

Article number  P1.19 
Number of pages  20 
Journal  The Electronic Journal of Combinatorics 
Volume  30 
Issue number  1 
DOIs  
Publication status  Published  2023 
Projects
 2 Finished

Edge decomposition of dense graphs
Australian Research Council (ARC)
30/06/17 → 31/10/22
Project: Research

Matchings in Combinatorial Structures
Wanless, I., Bryant, D. & Horsley, D.
Australian Research Council (ARC), Monash University, University of Queensland , University of Melbourne
1/01/15 → 10/10/20
Project: Research