Halin图的线性k-点荫度

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

Halin图谱半径的新上界及极图

利用移接变形的方法再结合特征值的计算技巧刻画出Halin图中谱半径达到第二大的极图,从而得到除轮图以外的Halin图的谱半径的上界以及极图.     

Halin图的Alon-Tarsi数

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

平面Halin图的强最大亏格

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

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.     

最大度不小于4的Halin图的强边着色

图G的强边着色是指图G的边着色使得G的任何一条长至多为3的路上的边所着的颜色两两不同.图G的强色指数是指对G进行强边着色所需用的最少颜色数.本文研究了最大度至少为4的Halin图的强色指数,进而部分地证明了W.C.Shiu等人提出的一个猜想.     

Halin图的邻和可区别边染色与边权点染色

记[k]={1,2,…,k),称为颜色集.设φ:E(G)→[k]为图G的边集合到[k]的映射,令f(v)表示与顶点v关联的边的颜色的加和.如果对任意一条边uv∈E(G),都有φ(u)≠φ(v),f(u)≠f(v),则称φ为图G的邻和可区别[k]-边染色,k的最小值称为图G的邻和可区别边色数,记为ndi_Σ(G).若对任意一条边uv∈E(G),都有f(u)≠f(v),则称φ为图G的k-边权点染色,称图G是k-边权可染的.运用组合零点定理证明了对于最大度不等于4的Halin图有:ndi_∑(G)≤Δ(G)+2,并证明了任一Halin图是4-边权可染的.     

路与星、扇、轮图的积图的邻点可区别I-全染色

图G的I-全染色是指若干种颜色对图G的顶点和边的一个分配,使得任意两个相邻顶点的颜色不同,任意两条相邻边的颜色不同.在图G的一个I-全染色下,G的任意一个点的色集合是指该点的颜色以及与该点相关联的全体边的颜色构成的集合.图G的一个I-全染色称为是邻点可区别的,如果任意两个相邻点的色集合不相等.对一个图G进行邻点可区别I-全染色所用的最少颜色的数目称为图G的邻点可区别I-全色数.应用构造具体染色的方法给出了路与星、扇、轮图的积图的邻点可区别I-全色数     

Mycielski图的BBC染色

基于图G的Mycielski图M（G）,研究xb（G,TG）与xb（M（G）,T’）之间的关系以及xb（G,TG）与xb（M（G）,T＂）之间的关系,其中Tc为G的生成树,T’,T＂分别为M（G）的两类特殊生成树．并给出当G为二部图,完全图以及Halin图时,Xb（M（G）,T＂）的值．     

路与星、扇、轮图的积图的邻点可区别Ⅰ-全染色

图G的Ⅰ-全染色是指若干种颜色对图G的顶点和边的一个分配,使得任意两个相邻顶点的颜色不同,任意两条相邻边的颜色不同.在图G的一个Ⅰ-全染色下,G的任意一个点的色集合是指该点的颜色以及与该点相关联的全体边的颜色构成的集合.图G的一个Ⅰ-全染色称为是邻点可区别的,如果任意两个相邻点的色集合不相等.对一个图G进行邻点可区别Ⅰ-全染色所用的最少颜色的数目称为图G的邻点可区别Ⅰ-全色数.应用构造具体染色的方法给出了路与星、扇、轮图的积图的邻点可区别Ⅰ-全色数     

Hamiltonicity of Amalgams

 An amalgam is obtained from two Halin graphs having skirting cycles of the same length. We are interested in hamiltonicity of amalgams constructed from two identical Halin graphs without any shift along the skirting cycle. We establish hamiltonicity of amalagams constructed from cubic Halin graphs. We give a sufficient condition for hamiltonicity of non-cubic amalgams and characterize infinite classes of non-Hamiltonian amalgams. We also characterize hamiltonicity of amalgams constructed by shifting the component Halin graphs by one and of general amalgams of higher degree. Received: June 23, 1997     

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     

3-正则Halin-图全色数的注(英文)

本文讨论了△（G）＝3的Halin-图的金色数Xr（G）＝4的充分条件，并提出了3－正则Halin-图Xr（G）＝5的充分必要条件的猜想，其中△（G），Xr（G）分别表示G的最大度和全色数．     

Multiobjective traveling salesperson problem on Halin graphs

In this paper, we study traveling salesperson (TSP) and bottleneck traveling salesperson (BTSP) problems on special graphs called Halin graphs. Although both problems are NP-Hard on general graphs, they are polynomially solvable on Halin graphs. We address the multiobjective versions of these problems. We show computational complexities of finding a single nondominated point as well as finding all nondominated points for different objective function combinations. We develop algorithms for the polynomially solvable combinations.     

On the net-embeddability of graphs

This paper provides two kinds of forbidden configurations for the rectilinear O-embeddability of triangle free planar graphs. Meanwhile, the characterizations of the O-embeddability for outerplanar graphs and Halin graphs are found.     

A 3-approximation for the pathwidth of Halin graphs

We prove that the pathwidth of Halin graphs can be 3-approximated in linear time. Our approximation algorithms is based on a combinatorial result about respectful edge orderings of trees. Using this result we prove that the linear width of Halin graph is always at most three times the linear width of its skeleton.     

生成树与图的结构

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

Upper bounds on vertex distinguishing chromatic index of some Halin graphs

A vertex distinguishing edge coloring of a graph G is a proper edge coloring of G such that any pair of vertices has the distinct sets of colors. The minimum number of colors required for a vertex distinguishing edge coloring of a graph G is denoted by ???? _s (G). In this paper, we obtained upper bounds on the vertex distinguishing chromatic index of 3-regular Halin graphs and Halin graphs with ??(G) ?? 4, respectively.