共查询到20条相似文献，搜索用时 15 毫秒
1.
Sheng Bau 《Quaestiones Mathematicae》2018,41(4):541-548
We show that if G is a 3-connected graph of minimum degree at least 4 and with |V (G)| ≥ 7 then one of the following is true: (1) G has an edge e such that G/e is a 3-connected graph of minimum degree at least 4; (2) G has two edges uv and xy with ux, vy, vx ∈ E(G) such that the graph G/uv/xy obtained by contraction of edges uv and xy in G is a 3-connected graph of minimum degree at least 4; (3) G has a vertex x with N(x) = {x1, x2, x3, x4} and x1x2, x3x4 ∈ E(G) such that the graph (G ? x)/x1x2/x3x4 obtained by contraction of edges x1x2 and x3x4 in G – x is a 3-connected graph of minimum degree at least 4.Each of the three reductions is necessary: there exists an infinite family of 3- connected graphs of minimum degree not less than 4 such that only one of the three reductions may be performed for the members of the family and not the two other reductions. 相似文献
2.
A.V. Kostochka 《Journal of Graph Theory》2014,75(4):377-386
Let denote the graph obtained from the complete graph by deleting the edges of some ‐subgraph. The author proved earlier that for each fixed s and , every graph with chromatic number has a minor. This confirmed a partial case of the corresponding conjecture by Woodall and Seymour. In this paper, we show that the statement holds already for much smaller t, namely, for . 相似文献
3.
4.
黄庆学 《高校应用数学学报(英文版)》2003,18(3)
§ 1 IntroductionLet V(G) and E(G) be the vertex setand the edge setof a graph G,respectively.Fori=1 ,...,p,if V(Gi) V(G) ,E(Gi)∩ E(Gj) = for i≠ j,and∪pi=1 E(Gi) =E(G) ,then wecall{ G1 ,...,GP} a decomposition of G.Let[i,j] be the integer interval including i and j.Let Knbe a complete graph with the vertex set[1 ,n] .For m disjointsubsets A1 ,...Amof[1 ,n] ,let K(A1 ,...,Am) be a complete m-partite graph having partite-sets A1 ,...,Am.If| Ai| =1 ,Ai is called a S-set;otherwi… 相似文献
5.
Emre Kolotoğlu 《组合设计杂志》2013,21(11):524-530
A decomposition of a complete graph into disjoint copies of a complete bipartite graph is called a ‐design of order n. The existence problem of ‐designs has been completely solved for the graphs for , for , K2, 3 and K3, 3. In this paper, I prove that for all , if there exists a ‐design of order N, then there exists a ‐design of order n for all (mod ) and . Giving necessary direct constructions, I provide an almost complete solution for the existence problem for complete bipartite graphs with fewer than 18 edges, leaving five orders in total unsolved. 相似文献
6.
《Quaestiones Mathematicae》2013,36(1-2):259-274
Abstract This paper brings together the theory of observational cosmology and the null-cone characteristic initial value problem (CIVP) of numerical relativity. A computer code is constructed which calculates the past behaviour of the Universe from input data that is, in principle, measurable. For practical reasons the code is limited to the case of axisymmetry without rotation. The construction of the code brings to light an interesting general point about observational cosmology. In a big-bang universe it is impossible, even in principle, to determine the state of the universe at early times. For the Einstein-de Sitter model this limit is t 0/27, where t 0 means now. 相似文献
7.
In this article we find necessary and sufficient conditions to decompose a complete equipartite graph into cycles of uniform length, in the case that the length is both even and short relative to the number of parts. © 2010 Wiley Periodicals, Inc. J Combin Designs 19:131‐143, 2011 相似文献
8.
Mateja &#x;ajna 《组合设计杂志》2002,10(1):27-78
We show that the necessary conditions for the decomposition of the complete graph of odd order into cycles of a fixed even length and for the decomposition of the complete graph of even order minus a 1‐factor into cycles of a fixed odd length are also sufficient. © 2002 John Wiley & Sons, Inc. J Combin Designs 10: 27–78, 2002 相似文献
9.
提出一种基于Hamilton路模型的新方法研究蛋白质结构预测问题,为使结构匹配序列,把已知蛋白质的3D结构信息转化为一个加权的完全图Kn,则求这个特定空间结构所匹配的氨基酸残基序列问题转化为求Kn图的最小H路问题.用此方法研究了72个单链蛋白质结构,结果表明Kn图的最小H路对应此蛋白质的序列,图的顶点数n与最小H路总长度成正比. 相似文献
10.
Galen E. Turner III 《Journal of Graph Theory》2009,62(1):100-108
In this paper we prove two results. The first is an extension of a result of Dirac which says that any set of n vertices of an n‐connected graph lies in a cycle. We prove that if V′ is a set of at most 2n vertices in an n‐connected graph G, then G has, as a minor, a cycle using all of the vertices of V′. The second result says that if G is an n+1‐connected graph with maximum vertex degree Δ then G contains a subgraph that is a subdivision of W2n if and only if Δ≥2n. © 2009 Wiley Periodicals, Inc. J Graph Theory 62: 100–108, 2009 相似文献
11.
We prove a decomposition theorem for the class of triangle‐free graphs that do not contain a subdivision of the complete graph on four vertices as an induced subgraph. We prove that every graph of girth at least five in this class is 3‐colorable. 相似文献
12.
设α≤b是非负整数，G=(V(G)，E(G))是一个图．G的一个支撑子图F称为G的一个[α,b]-因子，若对任意的v∈V(G)，有α≤dF(v)≤b．本文给出了一个图存在[α,b]-因子的关于最小度的充分条件及存在特殊[α,b]-因子的充分条件，推广了Y.Egawa等人的结果． 相似文献
13.
We construct a new symmetric Hamilton cycle decomposition of the complete graph Kn for odd n > 7. © 2003 Wiley Periodicals, Inc. 相似文献
14.
We show via an exhaustive computer search that there does not exist a (K6?e)‐decomposition of K29. This is the first example of a non‐complete graph G for which a G‐decomposition of K2|E(G)|+1 does not exist. © 2009 Wiley Periodicals, Inc. J Combin Designs 18: 94–104, 2010 相似文献
15.
Interval minors of bipartite graphs were recently introduced by Jacob Fox in the study of Stanley–Wilf limits. We investigate the maximum number of edges in ‐interval minor‐free bipartite graphs. We determine exact values when and describe the extremal graphs. For , lower and upper bounds are given and the structure of ‐interval minor‐free graphs is studied. 相似文献
16.
Let denote the number of convex cycles of a simple graph G of order n, size m, and girth . It is proved that and that equality holds if and only if G is an even cycle or a Moore graph. The equality also holds for a possible Moore graph of diameter 2 and degree 57 thus giving a new characterization of Moore graphs. 相似文献
17.
We prove that in a graph of order n and minimum degree d, the mean distance μ must satisfy . This asymptotically confirms, and improves, a conjecture of the computer program GRAFFITI. The result is close to optimal; examples show that for any d, μ may be larger than n/(d + 1). © 1997 John Wiley & Sons, Inc. J Graph Theory 25: 95–99, 1997 相似文献
18.
Justin Z. Schroeder 《组合设计杂志》2019,27(1):42-52
We provide two new constructions for pairs of mutually orthogonal symmetric hamiltonian double Latin squares. The first is a tripling construction, and the second is derived from known constructions of hamilton cycle decompositions of when is prime. 相似文献
19.
The complete equipartite graph $K_m * {overline{K_n}}$ has mn vertices partitioned into m parts of size n, with two vertices adjacent if and only if they are in different parts. In this paper, we determine necessary and sufficient conditions for the existence of a decomposition of $K_m * {overline{K_n}}$ into closed trails of length k. © 2009 Wiley Periodicals, Inc. J Combin Designs 17: 374–403, 2009 相似文献