Abstract | ||
---|---|---|
A spanning subgraph F of a graph G is called a star-cycle factor of G if each component of F is a star or cycle. Let G be a graph and f : V(G) -> {1, 2, 3,...} be a function. Let W = {v is an element of V(G) : f (v) = 1}. Under this notation, it was proved by Berge and Las Vergnas that G has a star-cycle factor F with the property that (i) if a component D of F is a star with center v, then deg(v) <= f(v), and (ii) if a component D of F is a cycle, then V(D) subset of W if and only if iso(G - S) <= Sigma(x is an element of s) f (x) for all S subset of V(G), where iso(G - S) denotes the number of isolated vertices of G - S. They proved this result by using circulation theory of flows and fractional factors of graphs. In this paper, we give an elementary and short proof of this theorem. |
Year | DOI | Venue |
---|---|---|
2014 | 10.7151/dmgt.1717 | DISCUSSIONES MATHEMATICAE GRAPH THEORY |
Keywords | Field | DocType |
star factor,cycle factor,star-cycle factor,factor of graph | Discrete mathematics,Graph,Combinatorics,Mathematics | Journal |
Volume | Issue | ISSN |
34 | 1 | 1234-3099 |
Citations | PageRank | References |
0 | 0.34 | 1 |
Authors | ||
3 |
Name | Order | Citations | PageRank |
---|---|---|---|
Yoshimi Egawa | 1 | 0 | 0.34 |
Mikio Kano | 2 | 548 | 99.79 |
Zheng Yan | 3 | 0 | 2.37 |