关于k—消去图的若干新结果

设G是一个图．k是自然数．图G的一个k-正则支撑子图称为G的一个k-因子．若对于G的每条边e．G—e都存在一个k-因子，则称G是一个k-消去图．该文得到了一个图是k-消去图的若干充分条件，推广了文［2—4］中有关结论．     

我所了解的图论(三)

第三讲图中之图这一讲准备进一步谈谈图的支撑子图.第一讲中我们提到了支撑树,第二讲中讲了支撑圈,现在我们所关心的是满足某种次(Yalency)条件的支撑子图.图G的一个子图被称为G的一个k-因子,如果它是k-价     

图中相互独立的4圈和含4个点的路

设k是一个正整数，G是一个顶点数为|G|=4k的图. 假设σ\-2(G)≥4k-1, 则G有一个支撑子图含k-1个4圈和一条顶点数为4的路，使得所有这些圈和路都是相互独立的. 设G=(V\-1,V \-2;E)是一个二分图使得|V\-1|=|V\-2|=2k. 如果对G中每一对满足x∈V\-1和y∈V\-2的不 相邻的顶点x和y 都有d(x)+d(y)≥2k+1, 则G包含k-1个相互独立的4圈和一条顶点数为4的路，使得所有这些圈和路都是相互独立的，并且此度条件是最好的.     

图的划分:一些进展与未解决问题(英文)

图的划分问题是图论研究中最重要的一个问题之一,图论研究的很多问题都是特殊形式的划分问题,比如经典染色理论要求将图划分成最少的独立集,而最大尼-部子图问题则是要找图中边数最多的一个k-部子图.本文给出划分问题的一些最新进展,以及一些尚未解决的问题,其中大部分是来自于求最大k-部子图的相关领域.     

关于k-消去二分图的一些结果

图 G的一个 k-正则支撑子图称为 G的 k-因子 ,若对 G的任一边 e,图 G- e总存在一个 k-因子 ,则称 G是 k-消去图 .证明了二分图 G=( X,Y) ,且 | X | =| Y|是 k-消去图的充分必要条件是 k| S|≤ r1 + 2 r2 +…+ k( rk+… + rΔ) - ε( S)对所有 S X成立 .并由此给出二分图是 k-消去图的充分度条件 .     

含有多个圈的图的秩

研究了含有多个圈的图的邻接矩阵的秩.将k(k≥2)条点不交的路,首和尾分别粘合得到的图称为Θ-图.用Γ(k-1)表示含有Θ-图作为导出子图的(k-1)-圈图的集合,而用C(η,k)表示含有n个顶点和k个边不交的圈的图的集合.确定了Γ(k-1)中秩等于5和6的图以及C(n,k)中秩等于4,5和6的图.     

Halin图的Alon-Tarsi数

图G的Alon-Tarsi数,是指最小的k使得G存在一个最大出度不大于k-1的定向D满足G的奇支撑欧拉子图的个数不同于偶支撑欧拉子图的个数.通过分析Halin图的结构,利用Alon-Tarsi定向的方法确定了Halin图的Alon-Tarsi数.     

蕴含三类导出子图的可图序列

对非负整数序列π=（d1,d2……,dn),0≤di≤n-1,本分别给出了它蕴含导出子图为几乎处处完全图,完全图去掉一个Hamilton圈的边,完全k-部图可图（即蕴含aw^1,Aw^2和Ar,r2…,rk-可图）的判别准则。     

3-连通3-正则图中的可序子集

图G的k元点集X={x1,x2,…,xk}被称为G的k-可序子集,如果X的任意排列都按序排在G的某个圈上.称G是k-可序图,如果G的每一个k元子集都是G的k-可序子集.称G为k-可序Hamilton图,如果X的任意排列都位于G的Hamilton圈上.研究了3-连通3-正则图的可序子集的存在性问题.     

没有K4-图子式的图的无圈边色数

一个图G 的无圈k- 边染色是指G 的一个正常的不产生双色圈的k- 边染色. G 的无圈边色数a′(G) 定义为使得G 有一个无圈k- 边染色的最小的整数k. 本文完全刻画了最大度不为4 的没有K₄-图子式的图的无圈边色数.     

Solving the generalized minimum spanning tree problem by a branch-and-bound algorithm

We present an exact algorithm for solving the generalized minimum spanning tree problem (GMST). Given an undirected connected graph and a partition of the graph vertices, this problem requires finding a least-cost subgraph spanning at least one vertex out of every subset. In this paper, the GMST is formulated as a minimum spanning tree problem with side constraints and solved exactly by a branch-and-bound algorithm. Lower bounds are derived by relaxing, in a Lagrangian fashion, complicating constraints to yield a modified minimum cost spanning tree problem. An efficient preprocessing algorithm is implemented to reduce the size of the problem. Computational tests on a large set of randomly generated instances with as many as 250 vertices, 1000 edges, and 25 subsets provide evidence that the proposed solution approach is very effective.     

Even subgraphs of bridgeless graphs and 2-factors of line graphs

By Petersen's theorem, a bridgeless cubic multigraph has a 2-factor. Fleischner generalised this result to bridgeless multigraphs of minimum degree at least three by showing that every such multigraph has a spanning even subgraph. Our main result is that every bridgeless simple graph with minimum degree at least three has a spanning even subgraph in which every component has at least four vertices. We deduce that if G is a simple bridgeless graph with n vertices and minimum degree at least three, then its line graph has a 2-factor with at most max{1,(3n-4)/10} components. This upper bound is best possible.     

Star partitions on graphs

Given an undirected graph, a star partition is a partition of the nodes into subsets with at least two nodes so that the subgraph induced by each subset has a spanning star. Star partitions are related to well-known problems concerning domination in graphs and edge covering. We focus on the Constrained Star Partition Problem (CSP) that asks for finding a star partition of given cardinality. The problem is new and presents interesting peculiarities. We explore the relation between the cardinalities of star partitions and domatic bipartitions, showing that there are star partitions of any cardinality between minimum and maximum values, and that a similar but weaker result holds for domatic bipartitions. We study the computational complexity of different versions of star partition and domatic bipartition problems, proving that most of them, in particular CSP, constrained domatic bipartition and balanced domatic bipartition, are NP-complete. We also show that star partition problems are polynomial on trees and, more generally, on bounded treewidth graphs. We introduce an integer linear programming formulation that defines a polytope containing all the star partitions of a graph, showing that its vertices have only integral components for trees, which implies that linear programming can be used to solve weighted star partition problems on trees.     

Spanning even subgraphs of 3‐edge‐connected graphs

By Petersen's theorem, a bridgeless cubic graph has a 2‐factor. H. Fleischner extended this result to bridgeless graphs of minimum degree at least three by showing that every such graph has a spanning even subgraph. Our main result is that, under the stronger hypothesis of 3‐edge‐connectivity, we can find a spanning even subgraph in which every component has at least five vertices. We show that this is in some sense best possible by constructing an infinite family of 3‐edge‐connected graphs in which every spanning even subgraph has a 5‐cycle as a component. © 2009 Wiley Periodicals, Inc. J Graph Theory 62: 37–47, 2009     

最小最大树划分的近似算法与最小和树划分的精确算法

本文研究把连通赋权图的点集划分成p个子集,要求每个点子集的导出子图都连通,并且使得所得到的p个子图的最小支撑树中权重最大者的权重达到最小(最小最大树划分问题),或者使得所得到的p个子图的最小支撑树权重之和达到最小(最小和树划分问题)．文中给出了最小最大树划分问题的强NP困难性证明,并给出了一个多项式时间算法,该算法是最小最大树划分问题的竞争比为p的近似算法,同时是最小和树划分问题的精确算法．     

On 3-Edge-Connected Supereulerian Graphs

The supereulerian graph problem, raised by Boesch et al. (J Graph Theory 1:79–84, 1977), asks when a graph has a spanning eulerian subgraph. Pulleyblank showed that such a decision problem, even when restricted to planar graphs, is NP-complete. Jaeger and Catlin independently showed that every 4-edge-connected graph has a spanning eulerian subgraph. In 1992, Zhan showed that every 3-edge-connected, essentially 7-edge-connected graph has a spanning eulerian subgraph. It was conjectured in 1995 that every 3-edge-connected, essentially 5-edge-connected graph has a spanning eulerian subgraph. In this paper, we show that if G is a 3-edge-connected, essentially 4-edge-connected graph and if for every pair of adjacent vertices u and v, d _G (u) + d _G (v) ≥ 9, then G has a spanning eulerian subgraph.     

Parity and disparity subgraphs

A parity subgraph of a graph is a spanning subgraph such that the degrees of each vertex have the same parity in both the subgraph and the original graph. Known results include that every graph has an odd number of minimal parity subgraphs. Define a disparity subgraph to be a spanning subgraph such that each vertex has degrees of opposite parities in the subgraph and the original graph. (Only graphs with all even-order components can have disparity subgraphs). Every even-order spanning tree contains both a unique parity subgraph and a unique disparity subgraph. Moreover, every minimal disparity subgraph is shown to be paired by sharing a spanning tree with an odd number of minimal parity subgraphs, and every minimal parity subgraph is similarly paired with either one or an even number of minimal disparity subgraphs.     

Conditions for graphs to be path partition optimal

The path partition number of a graph is the minimum number of edges we have to add to turn it into a Hamiltonian graph, and the separable degree is the minimum number of edges we have to add to turn it into a 2-connected graph. A graph is called path partition optimal if its path partition number is equal to its separable degree. We study conditions that guarantee path partition optimality. We extend several known results on Hamiltonicity to path partition optimality, in particular results involving degree conditions and induced subgraph conditions.     

Two-edge connected spanning subgraphs and polyhedra

This paper studies the problem of finding a two-edge connected spanning subgraph of minimum weight. This problem is closely related to the widely studied traveling salesman problem and has applications to the design of reliable communication and transportation networks. We discuss the polytope associated with the solutions to this problem. We show that when the graph is series-parallel, the polytope is completely described by the trivial constraints and the so-called cut constraints. We also give some classes of facet defining inequalities of this polytope when the graph is general.Research supported in part by the Natural Sciences and Engineering Research Council of Canada and CP Rail and the German Research Association (Deutsche Forschungsgemeinschaft SFR 303).     

ON THE MINIMUM FEASIBLE GRAPH FOR FOUR SETS

ＯＮＴＨＥＭＩＮＩＭＵＭＦＥＡＳＩＢＬＥＧＲＡＰＨＦＯＲＦＯＵＲＳＥＴＳＸＵＹＩＮＦＥＮＧＡＮＤＦＵＸＩＡＯＢＩＮＧＡｂｓｔｒａｃｔ：ＧｉｖｅｎａｃｏｍｐｌｅｔｅｇｒａｐｈｗｉｔｈｖｅｒｔｅｘｓｅｔＸａｎｄｓｕｂｓｅｔｓＸ＿１，Ｘ＿２，．．．，Ｘ＿ｎ...