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: 13

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

Wyniki wyszukiwania

help Sortuj według:

help Ogranicz wyniki do:
first rewind previous Strona / 1 next fast forward last
1
Content available remote

A Note on Barnette’s Conjecture

100%
Harant J.
Discussiones Mathematicae Graph Theory
|
2013
|
tom 33
|
nr 1
133-137
EN
Barnette conjectured that each planar, bipartite, cubic, and 3-connected graph is hamiltonian. We prove that this conjecture is equivalent to the statement that there is a constant c > 0 such that each graph G of this class contains a path on at least c|V (G)| vertices.
2
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.
3
Artykuł dostępny w postaci pełnego tekstu - kliknij by otworzyć plik
Content available

A note on domination in bipartite graphs

64%
Gerlach T., Harant J.
Discussiones Mathematicae Graph Theory
|
2002
|
tom 22
|
nr 2
229-231
EN
DOMINATING SET remains NP-complete even when instances are restricted to bipartite graphs, however, in this case VERTEX COVER is solvable in polynomial time. Consequences to VECTOR DOMINATING SET as a generalization of both are discussed.
4
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

64%
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.
5
Artykuł dostępny w postaci pełnego tekstu - kliknij by otworzyć plik
Content available

On double domination in graphs

64%
Harant J., Henning M.
Discussiones Mathematicae Graph Theory
|
2005
|
tom 25
|
nr 1-2
29-34
EN
In a graph G, a vertex dominates itself and its neighbors. A subset S ⊆ V(G) is a double dominating set of G if S dominates every vertex of G at least twice. The minimum cardinality of a double dominating set of G is the double domination number $γ_{×2}(G)$. A function f(p) is defined, and it is shown that $γ_{×2}(G) = min f(p)$, where the minimum is taken over the n-dimensional cube $Cⁿ = {p = (p₁,...,pₙ) | p_i ∈ IR, 0 ≤ p_i ≤ 1,i = 1,...,n}$. Using this result, it is then shown that if G has order n with minimum degree δ and average degree d, then $γ_{×2}(G) ≤ ((ln(1+d) + lnδ + 1)/δ)n$.
6
Artykuł dostępny w postaci pełnego tekstu - kliknij by otworzyć plik
Content available

Random procedures for dominating sets in bipartite graphs

64%
Artmann S., Harant J.
Discussiones Mathematicae Graph Theory
|
2010
|
tom 30
|
nr 2
277-288
EN
Using multilinear functions and random procedures, new upper bounds on the domination number of a bipartite graph in terms of the cardinalities and the minimum degrees of the two colour classes are established.
7
Artykuł dostępny w postaci pełnego tekstu - kliknij by otworzyć plik
Content available

On domination in graphs

64%
Göring F., Harant J.
Discussiones Mathematicae Graph Theory
|
2005
|
tom 25
|
nr 1-2
7-12
EN
For a finite undirected graph G on n vertices two continuous optimization problems taken over the n-dimensional cube are presented and it is proved that their optimum values equal the domination number γ of G. An efficient approximation method is developed and known upper bounds on γ are slightly improved.
8
Artykuł dostępny w postaci pełnego tekstu - kliknij by otworzyć plik
Content available

Preface

52%
Harant J., Voigt M., Schiermeyer I.
Discussiones Mathematicae Graph Theory
|
2002
|
tom 22
|
nr 1
5-6
9
Content available remote

On Longest Cycles in Essentially 4-Connected Planar Graphs

52%
Fabrici I., Harant J., Jendroľ S.
Discussiones Mathematicae Graph Theory
|
2016
|
tom 36
|
nr 3
565-575
EN
A planar 3-connected graph G is essentially 4-connected if, for any 3-separator S of G, one component of the graph obtained from G by removing S is a single vertex. Jackson and Wormald proved that an essentially 4-connected planar graph on n vertices contains a cycle C such that [...] . For a cubic essentially 4-connected planar graph G, Grünbaum with Malkevitch, and Zhang showed that G has a cycle on at least ¾ n vertices. In the present paper the result of Jackson and Wormald is improved. Moreover, new lower bounds on the length of a longest cycle of G are presented if G is an essentially 4-connected planar graph of maximum degree 4 or G is an essentially 4-connected maximal planar graph.
10
Content available remote

Eigenvalue Conditions for Induced Subgraphs

52%
Harant J., Niebling J., Richter S.
Discussiones Mathematicae Graph Theory
|
2015
|
tom 35
|
nr 2
355-363
EN
Necessary conditions for an undirected graph G to contain a graph H as induced subgraph involving the smallest ordinary or the largest normalized Laplacian eigenvalue of G are presented.
11
Artykuł dostępny w postaci pełnego tekstu - kliknij by otworzyć plik
Content available

Paths of low weight in planar graphs

52%
Fabrici I., Harant J., Jendrol' S.
Discussiones Mathematicae Graph Theory
|
2008
|
tom 28
|
nr 1
121-135
EN
The existence of paths of low degree sum of their vertices in planar graphs is investigated. The main results of the paper are: 1. Every 3-connected simple planar graph G that contains a k-path, a path on k vertices, also contains a k-path P such that for its weight (the sum of degrees of its vertices) in G it holds $w_G(P): = ∑_{u∈ V(P)} deg_G(u) ≤ (3/2)k² + 𝓞(k)$ 2. Every plane triangulation T that contains a k-path also contains a k-path P such that for its weight in T it holds $w_T(P): = ∑_{u∈ V(P)} deg_T(u) ≤ k² +13 k$ 3. Let G be a 3-connected simple planar graph of circumference c(G). If c(G) ≥ σ| V(G)| for some constant σ > 0 then for any k, 1 ≤ k ≤ c(G), G contains a k-path P such that $w_G(P) = ∑_{u∈ V(P)} deg_G(u) ≤ (3/σ + 3)k$.
12
Artykuł dostępny w postaci pełnego tekstu - kliknij by otworzyć plik
Content available

On long cycles through four prescribed vertices of a polyhedral graph

52%
Harant J., Jendrol' S., Walther H.
Discussiones Mathematicae Graph Theory
|
2008
|
tom 28
|
nr 3
441-451
EN
For a 3-connected planar graph G with circumference c ≥ 44 it is proved that G has a cycle of length at least (1/36)c+(20/3) through any four vertices of G.
13
Artykuł dostępny w postaci pełnego tekstu - kliknij by otworzyć plik
Content available

On 𝓕-independence in graphs

52%
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.
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ć.