Star-Cycle Factors of Graphs
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 ∈ V (G) : f(v) = 1}. Under this notation, it was proved by Berge and Las Vergnas that G has a star-cycle factor...
| Main Authors: | , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
University of Zielona Góra
2014-02-01
|
| Series: | Discussiones Mathematicae Graph Theory |
| Subjects: | |
| Online Access: | https://doi.org/10.7151/dmgt.1717 |
| _version_ | 1797757670582648832 |
|---|---|
| author | Egawa Yoshimi Kano Mikio Yan Zheng |
| author_facet | Egawa Yoshimi Kano Mikio Yan Zheng |
| author_sort | Egawa Yoshimi |
| collection | DOAJ |
| description | 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 ∈ 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 degF (v) ≤ f(v), and (ii) if a component D of F is a cycle, then V (D) ⊆ W if and only if iso(G − S) ≤ Σx∈S f(x) for all S ⊂ 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. |
| first_indexed | 2024-03-12T18:18:57Z |
| format | Article |
| id | doaj.art-20cf738df8014350b7c22cea44d2f250 |
| institution | Directory Open Access Journal |
| issn | 2083-5892 |
| language | English |
| last_indexed | 2024-03-12T18:18:57Z |
| publishDate | 2014-02-01 |
| publisher | University of Zielona Góra |
| record_format | Article |
| series | Discussiones Mathematicae Graph Theory |
| spelling | doaj.art-20cf738df8014350b7c22cea44d2f2502023-08-02T08:59:13ZengUniversity of Zielona GóraDiscussiones Mathematicae Graph Theory2083-58922014-02-0134119319810.7151/dmgt.1717dmgt.1717Star-Cycle Factors of GraphsEgawa Yoshimi0Kano Mikio1Yan Zheng2Tokyo University of Science, Shinjuku-Ku, Tokyo, JapanIbaraki University, Hitachi, Ibaraki, JapanIbaraki University, Hitachi, Ibaraki, JapanA 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 ∈ 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 degF (v) ≤ f(v), and (ii) if a component D of F is a cycle, then V (D) ⊆ W if and only if iso(G − S) ≤ Σx∈S f(x) for all S ⊂ 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.https://doi.org/10.7151/dmgt.1717star factorcycle factorstar-cycle factorfactor of graph |
| spellingShingle | Egawa Yoshimi Kano Mikio Yan Zheng Star-Cycle Factors of Graphs Discussiones Mathematicae Graph Theory star factor cycle factor star-cycle factor factor of graph |
| title | Star-Cycle Factors of Graphs |
| title_full | Star-Cycle Factors of Graphs |
| title_fullStr | Star-Cycle Factors of Graphs |
| title_full_unstemmed | Star-Cycle Factors of Graphs |
| title_short | Star-Cycle Factors of Graphs |
| title_sort | star cycle factors of graphs |
| topic | star factor cycle factor star-cycle factor factor of graph |
| url | https://doi.org/10.7151/dmgt.1717 |
| work_keys_str_mv | AT egawayoshimi starcyclefactorsofgraphs AT kanomikio starcyclefactorsofgraphs AT yanzheng starcyclefactorsofgraphs |