- Tytuł:
- New Formulae for the Decycling Number of Graphs
- Autorzy:
-
Yang, Chao
Ren, Han - Powiązania:
- https://bibliotekanauki.pl/articles/31343660.pdf
- Data publikacji:
- 2019-02-01
- Wydawca:
- Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
- Tematy:
-
decycling number
independence number
cycle rank
margin number - Opis:
- A set $S$ of vertices of a graph $G$ is called a decycling set if $G−S$ is acyclic. The minimum order of a decycling set is called the decycling number of $G$, and denoted by $ \nabla(G)$. Our results include: (a) For any graph $G$, $ \nabla (G) = n - \max_T \{ \alpha (G- E(T)) \} $, where $T$ is taken over all the spanning trees of $G$ and $ \alpha (G − E(T)) $ is the independence number of the co-tree $ G − E(T) $. This formula implies that computing the decycling number of a graph $G$ is equivalent to finding a spanning tree in $G$ such that its co-tree has the largest independence number. Applying the formula, the lower bounds for the decycling number of some (dense) graphs may be obtained. (b) For any decycling set $S$ of a $k$-regular graph $G$, $ |S| = \frac{1}{k-1} (\beta (G) + m(S)) $, where $ \beta(G) = |E(G)|−|V (G)|+1 $ and $ m(S) = c+|E(S)|−1$, $c$ and $|E(S)|$ are, respectively, the number of components of $G − S$ and the number of edges in $G[S]$. Hence $S$ is a $ \nabla$-set if and only if $m(S)$ is minimum, where $ \nabla$-set denotes a decycling set containing exactly $ \nabla(G)$ vertices of $G$. This provides a new way to locate $ \nabla(G) $ for $k$-regular graphs $G$. (c) 4-regular graphs $G$ with the decycling number $ \nabla (G) = \ceil{ \tfrac{ \beta(G)}{3} } $ are determined.
- Źródło:
-
Discussiones Mathematicae Graph Theory; 2019, 39, 1; 125-141
2083-5892 - Pojawia się w:
- Discussiones Mathematicae Graph Theory
- Dostawca treści:
- Biblioteka Nauki
Artykuł