图K_nH_((5n/2)-4)的升分解

Ａｌａｖｉ等人给出了图的升分解的概念并猜测任何一个有正数条边的图都可以升分解．Ｆａｕｄｒｅｅ等１９８７年证明了当完全图Ｋｎ的子图Ｈ至多有ｎ—１条边时，Ｋｎ－Ｈ可以升分解．马克杰等１９９７年证明了当Ｈ至多含有ｎ条边时，Ｋｎ－Ｈ可以升分解．作者１９９９年证明了当Ｈ的边数小于３ｎ／２时，Ｋｎ－Ｈ可以升分解．本文将证明当Ｈ的边数小于（５ｎ／２）－４时Ｋｎ－Ｈ有升分解．     

ON THE ASCENDING SUBGRAPH DECOMPOSITIONS OF REGULAR GRAPHS

The definition of the ascending suhgraph decomposition was given by Alavi. It has been conjectured that every graph of positive size has an ascending subgraph decomposition. In this paper it is proved that the regular graphs under some conditions do have an ascending subgraph decomposition.     

图有[a,b]因子的邻域条件

不含有图K1，R的图称为K1,r-free图，设G是一个具有顶点集V（G）的图，设n(≥3),a和b是整数，使得b≥a≥1，若b是奇数，设b≥n-1。我们证明了每个连通的K1,r-free图G在b|V(G)|为偶数，它的最小度至少是a n-1,|V(G）≥ （2(a b)-1)(a b-1)/b，以及|NG(x）∪NG（y)|≥a|V(G)|a b对V的任意两个不邻接的点x和y都成立时，G有一个[a,b]因子。     

退化图中的子图计数问题研究

令G表示n个顶点的图,如果G的每个子图中都包含一个度至多为k的顶点,则称G为k-退化图.令N(G,F)表示G中F子图的个数.主要研究了k-退化图中完全子图和完全二部子图的计数问题,给出了计数的上界以及相应的极图.首先,证明了Ν(G,K_t)≤(n-k)(k t-1)+(k t).其次,如果s,t≥1,n≥k+1且s+t≤k,我们证明了Ν(G,K_s,t)≤{(k s)(n-s s)-1/2(k s)(k-s s),t=s,(k s)(n-s t)+(k t)(n-t s)-(k t)(k-t s),t≠s.此外,还研究了在最大匹配和最小点覆盖为给定值的情况下,图G中的最大边数.记v(G),K(G)分别为图G的最大匹配数和最小点覆盖.证明了当v(G)≤k,K(G)=k+r且n≥2k+2r²+r+1时,有e(G)≤(k+r+1 2)+(k-r)(n-k-r-1).     

2-连通无爪图的连通因子

若图G不含有同构于K1,3的导出子图,则称G为一个无爪图.令a和b是两个整数满足2≤a≤b.本文证明了若G是一个含有[a,b]因子的2连通无爪图,则G有一个连通的[a,b 1]因子.     

图的预解Estrada指标的界的估计（英文）

n阶图G的子图中心度,即后来著名的Estrada指标定义为EE（G）=∑_（i=1）~N e~（λ2）.其中λ_1,λ_2……λ_n为图G的特征值.作为复杂网络的一种中心性测度和一种分子结构描述符,Estrada指标在许多研究领域有着广泛的应用.最近,Estrada和High-ama引进了一种新的复杂网络中心度,即∑_（i=1）~n n-1n-1λ_i：他们称之为预解中心度,后来又被称为预解Estrada指标.本文主要利用图G的顶点数和边数给出了图G的预解Estrada指标的若干界.     

Some graphs which have ascending subgraph decomposition

1.IntroductionIn[1],Alavietal.gavethefollowingdecompositionconjecture.Conjecture.LetGbeagraphwith("1')edges.ThentheedgesetofGcanbedecomposedintonsetsgeneratinggraphsGI,G2,'IG.suchthatIE(Gi)I=i(fori=1,2,',n)andGiisisomorphictoasubgraphofGi 1fori=1,2,'.)n--1.AgraphGthatcanbedecomposedasdescribedinConjecturewillbesaidtohaveanAscendingSubgraphDecomposition(AlsoabbreviatedasASD).ThesubgraphsGIIG2,',G.aresaidtobemembersofsuchadecomposition.Furthermore,ifeachGiisastar(matching,pat…     

Ascending Subgraph Decompositions in Oriented Complete Balanced Tripartite Graphs

In 1987, Alavi, Boals, Chartrand, Erdös, and Oellermann conjectured that all graphs have an ascending subgraph decomposition (ASD). Though different classes of graphs have been shown to have an ASD, the conjecture remains open. In this paper we investigate the similar problem for digraphs. In particular, we will show that any orientation of a compete balanced tripartite graph has an ASD.     

K3-free图的线图的哈密顿性

设G是一个简单图，Gi G，G1在G中的度定义为d（Gt）=∑v∈v（c）d（v），其中d（v）为v在G中的度数。本文的主要结果是：设G是n≥2阶几乎无桥的简单连通K3-free图，且G≌k1,n-1、Q1和Q2，若对G中任何同构于四个顶点路的导出子图I有d（I）≥n＋2，则G有一个D-闭迹，从而G的线图L（G）是哈密顿图。     

ON THE MINIMUM FEASIBLE GRAPH FOR FOUR SETS

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

Cycle double covers and spanning minors II

In this paper we continue our investigations from [R. Häggkvist, K. Markström, Cycle double covers and spanning minors, Technical Report 07, Department of Mathematics, Umeå University, Sweden, 2001, J. Combin. Theory, Ser. B, to appear] regarding spanning subgraphs which imply the existence of cycle double covers. We prove that if a cubic graph G has a spanning subgraph isomorphic to a subdivision of a bridgeless cubic graph on at most 10 vertices then G has a CDC. A notable result is thus that a cubic graph with a spanning Petersen minor has a CDC, a result also obtained by Goddyn [L. Goddyn, Cycle covers of graphs, Ph.D. Thesis, University of Waterloo, 1988].     

完全图与完全n部图的完全多部图分解

§ 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…     

Large Induced Forests in Triangle-Free Planar Graphs

Given a planar graph G, what is the largest subset of vertices of G that induces a forest? Albertson and Berman [2] conjectured that every planar graph has an induced subgraph on at least half of the vertices that is a forest. For bipartite planar graphs, Akiyama and Wanatabe [1] conjectured that there is always an induced forest of size at least 5n/8. Here we prove that every triangle-free (and therefore every bipartite) planar graph on n vertices has an induced forest of size at least (17n+24)/32.     

An Anti-Ramsey Theorem

Let be the Turán number which gives the maximum size of a graph of order containing no subgraph isomorphic to . In 1973, Erdős, Simonovits and Sós [5] proved the existence of an integer such that for every integer , the minimum number of colours , such that every -colouring of the edges of which uses all the colours produces at least one all whose edges have different colours, is given by . However, no estimation of was given in [5]. In this paper we prove that for . This formula covers all the relevant values of n and p. Received January 27, 1997/Revised March 14, 2000     

ON CONNECTED FACTORS IN K_(1,3)-FREE GRAPHS

1.IntroductionWeconsiderfinitesimplegraphs,andfollowBondyandMurtyl'lforgeneralterminologyandnotation.LetG=(V(G),E(G))beagraphwithavertexsetV(G)andanedgesetE(G).ForavertexvEV(G),N(v,G)denotesthesetofneighborsofvinG,anddG(v)=IN(v,G)l.Foravertexsubset(resp.subgraph)HofG,G--HdenotesthesubgraphofGobtainedfromGbydeletingthevenicesinHtogetherwiththeedgesincidelltwiththem.IfAisanedgesubsetofGandHasubgraphofG,thenH AdenotesthesubgraphofGobtainedfromHbyaddingtheedgesinAtogetherwiththeven…     

On Triangle‐Free Graphs That Do Not Contain a Subdivision of the Complete Graph on Four Vertices as an Induced Subgraph

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.     

关于简单MCD图

设G是阶为n的简单图，若G中没有两个等长圈且具有最大可能的边数，则称G为简单MCD图。本文通过引进路分解概念给出了两个关于图中圈数的结果并应用它们证明了下述定理：若G是简单MCD图，则G不是2连通可平面图且对所有整数n，除七个例外，G不是阶为n的含有同胚于K4的2连通图。     

关于图是(r,n)-临界图的一个邻域条件

设n，m和r是满足r≥2，n≥0，m≥3的整数，且当r是奇数时，假设r≥m-1．称一个图为K1,m-free，如果它不包含以Kt,m为导出的子图．称一个图G为一个（r,n）-临界图，如果在删去G的任意n个点后，剩下G的子图都有一个r-因子,设G是一个Kl,m-free的（n＋1）-连通图，且阶为｜G｜以及r（｜G｜≥n）是偶数,证明了：如果G的最小度至少是r＋n＋m-1，阶｜G｜≥8r5＋n，并且对V（G）的任意独立点集{x1，x2}都有｜NG（x1）∪NG（x2）｜≥（｜G｜＋n）／2，那么G是一个（r,n）-临界图．关于G的最小度和｜NG（x1）∪NG（X2）｜的下界是紧的。     

单圈混合图的极大谱半径(英文)

设U*为一个未定向的n个顶点上的单圈混合图,它是由一个三角形在其某个顶点上附加n-3个悬挂边而获得.在文[Largest eigenvalue of a unicyclic mixed graph,Applied Mathematics A Journal of Chinese Universities(Ser.B),2004,19(2):140-148]中,作者证明了:在相差符号同构意下,在所有n个顶点上的单圈混合图中,U*是唯一的达到最大Laplace谱半径的混合图.本文应用非负矩阵的Perron向量,给出上述结论的一个简单的证明.     

Forbidden subgraphs and the Kőnig property

A graph has the Kőnig property if its matching number equals its transversal number. Lovász proved a characterization of graphs having the Kőnig property by forbidden subgraphs, restricted to graphs with a perfect matching. Korach, Nguyen, and Peis proposed an extension of Lovászʼs result to a characterization of all graphs having the Kőnig property in terms of forbidden configurations (certain arrangements of a subgraph and a maximum matching). In this work, we prove a characterization of graphs having the Kőnig property in terms of forbidden subgraphs which is a strengthened version of the characterization by Korach et al. As a consequence of our characterization of graphs with the Kőnig property, we prove a forbidden subgraph characterization for the class of edge-perfect graphs.