Informacja

Drogi użytkowniku, aplikacja do prawidłowego działania wymaga obsługi JavaScript. Proszę włącz obsługę JavaScript w Twojej przeglądarce.

English (EN)·Polski (PL)·Yкраїнський (UK)
Przejdź do strony domowej biblioteki Centralna Biblioteka Wojskowa Link otwiera się w nowym oknie Logo biblioteki Prolib Integro - strona głównaCentralna Biblioteka Wojskowa

Wyszukujesz frazę "perfect" wg kryterium: Temat

  Lista filtrów
Wyrównaj
Wyświetlanie 1-15 z 31
Tytuł:
Distance perfectness of graphs
Autorzy:
Włoch, Andrzej
Powiązania:
https://bibliotekanauki.pl/articles/744239.pdf
Data publikacji:
1999
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
perfect graphs
strongly perfect graphs
chromatic number
Opis:
In this paper, we propose a generalization of well known kinds of perfectness of graphs in terms of distances between vertices. We introduce generalizations of α-perfect, χ-perfect, strongly perfect graphs and we establish the relations between them. Moreover, we give sufficient conditions for graphs to be perfect in generalized sense. Other generalizations of perfectness are given in papers [3] and [7].
Źródło:
Discussiones Mathematicae Graph Theory; 1999, 19, 1; 31-43
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
Mycielskians and matchings
Autorzy:
Doslić, Tomislav
Powiązania:
https://bibliotekanauki.pl/articles/744354.pdf
Data publikacji:
2005
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
Mycielskian
factor-critical graph
perfect matching
perfect 2-matching
Opis:
It is shown in this note that some matching-related properties of graphs, such as their factor-criticality, regularizability and the existence of perfect 2-matchings, are preserved when iterating Mycielski's construction.
Źródło:
Discussiones Mathematicae Graph Theory; 2005, 25, 3; 261-266
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
On Fulkerson conjecture
Autorzy:
Fouquet, Jean-Luc
Vanherpe, Jean-Marie
Powiązania:
https://bibliotekanauki.pl/articles/743867.pdf
Data publikacji:
2011
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
cubic graph
perfect matchings
Opis:
If G is a bridgeless cubic graph, Fulkerson conjectured that we can find 6 perfect matchings (a Fulkerson covering) with the property that every edge of G is contained in exactly two of them. A consequence of the Fulkerson conjecture would be that every bridgeless cubic graph has 3 perfect matchings with empty intersection (this problem is known as the Fan Raspaud Conjecture). A FR-triple is a set of 3 such perfect matchings. We show here how to derive a Fulkerson covering from two FR-triples. Moreover, we give a simple proof that the Fulkerson conjecture holds true for some classes of well known snarks.
Źródło:
Discussiones Mathematicae Graph Theory; 2011, 31, 2; 253-272
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
On a perfect problem
Autorzy:
Zverovich, Igor
Powiązania:
https://bibliotekanauki.pl/articles/743945.pdf
Data publikacji:
2006
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
hereditary classes
perfect graphs
Opis:
We solve Open Problem (xvi) from Perfect Problems of Chvátal [1] available at ftp://dimacs.rutgers.edu/pub/perfect/problems.tex: Is there a class C of perfect graphs such that (a) C does not include all perfect graphs and (b) every perfect graph contains a vertex whose neighbors induce a subgraph that belongs to C? A class P is called locally reducible if there exists a proper subclass C of P such that every graph in P contains a local subgraph belonging to C. We characterize locally reducible hereditary classes. It implies that there are infinitely many solutions to Open Problem (xvi). However, it is impossible to find a hereditary class C of perfect graphs satisfying both (a) and (b).
Źródło:
Discussiones Mathematicae Graph Theory; 2006, 26, 2; 273-277
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
Kernels by Monochromatic Paths and Color-Perfect Digraphs
Autorzy:
Galeana-Śanchez, Hortensia
Sánchez-López, Rocío
Powiązania:
https://bibliotekanauki.pl/articles/31340961.pdf
Data publikacji:
2016-05-01
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
kernel
kernel perfect digraph
kernel by monochromatic paths
color-class digraph
quasi color-perfect digraph
color-perfect digraph
Opis:
For a digraph D, V (D) and A(D) will denote the sets of vertices and arcs of D respectively. In an arc-colored digraph, a subset K of V(D) is said to be kernel by monochromatic paths (mp-kernel) if (1) for any two different vertices x, y in N there is no monochromatic directed path between them (N is mp-independent) and (2) for each vertex u in V (D) \ N there exists v ∈ N such that there is a monochromatic directed path from u to v in D (N is mp-absorbent). If every arc in D has a different color, then a kernel by monochromatic paths is said to be a kernel. Two associated digraphs to an arc-colored digraph are the closure and the color-class digraph C(D). In this paper we will approach an mp-kernel via the closure of induced subdigraphs of D which have the property of having few colors in their arcs with respect to D. We will introduce the concept of color-perfect digraph and we are going to prove that if D is an arc-colored digraph such that D is a quasi color-perfect digraph and C(D) is not strong, then D has an mp-kernel. Previous interesting results are generalized, as for example Richardson′s Theorem.
Źródło:
Discussiones Mathematicae Graph Theory; 2016, 36, 2; 309-321
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
A note on strong and co-strong perfectness of the X-join of graphs
Autorzy:
Szelecka, Alina
Włoch, Andrzej
Powiązania:
https://bibliotekanauki.pl/articles/972008.pdf
Data publikacji:
1996
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
strongly perfect graphs
co-strongly perfect graphs
the X-join of graphs
Opis:
Strongly perfect graphs were introduced by C. Berge and P. Duchet in [1]. In [4], [3] the following was studied: the problem of strong perfectness for the Cartesian product, the tensor product, the symmetrical difference of n, n ≥ 2, graphs and for the generalized Cartesian product of graphs. Co-strong perfectness was first studied by G. Ravindra andD. Basavayya [5]. In this paper we discuss strong perfectness and co-strong perfectness for the generalized composition (the lexicographic product) of graphs named as the X-join of graphs.
Źródło:
Discussiones Mathematicae Graph Theory; 1996, 16, 2; 151-155
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
Lattice-Like Total Perfect Codes
Autorzy:
Araujo, Carlos
Dejter, Italo
Powiązania:
https://bibliotekanauki.pl/articles/30147219.pdf
Data publikacji:
2014-02-01
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
perfect dominating sets
hypercubes
lattices
Opis:
A contribution is made to the classification of lattice-like total perfect codes in integer lattices $Λ_n$ via pairs ($G, Φ$) formed by abelian groups $G$ and homomorphisms $Φ: Z^n → G$. A conjecture is posed that the cited contribution covers all possible cases. A related conjecture on the unfinished work on open problems on lattice-like perfect dominating sets in $Λ_n$ with induced components that are parallel paths of length > 1 is posed as well.
Źródło:
Discussiones Mathematicae Graph Theory; 2014, 34, 1; 57-74
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
An inequality chain of domination parameters for trees
Autorzy:
Cockayne, E.
Favaron, O.
Puech, J.
Mynhardt, C.
Powiązania:
https://bibliotekanauki.pl/articles/744211.pdf
Data publikacji:
1998
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
domination
irredundance
packing
perfect neighbourhoods
annihilation
Opis:
We prove that the smallest cardinality of a maximal packing in any tree is at most the cardinality of an R-annihilated set. As a corollary to this result we point out that a set of parameters of trees involving packing, perfect neighbourhood, R-annihilated, irredundant and dominating sets is totally ordered. The class of trees for which all these parameters are equal is described and we give an example of a tree in which most of them are distinct.
Źródło:
Discussiones Mathematicae Graph Theory; 1998, 18, 1; 127-142
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
Game-Perfect Semiorientations of Forests
Autorzy:
Andres, Stephan Dominique
Charpentier, Clément
Fong, Wai Lam
Powiązania:
https://bibliotekanauki.pl/articles/32361719.pdf
Data publikacji:
2022-05-01
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
game chromatic number
game-perfect digraph
forest
dichromatic number
game-perfect graph
forbidden induced subdigraph
Opis:
We consider digraph colouring games where two players, Alice and Bob, alternately colour vertices of a given digraph D with a colour from a given colour set in a feasible way. The game ends when such move is not possible any more. Alice wins if every vertex is coloured at the end, otherwise Bob wins. The smallest size of a colour set such that Alice has a winning strategy is the game chromatic number of D. The digraph D is game-perfect if, for every induced subdigraph H of D, the game chromatic number of H equals the size of the largest symmetric clique of H. In the strong game, colouring a vertex is feasible if its colour is different from the colours of its in-neighbours. In the weak game, colouring a vertex is feasible unless it creates a monochromatic directed cycle. There are six variants for each game, which specify the player who begins and whether skipping is allowed for some player. For all six variants of both games, we characterise the class of game-perfect semiorientations of forests by a set of forbidden induced subdigraphs and by an explicit structural description.
Źródło:
Discussiones Mathematicae Graph Theory; 2022, 42, 2; 501-534
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
Perfect connected-dominant graphs
Autorzy:
Zverovich, Igor
Powiązania:
https://bibliotekanauki.pl/articles/743393.pdf
Data publikacji:
2003
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
Connected domination
perfect connected-dominant graph
Opis:
If D is a dominating set and the induced subgraph G(D) is connected, then D is a connected dominating set. The minimum size of a connected dominating set in G is called connected domination number $γ_c(G)$ of G. A graph G is called a perfect connected-dominant graph if $γ(H) = γ_c(H)$ for each connected induced subgraph H of G.We prove that a graph is a perfect connected-dominant graph if and only if it contains no induced path P₅ and induced cycle C₅.
Źródło:
Discussiones Mathematicae Graph Theory; 2003, 23, 1; 159-162
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
Some sufficient conditions on odd directed cycles of bounded length for the existence of a kernel
Autorzy:
Galeana-Sánchez, Hortensia
Powiązania:
https://bibliotekanauki.pl/articles/744469.pdf
Data publikacji:
2004
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
kernel
kernel-perfect
critical kernel-imperfect
Opis:
A kernel N of a digraph D is an independent set of vertices of D such that for every w ∈ V(D)-N there exists an arc from w to N. If every induced subdigraph of D has a kernel, D is said to be a kernel-perfect digraph. In this paper I investigate some sufficient conditions for a digraph to have a kernel by asking for the existence of certain diagonals or symmetrical arcs in each odd directed cycle whose length is at most 2α(D)+1, where α(D) is the maximum cardinality of an independent vertex set of D. Previous results are generalized.
Źródło:
Discussiones Mathematicae Graph Theory; 2004, 24, 2; 171-182
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
On graphs all of whose {C₃,T₃}-free arc colorations are kernel-perfect
Autorzy:
Galeana-Sánchez, Hortensia
García-Ruvalcaba, José
Powiązania:
https://bibliotekanauki.pl/articles/743429.pdf
Data publikacji:
2001
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
kernel
kernel-perfect digraph
m-coloured digraph
Opis:
A digraph D is called a kernel-perfect digraph or KP-digraph when every induced subdigraph of D has a kernel.
We call the digraph D an m-coloured digraph if the arcs of D are coloured with m distinct colours. A path P is monochromatic in D if all of its arcs are coloured alike in D. The closure of D, denoted by ζ(D), is the m-coloured digraph defined as follows:
V( ζ(D)) = V(D), and
A( ζ(D)) = ∪_{i} {(u,v) with colour i: there exists a monochromatic path of colour i from the vertex u to the vertex v contained in D}.
We will denoted by T₃ and C₃, the transitive tournament of order 3 and the 3-directed-cycle respectively; both of whose arcs are coloured with three different colours.
Let G be a simple graph. By an m-orientation-coloration of G we mean an m-coloured digraph which is an asymmetric orientation of G.
By the class E we mean the set of all the simple graphs G that for any m-orientation-coloration D without C₃ or T₃, we have that ζ(D) is a KP-digraph.
In this paper we prove that if G is a hamiltonian graph of class E, then its complement has at most one nontrivial component, and this component is K₃ or a star.
Źródło:
Discussiones Mathematicae Graph Theory; 2001, 21, 1; 77-93
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
A New Upper Bound for the Perfect Italian Domination Number of a Tree
Autorzy:
Nazari-Moghaddam, Sakineh
Chellali, Mustapha
Powiązania:
https://bibliotekanauki.pl/articles/32304138.pdf
Data publikacji:
2022-08-01
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
Italian domination
Roman domination
perfect Italian domination
Opis:
A perfect Italian dominating function (PIDF) on a graph $G$ is a function $ f : V (G) \rightarrow \{ 0, 1, 2 \} $ satisfying the condition that for every vertex u with $f(u) = 0$, the total weight of $f$ assigned to the neighbors of $u$ is exactly two. The weight of a PIDF is the sum of its functions values over all vertices. The perfect Italian domination number of $G$, denoted $ \gamma_I^p (G) $, is the minimum weight of a PIDF of $G$. In this paper, we show that for every tree $T$ of order $ n \ge 3 $, with $ \mathcal{l} (T) $ leaves and $s(T)$ support vertices, \( \gamma_I^p (T) \ge \tfrac {4n- \mathscr{l}(T) + 2s (T) - 1}{5} \), improving a previous bound given by T.W. Haynes and M.A. Henning in [Perfect Italian domination in trees, Discrete Appl. Math. 260 (2019) 164–177].
Źródło:
Discussiones Mathematicae Graph Theory; 2022, 42, 3; 1005-1022
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
On (k,l)-kernel perfectness of special classes of digraphs
Autorzy:
Kucharska, Magdalena
Powiązania:
https://bibliotekanauki.pl/articles/744319.pdf
Data publikacji:
2005
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
kernel
(k,l)-kernel
kernel-perfect digraph
Opis:
In the first part of this paper we give necessary and sufficient conditions for some special classes of digraphs to have a (k,l)-kernel. One of them is the duplication of a set of vertices in a digraph. This duplication come into being as the generalization of the duplication of a vertex in a graph (see [4]). Another one is the D-join of a digraph D and a sequence α of nonempty pairwise disjoint digraphs. In the second part we prove theorems, which give necessary and sufficient conditions for special digraphs presented in the first part to be (k,l)-kernel-perfect digraphs. The concept of a (k,l)-kernel-perfect digraph is the generalization of the well-know idea of a kernel perfect digraph, which was considered in [1] and [6].
Źródło:
Discussiones Mathematicae Graph Theory; 2005, 25, 1-2; 103-119
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
Choice-Perfect Graphs
Autorzy:
Tuza, Zsolt
Powiązania:
https://bibliotekanauki.pl/articles/30146654.pdf
Data publikacji:
2013-03-01
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
graph coloring
list coloring
choice-perfect graph
Opis:
Given a graph $ G = (V,E) $ and a set $ L_v $ of admissible colors for each vertex $ v \in V $ (termed the list at $v$), a list coloring of $G$ is a (proper) vertex coloring $ \phi : V \rightarrow \bigcup \text{}_{v \in V} L_v $ such that $ \phi (v) \in L_v $ for all $ v \in V $ and $ \phi(u) \ne \phi(v) $ for all $ uv \in E $. If such a $ \phi $ exists, $G$ is said to be list colorable. The choice number of $G$ is the smallest natural number $k$ for which $G$ is list colorable whenever each list contains at least $k$ colors. In this note we initiate the study of graphs in which the choice number equals the clique number or the chromatic number in every induced subgraph. We call them choice-ω-perfect and choice-χ-perfect graphs, respectively. The main result of the paper states that the square of every cycle is choice-χ-perfect.
Źródło:
Discussiones Mathematicae Graph Theory; 2013, 33, 1; 231-242
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Wyświetlanie 1-15 z 31

Ta witryna wykorzystuje pliki cookies do przechowywania informacji na Twoim komputerze. Pliki cookies stosujemy w celu świadczenia usług na najwyższym poziomie, w tym w sposób dostosowany do indywidualnych potrzeb. Korzystanie z witryny bez zmiany ustawień dotyczących cookies oznacza, że będą one zamieszczane w Twoim komputerze. W każdym momencie możesz dokonać zmiany ustawień dotyczących cookies