Autor: Meddah, Nacéra - Katalog OPAC zbiorów

Skocz do pozycji: 1.

Tytuł:: Trees with equal 2-domination and 2-independence numbers
Autorzy:: Chellali, Mustapha
Meddah, Nacéra
Powiązania:: https://bibliotekanauki.pl/articles/743338.pdf
Data publikacji:: 2012
Wydawca:: Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:: 2-domination number
2-independence number
trees
Opis:: Let G = (V,E) be a graph. A subset S of V is a 2-dominating set if every vertex of V-S is dominated at least 2 times, and S is a 2-independent set of G if every vertex of S has at most one neighbor in S. The minimum cardinality of a 2-dominating set a of G is the 2-domination number γ₂(G) and the maximum cardinality of a 2-independent set of G is the 2-independence number β₂(G). Fink and Jacobson proved that γ₂(G) ≤ β₂(G) for every graph G. In this paper we provide a constructive characterization of trees with equal 2-domination and 2-independence numbers.
Źródło:: Discussiones Mathematicae Graph Theory; 2012, 32, 2; 263-270
2083-5892
Pojawia się w:: Discussiones Mathematicae Graph Theory
Dostawca treści:: Biblioteka Nauki

Artykuł

Skocz do pozycji: 2.

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ł

Skocz do pozycji: 3.

Tytuł:: Maximal k-independent sets in graphs
Autorzy:: Blidia, Mostafa
Chellali, Mustapha
Favaron, Odile
Meddah, Nacéra
Powiązania:: https://bibliotekanauki.pl/articles/743533.pdf
Data publikacji:: 2008
Wydawca:: Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:: k-independent
cactus
Opis:: A subset of vertices of a graph G is k-independent if it induces in G a subgraph of maximum degree less than k. The minimum and maximum cardinalities of a maximal k-independent set are respectively denoted iₖ(G) and βₖ(G). We give some relations between βₖ(G) and $β_j(G)$ and between iₖ(G) and $i_j(G)$ for j ≠ k. We study two families of extremal graphs for the inequality i₂(G) ≤ i(G) + β(G). Finally we give an upper bound on i₂(G) and a lower bound when G is a cactus.
Źródło:: Discussiones Mathematicae Graph Theory; 2008, 28, 1; 151-163
2083-5892
Pojawia się w:: Discussiones Mathematicae Graph Theory
Dostawca treści:: Biblioteka Nauki

Artykuł

Informacja