Temat: vertex partition - Prolib Integro

Skocz do pozycji: 1.

Tytuł:: On Graphs with Disjoint Dominating and 2-Dominating Sets
Autorzy:: Henning, Michael A.
Rall, Douglas F.
Tematy:: domination
2-domination
vertex partition; Pokaż więcej
Wydawca:: Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Powiązania:: https://bibliotekanauki.pl/articles/30146715.pdf Link otwiera się w nowym oknie
Opis:: A DD₂-pair of a graph G is a pair (D,D₂) of disjoint sets of vertices of G such that D is a dominating set and D₂ is a 2-dominating set of G. Although there are infinitely many graphs that do not contain a DD₂-pair, we show that every graph with minimum degree at least two has a DD₂-pair. We provide a constructive characterization of trees that have a DD₂-pair and show that K_3,3 is the only connected graph with minimum degree at least three for which D ∪ D₂ necessarily contains all vertices of the graph.
Dostawca treści:: Biblioteka Nauki

Artykuł

na półce

Skocz do pozycji: 2.

Tytuł:: A path(ological) partition problem
Autorzy:: Broere, Izak
Dorfling, Michael
Dunbar, Jean
Frick, Marietjie
Tematy:: vertex partition
τ-partitionable
decomposable graph; Pokaż więcej
Wydawca:: Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Powiązania:: https://bibliotekanauki.pl/articles/744209.pdf Link otwiera się w nowym oknie
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.
Dostawca treści:: Biblioteka Nauki

Artykuł

na półce

Skocz do pozycji: 3.

Tytuł:: Domination in partitioned graphs
Autorzy:: Tuza, Zsolt
Vestergaard, Preben
Tematy:: graph
dominating set
domination number
vertex partition; Pokaż więcej
Wydawca:: Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Powiązania:: https://bibliotekanauki.pl/articles/743565.pdf Link otwiera się w nowym oknie
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δ)/(δ).
Dostawca treści:: Biblioteka Nauki

Artykuł

na półce

Skocz do pozycji: 4.

Tytuł:: Coalition graphs of paths, cycles, and trees
Autorzy:: Haynes, Teresa W.
Hedetniemi, Jason T.
Hedetniemi, Stephen T.
McRae, Alice A.
Mohan, Raghuveer
Tematy:: vertex partition
dominating set
coalition; Pokaż więcej
Wydawca:: Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Powiązania:: https://bibliotekanauki.pl/articles/59898534.pdf Link otwiera się w nowym oknie
Opis:: A coalition in a graph $G = (V, E)$ consists of two disjoint sets of vertices $V_1$ and $V_2$, neither of which is a dominating set of $G$ but whose union $V_1 \cup V_2$ is a dominating set of $G$. A coalition partition in a graph $G$ of order $n = |V|$ is a vertex partition $\pi = \{V_1, V_2, \ldots , V_k\}$ of $V$ such that every set $V_i$ either is a dominating set consisting of a single vertex of degree $n-1$, or is not a dominating set but forms a coalition with another set $V_j$ which is not a dominating set. Associated with every coalition partition $\pi$ of a graph $G$ is a graph called the coalition graph of $G$ with respect to $\pi$, denoted $CG(G,\pi)$, the vertices of which correspond one-to-one with the sets $V_1, V_2, \ldots, V_k$ of $\pi$ and two vertices are adjacent in $CG(G,\pi)$ if and only if their corresponding sets in $\pi$ form a coalition. In this paper we study coalition graphs, focusing on the coalition graphs of paths, cycles, and trees. We show that there are only finitely many coalition graphs of paths and finitely many coalition graphs of cycles and we identify precisely what they are. On the other hand, we show that there are infinitely many coalition graphs of trees and characterize this family of graphs.
Dostawca treści:: Biblioteka Nauki

Artykuł

na półce

Skocz do pozycji: 5.

Tytuł:: Maximal graphs with respect to hereditary properties
Autorzy:: Broere, Izak
Frick, Marietjie
Semanišin, Gabriel
Tematy:: hereditary property of graphs
maximal graphs
vertex partition; Pokaż więcej
Wydawca:: Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Powiązania:: https://bibliotekanauki.pl/articles/972029.pdf Link otwiera się w nowym oknie
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.
Dostawca treści:: Biblioteka Nauki

Artykuł

na półce

Skocz do pozycji: 6.

Tytuł:: On the factorization of reducible properties of graphs into irreducible factors
Autorzy:: Mihók, P.
Vasky, R.
Tematy:: hereditary property of graphs
additivity
reducibility
vertex partition; Pokaż więcej
Wydawca:: Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Powiązania:: https://bibliotekanauki.pl/articles/972030.pdf Link otwiera się w nowym oknie
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.
Dostawca treści:: Biblioteka Nauki

Artykuł

na półce

Skocz do pozycji: 7.

Tytuł:: Uniquely partitionable graphs
Autorzy:: Bucko, Jozef
Frick, Marietjie
Mihók, Peter
Vasky, Roman
Tematy:: hereditary property of graphs
additivity
reducibility
vertex partition; Pokaż więcej
Wydawca:: Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Powiązania:: https://bibliotekanauki.pl/articles/972032.pdf Link otwiera się w nowym oknie
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.
Dostawca treści:: Biblioteka Nauki

Artykuł

na półce

Skocz do pozycji: 8.

Tytuł:: Partitioning a graph into a dominating set, a total dominating set, and something else
Autorzy:: Henning, Michael
Löwenstein, Christian
Rautenbach, Dieter
Tematy:: domination
total domination
domatic number
vertex partition
Petersen graph; Pokaż więcej
Wydawca:: Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Powiązania:: https://bibliotekanauki.pl/articles/744065.pdf Link otwiera się w nowym oknie
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.
Dostawca treści:: Biblioteka Nauki

Artykuł

na półce

Skocz do pozycji: 9.

Tytuł:: The directed path partition conjecture
Autorzy:: Frick, Marietjie
van Aardt, Susan
Dlamini, Gcina
Dunbar, Jean
Oellermann, Ortrud
Tematy:: longest path
Path Partition Conjecture
vertex partition
digraph
prismatic colouring; Pokaż więcej
Wydawca:: Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Powiązania:: https://bibliotekanauki.pl/articles/744375.pdf Link otwiera się w nowym oknie
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.
Dostawca treści:: Biblioteka Nauki

Artykuł

na półce

Skocz do pozycji: 10.

Tytuł:: On generalized list colourings of graphs
Autorzy:: Borowiecki, Mieczysław
Broere, Izak
Mihók, Peter
Tematy:: hereditary property of graphs
list colouring
vertex partition number; Pokaż więcej
Wydawca:: Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Powiązania:: https://bibliotekanauki.pl/articles/972024.pdf Link otwiera się w nowym oknie
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.
Dostawca treści:: Biblioteka Nauki

Artykuł

na półce

Informacja

Wyszukujesz frazę "vertex partition" wg kryterium: Temat