- Tytuł:
- A Characterization of Trees for a New Lower Bound on the K-Independence Number
- Autorzy:
-
Meddah, Nacéra
Blidia, Mostafa - Powiązania:
- https://bibliotekanauki.pl/articles/30146579.pdf
- Data publikacji:
- 2013-05-01
- Wydawca:
- Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
- Tematy:
-
domination
independence
k-independence - Opis:
- Let $k$ be a positive integer and $G = (V,E)$ a graph of order $n$. A subset $S$ of $V$ is a $k$-independent set of $G$ if the maximum degree of the subgraph induced by the vertices of $S$ is less or equal to $k − 1$. The maximum cardinality of a $k$-independent set of $G$ is the $k$-independence number $\beta_k (G)$. In this paper, we show that for every graph $ G $, $\beta_k (G) \geq $ \( \lceil ( n + ( \chi(G)-1) \Sigma_{v \in S(G)} \min ( | L_v|, k-1) ) / \chi(G) \rceil \), where $\chi(G)$, $s(G)$ and $L_v$ are the chromatic number, the number of supports vertices and the number of leaves neighbors of $v$, in the graph $G$, respectively. Moreover, we characterize extremal trees attaining these bounds.
- Źródło:
-
Discussiones Mathematicae Graph Theory; 2013, 33, 2; 395-410
2083-5892 - Pojawia się w:
- Discussiones Mathematicae Graph Theory
- Dostawca treści:
- Biblioteka Nauki
Artykuł