首页 | 本学科首页   官方微博 | 高级检索  
相似文献
 共查询到10条相似文献,搜索用时 46 毫秒
1.
2.
3.
4.
We construct highly edge-connected r-regular graphs of even order which do not contain r ? 2 pairwise disjoint perfect matchings. When r is a multiple of 4, the result solves a problem of Thomassen [4].  相似文献   

5.
A nonempty set C of vertices is a star-cutset in a graph G if GC is disconnected and some vertex in C is adjacent to all the remaining vertices in C. Va?ek Chvátal proposed to call a graph G unbreakable if neither G nor its complement G has a star-cutset. A path with four vertices and three edges will be termed a P4. An edge uv of a graph G is called a wing, if for some vertices x, y, {u,v,x,y} induces a P4 in G. We define recursively the coercion class Cuv of a wing uv as follows:
  • 1 uvCuv, and
  • 1 if xyCuv and xy, x'y' are wings of a same P4 in G, then x'y'Cuv.
The purpose of this work is to present new results concerning unbreakable graphs, using the notion of coercion class. These results include a theorem asserting that every unbreakable graph contains at most two distinct coercion classes and a structure theorem for those unbreakable graphs that contain precisely two coercion classes. These results generalize several previously known results about unbreakable graphs.  相似文献   

6.
Denote byG(n; m) a graph ofn vertices andm edges. We prove that everyG(n; [n 2/4]+1) contains a circuit ofl edges for every 3 ≦l<c 2 n, also that everyG(n; [n 2/4]+1) contains ak e(u n, un) withu n=[c 1 logn] (for the definition ofk e(u n, un) see the introduction). Finally fort>t 0 everyG(n; [tn 3/2]) contains a circuit of 2l edges for 2≦l<c 3 t 2. This work was done while the author received support from the National Science Foundation, N.S.F. G.88.  相似文献   

7.
8.
A bull is a graph obtained by adding a pendant vertex at two vertices of a triangle. Chvátal and Sbihi showed that the Strong Perfect Graph Conjecture holds for bull-free graphs. We show that bull-free perfect graphs are quasi-parity graphs, and that bull-free perfect graphs with no antihole are perfectly contractile. Our proof yields a polynomial algorithm for coloring bull-free strict quasi-parity graphsPartially supported by CNPq, grant 30 1160/91.0  相似文献   

9.
Let S m 0 be the set of all irreducible permutations of the numbers {1, ??,m} (m ?? 3). We define Rauzy induction mappings a and b acting on the set S m 0 . For a permutation ?? ?? S m 0 , denote by R(??) the orbit of the permutation ?? under the mappings a and b. This orbit can be endowed with the structure of an oriented graph according to the action of the mappings a and b on this set: the edges of this graph belong to one of the two types, a or b. We say that the graph R(??) is a tree composed of cycles if any simple cycle in this graph consists of edges of the same type. An equivalent formulation of this condition is as follows: a dual graph R*(??) of R(??) is a tree. The main result of the paper is as follows: if the graph R(??) of a permutation ?? ?? S m 0 is a tree composed of cycles, then the set R(??) contains a permutation ?? 0: i ? m + 1 ? i, i = 1, ??,m. The converse result is also proved: the graph R(?? 0) is a tree composed of cycles; in this case, the structure of the graph is explicitly described.  相似文献   

10.
A characterization of all vertex-transitive graphs Γ of connectivity l is given in terms of the lobe structure of Γ. Among these, all graphs are determined whose automorphism groups act primitively (respectively, regularly) on the vertex set.  相似文献   

设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号