图的星色数

给出了一些星色数为４的平面图,它们不含有轮图作为子图,这回答了Ｚｈｕ的一个问题,给出了一类４连通平面图其星色数在３与４之间,这也回答了Ａｂｂｏｔｔ和Ｚｈｏｕ的一个问题,应用图的同态概念,讨论了某些图的字典积的星色数,证明了一个图及其补图的星色数的和与积所满足的两个不等式。     

图的星临界性

图的星着色是图的正常着色的推广。本文对图的星临界性及其与图的临界性之间的关系进行研究，给出了两类星临界但非临界的平面图。     

射影平面上标号图的辅助图

刘彦佩教授给出了平面图的辅助图.推广平面图的辅助图到射影平面,给出标号图的射影平面性的如下刻画:给定标号图$G$对应的辅助图是平衡的当且仅当$G$是射影平面图.     

IC-平面图为第一类图的一个充分条件

图G的一个正常k-边染色是指一个映射Φ:E(G)→{1,2,…,k},使得任意两条相邻的边x,y∈E(G)满足Φ(x)≠Φ(y).使得G具有正常k-边染色的最小正整数k称为图G的边色数,记为χ'(G).著名Vizing定理证明每个简单图G的边色数χ'(G)要么等于最大度Δ(G)要么等于Δ(G)+1.这个定理将所有的图分成了两类:第一类图满足关系式χ'(G)=Δ(G),第二类图满足关系式χ'(G)=Δ(G)十1.本文主要讨论特殊1-平面图的正常边染色问题.1-平面图G是指G能够嵌入到平面上使得G的任意一条边最多被交叉一次.1-平面图G按照上述条件的一种画法称为G的一种1-平面嵌入.所以1-平面图中的每个交叉点w都是由两条边相交所得,从而每个交叉点w都对应着两条相交边,同时也对应着由这两条相交边的四个端点组成的集合ψ(w).如果1-平面图的一个1-平面嵌入中任意两个交叉点w和w'满足ψ(w)∩ψ(w')=Φ,那么称此1-平面图为IC-平面图.在本文中,通过观察分析Δ-临界图和不含相邻弦6-圈的IC-平面图的结构,应用权值转移方法证明了任何最大度为7且不含相邻弦6-圈的IC-平面图G是第一类图.     

极大外平面图的不可定向强最大亏格

强嵌入猜想称:任意2-连通图都可以强嵌入到某一曲面上．本文通过分析极大外平面图的结构以及强嵌入的特征,讨论了该图类的不可定向强最大亏格,并给出了一个复杂度为O(nlogn)的算法．其中部分图类的强最大亏格嵌入提供该图的一个少双圈覆盖．     

三正则平面图的对偶图的哈密顿性的注记

本文给出了三正则平面图的对偶图为哈密顿图的一个充分条件。     

图的路径与半边路径之间的一种关系

本文主要研究了连通图的半边路径数目和两个辅助图的路径数目之间的一种关系.并且根据这种关系,我们给出了连通图和平面图的无符号拉普拉斯谱半径的一些上界.     

连通图的度序列及连通平面图的低度点个数

美国数学家Bondy给出了一个非负整数序列为简单图的度序列的充要条件.本文对此进行了发展,证明了一个正整数序列为连通简单图的度序列的充要条件;然后在此基础上又探讨了平面图的低度点个数问题并定义了描述连通平面图的低度点个数的一个概念φ(n,m),并对某些低阶平面图求出了φ(n,m)的值.最后给出了φ(n,m)的上下界.     

外平面图和Halin图谱半径的上界

本文给出了平面图中的外平面图的谱半径的上界,ρ（Ｇ）≤３／２＋．改进了１９９３年,ＣａｏＤａｓｏｎｇ和 Ｖｉｎｃｅ Ａ关于外平面图的谱半径上界;然后给出了 Ｈａｌｉｎ图的谱半径的可达上界,并刻划了达到上界的极图 ρ（Ｇ）≤１＋,等式成立当且仅当 Ｇ≌ Ｗｎ（轮图）．     

图的平面Turán数和平面anti-Ramsey数（英文）

在所有顶点数为n且不包含图G作为子图的平面图中,具有最多边数的图的边数称为图G的平面Turán数,记为ex_P(n,G)。给定正整数n以及平面图H,用T_n(H)来表示所有顶点数为n且不包含H作为子图的平面三角剖分图所组成的图集合。设图集合T_n (H)中的任意平面三角剖分图的任意k边染色都不包含彩虹子图H,则称满足上述条件的k的最大值为图H的平面anti-Ramsey数,记作ar_P(n,H)。两类问题的研究均始于2015年左右,至今已经引起了广泛关注。全面地综述两类问题的主要研究成果,以及一些公开问题。     

Bounds for the incidentor chromatic number of a weighted undirected multigraph

A proper incidentor coloring of an undirected weighted multigraph is called admissible if the absolute value of the difference between the colors of the incidentors of each edge is at least the weight of this edge. The minimum number of colors necessary for an admissible incidentor coloring is called the incidentor chromatic number of the multigraph. The problem of finding this number is studied in the paper. The NP-hardness of this problem is proved for Δ colors. Some upper and lower bounds are found for the incidentor chromatic number.     

Edge Domination in Graphs of Cubes

The signed edge domination number and the signed total edge domination number of a graph are considered; they are variants of the domination number and the total domination number. Some upper bounds for them are found in the case of the n-dimensional cube Q _n.     

Lower bounds on the cardinality of the maximum matchings of planar graphs

Lower bounds on the cardinality of the maximum matchings of planar graphs, with a constraint on the minimum degree, are established in terms of a linear polynomial of the number of vertices. The bounds depend upon the minimum degree and the connectivity of graphs. Some examples are given which show that all the lower bounds are best possible in the sense that neither the coefficients nor the constant terms can be improved.     

Triangulations intersect nicely

We show that there is a matching between the edges of any two triangulations of a planar point set such that an edge of one triangulation is matched either to the identical edge in the other triangulation or to an edge that crosses it. This theorem also holds for the triangles of the triangulations and in general independence systems. As an application, we give some lower bounds for the minimum-weight triangulation which can be computed in polynomial time by matching and network-flow techniques. We exhibit an easy-to-recognize class of point sets for which the minimum-weight triangulation coincides with the greedy triangulation.     

The edge density of 4-critical planar graphs

Several constructions of 4-critical planar graphs are given. These provide answers to two questions of B. Grünbaum and give improved bounds for the maximum edge density of such graphs.     

On real eigenvalues of real tridiagonal matrices

Lower bounds for the number of different real eigenvalues as well as for the number of real simple eigenvalues of a class of real irreducible tridiagonal matrices are given. Some numerical implications are discussed.     

Vertex‐distinguishing edge colorings of graphs

We consider lower bounds on the the vertex‐distinguishing edge chromatic number of graphs and prove that these are compatible with a conjecture of Burris and Schelp 8 . We also find upper bounds on this number for certain regular graphs G of low degree and hence verify the conjecture for a reasonably large class of such graphs. © 2002 Wiley Periodicals, Inc. J Graph Theory 42: 95–109, 2003     

An algorithm and upper bounds for the weighted maximal planar graph problem

In this paper, we investigate the weighted maximal planar graph (WMPG) problem. Given a complete, edge-weighted, simple graph, the WMPG problem involves finding a subgraph with the highest sum of edge weights that is maximal planar, namely, it can be embedded in the plane without any of its edges intersecting, and no additional edge can be added to the subgraph without violating its planarity. We present a new integer linear programming (ILP) model for this problem. We then develop a cutting-plane algorithm to solve the WMPG problem based on the proposed ILP model. This algorithm enables the problem to be solved more efficiently than previously reported algorithms. New upper bounds are also provided, which are useful in evaluating the quality of heuristic solutions or in generating initial solutions for meta-heuristics. Computational results are reported for a set of 417 test instances of size varying from 6 to 100 nodes including 105 instances from the literature and 312 randomly generated instances. The computational results indicate that instances with up to 24 nodes can be solved optimally in reasonable computational time and the new upper bounds for larger instances significantly improve existing upper bounds.     

On the limit cycles of perturbed discontinuous planar systems with 4 switching lines

Limit cycle bifurcations for a class of perturbed planar piecewise smooth systems with 4 switching lines are investigated. The expressions of the first order Melnikov function are established when the unperturbed system has a compound global center, a compound homoclinic loop, a compound 2-polycycle, a compound 3-polycycle or a compound 4-polycycle, respectively. Using Melnikov’s method, we obtain lower bounds of the maximal number of limit cycles for the above five different cases. Further, we derive upper bounds of the number of limit cycles for the later four different cases. Finally, we give a numerical example to verify the theory results.     

Clique partitions of distance multigraphs

We consider the minimum number of cliques needed to partition the edge set of D(G), the distance multigraph of a simple graph G. Equivalently, we seek to minimize the number of elements needed to label the vertices of a simple graph G by sets so that the distance between two vertices equals the cardinality of the intersection of their labels. We use a fractional analogue of this parameter to find lower bounds for the distance multigraphs of various classes of graphs. Some of the bounds are shown to be exact.