Star partitions of graphs

Star partitions of graphs,10.1002/(SICI)1097-0118(199707)25:3<185::AID-JGT2>3.0.CO;2-H,Journal of Graph Theory,Y. Egawa,M. Kano,Alexander K. Kelmans

Star partitions of graphs   (Citations: 8)
BibTex | RIS | RefWorks Download
Abstract Let G be a graph and n ≥ 2 an integer. We prove that the following are equivalent: (i) there is a partition (V1,...,Vm )o fV (G) such that each Vi induces one of stars K1,1,...,K1,n, and (ii) for every subset S of V (G), G\S has at most n|S| components with the property that each of their blocks is an odd order complete graph.
Journal: Journal of Graph Theory - JGT , vol. 25, no. 3, pp. 185-190, 1997
Cumulative Annual
View Publication
The following links allow you to view full publications. These links are maintained by other sources not affiliated with Microsoft Academic Search.
    • ...}). The induced {S1 ,..., Sk}-packing problemwasfirststudiedbyEgawa,KanoandKelmans[6,10]whogaveapolynomial algorithm, a Gallai–Edmonds type structure theorem and a Tutte type theorem...
    • ...The induced ≤ k-star packing problem (H ={ Si : 1 ≤ i ≤ k}) was introduced by Egawa, Kano and Kelmans [6,10]...
    • ...3.1, and we even allow F � . Independently, Egawa, Kano and Kelmans [6] gave a simpler inductive proof to this Tutte type theorem...
    • ...The present treatment of the induced ≤ k-star packing problem is much more compact than in [6,10]...

    Zoltán Királyet al. Induced Graph Packing Problems

    • ...The case m(v) k > 1 was examined in [6], [2] and [8]...

    Zoltan Kiraly. supermodular functions and dual packing theory

Sort by: