共查询到20条相似文献,搜索用时 203 毫秒
2.
点度和面度的最小值是3的连通平图 总被引:1,自引:1,他引:0
称一个连通平图是k||δ_(v,f~-)平图,若其顶点的最小度δ_v和面的最小度δ_f的最小值δ_(v,f)是k.本文研究3||δ_(v,f~-)平图.通过一个图运算构造证明链环分支数等于1的3||δ_(v,f~-)平图的存在性,并证明在相等意义下链环分支数不小于基圈数的3||δ_(v,f~-)平图是唯一的.然后证明在相等意义下,边数等于6,8的3||δ_(v,f~-)平图都是唯一的,边数等于9的3||δ_(v,f~-)平图有且只有两个且它们是互为对偶的.接着研究连通平图与其中间图在相等意义下的相互关系.作为运用,证明了无弓形链环图的三个唯一性结论. 相似文献
3.
一个平面图G被称为1-外平面图如果存在一个顶点u 使得G- u 是一个外平面图.本文证明了Melnikov 的边面染色猜想对所有1-外平面图成立. 相似文献
4.
所有的2-连通平图可通过收缩2度点变换成无2度点的、基圈数不变的2-连通平图.本文给出了基圈数为5的、无2度点的所有2-连通平图. 相似文献
5.
设Kv是一个v点完全图,G是一个有限简单图,Kv上的一个图设计G-GD(v)是一个对子(X,B),其中X是Kv的顶点集合,B是Kv的一些与G同构的子图(称为区组)的集合,使得Kv的任意一条边恰出现在B的一个区组中.文中讨论的简单图是C(r)10,即带有一条弦的10长圈(含有11条边),其中r表示弦的两个端点之间的顶点个数,1≤r≤4.给出了C^(r)10-GD(v)的存在谱:v=0,1(mod11)且v≥11. 相似文献
6.
7.
8.
9.
10.
11.
We prove that each 3-connected plane graph G without triangular or quadrangular faces either contains a k-path P
k
, a path on k vertices, such that each of its k vertices has degree ≤5/3k in G or does not contain any k-path. We also prove that each 3-connected pentagonal plane graph G which has a k-cycle, a cycle on k vertices, k∈ {5,8,11,14}, contains a k-cycle such that all its vertices have, in G, bounded degrees. Moreover, for all integers k and m, k≥ 3, k∉ {5,8,11,14} and m≥ 3, we present a graph in which every k-cycle contains a vertex of degree at least m.
Received: June 29, 1998 Final version received: April 11, 2000 相似文献
12.
刘彦佩教授给出了平面图的辅助图.推广平面图的辅助图到射影平面,给出标号图的射影平面性的如下刻画:给定标号图$G$对应的辅助图是平衡的当且仅当$G$是射影平面图. 相似文献
13.
A signed graph has a plus or minus sign on each edge. A simple cycle is positive or negative depending on whether it contains an even or odd number of negative edges, respectively. We consider embeddings of a signed graph in the projective plane for which a simple cycle is essential if and only if it is negative. We characterize those signed graphs that have such a projective-planar embedding. Our characterization is in terms of a related signed graph formed by considering the theta subgraphs in the given graph. 相似文献
14.
We study vertex‐colorings of plane graphs that do not contain a rainbow face, i.e., a face with vertices of mutually distinct colors. If G is a 3 ‐connected plane graph with n vertices, then the number of colors in such a coloring does not exceed . If G is 4 ‐connected, then the number of colors is at most , and for n≡3(mod8), it is at most . Finally, if G is 5 ‐connected, then the number of colors is at most . The bounds for 3 ‐connected and 4 ‐connected plane graphs are the best possible as we exhibit constructions of graphs with colorings matching the bounds. © 2009 Wiley Periodicals, Inc. J Graph Theory 63: 129–145, 2010 相似文献
15.
A polychromatic k‐coloring of a plane graph G is an assignment of k colors to the vertices of G such that every face of G has all k colors on its boundary. For a given plane graph G, one seeks the maximum number k such that G admits a polychromatic k ‐coloring. In this paper, it is proven that every connected plane graph of order at least three, and maximum degree three, other than K4 or a subdivision of K4 on five vertices, admits a 3‐coloring in the regular sense (i.e., no monochromatic edges) that is also a polychromatic 3‐coloring. Our proof is constructive and implies a polynomial‐time algorithm. © 2009 Wiley Periodicals, Inc. J Graph Theory 60: 269‐283, 2009 相似文献
16.
Alex Wendland 《Journal of Graph Theory》2016,83(4):359-371
The Four Color Theorem asserts that the vertices of every plane graph can be properly colored with four colors. Fabrici and Göring conjectured the following stronger statement to also hold: the vertices of every plane graph can be properly colored with the numbers 1, …, 4 in such a way that every face contains a unique vertex colored with the maximal color appearing on that face. They proved that every plane graph has such a coloring with the numbers 1, …, 6. We prove that every plane graph has such a coloring with the numbers 1, …, 5 and we also prove the list variant of the statement for lists of sizes seven. 相似文献
17.
A straight-line planar drawing of a plane graph is called a convex drawing if every facial cycle is drawn as a convex polygon. Convex drawings of graphs is a well-established aesthetic in graph drawing, however not all planar graphs admit a convex drawing. Tutte [W.T. Tutte, Convex representations of graphs, Proc. of London Math. Soc. 10 (3) (1960) 304–320] showed that every triconnected plane graph admits a convex drawing for any given boundary drawn as a convex polygon. Thomassen [C. Thomassen, Plane representations of graphs, in: Progress in Graph Theory, Academic Press, 1984, pp. 43–69] gave a necessary and sufficient condition for a biconnected plane graph with a prescribed convex boundary to have a convex drawing.In this paper, we initiate a new notion of star-shaped drawing of a plane graph as a straight-line planar drawing such that each inner facial cycle is drawn as a star-shaped polygon, and the outer facial cycle is drawn as a convex polygon. A star-shaped drawing is a natural extension of a convex drawing, and a new aesthetic criteria for drawing planar graphs in a convex way as much as possible. We give a sufficient condition for a given set A of corners of a plane graph to admit a star-shaped drawing whose concave corners are given by the corners in A, and present a linear time algorithm for constructing such a star-shaped drawing. 相似文献
18.
类八面体是顶点度数为4,而仅具有3边面与4边面的多面体.本论文研究把类八面体、中点多面体及其它相关多面体,分解为无共享边的中央回路.除新结果外,也将此方面的已知结果整理为表与图,方便想进一步研究者参考所需. 相似文献
19.
Precise upper bounds are obtained for the minimum weight of minor faces in normal plane maps and 3-polytopes with specified
maximum vertex degree.
Translated fromMatematicheskie Zametki, Vol. 64, No. 5, pp. 648–657, November, 1998.
The research of the first named author was supported in part by the Visiting Fellowship Research Grant GR/K00561 from the
Engineering and Physical Sciences Research Council and by the Russian Foundation for Basic Research under grant No. 96-01-01614
and No. 97-01-01075. 相似文献
20.
We study planar graphs embedded in the plane that have chemical applications: the degrees of all vertices are 3 or 2, all
internal faces but one or two arer-gons, and each internal face is a simply connected domain. For wide classes of such graphs, we solve the existence problem
for embeddings of the graph metric on the vertices in multidimensional cubes or cubical lattices preserving or doubling all
the distances. Incidentally we present a complete classification of some interesting families of such graphs.
Translated fromMatematicheskie Zametki, Vol. 68, No. 3, pp. 339–352, September, 2000. 相似文献