Dirac定理的局部化与Hamilton图

设Ｇ为一个ｎ阶２－连通图，ｎ≥３．若｜Ｄ_ｎ／２（Ｋ_１，３）｜≥２且满足下述条件之一：ｉ）｜Ｄ_ｎ／２（Ｋ_１，３＋ｅ）｜≥２，ii）若Ｋ_１，３＋ｅ→Ｇ，ｘｙ(?)Ｅ（Ｋ_１，３＋ｅ），则ｍａｘ｛ｄＧ（ｘ），ｄＧ（ｙ）｝≥ｎ／２，则Ｇ是一个Ｈａｍｉｌｔｏｎｉａｎ图或其闭包为ｓＰ|⊕Ｈ，这里ｓＰ⊕Ｈ是一类极小２－边连通图．     

平面Halin图的强最大亏格

本文给出了平面Halin图的可定向与不可定向强最大亏格．     

Halin图的点着色算法

本文解决了Halin图的点色数问题,并给出了一个可在线性时间内对Halin图进行点着色的算法。     

Halin图的Alon-Tarsi数

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

Halin图$Q$-谱半径的最大值

The Q-index of a graph G is the largest eigenvalue q(G) of its signless Laplacian matrix Q(G). In this paper, we prove that the wheel graph W_n = K_1 ∨C_(n-1)is the unique graph with maximal Q-index among all Halin graphs of order n. Also we obtain the unique graph with second maximal Q-index among all Halin graphs of order n.     

Hamilton连通图的一个充分条件

Let G be a3-connected graph with n vertices.The paper proves that if for each pair of verti-ces u and v of G,d(u,v)=2,has|N(u)∩N(v)|≤α（αis the minimum independent set num-ber),and then max{d(u),d(v)|≥n 1/2,then G is a Hamilton connected graph.     

Hamilton图的特定生成了图问题的反例

［１］定理３断言：一个Ｈａｍｉｌｔｏｎ图Ｇ必存在仅有ｐ条桥的相间偶圈，如果相间偶圈的边中有边在Ｇ的ｐ个不连通初等子圈上（ｐ≥２）。本的反例表明上述结论是错的，从而［１］中关于Ｐｅｔｅｒｓｏｎ图不是Ｈａｍｉｌｔｏｎ图的证明也不成立。     

Hamilton连通性和邻域并条件

设G＝（V，E）为简单图，δ为图G的最小度，1987年Faudree等人给出NC＝min{|N(x)∪N(y)‖x,y∈V(G),xy∈N(G)}，有关文献曾研究3连通的H连通图，本文进一步得到：若G是n阶2连通图，且NC≥n-δ，则G除几个图外均是H连通图，从而，完成了邻并条件的H连通图问题。     

Halin图的线性k-点荫度

图G的线性点荫度vla(G)是指V(G)的最小划分数,使得每个点划分集的导出子图为线性森林.G的线性k-点荫度vla_k(G)是指V(G)的最小划分数,使得每个点划分集的导出子图的每个连通分支为长度至多为k的路.1998年,吴建良证明了Halin图的线性点荫度为2.本文在此基础上,证明了对Halin图G,有vla_k(G)=2,其中■     

Boxicity of Halin graphs

A k-dimensional box is the Cartesian product R₁×R₂×?×R_k where each R_i is a closed interval on the real line. The boxicity of a graph G, denoted as is the minimum integer k such that G is the intersection graph of a collection of k-dimensional boxes. Halin graphs are the graphs formed by taking a tree with no degree 2 vertex and then connecting its leaves to form a cycle in such a way that the graph has a planar embedding. We prove that if G is a Halin graph that is not isomorphic to K₄, then . In fact, we prove the stronger result that if G is a planar graph formed by connecting the leaves of any tree in a simple cycle, then unless G is isomorphic to K₄ (in which case its boxicity is 1).     

Hamiltonian connectedness in 3-connected line graphs

We investigate graphs G such that the line graph L(G) is hamiltonian connected if and only if L(G) is 3-connected, and prove that if each 3-edge-cut contains an edge lying in a short cycle of G, then L(G) has the above mentioned property. Our result extends Kriesell’s recent result in [M. Kriesell, All 4-connected line graphs of claw free graphs are hamiltonian-connected, J. Combin. Theory Ser. B 82 (2001) 306-315] that every 4-connected line graph of a claw free graph is hamiltonian connected. Another application of our main result shows that if L(G) does not have an hourglass (a graph isomorphic to K₅−E(C₄), where C₄ is an cycle of length 4 in K₅) as an induced subgraph, and if every 3-cut of L(G) is not independent, then L(G) is hamiltonian connected if and only if κ(L(G))≥3, which extends a recent result by Kriesell [M. Kriesell, All 4-connected line graphs of claw free graphs are hamiltonian-connected, J. Combin. Theory Ser. B 82 (2001) 306-315] that every 4-connected hourglass free line graph is hamiltonian connected.     

Minimum cycle bases of Halin graphs

Halin graphs are planar 3‐connected graphs that consist of a tree and a cycle connecting the end vertices of the tree. It is shown that all Halin graphs that are not “necklaces” have a unique minimum cycle basis. © 2003 Wiley Periodicals, Inc. J Graph Theory 43: 150–155, 2003     

A Degree Constraint for Uniquely Hamiltonian Graphs

A graph, G, is called uniquely Hamiltonian if it contains exactly one Hamilton cycle. We show that if G=(V, E) is uniquely Hamiltonian then Where #(G)=1 if G has even number of vertices and 2 if G has odd number of vertices. It follows that every n-vertex uniquely Hamiltonian graph contains a vertex whose degree is at most c log₂n+2 where c=(log₂3−1)⁻¹≈1.71 thereby improving a bound given by Bondy and Jackson [3].     

Halin-图的邻强边染色

图G(V,E)的正常κ-边染色f叫做图G(V,E)的κ-邻强边染色当且仅当任意uv∈E(G)满足f[u]≠f[v],其中,f[u]={f(uw)|uw∈E(G)},称f是G的κ-临强边染色,简记为κ-ASEC.并且x′_as(G)=min{k|κ-ASEC of G}叫做G(V,E)的邻强边色数.本文研究了△(G)≥5的Halin-图的邻强边色数.     

Decomposing Graphs into Long Paths

It is known that the edge set of a 2-edge-connected 3-regular graph can be decomposed into paths of length 3. W. Li asked whether the edge set of every 2-edge-connected graph can be decomposed into paths of length at least 3. The graphs C ₃, C ₄, C ₅, and K ₄−e have no such decompositions. We construct an infinite sequence {F _i } _i=0 ^∞ of nondecomposable graphs. On the other hand, we prove that every other 2-edge-connected graph has a desired decomposition. This revised version was published online in June 2006 with corrections to the Cover Date.     

生成树与图的结构

在网络研究中,人们需要将图分解为指定的结构,来研究网络的普适性、鲁棒又脆弱性,探索网络进化、动力学复杂性、节点多样性、时空演化复杂性等.生成树与图的结构得到研究,海林图,唯一圈图,具有特殊完美匹配树等图的结构得到刻画.     

K_(1,4)-受限图的最长路

图G中同构于K_(1,p)的子图叫G的p-爪(p≥3).如果G中任意一个p-爪中1度顶点之间边(在G中的边)的数目≥p-2,则称G为K(1,p-)-受限图,它是无爪图(p=3)时的推广.本文证明了:连通的K_(1,4-)受限图G,若|G|≥7,则G有Hamilton路或有长至少为2δ+2的路.