Wyniki wyszukiwania

1

Artykuł dostępny w postaci pełnego tekstu - kliknij by otworzyć plik

A path(ological) partition problem

100%

Broere I., Dorfling M., Dunbar J., Frick M.

Discussiones Mathematicae Graph Theory

|

1998

|

tom 18

|

nr 1

113-125

EN

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.

2

On the factorization of reducible properties of graphs into irreducible factors

100%

Mihók P., Vasky R.

Discussiones Mathematicae Graph Theory

|

1995

|

tom 15

|

nr 2

195-203

EN

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.

3

Maximal graphs with respect to hereditary properties

100%

Broere I., Frick M., Semanišin G.

Discussiones Mathematicae Graph Theory

|

1997

|

tom 17

|

nr 1

51-66

EN

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.

4

Domination in partitioned graphs

100%

Tuza Z., Vestergaard P.

Discussiones Mathematicae Graph Theory

|

2002

|

tom 22

|

nr 1

199-210

EN

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δ)/(δ).

5

On Graphs with Disjoint Dominating and 2-Dominating Sets

100%

Henning M. A., Rall D. F.

Discussiones Mathematicae Graph Theory

|

2013

|

tom 33

|

nr 1

139-146

EN

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.

6

Uniquely partitionable graphs

100%

Bucko J., Frick M., Mihók P., Vasky R.

Discussiones Mathematicae Graph Theory

|

1997

|

tom 17

|

nr 1

103-113

EN

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.

7

A survey of hereditary properties of graphs

88%

Borowiecki M., Broere I., Frick M., Mihók P., Semanišin G.

Discussiones Mathematicae Graph Theory

|

1997

|

tom 17

|

nr 1

5-50

EN

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.

8

Remarks on the existence of uniquely partitionable planar graphs

88%

Borowiecki M., Mihók P., Tuza Z., Voigt M.

Discussiones Mathematicae Graph Theory

|

1999

|

tom 19

|

nr 2

159-166

EN

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".

9

The directed path partition conjecture

88%

Frick M., van Aardt S., Dlamini G., Dunbar J., Oellermann O.

Discussiones Mathematicae Graph Theory

|

2005

|

tom 25

|

nr 3

331-343

EN

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.

10

Partitioning a graph into a dominating set, a total dominating set, and something else

88%

Henning M., Löwenstein C., Rautenbach D.

Discussiones Mathematicae Graph Theory

|

2010

|

tom 30

|

nr 4

563-574

EN

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.

11

Detour chromatic numbers

75%

Frick M., Bullock F.

Discussiones Mathematicae Graph Theory

|

2001

|

tom 21

|

nr 2

283-291

EN

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.

Ograniczanie wyników

A path(ological) partition problem

On the factorization of reducible properties of graphs into irreducible factors

Maximal graphs with respect to hereditary properties

Domination in partitioned graphs

On Graphs with Disjoint Dominating and 2-Dominating Sets

Uniquely partitionable graphs

A survey of hereditary properties of graphs

Remarks on the existence of uniquely partitionable planar graphs

The directed path partition conjecture

Partitioning a graph into a dominating set, a total dominating set, and something else

Detour chromatic numbers