The concept of H-decompositions of graphs was first introduced by Erd?s, Goodman and Pósa in 1966, who were motivated by the problem of representing graphs by set intersections. Given graphs G and H, an H-decompo...The concept of H-decompositions of graphs was first introduced by Erd?s, Goodman and Pósa in 1966, who were motivated by the problem of representing graphs by set intersections. Given graphs G and H, an H-decomposition of G is a partition of the edge set of G such that each part is either a single edge or forms a graph isomorphic to H. Let Ф(n,H) be the smallest number Ф, such that, any graph of order n admits an H-decomposition with at most Ф parts. The exact computation of Ф(n,H) for an arbitrary H is still an open problem. Recently, a few papers have been published about this problem. In this survey we will bring together all the results about H-decompositions. We will also introduce two new related problems, namely Weighted H-Decompositions of graphs and Monochromatic H-Decom- positions of graphs.展开更多
<div style="text-align:justify;"> <span style="font-family:Verdana;">In the field of design theory, the most well-known design is a Steiner Triple System. In general, a G-design on H is...<div style="text-align:justify;"> <span style="font-family:Verdana;">In the field of design theory, the most well-known design is a Steiner Triple System. In general, a G-design on H is an edge-disjoint decomposition of H into isomorphic copies of G. In a Steiner Triple system, a complete graph is decomposed into triangles. In this paper we let H be a complete graph with a hole and G be a complete graph on four vertices minus one edge, also referred to as a <img alt="" src="Edit_e69ee166-4bbc-48f5-8ba1-b446e7d3738c.png" /> . A complete graph with a hole, <img alt="" src="Edit_558c249b-55e8-4f3b-a043-e36d001c4250.png" />, consists of a complete graph on <em>d</em> vertices, <img alt="" src="Edit_cb1772f7-837c-4aea-b4a6-cb38565f5a8b.png" />, and a set of independent vertices of size<em> v, V,</em> where each vertex in <em>V</em> is adjacent to each vertex in <img alt="" src="Edit_cb1772f7-837c-4aea-b4a6-cb38565f5a8b.png" />. When <em>d</em> is even, we give two constructions for the decomposition of a complete graph with a hole into copies of <img alt="" src="Edit_e69ee166-4bbc-48f5-8ba1-b446e7d3738c.png" /> : the Alpha-Delta Construction, and the Alpha-Beta-Delta Construction. By restricting <em>d</em> and <em>v</em> so that <img alt="" src="Edit_6bb9e3b4-1769-4b28-bf89-bc97c47c637e.png" /><span style="white-space:nowrap;"> </span>, we are able to resolve both of these cases for a subset of <img alt="" src="Edit_558c249b-55e8-4f3b-a043-e36d001c4250.png" />using difference methods and 1-factors.</span> </div>展开更多
In this paper we consider the problem of finding the smallest number such that any graph G of order n admits a decomposition into edge disjoint copies of C4 and single edges with at most elements. We solve this proble...In this paper we consider the problem of finding the smallest number such that any graph G of order n admits a decomposition into edge disjoint copies of C4 and single edges with at most elements. We solve this problem for n sufficiently large.展开更多
In this paper,a new concept of an optimal complete multipartite decomposition of type 1 (type 2) of a complete n-partite graph Q n is proposed and another new concept of a normal complete multipartite decomposition o...In this paper,a new concept of an optimal complete multipartite decomposition of type 1 (type 2) of a complete n-partite graph Q n is proposed and another new concept of a normal complete multipartite decomposition of K n is introduced.It is showed that an optimal complete multipartite decomposition of type 1 of K n is a normal complete multipartite decomposition.As for any complete multipartite decomposition of K n,there is a derived complete multipartite decomposition for Q n.It is also showed that any optimal complete multipartite decomposition of type 1 of Q n is a derived decomposition of an optimal complete multipartite decomposition of type 1 of K n.Besides,some structural properties of an optimal complete multipartite decomposition of type 1 of K n are given.展开更多
The bipartite Star<sub>123</sub>-free graphs were introduced by V. Lozin in [1] to generalize some already known classes of bipartite graphs. In this paper, we extend to bipartite Star<sub>123</su...The bipartite Star<sub>123</sub>-free graphs were introduced by V. Lozin in [1] to generalize some already known classes of bipartite graphs. In this paper, we extend to bipartite Star<sub>123</sub>-free graphs a linear time algorithm of J. L. Fouquet, V. Giakoumakis and J. M. Vanherpe for finding a maximum matching in bipartite Star<sub>123</sub>, P<sub>7</sub>-free graphs presented in [2]. Our algorithm is a solution of Lozin’s conjecture.展开更多
This paper proposes Adaptive Genetic Algorithms Guided by structural knowledges coming from decomposition methods, for solving PCSPs. The family of algorithms called AGAGD_x_y is designed to be doubly genetic, meaning...This paper proposes Adaptive Genetic Algorithms Guided by structural knowledges coming from decomposition methods, for solving PCSPs. The family of algorithms called AGAGD_x_y is designed to be doubly genetic, meaning that any decomposition method and different heuristics for the genetic operators can be considered. To validate the approach, the decomposition algorithm due to Newman was used and several crossover operators based on structural knowledge such as the cluster, separator and the cut were tested. The experimental results obtained on the most challenging Minimum Interference-FAP problems of CALMA instances are very promising and lead to interesting perspectives to be explored in the future.展开更多
文摘The concept of H-decompositions of graphs was first introduced by Erd?s, Goodman and Pósa in 1966, who were motivated by the problem of representing graphs by set intersections. Given graphs G and H, an H-decomposition of G is a partition of the edge set of G such that each part is either a single edge or forms a graph isomorphic to H. Let Ф(n,H) be the smallest number Ф, such that, any graph of order n admits an H-decomposition with at most Ф parts. The exact computation of Ф(n,H) for an arbitrary H is still an open problem. Recently, a few papers have been published about this problem. In this survey we will bring together all the results about H-decompositions. We will also introduce two new related problems, namely Weighted H-Decompositions of graphs and Monochromatic H-Decom- positions of graphs.
文摘<div style="text-align:justify;"> <span style="font-family:Verdana;">In the field of design theory, the most well-known design is a Steiner Triple System. In general, a G-design on H is an edge-disjoint decomposition of H into isomorphic copies of G. In a Steiner Triple system, a complete graph is decomposed into triangles. In this paper we let H be a complete graph with a hole and G be a complete graph on four vertices minus one edge, also referred to as a <img alt="" src="Edit_e69ee166-4bbc-48f5-8ba1-b446e7d3738c.png" /> . A complete graph with a hole, <img alt="" src="Edit_558c249b-55e8-4f3b-a043-e36d001c4250.png" />, consists of a complete graph on <em>d</em> vertices, <img alt="" src="Edit_cb1772f7-837c-4aea-b4a6-cb38565f5a8b.png" />, and a set of independent vertices of size<em> v, V,</em> where each vertex in <em>V</em> is adjacent to each vertex in <img alt="" src="Edit_cb1772f7-837c-4aea-b4a6-cb38565f5a8b.png" />. When <em>d</em> is even, we give two constructions for the decomposition of a complete graph with a hole into copies of <img alt="" src="Edit_e69ee166-4bbc-48f5-8ba1-b446e7d3738c.png" /> : the Alpha-Delta Construction, and the Alpha-Beta-Delta Construction. By restricting <em>d</em> and <em>v</em> so that <img alt="" src="Edit_6bb9e3b4-1769-4b28-bf89-bc97c47c637e.png" /><span style="white-space:nowrap;"> </span>, we are able to resolve both of these cases for a subset of <img alt="" src="Edit_558c249b-55e8-4f3b-a043-e36d001c4250.png" />using difference methods and 1-factors.</span> </div>
基金support from FCT—Fundacao para a Ciencia e a Tecnologia(Portugal),through Projects PTDC/MAT/113207/2009PEst-OE/MAT/UI0297/2011(CMA).
文摘In this paper we consider the problem of finding the smallest number such that any graph G of order n admits a decomposition into edge disjoint copies of C4 and single edges with at most elements. We solve this problem for n sufficiently large.
基金Supported by the National Natural Science Foundation of China( 1 0 2 71 1 1 0 )
文摘In this paper,a new concept of an optimal complete multipartite decomposition of type 1 (type 2) of a complete n-partite graph Q n is proposed and another new concept of a normal complete multipartite decomposition of K n is introduced.It is showed that an optimal complete multipartite decomposition of type 1 of K n is a normal complete multipartite decomposition.As for any complete multipartite decomposition of K n,there is a derived complete multipartite decomposition for Q n.It is also showed that any optimal complete multipartite decomposition of type 1 of Q n is a derived decomposition of an optimal complete multipartite decomposition of type 1 of K n.Besides,some structural properties of an optimal complete multipartite decomposition of type 1 of K n are given.
文摘The bipartite Star<sub>123</sub>-free graphs were introduced by V. Lozin in [1] to generalize some already known classes of bipartite graphs. In this paper, we extend to bipartite Star<sub>123</sub>-free graphs a linear time algorithm of J. L. Fouquet, V. Giakoumakis and J. M. Vanherpe for finding a maximum matching in bipartite Star<sub>123</sub>, P<sub>7</sub>-free graphs presented in [2]. Our algorithm is a solution of Lozin’s conjecture.
文摘This paper proposes Adaptive Genetic Algorithms Guided by structural knowledges coming from decomposition methods, for solving PCSPs. The family of algorithms called AGAGD_x_y is designed to be doubly genetic, meaning that any decomposition method and different heuristics for the genetic operators can be considered. To validate the approach, the decomposition algorithm due to Newman was used and several crossover operators based on structural knowledge such as the cluster, separator and the cut were tested. The experimental results obtained on the most challenging Minimum Interference-FAP problems of CALMA instances are very promising and lead to interesting perspectives to be explored in the future.
