Displaying similar documents to “Partition problems and kernels of graphs”

Constant Sum Partition of Sets of Integers and Distance Magic Graphs

Sylwia Cichacz, Agnieszka Gőrlich (2018)

Discussiones Mathematicae Graph Theory

Similarity:

Let A = {1, 2, . . . , tm+tn}. We shall say that A has the (m, n, t)-balanced constant-sum-partition property ((m, n, t)-BCSP-property) if there exists a partition of A into 2t pairwise disjoint subsets A1, A2, . . . , At, B1, B2, . . . , Bt such that |Ai| = m and |Bi| = n, and ∑a∈Ai a = ∑b∈Bj b for 1 ≤ i ≤ t and 1 ≤ j ≤ t. In this paper we give sufficient and necessary conditions for a set A to have the (m, n, t)-BCSP-property in the case when m and n are both even. We use this result...

Some additions to the theory of star partitions of graphs

Francis K. Bell, Dragos Cvetković, Peter Rowlinson, Slobodan K. Simić (1999)

Discussiones Mathematicae Graph Theory

Similarity:

This paper contains a number of results in the theory of star partitions of graphs. We illustrate a variety of situations which can arise when the Reconstruction Theorem for graphs is used, considering in particular galaxy graphs - these are graphs in which every star set is independent. We discuss a recursive ordering of graphs based on the Reconstruction Theorem, and point out the significance of galaxy graphs in this connection.

A path(ological) partition problem

Izak Broere, Michael Dorfling, Jean E. Dunbar, Marietjie Frick (1998)

Discussiones Mathematicae Graph Theory

Similarity:

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.