称一个连通平图是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- 平图有且只有两个且它们是互为对偶的.接着研究连通平图与其中间图在相等意义下的相互关系.作为运用,证明了无弓形链环图的三个唯一性结论.
Abstract
A connected plane graph G is called a k‖δv,f- plane graph if δv,fk.there, δv,f is the minimum value of δv and δf, δv is the minimum degree of vertices ofGand δf is the minimum degree of faces of G.We mainly study the 3‖δv,f-plane graphs.We first prove the existence of the 3‖δv,f-plane graphs with the link component number 1 by constructing them via a graph operation, and prove the uniqueness of the 3‖δv,f-plane graph with link component number not less than nullity in the sense of equivalence.Then we prove the uniqueness of 3‖δv,f-plane graph with the edge number 6 and 8 in the sense of equivalence.We also show that there are only two 3‖δv,f-plane graphs with the edge number 9 in the sense of equivalence, furthermore, they are dual.After that, we study the correlations between a connected plane graph and its medial graphs in the sense of equivalence.Finally, as applications, we prove three uniqueness conclusions of lune-free link graphs.
关键词
3‖&delta /
v /
f- 平图 /
链环分支数 /
无弓形链环图
{{custom_keyword}} /
Key words
3‖δv,f-plane graphs /
link component number /
lune-free link graphs
{{custom_keyword}} /
{{custom_sec.title}}
{{custom_sec.title}}
{{custom_sec.content}}
参考文献
[1] Bondy J.A., Murty U.S.R., Graph Theory, GTM244, Springer, 2008.
[2] Eliahou S., Harary F., Kauffman L.H., Lune-free knot graphs, J.Knot Theor.Ramif., 2008, 17(1): 55-74.
[3] Godsil C., Royle G., Algebraic Graph Theory, Springer-Verlag, New York, 2001: 398-400.
[4] Jeong D.Y., Realizations with a cut-through Eulerian circuit, Discrete Math., 1995, 137(1-3): 265-275.
[5] Jiang L.P., Jin X., Deng K.C., Determining the component number of links corresponding to triangular and honeycomb lattices, J.Knot Theor.Ramif., 2012, 21(2): 1250018, 14 pages.
[6] Jin X., Dong F.M., Tay E.G., Determining the component number of links corresponding to lattices, J. Knot Theor.Ramif., 2009, 18(12): 1711-1726.
[7] Jin X., Dong F.M., Tay E.G., On graphs determining links with maximal number of components via medial construction, Discrete Appl.Math., 2009, 157(14): 3099-3110.
[8] Lin Y.F., The uniqueness of the near-extremal graphs with subgraph K4 and no cut vertices (in Chinese), Math.Pract.Theory, 2013, 43(10): 156-160.
[9] Lin Y.F., Jin X., The constructions and the judgement algorithms about G-extremal graphs and G-nearextremal graphs (in Chinese), Advances in Mathematics, 2013, 42(6): 817-822.
[10] Lin Y.F., Noble S.D., Jin X., et al., On plane graphs with link component number equal to the nullity, Discrete Appl.Math., 2012, 160(9): 1369-1375.
[11] Liu S.Y., Zheng H.P., Genera of the links derived from 2-connected plane graphs, J.Knot Theor.Ramif., 2012, 21(14): 1250129, 14 pages.
[12] Mphako E.G., The component number of links from graphs, Proc.Edinburgh Math.Soc., 2002, 45(3): 723-730.
[13] Murasugi K., Knot Theory and its Applications, Birkhauser, Boston, 1996: 34-39.
[14] Noble S.D., Welsh D.J.A., Knot graphs, J.Graph Theory, 2000, 34(1): 100-111.
[15] Pisanski T., Tucker T.W., Zitnik A., Straight-ahead walks in Eulerian graphs, Discrete Math., 2004, 281(1. 3): 237-246.
[16] Shank H., The Theory of Left-Right Paths, CombinatorialMath.III, Lecture Notes in Mathematics, Springerverlag, Berlin, 1975, 452: 42-54.
{{custom_fnGroup.title_cn}}
脚注
{{custom_fn.content}}
基金
福建省教育厅科技项目(JA11332, JB13366)
{{custom_fund}}
PDF(825 KB)
