共查询到20条相似文献,搜索用时 93 毫秒
1.
2.
刘彦佩教授给出了平面图的辅助图.推广平面图的辅助图到射影平面,给出标号图的射影平面性的如下刻画:给定标号图$G$对应的辅助图是平衡的当且仅当$G$是射影平面图. 相似文献
3.
4.
《应用数学学报》2020,(4)
图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是第一类图. 相似文献
5.
强嵌入猜想称:任意2-连通图都可以强嵌入到某一曲面上.本文通过分析极大外平面图的结构以及强嵌入的特征,讨论了该图类的不可定向强最大亏格,并给出了一个复杂度为O(nlogn)的算法.其中部分图类的强最大亏格嵌入提供该图的一个少双圈覆盖. 相似文献
6.
三正则平面图的对偶图的哈密顿性的注记 总被引:1,自引:0,他引:1
陈婵 《高校应用数学学报(A辑)》2001,16(2):248-250
本文给出了三正则平面图的对偶图为哈密顿图的一个充分条件。 相似文献
7.
8.
9.
本文给出了平面图中的外平面图的谱半径的上界,ρ(G)≤3/2+.改进了1993年,CaoDasong和 Vince A关于外平面图的谱半径上界;然后给出了 Halin图的谱半径的可达上界,并刻划了达到上界的极图 ρ(G)≤1+,等式成立当且仅当 G≌ Wn(轮图). 相似文献
10.
11.
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. 相似文献
12.
Bohdan Zelinka 《Czechoslovak Mathematical Journal》2002,52(4):875-879
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. 相似文献
13.
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. 相似文献
14.
O. Aichholzer F. Aurenhammer Siu-Wing Cheng N. Katoh G. Rote M. Taschwer Yin-Feng Xu 《Discrete and Computational Geometry》1996,16(4):339-359
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. 相似文献
15.
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. 相似文献
16.
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. 相似文献
17.
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 相似文献
18.
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. 相似文献
19.
Amir Ahmadi-Javid Amir Ardestani-Jaafari Leslie R Foulds Hossein Hojabri Reza Zanjirani Farahani 《The Journal of the Operational Research Society》2015,66(8):1399-1412
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. 相似文献
20.
Michael S. Cavers Randall J. Elzinga Sarah E. Vanderlinde 《Discrete Mathematics》2008,308(15):3230-3240
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. 相似文献