期刊文献+
共找到6篇文章
< 1 >
每页显示 20 50 100
COMPLETE MULTIPARTITE DECOMPOSITIONS OF COMPLETE GRAPHS AND COMPLETE n-PARTITE GRAPHS
1
作者 Huang QingxueDept. of Math., Zhejiang Univ., Hangzhou 310027, China. 《Applied Mathematics(A Journal of Chinese Universities)》 SCIE CSCD 2003年第3期352-360,共9页
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. 展开更多
关键词 complete n-partite graph decomposition of graph complete multipartite decomposition
下载PDF
4-Cycle Decompositions of Graphs
2
作者 Teresa Sousa 《Open Journal of Discrete Mathematics》 2012年第4期125-130,共6页
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. 展开更多
关键词 graph Decomposition 4-Cycle Packing graph Packing
下载PDF
The <i>H</i>-Decomposition Problem for Graphs
3
作者 Teresa Sousa 《Applied Mathematics》 2012年第11期1719-1722,共4页
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. 展开更多
关键词 graph decompositions Weighted graph decompositions Monochromatic graph decompositions Turán graph Ramsey Numbers
下载PDF
A Decomposition of a Complete Graph with a Hole
4
作者 Roxanne Back Alejandra Brewer Castano +1 位作者 Rachel Galindo Jessica Finocchiaro 《Open Journal of Discrete Mathematics》 2021年第1期1-12,共12页
<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> 展开更多
关键词 graph Decomposition Combinatorial Design Complete graph with a Hole
下载PDF
Solving the Maximum Matching Problem on Bipartite Star123-Free Graphs in Linear Time
5
作者 Ruzayn Quaddoura 《Open Journal of Discrete Mathematics》 2016年第1期13-24,共12页
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. 展开更多
关键词 Bipartite graphs Decomposition of graphs Design and Analysis of Algorithms MATCHING
下载PDF
Adaptive genetic algorithms guided by decomposition for PCSPs: application to frequency assignment problems
6
作者 Lamia SADEG-BELKACEM Zineb HABBAS Wassila AGGOUNE-MTALAA 《Frontiers of Computer Science》 SCIE EI CSCD 2016年第6期1012-1025,共14页
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. 展开更多
关键词 optimization problems partial constraint satisfaction problems frequency assignment problems graph decomposition adaptive genetic algorithm (AGA) AGA guided by decomposition (AGAGD).
原文传递
上一页 1 下一页 到第
使用帮助 返回顶部