共查询到20条相似文献,搜索用时 31 毫秒
1.
对非负整数序列π=(d1,d2……,dn),0≤di≤n-1,本分别给出了它蕴含导出子图为几乎处处完全图,完全图去掉一个Hamilton圈的边,完全k-部图可图(即蕴含aw^1,Aw^2和Ar,r2…,rk-可图)的判别准则。 相似文献
2.
3.
对于给定的图H,如果可图序列π有一个实现包含H作为子图,则称π是蕴含H-可图的.本文给出了可图序列π蕴含W_6-可图的一个充分条件,其中W_r是r个顶点的轮图. 相似文献
4.
尹建华 《数学物理学报(A辑)》2009,29(5):1376-1389
设K r +1是一个r +1个顶点的完全图. 一个可图序列π =(d1, d2,…, dn)称为是蕴含K r+1 -可图的, 如果π有一个实现包含
K r +1作为子图. 该文进一步研究了蕴含K r+1 -可图序列的一些新的条件, 证明了这些条件包含文献[14,10,11]中的一些主要结果和当n≥5r/2 +1时,σ(K r+1, n)之值(此值在文献[2]中被猜测, 在文献[6,7,8,3]中被证实). 此外, 确定了所有满足n≥5, d5≥4 且不蕴含K5 -可图序列π=(d1, d2,…, dn)的集合. 相似文献
5.
6.
n项非增非负整数序列是可图的,若是某个阶简单图的度序列.所有项和为2m、迹为f的n项可图序列的集合Gn,m,f在优超关系下是一个偏序集.本文刻划了偏序集Gn,m,f的极小元,并确定各种可图序列偏序集中极小元的个数. 相似文献
7.
8.
对于给定的图日,若可图序列π有一个实现G以H为其子图,则称π为蕴含日一可图的.在本文,作者刻划了蕴含K6-Z6-可图序列. 相似文献
9.
对于给定的图H,若存在可图序列π的一个实现包含H作为子图,则称π为蕴含H-可图的.Gould等人考虑了下述极值问题的变形:确定最小的偶整数σ(H,n),使得每个满足σ(π)≥σ(H,n)的n项可图序列π=(d1,d2,…,dn)是蕴含H-可图的,其中σ(π)=∑di.本文刻划了蕴含K4+P2-可图序列,其中K4+P2是向致的一个顶点添加两条悬挂边后构成的简单图.这一刻划导出σ(K4+P2,n)的值. 相似文献
10.
王殿军 《高校应用数学学报(A辑)》1993,(4):425-429
本文给出完全图圈分解的一种新方法,设Kn(n≥3)是一个n阶完全图,我们得到下列结果:(1)若n为奇数,G是n阶群,并且{o(x)│∈G,o(x)≥3}={a1,…,at},则Kn=m1Ca1+…+mtCat。(2)若n为偶数,G是n阶群,T={x│x∈G,o(x)=2}={x0,x1,y1,…,xs,ys},o(xiyi)=bi,i=1,…,s及{o(x)│x∈G,o(x)≥}={a1,…,at 相似文献
11.
12.
Guoli Ding 《Journal of Graph Theory》1992,16(5):489-502
Let ?? be a class of graphs and let ? be the subgraph or the induced subgraph relation. We call ? an ideal (with respect to ?) if ? implies that ?. In this paper, we study the ideals that are well-quasiordered by ?. The following are our main results. If ? is the subgraph relation, we characterize the well-quasi-ordered ideals in terms of exluding subgraphs. If?is the induced subgraph relation, we present three wellquasi-ordered ideals. We also construct examples to disprove some of the possible generalizations of our results. The connections between some of our results and digraphs are considered in this paper too. 相似文献
13.
Lars Døvling Andersen Preben Dahl Vestergaard Zsott Tuza 《Graphs and Combinatorics》2006,22(4):453-470
The reduction number r(G) of a graph G is the maximum integer m≤|E(G)| such that the graphs G−E, E⊆E(G),|E|≤m, are mutually non-isomorphic, i.e., each graph is unique as a subgraph of G. We prove that and show by probabilistic methods that r(G) can come close to this bound for large orders. By direct construction, we exhibit graphs with large reduction number, although
somewhat smaller than the upper bound. We also discuss similarities to a parameter introduced by Erdős and Rényi capturing
the degree of asymmetry of a graph, and we consider graphs with few circuits in some detail.
Supported by a grant from the Danish Natural Science Research Council. 相似文献
14.
We say that a family of graphs is p-quasi-random, 0<p<1, if it shares typical properties of the random graph G(n,p); for a definition, see below. We denote by the class of all graphs H for which and the number of not necessarily induced labeled copies of H in Gn is at most (1+o(1))pe(H)nv(H) imply that is p-quasi-random. In this note, we show that all complete bipartite graphs Ka,b, a,b2, belong to for all 0<p<1.Acknowledgments We would like to thank Andrew Thomason for fruitful discussions and Yoshi Kohayakawa for organizing Extended Workshop on Combinatorics in eq5 Paulo, Ubatuba, and Rio de Janeiro, where a part of this work was done. We also thank the referees for their careful work.The first author was partially supported by NSF grant INT-0072064The second author was partially supported by NSF grants DMS-9970622, DMS-0301228 and INT-0072064Final version received: October 24, 2003 相似文献
15.
David Ruelle 《Journal of Algebraic Combinatorics》1999,9(2):157-160
Given an arbitrary finite graph, the polynomial
associates a weight zcardF to each unbranched subgraph F of length cardF. We show that all the zeros of Q have negative real part. 相似文献
16.
Acta Mathematicae Applicatae Sinica, English Series - The perfect matching polytope of a graph G is the convex hull of the incidence vectors of all perfect matchings of G. A graph G is PM-compact... 相似文献
17.
Keiko Kotani 《Graphs and Combinatorics》2001,17(3):511-515
Let G be a connected graph without loops and without multiple edges, and let p be an integer such that 0 < p<|V(G)|. Let f be an integer-valued function on V(G) such that 2≤f(x)≤ deg
G
(x) for all x∈V(G). We show that if every connected induced subgraph of order p of G has an f-factor, then G has an f-factor, unless ∑
x
∈
V
(
G
)
f(x) is odd.
Received: June 29, 1998?Final version received: July 30, 1999 相似文献
18.
Two questions are considered, namely (i) How many colors are needed for a coloring of the n-cube without monochromatic quadrangles or hexagons? We show that four colors suffice and thereby settle a problem of Erdös. (ii) Which vertex-transitive induced subgraphs does a hypercube have? An interesting graph has come up in this context: If we delete a Hamming code from the 7-cube, the resulting graph is 6-regular, vertex-transitive and its edges can be two-colored such that the two monochromatic subgraphs are isomorphic, cubic, edge-transitive, nonvertex-transitive graphs of girth 10. 相似文献
19.
J.H. Koolen 《Journal of Algebraic Combinatorics》1992,1(4):353-362
Terwilliger [15] has given the diameter bound d (s – 1)(k – 1) + 1 for distance-regular graphs with girth 2s and valency k. We show that the only distance-regular graphs with even girth which reach this bound are the hypercubes and the doubled Odd graphs. Also we improve this bound for bipartite distance-regular graphs. Weichsel [17] conjectures that the only distance-regular subgraphs of a hypercube are the even polygons, the hypercubes and the doubled Odd graphs and proves this in the case of girth 4. We show that the only distance-regular subgraphs of a hypercube with girth 6 are the doubled Odd graphs. If the girth is equal to 8, then its valency is at most 12. 相似文献
20.
M. Stiebitz 《Combinatorica》1987,7(3):303-312
Some problems and results on the distribution of subgraphs in colour-critical graphs are discussed.
In section 3 arbitrarily largek-critical graphs withn vertices are constructed such that, in order to reduce the chromatic number tok−2, at leastc
k
n
2 edges must be removed.
In section 4 it is proved that a 4-critical graph withn vertices contains at mostn triangles. Further it is proved that ak-critical graph which is not a complete graph contains a (k−1)-critical graph which is not a complete graph. 相似文献