Pełnotekstowe zasoby PLDML oraz innych baz dziedzinowych są już dostępne w nowej Bibliotece Nauki.
Zapraszamy na https://bibliotekanauki.pl
Preferencje help
Polish version English version Język
Widoczny [Schowaj] Abstrakt
Liczba wyników

Znaleziono wyników: 8

Liczba wyników na stronie
first rewind previous Strona / 1 next fast forward last

Wyniki wyszukiwania

Wyszukiwano:
w słowach kluczowych:  independence
help Sortuj według:

help Ogranicz wyniki do:
first rewind previous Strona / 1 next fast forward last
1
Artykuł dostępny w postaci pełnego tekstu - kliknij by otworzyć plik
Content available

Some news about the independence number of a graph

100%
Harant J.
Discussiones Mathematicae Graph Theory
|
2000
|
tom 20
|
nr 1
71-79
EN
For a finite undirected graph G on n vertices some continuous optimization problems taken over the n-dimensional cube are presented and it is proved that their optimum values equal the independence number of G.
2
Artykuł dostępny w postaci pełnego tekstu - kliknij by otworzyć plik
Content available

Domination and independence subdivision numbers of graphs

80%
Haynes T., Hedetniemi S., Hedetniemi S.
Discussiones Mathematicae Graph Theory
|
2000
|
tom 20
|
nr 2
271-280
EN
The domination subdivision number $sd_γ(G)$ of a graph is the minimum number of edges that must be subdivided (where an edge can be subdivided at most once) in order to increase the domination number. Arumugam showed that this number is at most three for any tree, and conjectured that the upper bound of three holds for any graph. Although we do not prove this interesting conjecture, we give an upper bound for the domination subdivision number for any graph G in terms of the minimum degrees of adjacent vertices in G. We then define the independence subdivision number $sd_β(G)$ to equal the minimum number of edges that must be subdivided (where an edge can be subdivided at most once) in order to increase the independence number. We show that for any graph G of order n ≥ 2, either $G = K_{1,m}$ and $sd_β(G) = m$, or $1 ≤ sd_β(G) ≤ 2$. We also characterize the graphs G for which $sd_β(G) = 2$.
3
Content available remote

A Characterization of Trees for a New Lower Bound on the K-Independence Number

80%
Meddah N., Blidia M.
Discussiones Mathematicae Graph Theory
|
2013
|
tom 33
|
nr 2
395-410
EN
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 βk(G). In this paper, we show that for every graph [xxx], where χ(G), s(G) and Lv 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.
4
Artykuł dostępny w postaci pełnego tekstu - kliknij by otworzyć plik
Content available

Hereditary domination and independence parameters

80%
Goddard W., Haynes T., Knisley D.
Discussiones Mathematicae Graph Theory
|
2004
|
tom 24
|
nr 2
239-248
EN
For a graphical property P and a graph G, we say that a subset S of the vertices of G is a P-set if the subgraph induced by S has the property P. Then the P-domination number of G is the minimum cardinality of a dominating P-set and the P-independence number the maximum cardinality of a P-set. We show that several properties of domination, independent domination and acyclic domination hold for arbitrary properties P that are closed under disjoint unions and subgraphs.
5
Artykuł dostępny w postaci pełnego tekstu - kliknij by otworzyć plik
Content available

A lower bound on the independence number of a graph in terms of degrees

80%
Harant J., Schiermeyer I.
Discussiones Mathematicae Graph Theory
|
2006
|
tom 26
|
nr 3
431-437
EN
For a connected and non-complete graph, a new lower bound on its independence number is proved. It is shown that this bound is realizable by the well known efficient algorithm MIN.
6
Artykuł dostępny w postaci pełnego tekstu - kliknij by otworzyć plik
Content available

On 𝓕-independence in graphs

80%
Göring F., Harant J., Rautenbach D., Schiermeyer I.
Discussiones Mathematicae Graph Theory
|
2009
|
tom 29
|
nr 2
377-383
EN
Let 𝓕 be a set of graphs and for a graph G let $α_{𝓕}(G)$ and $α*_{𝓕}(G)$ denote the maximum order of an induced subgraph of G which does not contain a graph in 𝓕 as a subgraph and which does not contain a graph in 𝓕 as an induced subgraph, respectively. Lower bounds on $α_{𝓕}(G)$ and $α*_{𝓕}(G)$ are presented.
7
Artykuł dostępny w postaci pełnego tekstu - kliknij by otworzyć plik
Content available

Associative graph products and their independence, domination and coloring numbers

70%
Nowakowski R., Rall D.
Discussiones Mathematicae Graph Theory
|
1996
|
tom 16
|
nr 1
53-79
EN
Associative products are defined using a scheme of Imrich & Izbicki [18]. These include the Cartesian, categorical, strong and lexicographic products, as well as others. We examine which product ⊗ and parameter p pairs are multiplicative, that is, p(G⊗H) ≥ p(G)p(H) for all graphs G and H or p(G⊗H) ≤ p(G)p(H) for all graphs G and H. The parameters are related to independence, domination and irredundance. This includes Vizing's conjecture directly, and indirectly the Shannon capacity of a graph and Hedetniemi's coloring conjecture.
8
Artykuł dostępny w postaci pełnego tekstu - kliknij by otworzyć plik
Content available

Domination, independence and irredundance in graphs

62%
Topp J.
Instytut Matematyczny Polskiej Akademii Nauk
EN
CONTENTS 1. Introduction........................................................................................................ 5  1.1. Purpose and scope................................................................................. 5  1.2. Basic graphtheoretical terms................................................................ 6 2. Domination, independence and irredundance in graphs................................ 9  2.1. Introduction and preliminaries.............................................................. 9  2.2. Domination parameters of vertex and edgedeleted subgraphs..... 15  2.3. Packing and covering numbers............................................................ 25  2.4. Conditions for equalities of domination parameters........................ 35 3. Well covered graphs........................................................................................ 46  3.1. Introduction and preliminary results..................................................... 46  3.2. The well coveredness of products of graphs..................................... 55  3.3. Well covered simplicial and chordal graphs...................................... 67  3.4. Well covered line and total graphs....................................................... 73  3.5. Well covered generalized Petersen graphs........................................ 78  3.6. Well irredundant graphs......................................................................... 80 4. Graphical sequences and sets of integers......................................................... 85  4.1. Dominationfeasible sequences........................................................... 86  4.2. Interpolation properties of domination parameters.......................... 91 References.................................................................................................................... 94
first rewind previous Strona / 1 next fast forward last
JavaScript jest wyłączony w Twojej przeglądarce internetowej. Włącz go, a następnie odśwież stronę, aby móc w pełni z niej korzystać.