Wyniki wyszukiwania - BazTech

Ograniczanie wyników

Znaleziono wyników: 3

Liczba wyników na stronie

Wyniki wyszukiwania

Wyszukiwano:
w słowach kluczowych: independence number

Sortuj według:

Ogranicz wyniki do:

On the independence number of some strong products of cycle-powers

Jurkiewicz M., Kubale M., Ocetkiewicz K.

Foundations of Computing and Decision Sciences

2015

Vol. 40, No. 2

133--141

In the paper we give some theoretical and computational results on the third strong power of cycle-powers, for example, we have found the independence numbers α((C210)⊠3) = 30 and α((C414)⊠3) = 14. A number of optimizations have been introduced to improve the running time of our exhaustive algorithm used to establish the independence number of the third strong power of cycle-powers. Moreover, our results establish new exact values and/or lower bounds on the Shannon capacity of noisy channels.

Bounds on the 2-domination number in cactus graphs

Chellali M.

Opuscula Mathematica

2006

Vol. 26, no. 1

5-12

A 2-dominating set of a graph G is a set D of vertices of G such that every vertex not in S is dominated at least twice. The minimum cardinality of a 2-dominating set of G is the 2-domination number γ2(G). We show that if G is a nontrivial connected cactus graph with k(G) even cycles (k(G) ≥ 0), then γ2(G) ≥ γt(G) - k(G), and if G is a graph of order n with at most one cycle, then γ2(G) ≥ (n + l - s)/2 improving Fink and Jacobson's lower bound for trees with l > s, where γt(G), l and s are the total domination number, the number of leaves and support vertices of G, respectively. We also show that if T is a tree of order n ≥ 3, then γ2(T) ≤ β(T) + s - 1, where β(T) is the independence number of T.

A note of arbitrarily vertex decomposable graphs

Marczyk A.

Opuscula Mathematica

2006

Vol. 26, no. 1

109-118

A graph G of order n is said to be arbitrarily vertex decomposable if for each sequence (n1,..., nk) of positive integers such that n1 + ... + nk = n there exists a partition (V1,..., Vk) of the vertex set of G such that for each i ∈ {1,..., k}, Vi induces a connected subgraph of G on ni vertices. In this paper we show that if G is a two-connected graph on n vertices with the independence number at most ⌈n/2⌉ and such that the degree sum of any pair of non-adjacent vertices is at least n - 3, then G is arbitrarily vertex decomposable. We present another result for connected graphs satisfying a similar condition, where the bound n - 3 is replaced by n - 2.