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ę "vertex partition" wg kryterium: Temat

  Lista filtrów
Wyrównaj
    Wyświetlanie 1-15 z 15
    Tytuł:
    On Graphs with Disjoint Dominating and 2-Dominating Sets
    Autorzy:
    Henning, Michael A.
    Rall, Douglas F.
    Powiązania:
    https://bibliotekanauki.pl/articles/30146715.pdf
    Data publikacji:
    2013-03-01
    Wydawca:
    Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
    Tematy:
    domination
    2-domination
    vertex partition
    Opis:
    A DD2-pair of a graph G is a pair (D,D2) of disjoint sets of vertices of G such that D is a dominating set and D2 is a 2-dominating set of G. Although there are infinitely many graphs that do not contain a DD2-pair, we show that every graph with minimum degree at least two has a DD2-pair. We provide a constructive characterization of trees that have a DD2-pair and show that K3,3 is the only connected graph with minimum degree at least three for which D ∪ D2 necessarily contains all vertices of the graph.
    Źródło:
    Discussiones Mathematicae Graph Theory; 2013, 33, 1; 139-146
    2083-5892
    Pojawia się w:
    Discussiones Mathematicae Graph Theory
    Dostawca treści:
    Biblioteka Nauki
    Artykuł
    Tytuł:
    A path(ological) partition problem
    Autorzy:
    Broere, Izak
    Dorfling, Michael
    Dunbar, Jean
    Frick, Marietjie
    Powiązania:
    https://bibliotekanauki.pl/articles/744209.pdf
    Data publikacji:
    1998
    Wydawca:
    Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
    Tematy:
    vertex partition
    τ-partitionable
    decomposable graph
    Opis:
    Let τ(G) denote the number of vertices in a longest path of the graph G and let k₁ and k₂ be positive integers such that τ(G) = k₁ + k₂. The question at hand is whether the vertex set V(G) can be partitioned into two subsets V₁ and V₂ such that τ(G[V₁] ) ≤ k₁ and τ(G[V₂] ) ≤ k₂. We show that several classes of graphs have this partition property.
    Źródło:
    Discussiones Mathematicae Graph Theory; 1998, 18, 1; 113-125
    2083-5892
    Pojawia się w:
    Discussiones Mathematicae Graph Theory
    Dostawca treści:
    Biblioteka Nauki
    Artykuł
    Tytuł:
    Domination in partitioned graphs
    Autorzy:
    Tuza, Zsolt
    Vestergaard, Preben
    Powiązania:
    https://bibliotekanauki.pl/articles/743565.pdf
    Data publikacji:
    2002
    Wydawca:
    Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
    Tematy:
    graph
    dominating set
    domination number
    vertex partition
    Opis:
    Let V₁, V₂ be a partition of the vertex set in a graph G, and let $γ_i$ denote the least number of vertices needed in G to dominate $V_i$. We prove that γ₁+γ₂ ≤ [4/5]|V(G)| for any graph without isolated vertices or edges, and that equality occurs precisely if G consists of disjoint 5-paths and edges between their centers. We also give upper and lower bounds on γ₁+γ₂ for graphs with minimum valency δ, and conjecture that γ₁+γ₂ ≤ [4/(δ+3)]|V(G)| for δ ≤ 5. As δ gets large, however, the largest possible value of (γ₁+γ₂)/|V(G)| is shown to grow with the order of (logδ)/(δ).
    Źródło:
    Discussiones Mathematicae Graph Theory; 2002, 22, 1; 199-210
    2083-5892
    Pojawia się w:
    Discussiones Mathematicae Graph Theory
    Dostawca treści:
    Biblioteka Nauki
    Artykuł
    Tytuł:
    Maximal graphs with respect to hereditary properties
    Autorzy:
    Broere, Izak
    Frick, Marietjie
    Semanišin, Gabriel
    Powiązania:
    https://bibliotekanauki.pl/articles/972029.pdf
    Data publikacji:
    1997
    Wydawca:
    Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
    Tematy:
    hereditary property of graphs
    maximal graphs
    vertex partition
    Opis:
    A property of graphs is a non-empty set of graphs. A property P is called hereditary if every subgraph of any graph with property P also has property P. Let P₁, ...,Pₙ be properties of graphs. We say that a graph G has property P₁∘...∘Pₙ if the vertex set of G can be partitioned into n sets V₁, ...,Vₙ such that the subgraph of G induced by V_i has property $P_i$; i = 1,..., n. A hereditary property R is said to be reducible if there exist two hereditary properties P₁ and P₂ such that R = P₁∘P₂. If P is a hereditary property, then a graph G is called P- maximal if G has property P but G+e does not have property P for every e ∈ E([G̅]). We present some general results on maximal graphs and also investigate P-maximal graphs for various specific choices of P, including reducible hereditary properties.
    Źródło:
    Discussiones Mathematicae Graph Theory; 1997, 17, 1; 51-66
    2083-5892
    Pojawia się w:
    Discussiones Mathematicae Graph Theory
    Dostawca treści:
    Biblioteka Nauki
    Artykuł
    Tytuł:
    On the factorization of reducible properties of graphs into irreducible factors
    Autorzy:
    Mihók, P.
    Vasky, R.
    Powiązania:
    https://bibliotekanauki.pl/articles/972030.pdf
    Data publikacji:
    1995
    Wydawca:
    Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
    Tematy:
    hereditary property of graphs
    additivity
    reducibility
    vertex partition
    Opis:
    A hereditary property R of graphs is said to be reducible if there exist hereditary properties P₁,P₂ such that G ∈ R if and only if the set of vertices of G can be partitioned into V(G) = V₁∪V₂ so that ⟨V₁⟩ ∈ P₁ and ⟨V₂⟩ ∈ P₂. The problem of the factorization of reducible properties into irreducible factors is investigated.
    Źródło:
    Discussiones Mathematicae Graph Theory; 1995, 15, 2; 195-203
    2083-5892
    Pojawia się w:
    Discussiones Mathematicae Graph Theory
    Dostawca treści:
    Biblioteka Nauki
    Artykuł
    Tytuł:
    Uniquely partitionable graphs
    Autorzy:
    Bucko, Jozef
    Frick, Marietjie
    Mihók, Peter
    Vasky, Roman
    Powiązania:
    https://bibliotekanauki.pl/articles/972032.pdf
    Data publikacji:
    1997
    Wydawca:
    Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
    Tematy:
    hereditary property of graphs
    additivity
    reducibility
    vertex partition
    Opis:
    Let ₁,...,ₙ be properties of graphs. A (₁,...,ₙ)-partition of a graph G is a partition of the vertex set V(G) into subsets V₁, ...,Vₙ such that the subgraph $G[V_i]$ induced by $V_i$ has property $_i$; i = 1,...,n. A graph G is said to be uniquely (₁, ...,ₙ)-partitionable if G has exactly one (₁,...,ₙ)-partition. A property is called hereditary if every subgraph of every graph with property also has property . If every graph that is a disjoint union of two graphs that have property also has property , then we say that is additive. A property is called degenerate if there exists a bipartite graph that does not have property . In this paper, we prove that if ₁,..., ₙ are degenerate, additive, hereditary properties of graphs, then there exists a uniquely (₁,...,ₙ)-partitionable graph.
    Źródło:
    Discussiones Mathematicae Graph Theory; 1997, 17, 1; 103-113
    2083-5892
    Pojawia się w:
    Discussiones Mathematicae Graph Theory
    Dostawca treści:
    Biblioteka Nauki
    Artykuł
    Tytuł:
    The directed path partition conjecture
    Autorzy:
    Frick, Marietjie
    van Aardt, Susan
    Dlamini, Gcina
    Dunbar, Jean
    Oellermann, Ortrud
    Powiązania:
    https://bibliotekanauki.pl/articles/744375.pdf
    Data publikacji:
    2005
    Wydawca:
    Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
    Tematy:
    longest path
    Path Partition Conjecture
    vertex partition
    digraph
    prismatic colouring
    Opis:
    The Directed Path Partition Conjecture is the following: If D is a digraph that contains no path with more than λ vertices then, for every pair (a,b) of positive integers with λ = a+b, there exists a vertex partition (A,B) of D such that no path in D⟨A⟩ has more than a vertices and no path in D⟨B⟩ has more than b vertices. We develop methods for finding the desired partitions for various classes of digraphs.
    Źródło:
    Discussiones Mathematicae Graph Theory; 2005, 25, 3; 331-343
    2083-5892
    Pojawia się w:
    Discussiones Mathematicae Graph Theory
    Dostawca treści:
    Biblioteka Nauki
    Artykuł
    Tytuł:
    On generalized list colourings of graphs
    Autorzy:
    Borowiecki, Mieczysław
    Broere, Izak
    Mihók, Peter
    Powiązania:
    https://bibliotekanauki.pl/articles/972024.pdf
    Data publikacji:
    1997
    Wydawca:
    Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
    Tematy:
    hereditary property of graphs
    list colouring
    vertex partition number
    Opis:
    Vizing [15] and Erdős et al. [8] independently introduce the idea of considering list-colouring and k-choosability. In the both papers the choosability version of Brooks' theorem [4] was proved but the choosability version of Gallai's theorem [9] was proved independently by Thomassen [14] and by Kostochka et al. [11]. In [3] some extensions of these two basic theorems to (,k)-choosability have been proved.
    In this paper we prove some extensions of the well-known bounds for the -chromatic number to the (,k)-choice number and then an extension of Brooks' theorem.
    Źródło:
    Discussiones Mathematicae Graph Theory; 1997, 17, 1; 127-132
    2083-5892
    Pojawia się w:
    Discussiones Mathematicae Graph Theory
    Dostawca treści:
    Biblioteka Nauki
    Artykuł
    Tytuł:
    Generalized list colourings of graphs
    Autorzy:
    Borowiecki, Mieczysław
    Drgas-Burchardt, Ewa
    Mihók, Peter
    Powiązania:
    https://bibliotekanauki.pl/articles/972045.pdf
    Data publikacji:
    1995
    Wydawca:
    Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
    Tematy:
    hereditary property of graphs
    list colouring
    vertex partition number
    Opis:
    We prove: (1) that $ch_P(G) - χ_P(G)$ can be arbitrarily large, where $ch_P(G)$ and $χ_P(G)$ are P-choice and P-chromatic numbers, respectively, (2) the (P,L)-colouring version of Brooks' and Gallai's theorems.
    Źródło:
    Discussiones Mathematicae Graph Theory; 1995, 15, 2; 185-193
    2083-5892
    Pojawia się w:
    Discussiones Mathematicae Graph Theory
    Dostawca treści:
    Biblioteka Nauki
    Artykuł
    Tytuł:
    Partitioning a graph into a dominating set, a total dominating set, and something else
    Autorzy:
    Henning, Michael
    Löwenstein, Christian
    Rautenbach, Dieter
    Powiązania:
    https://bibliotekanauki.pl/articles/744065.pdf
    Data publikacji:
    2010
    Wydawca:
    Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
    Tematy:
    domination
    total domination
    domatic number
    vertex partition
    Petersen graph
    Opis:
    A recent result of Henning and Southey (A note on graphs with disjoint dominating and total dominating set, Ars Comb. 89 (2008), 159-162) implies that every connected graph of minimum degree at least three has a dominating set D and a total dominating set T which are disjoint. We show that the Petersen graph is the only such graph for which D∪T necessarily contains all vertices of the graph.
    Źródło:
    Discussiones Mathematicae Graph Theory; 2010, 30, 4; 563-574
    2083-5892
    Pojawia się w:
    Discussiones Mathematicae Graph Theory
    Dostawca treści:
    Biblioteka Nauki
    Artykuł
    Tytuł:
    Remarks on the existence of uniquely partitionable planar graphs
    Autorzy:
    Borowiecki, Mieczysław
    Mihók, Peter
    Tuza, Zsolt
    Voigt, M.
    Powiązania:
    https://bibliotekanauki.pl/articles/744146.pdf
    Data publikacji:
    1999
    Wydawca:
    Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
    Tematy:
    property of graphs
    additive
    hereditary
    vertex partition
    uniquely partitionable graphs
    Opis:
    We consider the problem of the existence of uniquely partitionable planar graphs. We survey some recent results and we prove the nonexistence of uniquely (₁,₁)-partitionable planar graphs with respect to the property ₁ "to be a forest".
    Źródło:
    Discussiones Mathematicae Graph Theory; 1999, 19, 2; 159-166
    2083-5892
    Pojawia się w:
    Discussiones Mathematicae Graph Theory
    Dostawca treści:
    Biblioteka Nauki
    Artykuł
    Tytuł:
    Generalized Hypergraph Coloring
    Autorzy:
    Schweser, Thomas
    Powiązania:
    https://bibliotekanauki.pl/articles/32083810.pdf
    Data publikacji:
    2021-02-01
    Wydawca:
    Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
    Tematy:
    hypergraph decomposition
    vertex partition
    degeneracy
    coloring of hypergraphs
    hypergraph properties
    Opis:
    A smooth hypergraph property \(\mathcal{P}\) is a class of hypergraphs that is hereditary and non-trivial, i.e., closed under induced subhypergraphs and it contains a non-empty hypergraph but not all hypergraphs. In this paper we examine \(\mathcal{P}\)-colorings of hypergraphs with smooth hypergraph properties \(\mathcal{P}\). A \(\mathcal{P}\)-coloring of a hypergraph $H$ with color set $C$ is a function $\varphi : V(H) → C$ such that \(H\big[\varphi^{−1}(c)\big]\) belongs to \(\mathcal{P}\) for all $c ∈ C$. Let $L : V (H) → 2^C$ be a so called list-assignment of the hypergraph $H$. Then, a (\(\mathcal{P}, L\))-coloring of $H$ is a \(\mathcal{P}\)-coloring $\varphi$ of $H$ such that $\varphi(v) ∈ L(v)$ for all $v ∈ V (H)$. The aim of this paper is a characterization of (\(\mathcal{P}, L\))-critical hypergraphs. Those are hypergraphs $H$ such that $H − v$ is (\(\mathcal{P}, L\))-colorable for all $v ∈ V (H)$ but $H$ itself is not. Our main theorem is a Gallai-type result for critical hypergraphs, which implies a Brooks-type result for (\(\mathcal{P}, L\))-colorable hypergraphs. In the last section, we prove a Gallai-type bound for the degree sum of (\(\mathcal{P}, L\))-critical locally simple hypergraphs.
    Źródło:
    Discussiones Mathematicae Graph Theory; 2021, 41, 1; 103-121
    2083-5892
    Pojawia się w:
    Discussiones Mathematicae Graph Theory
    Dostawca treści:
    Biblioteka Nauki
    Artykuł
    Tytuł:
    A survey of hereditary properties of graphs
    Autorzy:
    Borowiecki, Mieczysław
    Broere, Izak
    Frick, Marietjie
    Mihók, Peter
    Semanišin, Gabriel
    Powiązania:
    https://bibliotekanauki.pl/articles/971986.pdf
    Data publikacji:
    1997
    Wydawca:
    Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
    Tematy:
    hereditary property of graphs
    vertex partition
    reducible property
    graph invariants
    complexity
    Opis:
    In this paper we survey results and open problems on the structure of additive and hereditary properties of graphs. The important role of vertex partition problems, in particular the existence of uniquely partitionable graphs and reducible properties of graphs in this structure is emphasized. Many related topics, including questions on the complexity of related problems, are investigated.
    Źródło:
    Discussiones Mathematicae Graph Theory; 1997, 17, 1; 5-50
    2083-5892
    Pojawia się w:
    Discussiones Mathematicae Graph Theory
    Dostawca treści:
    Biblioteka Nauki
    Artykuł
    Tytuł:
    Detour chromatic numbers
    Autorzy:
    Frick, Marietjie
    Bullock, Frank
    Powiązania:
    https://bibliotekanauki.pl/articles/743511.pdf
    Data publikacji:
    2001
    Wydawca:
    Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
    Tematy:
    detour
    generalised chromatic number
    longest path
    vertex partition
    girth
    circumference
    nearly bipartite
    Opis:
    The nth detour chromatic number, χₙ(G) of a graph G is the minimum number of colours required to colour the vertices of G such that no path with more than n vertices is monocoloured. The number of vertices in a longest path of G is denoted by τ( G). We conjecture that χₙ(G) ≤ ⎡(τ(G))/n⎤ for every graph G and every n ≥ 1 and we prove results that support the conjecture. We also present some sufficient conditions for a graph to have nth chromatic number at most 2.
    Źródło:
    Discussiones Mathematicae Graph Theory; 2001, 21, 2; 283-291
    2083-5892
    Pojawia się w:
    Discussiones Mathematicae Graph Theory
    Dostawca treści:
    Biblioteka Nauki
    Artykuł
    Tytuł:
    Partitions of a graph into cycles containing a specified linear forest
    Autorzy:
    Matsubara, Ryota
    Matsumura, Hajime
    Powiązania:
    https://bibliotekanauki.pl/articles/743517.pdf
    Data publikacji:
    2008
    Wydawca:
    Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
    Tematy:
    partition of a graph
    vertex-disjoint cycle
    2-factor
    linear forest
    Opis:
    In this note, we consider the partition of a graph into cycles containing a specified linear forest. Minimum degree and degree sum conditions are given, which are best possible.
    Źródło:
    Discussiones Mathematicae Graph Theory; 2008, 28, 1; 97-107
    2083-5892
    Pojawia się w:
    Discussiones Mathematicae Graph Theory
    Dostawca treści:
    Biblioteka Nauki
    Artykuł
      Wyświetlanie 1-15 z 15

      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