- Tytuł:
- Star-Cycle Factors of Graphs
- Autorzy:
-
Egawa, Yoshimi
Kano, Mikio
Yan, Zheng - Powiązania:
- https://bibliotekanauki.pl/articles/30147223.pdf
- Data publikacji:
- 2014-02-01
- Wydawca:
- Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
- Tematy:
-
star factor
cycle factor
star-cycle factor
factor of graph - Opis:
- 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 $deg_F (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.
- Źródło:
-
Discussiones Mathematicae Graph Theory; 2014, 34, 1; 193-198
2083-5892 - Pojawia się w:
- Discussiones Mathematicae Graph Theory
- Dostawca treści:
- Biblioteka Nauki
Artykuł