Search

For a given graph G , a nonempty subset S contained in V ( G ) is an alliance iff for each vertex v ? S there are at least as many vertices from the closed neighbourhood of v in S as in V ( G ) - S . An alliance is global if it is also a dominating set of G . The alliance partition number of G was defined in Hedetniemi et?al. (2004) to be the maximum number of sets in a partition of V ( G ) such that each set is an alliance. Similarly, in Eroh and Gera (2008) the global alliance partition number is defined for global alliances, where the authors studied the problem for (binary) trees.In the paper we introduce a new concept of strategic balance in graphs: for a given graph G , determine whether there is a partition of vertex set V ( G ) into three subsets N , S and I such that both N and S are global alliances. We give a survey of its general properties, e.g.,?showing that a graph G has a strategic balance iff its global alliance partition number equals at least 2. We construct a linear time algorithm for solving the problem in trees (thus giving an answer to the open question stated in Eroh and Gera (2008)) and studied this problem for many classes of graphs: paths, cycles, wheels, stars, complete graphs and complete k -partite graphs. Moreover, we prove that this problem is NP -complete for graphs with a degree bounded by 4 and state an open question regarding subcubic graphs.

The theory of sortability of a partition property was introduced to prove the existence of an optimal partition satisfying the property for optimal partition problems over single-parameter space, and then extended to multi-dimensional parameter spaces. For each partition property of interest, almost all levels of sortabilities have been obtained; however, the part-specific-sortabilities are hard to be determined for many properties. In this paper, we establish a rule to generate examples that reveal the non-part-specific-sortabilities of these properties for almost all cases. Such a rule also has potential of generating more concise examples to support known results.

The list monopolar partition problem asks whether a graph G together with lists L ( v ) ⊆ { 0 , 1 } , v ∈ V ( G ) admits a mapping f : V ( G ) → { 0 , 1 } such that f ( v ) ∈ L ( v ) for each v ∈ V ( G ) , f − 1 ( 0 ) induces an independent set and f − 1 ( 1 ) induces a disjoint union of cliques in G . This problem is NP-complete in general. We show that the problem is solvable in time O ( n 2 m ) for claw-free graphs where n and m are the numbers of vertices and edges respectively in the input graph.

International audience; Given an undirected graph G, a uniform cut polytope is defined as the convex hull of the incidence vectors of the cuts in G for which the size of the shores are fixed. In this paper we show that simple extensions of facet-defining inequalities for the equipartition polytope introduced by Conforti et al. in [5] and [6] provide facet-defining inequalities for uniform cut polyhedra.

We consider the problem of clustering a set of items into subsets whose sizes are bounded from above and below. We formulate the problem as a graph partitioning problem and propose an integer programming model for solving it. This formulation generalizes several well-known graph partitioning problems from the literature like the clique partitioning problem, the equi-partition problem and the k-way equi-partition problem. In this paper, we analyze the structure of the corresponding polytope and prove several results concerning the facial structure. Our analysis yields important results for the closely related equi-partition and k-way equi-partition polytopes as well. (C) 2010 Elsevier B.V. All rights reserved.

A linear forest is a graph that connected components are chordless paths. A linear partition of a graph G is a partition of its edge set into linear forests and la(G) is the minimum number of linear forests in a linear partition. It is well known that l a ( G ) = 2 when G is a cubic graph and Wormald [Wormald, N., Problem 13, Ars Combinatoria 23 (1987), pp. 332–334] conjectured that if | V ( G ) | ≡ 0 ( mod 4 ) , then it is always possible to find a linear partition in two isomorphic linear forests. We give here some new results concerning this conjecture.

We describe how eight copies of the Best code can be imbedded in the binary Hamming graph of length 10 in such a way that they form part of a partition design π1. We study those isometries of the binary Hamming graph which stabilize π1. A partition design π2, coarser than π1, will be the subject of the second part of this work. Let M be the adjacency matrix of π2. We will show that M is extreme in some sense. Namely, π2 has the following interesting property: π2 is the unique partition design with adjacency matrix M.

This article surveys recent results on the degree conditions that guarantee the existence of a 2-factor with a specified number of components satisfying some additional properties. Related topics such as packing problem and partition into paths are also discussed.

It is known that the edge set of a connected graph of even size has a partition into pairs of incident edges. Based on a matching theorem of D.P. Summer we extend this result to uniform hypergraphs. The obtained partition results are tight; our hypergraph constructions also show that D.P. Sumner's matching theorem cannot be strengthened.

A partition graph is an intersection graph for a collection of subsets of auniversal set S with the property that every maximal independent set of vertices corresponds to a partition of S . Two questions which arose in the study of partition graphs are answered by recently discovered examples. An enumeration of the partition graphs on ten or fewer vertices is provided.

A continuous version of the following problem is solved: Let G be a multipartite graph with a given partition of its vertex set, A 1 ∪ A 2 ∪…∪ A N . Find the maximum possible number of edges in G such that G has no connected component with more than t vertices.

We prove the following theorem.

Let G be an infinite graph; define deg∞ G to be the least m such that any partition P of the vertex set of G into sets of uniformly bounded cardinality contains a set which is adjacent to at least m other sets of the partition. If G is either a regular tree on a triangular, square or hexagonal planar mosaic graph, it is shown that deg∞ G equals the degree of G . This verifies some conjectures of S . Ulam. Several open problems are given.

International audience; Adapting the method introduced in Graph Minors X, we propose a new proof of the duality between the bramble number of a graph and its tree-width. Our approach is based on a new definition of submodularity on partition functions which naturally extends the usual one on set functions. The proof does not rely on Menger's theorem, and thus generalises the original one. It thus provides a dual for matroid tree-width. One can also derive all known dual notions of other classical width-parameters from it.

A general partition graph is an intersection graph G on a set S so that for every maximal independent set M of vertices in G , the subsets assigned to the vertices in M partition S . It is shown that such graphs are characterized by there existing a clique cover of G so that every maximal independent set has a vertex from each clique in the cover. A process is described showing how to construct a partition graph with certain prescribed graph theoretic invariants starting with an arbitrary graph with similar invariants. Hereditary properties for various graph products are examined. It is also shown that partition graphs are preserved by removal of any vertex whose closed neighborhood properly contains the closed neighborhood of some other vertex.